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

[Aleksey Kudinov]

Вам тут высокие материи всё, а я сегодня из МБА претендующего на роль бизнес аналитика не смог вытянуть что есть internal rate of return. Кто знает, тот поймёт. А present value of $30 2 years from now at a 10% discount rate у него получилось $24... Рукалицо.

[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. Без всяких досок и квадратиков.

Код: Выделить всё

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. Без всяких досок и квадратиков.

Код: Выделить всё

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, количество памяти и коров значение не имеют
Что то вроде такого.

Код: Выделить всё

        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

Код: Выделить всё

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

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

Код: Выделить всё

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 лет назад), писали что то типа, что выбор конкретного алгоритма сортировки, "в реальных программах", зависит от многих факторов, и лучше использовать несколько алгоритмов, и применять в зависимости от ситуации, или модифицировать какой нибудь из "улучшенных" алгоритмов. Ведь не секрет, что при определённых условиях быстрая сортировка проиграет пузырьковой "улучшенной" и некоторым другим, как "улучшенным" (не факт, надо проверить) так и нет.