BrotherFlame (brotherflame) wrote,
BrotherFlame
brotherflame

Конец собеседований

В общем, если яндекс и еще пара мест были сугубо для разминки, то пройти в райф или сбер я более менее рассчитывал, но обломался.

Причем никогда не знаешь, чем тебя заебут, когда уже вроде как прошел тех интервью. На втором в этот раз это был провокационный вопрос: "Зачем отдавать тестировщику код на тестирование, когда можно самому проверить?" Минут 5 не мог понять, что он хочет услышать. Всего интервьюверов было три. Злой полицейский, добрый полицейский и девушка.



Ну и всякие вопросы про конфликты в команде и их разруливании.
Был у меня конфликт реальный с тим лидом на одном из мест. Тим лид сделал некомпетентную на мой взгляд вещь, что было полбеды. Основная беда была в том, что это поломало к херам то, что делал я. Поэтому я пошел к менеджеру и аргументировал, что так дальше никак.
На что вопрос интервьюверши:
"А если бы менеджер не разрулил конфликт, то уволился бы?"
Я:"Не думал даже об этом, так далеко"

Ну и с детской задачей затупил.
Сколько нулей на конце числа 100!

Сразу понятно, что нули на конце дают произведения 2 и 5. И никак иначе их не получить. Поэтому нужно разложить все множители числа на простые и посчитать кол-во вхождений пятерки. Двойку можно не считать, ее заведомо больше чем вхожлений 5. Число нулей будет равно числу пятерок в произведении, которые дадут:
5, 10, 15, 20, 25(х2), 30, 35, 40, 45, 50(х2), 55, 60, 65, 70, 75(х2), 80, 85, 90, 95, 100(х2)
Всего: 24


Задача 2.
Даны два массива, надо найти их пересечение (элементы, которые есть и там и там)
Использовать добавление в Set нельзя, нужно алгоритм написать.

Общий план решения:
1. Сортируем массивы. На несортированных кроме полного перебора ничего в голову не приходит, но полный перебор это квадратичная сложность. О(N^2)
Такое решение никого не устроит.
Сортируем, например, быстрой сортировкой или сортировкой слиянием. Это N*log(N)
В первом массиве берем первый элемент и бинарным поиском ищем его во втором. Сложность поиска log(N)
Т.е. общая сложность будет
N*log(N)*log(N)
Можно улучшить, вводя всякий доп проверки для отсечения крайних случаев, когда все элементы второго массива больше или меньше любого элемента первого.
Ну и добавление элементов в дерево отсортированное, имеет сложность N*log(N). Если дважды это сделать, добавляя сначала первый массив, потом второй, и проверяя, есть ли уже такой элемент, и если есть, добавлять его в результирующий массив, то сложность станет чуть лучше, N*log(N). Но о таком варианте на собесах я стараюсь не говорить, чтобы не просили реализовать черно-красное дерево.
В общем, для решения подобных задач хватит знания трех алгоритмов:
Быстрая сортировка, сортировка слиянием и Timsort.
А знание алгоритма вставки и поиска в сбалансированном бинарном дереве покроет почти на 100% варианты решения таких задач.

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

2. С другого, тренировочного собеса.
Есть массив, найти в нем все пары, которые в сумме дают 0.
Опять же, детский сад с полным перебором, который прокатывает в школе никого не интересует.
Поэтому снова сортируем массив, если он не отсортирован.
Это N*log(N)
Дальше берем элемент и бинарным поиском ищем ему пару.
Опять же эвристики всякие, если все больше нуля или все меньше, то не ищем ничего.
Это даст все тот же N*log(N)*log(N)

3. Задача с сберовского собеса.
Дано число типа int. Определить, является ли оно степенью двойки.

Есть разные решения. Например, если взять логарифм двоичный от числа, и получить целое число, то можно сказать, что наше число это степень двойки.
Но скорее всего захотят увидеть
другое решение:
Побитовое сравнение

x & (x - 1) == 0

Можно воспользоваться методом
Integer.bitCount(int i)
Он возвращает количество битов, равных единице. У степеней двойки такой бит всегда один.
И решение будет выглядеть так:

Integer.bitCount(x) == 1

Tags: pretty fly for a white guy, work
Subscribe

  • Автоогорчение

    Рассмотрев под лупой mercedes a class и kia proceed gt, решил брать кию, при одном ее существенном недостатке, на который мне пофиг, в остальном она…

  • Про автокредиты

    У втб на сайте калькулятор показывает ставку 2%, для зарплатных клиентов и 3% для остальных, если берешь каско и страхование жизни. И 7% и 8%…

  • Неспеша думаю обновить авто

    Бюджет ~2м Кроссоверы не рассматриваю вообще, а так бы тигуан взял. Еще можно уменьшить бюджет на 200р и взять шкоду, но че-то не стоит на нее.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 23 comments

  • Автоогорчение

    Рассмотрев под лупой mercedes a class и kia proceed gt, решил брать кию, при одном ее существенном недостатке, на который мне пофиг, в остальном она…

  • Про автокредиты

    У втб на сайте калькулятор показывает ставку 2%, для зарплатных клиентов и 3% для остальных, если берешь каско и страхование жизни. И 7% и 8%…

  • Неспеша думаю обновить авто

    Бюджет ~2м Кроссоверы не рассматриваю вообще, а так бы тигуан взял. Еще можно уменьшить бюджет на 200р и взять шкоду, но че-то не стоит на нее.…