Задачи для IT интервью

[whatnext]

нашел что то мож кому поможет

phpBB [video]

[liamkin]

Сдвиг массива длиной N на количество шагов M был?

[valchkou]

кривые квадратики каждый рисовать умеет.
МоржСорт имплементед:
https://github.com/valchkou/JavaSnippet ... eSort.java

нашел что то мож кому поможет

phpBB [video]

[3DD]

Или на HackerRank:

phpBB [video]

[nyekimov]

кривые квадратики каждый рисовать умеет.
МоржСорт имплементед:
https://github.com/valchkou/JavaSnippet ... eSort.java

нашел что то мож кому поможет

phpBB [video]

Не знаю, приветствуется ли код ревью, но читать (a<=b) вместо (a <= b) лично мне тяжело, также и с плюсами, особенно когда стиль пляшет то первый вариант, то второй. Есть пару ошибок в комментах к коду.
Ну и for(int k=0; k < arr.lenght(); k++) { print arr[k] } вместо for(int element in arr) { print element } вообще тут уже обсуждалось.

[valchkou]

кривые квадратики каждый рисовать умеет.
МоржСорт имплементед:
https://github.com/valchkou/JavaSnippet ... eSort.java

нашел что то мож кому поможет

phpBB [video]

Не знаю, приветствуется ли код ревью, но читать (a<=b) вместо (a <= b) лично мне тяжело, также и с плюсами, особенно когда стиль пляшет то первый вариант, то второй. Есть пару ошибок в комментах к коду.
Ну и for(int k=0; k < arr.lenght(); k++) { print arr[k] } вместо for(int element in arr) { print element } вообще тут уже обсуждалось.

комментарии конечно приветствуются, я этот код лет 6 назад написал судя по гитхабу.
Но честно сказать ты первый кто удосужился прокомментировать, а может даже и просмотреть.
И даже мне он кажется каким то странным.

Но суть не в этом, а в том что написать работающий сортморж намного сложнее чем вот то виде с доской и квадратиками.

[John Smith]

для быстрой сортировки int[] - radix sort - выбор мастеров, быстрее стандартного джавского Arrays.sort() в 3 раза

[fleshold]

Но суть не в этом, а в том что написать работающий сортморж намного сложнее чем вот то виде с доской и квадратиками.

На современных языках с их синтаксическим сахаром, подобное пишется быстро и строчек в 30. Без всяких досок и квадратиков.

Code: Select all

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
  guard array.count > 1 else { return array }
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
  var leftIndex = 0
  var rightIndex = 0
  var result: [Element] = []
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

[John Smith]

Но суть не в этом, а в том что написать работающий сортморж намного сложнее чем вот то виде с доской и квадратиками.

На современных языках с их синтаксическим сахаром, подобное пишется быстро и строчек в 30. Без всяких досок и квадратиков.

Code: Select all

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
  guard array.count > 1 else { return array }
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
  var leftIndex = 0
  var rightIndex = 0
  var result: [Element] = []
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

каков cost result.append() ? сдается мне что эта реализация будет за O(n^2) работать

[liamkin]

Писали же раньше что quicksort самый быстрый?

[valchkou]

А можно попросить ваш современный код отсортировать 1 млн интегеров и замерить время.
Ради интереса, что оптимизирует сахар под капотом. Думаю что в контексте данного теста железо не так важно
но если что у меня mac intel i7, количество памяти и коров значение не имеют
Что то вроде такого.

Code: Select all

        int max = 1000000;
        int[] arr = new int[max];
        for (int i = 0; i<max; i++) {
            arr[i] = ThreadLocalRandom.current().nextInt(max);
        }

        long t = System.currentTimeMillis();
        sort(arr);
        System.out.println(System.currentTimeMillis() - t);

мой сорт занял 15 сек что очень долго
к слову родной ява сорт занимает всего 250 mls для 1mln

Code: Select all

int[] sorted = IntStream.of(arr).sorted().toArray();

На современных языках с их синтаксическим сахаром, подобное пишется быстро и строчек в 30. Без всяких досок и квадратиков.

Code: Select all

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
  guard array.count > 1 else { return array }
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
  var leftIndex = 0
  var rightIndex = 0
  var result: [Element] = []
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

[valchkou]

Писали же раньше что quicksort самый быстрый?

наверное если бы он был самым быстрым то не стали бы придумывать ничего другого.
ява использует аналог тимсорт
https://en.wikipedia.org/wiki/Timsort

[liamkin]

Писали же раньше что quicksort самый быстрый?

наверное если бы он был самым быстрым то не стали бы придумывать ничего другого.
ява использует аналог тимсорт
https://en.wikipedia.org/wiki/Timsort

Кроме скорости, есть другие причины выдумывать собственные сортировки. Мозги-то шевелятся, шарики-то крутятся. Вот в поиске простых чисел придумано ли что-то лучше Евклидова сита?

[John Smith]

сортировка 100 mln ints на моем ноуте занимает

Arrays.sort() - 9.5 sec
merge sort - 19.5 sec
radix sort - 4.2 sec

[fleshold]

А можно попросить ваш современный код отсортировать 1 млн интегеров и замерить время.
Ради интереса, что оптимизирует сахар под капотом. Думаю что в контексте данного теста железо не так важно
но если что у меня mac intel i7, количество памяти и коров значение не имеют
Что то вроде такого.

Конечно. Попробую. Чуть позже.

Писали же раньше что quicksort самый быстрый?

Насколько помню, никогда так вот в книжках не писали. Смысл тогда в других алгоритмах? Насколько я могу помнить (всё таки читал такие книжки 20-25 лет назад), писали что то типа, что выбор конкретного алгоритма сортировки, "в реальных программах", зависит от многих факторов, и лучше использовать несколько алгоритмов, и применять в зависимости от ситуации, или модифицировать какой нибудь из "улучшенных" алгоритмов. Ведь не секрет, что при определённых условиях быстрая сортировка проиграет пузырьковой "улучшенной" и некоторым другим, как "улучшенным" (не факт, надо проверить) так и нет.

[mikeG]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

[valchkou]

сортировка 100 mln ints на моем ноуте занимает

Arrays.sort() - 9.5 sec
merge sort - 19.5 sec
radix sort - 4.2 sec

Arrays.parallelSort(arr); менее 3х сек

[Lisa]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

Отсортировать сначала, потом носить

[3DD]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

[mikeG]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

Нет, просто в ряд стоят, нужно по порядку переставить.

[fleshold]

А можно попросить ваш современный код отсортировать 1 млн интегеров и замерить время.
Ради интереса, что оптимизирует сахар под капотом. Думаю что в контексте данного теста железо не так важно
но если что у меня mac intel i7, количество памяти и коров значение не имеют
Что то вроде такого.

Code: Select all

        int max = 1000000;
        int[] arr = new int[max];
        for (int i = 0; i<max; i++) {
            arr[i] = ThreadLocalRandom.current().nextInt(max);
        }

        long t = System.currentTimeMillis();
        sort(arr);
        System.out.println(System.currentTimeMillis() - t);

мой сорт занял 15 сек что очень долго
к слову родной ява сорт занимает всего 250 mls для 1mln

Code: Select all

int[] sorted = IntStream.of(arr).sorted().toArray();

Обратный порядок массива
---Example of MergeSort---
2019-07-10 05:54:14 +0000
2019-07-10 05:54:23 +0000

Случайный
---Example of MergeSort shuffled---
2019-07-10 05:57:14 +0000
2019-07-10 05:57:22 +0000

Родной .sort() обратный порядок (также и случайный)
---Example of sort---
2019-07-10 06:11:59 +0000
2019-07-10 06:11:59 +0000

Radix говорите? Хорошо.
Radix в любом порядке
---Example of radixsotr---
2019-07-10 06:41:04 +0000
2019-07-10 06:41:07 +0000

Поразрядная Radix известно что O(k * n) , хорошо, сделаем k - кнстантой
---Example of radixsotr---
2019-07-10 06:55:53 +0000
2019-07-10 06:55:54 +0000

Program ended with exit code: 0

[fleshold]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

Нет, просто в ряд стоят, нужно по порядку переставить.

Отсортировать по весу? По цвету? Размеру? По ценности содержимого в оных?

[fleshold]

Переделал в расширений (extension) к структуре Array. Изменился только mergeSort()
---Example of Array extension mergeSort()---
2019-07-10 11:56:09 +0000
2019-07-10 11:56:13 +0000

[mikeG]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

Нет, просто в ряд стоят, нужно по порядку переставить.

Отсортировать по весу? По цвету? Размеру? По ценности содержимого в оных?

Не важно. Можно считать, что на каждой номер написан.

[3DD]

Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

Нет, просто в ряд стоят, нужно по порядку переставить.

Отсортировать по весу? По цвету? Размеру? По ценности содержимого в оных?

Не важно. Можно считать, что на каждой номер написан.

ну если силы есть и оплата почасовая, то и таскайте их по одной, хоть бабл сортом переставляя, в чем вопрос?