У вас постановка задачи — написать itoa. На вашем любимом языке. Например, в проекте нужно записать число в нестандартной кодировке (вместо 0 — a, вместо 1 — b, и т.д.)
на C++ без использования ф-ий std::string
Где вы это требование взяли? Я вам написал выше — используйте любые методы std::string и стандартные алгоримы. Все, кроме, собственно to_string.
Если вы вместо этого "говнокода" напишете рабочую версию с std::string::push_back и std::reverse, вам это зачтется за правильный ответ, если, разумеется, сможете объяснить сколько это будет работать и почему.
Один мелкий недочет — в интервью бы исправилось сразу при написании — кто вам сказал, что офисов 12? Их N. Но это у вас просто 12 в нескольких местах на N поменять надо.
Решение отличное. Вы даже учли случай, когда из начального офиса нельзя никуда улететь вообще.
Если осталось время на интервью, я бы попросил вместо коментариев сделать имена переменным осмысленные, но это не критично. Еще обязательно спросил бы про сложность вашего решения. Может быть обсудил бы еще, почему вы считате, что можно -1 использовать для недостижимых позиций (очвидно — мы счиатем, что не может быть отрицательного количества выходных, поэтому -1 мы в достижимых позициях не получим никогда. Но хотелось бы это услышать на интервью).
А вот понадобится вам чуть нестандартный LinkedHashMap. Например, некотрые элементы нужно поментить, как неудаляемые из кэша. Простым LinkedHashMap уже не сделать. Вернее не сделать быстро.
Вообще, 2D деревья отрезков — это немножко дичь. Там нельзя наивно пилить прямоугольник на 4 части-угла. Это будет иногда работать за линию. Надо делать дерево отрезков по одной координате и там каждая вершина будет деревом отрезков по второй координате. Если специально не тренировать это — не закодишь.
Поэтому я считаю, что это решение на 5+. Если кандидат сам сразу придумал и уверен в себе — честь и хвала такому кандидату. Иначе, ни в коем случаее не надо подталкивать кандидата к этому решению и если времени на кодинг осталось мало, то попросить написать что-нибудь попроще.
Примерно такой ответ и был и устроил собеседуюшего. Я правда, развернул рекурсию и делал двумя циклами в матрице.
Только надо не забыть, что можно в офисе остаться при переборе следующего и в финале не перебираем первый уровень — нам же дан стартовый офис.
Конечно, надо в коде. Но это 10-20 строк всего. Чего тут за 30 минут можно не написать? Код не надо компилировать, если там будут опечатки — это не минус для оценки. Если забудете что-то (напрмер, остаться в офисе) — интервьювер даст подсказки, типа "а вы нечего не забыли? А если такой тест?".
И да, я забыл рассказать самое интересное. Результат собеседования это галочка/крестик/boolean — «брать» или «не брать» («hire»/«no hire»).
В гугле не так. Во первых, градаций больше, есть еще leaning hire/no-hire. Во вторых, результат — это не просто оценка, а детальный отчет. Этоти отчеты от всех 4-5 интервьюверов смотрит отдельный комитет. Они читают все и могут вообще проигнорировать отчет какого-то интервьювера, если там нет объективных сигналов.
С телефонными ближе к тому, что вы сказали, но там тоже детальный отчет читает рекрутер. Если есть основания пологать, что вы просто не понравились интервьюверу — вам назначат второе собеседование.
Ну вот вам пример запрещенной теперь к интервью задачи (потому что утекла) — меня именно ее пару лет назад и спрашивали:
У гугла куча офисов в разных странах. В разных странах разное количество праздников. Можно раз в месяц перелетать в другой офис (в конце месяца). Как и куда лететь, чтобы максимизировать количество выходных? Дано сколько выходных в каком офисе в каждом из 12 месяцев. Еще дан список возможных перелетов офис->офис. Верните список из 12 офисов.
Из уточнений — не обязательно перелетать, можно сидеть в офисе несколько месяцев подряд; нельзя делать несколько перелетов подряд, т.е. лететь только без пересадок. Перелеты однонаправленные (если дано A->B, то не обязательно можно лететь B->A); Вам дан начальный офис, заканчивать год можно где угодно.
Ненамного сложнее того, что вы упомянули, но ничего сверхъестественного. Решение — буквально 10 строк. Да, тут еще как-бы и граф есть но ДП на графах — тоже стандартная вещь.
Ну нет. Идете на тот-же leetcode, и прорешиваете задачки с подсказками. Пару вечеров в неделю, да выходные — за пару недель можно натаскаться. Там же основная идея одна и та же. Осталось только натаскаться угадывать, что взять параметрами.
Динамическое программирование — это не просто академическая игрушка и головоломка-пароль, чтобы пройти в гугл. Я на практике как раз в гугле применял. Пару раз вместо полного 2^N перебора можно было сделать что-то квадратичное или кубическое.
Поэтому стоит его ожидать на интервью и дальше и подучить его.
Вообще, о том, что «всем давно известно, что в Гугле stl нельзя использовать на интервью» можно догадаться
Что? Первый раз слышу. Сам на интервью использовал несколько раз. Более того, я еще и порядок аргументов напутал, интервьюверов это не волнует вообще.
интервьюверу мог не понравиться мой коммент,
Интервьювер может написать об этом в своем отчете, но все-равно, на это будет смотреть комитет. Так что это не просто мнение одного чувака, которому что-то не понравилось. С ним, как минимум, еще несколько человек согласилось.
В гугле все не так. Там не HR, а коллеги пишут отзывы и оценки. А менеджеры потом очень долго и много обсуждают, чтобы всех по организации оценить одинаково.
Да, периодичность ревью вызывает некоторые негативные моменты — типа запусков сыроватых продуктов, чтобы пунктик себе записать, но это редкость.
но не помнишь порядок аргументов в одной из функций, а гуглить нельзя,
В адекватных конторах это обычно не проблема. Я на одном собеседовании просто сказал, что вот не помню порядок аргументов и точное название стандартного метода. Собеседователь сказал, что это вообще неважно, итак на псевдокоде пишем. Никаких проблем не было.
Почему вы уверены в «снижении качества образования»?
Я не уверен. vershinin предъявляет это как свидетельство ужасных проблем "у них". Я решил не тратить энергию на развенчание этой проблемы, а вместо этого привести сравнение с проблемами в России.
Пытки в тюрьме, потому что товарищу милиционеру нужно было выполнить план по экстремистам vs. снижать качество образования, чтобы ни в ком случае не обидеть "меньшинства".
Везде одно и тоже. И там, и там — неудобства и неприятности [/sarcasm]
У вас постановка задачи — написать itoa. На вашем любимом языке. Например, в проекте нужно записать число в нестандартной кодировке (вместо 0 — a, вместо 1 — b, и т.д.)
Где вы это требование взяли? Я вам написал выше — используйте любые методы std::string и стандартные алгоримы. Все, кроме, собственно to_string.
Если вы вместо этого "говнокода" напишете рабочую версию с std::string::push_back и std::reverse, вам это зачтется за правильный ответ, если, разумеется, сможете объяснить сколько это будет работать и почему.
Один мелкий недочет — в интервью бы исправилось сразу при написании — кто вам сказал, что офисов 12? Их N. Но это у вас просто 12 в нескольких местах на N поменять надо.
Решение отличное. Вы даже учли случай, когда из начального офиса нельзя никуда улететь вообще.
Если осталось время на интервью, я бы попросил вместо коментариев сделать имена переменным осмысленные, но это не критично. Еще обязательно спросил бы про сложность вашего решения. Может быть обсудил бы еще, почему вы считате, что можно -1 использовать для недостижимых позиций (очвидно — мы счиатем, что не может быть отрицательного количества выходных, поэтому -1 мы в достижимых позициях не получим никогда. Но хотелось бы это услышать на интервью).
А вот понадобится вам чуть нестандартный LinkedHashMap. Например, некотрые элементы нужно поментить, как неудаляемые из кэша. Простым LinkedHashMap уже не сделать. Вернее не сделать быстро.
Вообще, 2D деревья отрезков — это немножко дичь. Там нельзя наивно пилить прямоугольник на 4 части-угла. Это будет иногда работать за линию. Надо делать дерево отрезков по одной координате и там каждая вершина будет деревом отрезков по второй координате. Если специально не тренировать это — не закодишь.
Поэтому я считаю, что это решение на 5+. Если кандидат сам сразу придумал и уверен в себе — честь и хвала такому кандидату. Иначе, ни в коем случаее не надо подталкивать кандидата к этому решению и если времени на кодинг осталось мало, то попросить написать что-нибудь попроще.
Я правильно понимаю, что тут достаточно линейного решения для update и count, и не требуется (log n)^2 решение на двумерных деревьях отрезков/фенвика?
Примерно такой ответ и был и устроил собеседуюшего. Я правда, развернул рекурсию и делал двумя циклами в матрице.
Только надо не забыть, что можно в офисе остаться при переборе следующего и в финале не перебираем первый уровень — нам же дан стартовый офис.
Конечно, надо в коде. Но это 10-20 строк всего. Чего тут за 30 минут можно не написать? Код не надо компилировать, если там будут опечатки — это не минус для оценки. Если забудете что-то (напрмер, остаться в офисе) — интервьювер даст подсказки, типа "а вы нечего не забыли? А если такой тест?".
В гугле не так. Во первых, градаций больше, есть еще leaning hire/no-hire. Во вторых, результат — это не просто оценка, а детальный отчет. Этоти отчеты от всех 4-5 интервьюверов смотрит отдельный комитет. Они читают все и могут вообще проигнорировать отчет какого-то интервьювера, если там нет объективных сигналов.
С телефонными ближе к тому, что вы сказали, но там тоже детальный отчет читает рекрутер. Если есть основания пологать, что вы просто не понравились интервьюверу — вам назначат второе собеседование.
Ну вот вам пример запрещенной теперь к интервью задачи (потому что утекла) — меня именно ее пару лет назад и спрашивали:
У гугла куча офисов в разных странах. В разных странах разное количество праздников. Можно раз в месяц перелетать в другой офис (в конце месяца). Как и куда лететь, чтобы максимизировать количество выходных? Дано сколько выходных в каком офисе в каждом из 12 месяцев. Еще дан список возможных перелетов офис->офис. Верните список из 12 офисов.
Из уточнений — не обязательно перелетать, можно сидеть в офисе несколько месяцев подряд; нельзя делать несколько перелетов подряд, т.е. лететь только без пересадок. Перелеты однонаправленные (если дано A->B, то не обязательно можно лететь B->A); Вам дан начальный офис, заканчивать год можно где угодно.
Ненамного сложнее того, что вы упомянули, но ничего сверхъестественного. Решение — буквально 10 строк. Да, тут еще как-бы и граф есть но ДП на графах — тоже стандартная вещь.
Ну нет. Идете на тот-же leetcode, и прорешиваете задачки с подсказками. Пару вечеров в неделю, да выходные — за пару недель можно натаскаться. Там же основная идея одна и та же. Осталось только натаскаться угадывать, что взять параметрами.
Динамическое программирование — это не просто академическая игрушка и головоломка-пароль, чтобы пройти в гугл. Я на практике как раз в гугле применял. Пару раз вместо полного 2^N перебора можно было сделать что-то квадратичное или кубическое.
Поэтому стоит его ожидать на интервью и дальше и подучить его.
Да, вы правы, телефонки комитет не рассматривает. Но кто-то там тоже посмотрит отчет и если надо, второе интервью назначит.
Что? Первый раз слышу. Сам на интервью использовал несколько раз. Более того, я еще и порядок аргументов напутал, интервьюверов это не волнует вообще.
Интервьювер может написать об этом в своем отчете, но все-равно, на это будет смотреть комитет. Так что это не просто мнение одного чувака, которому что-то не понравилось. С ним, как минимум, еще несколько человек согласилось.
В гугле все не так. Там не HR, а коллеги пишут отзывы и оценки. А менеджеры потом очень долго и много обсуждают, чтобы всех по организации оценить одинаково.
Да, периодичность ревью вызывает некоторые негативные моменты — типа запусков сыроватых продуктов, чтобы пунктик себе записать, но это редкость.
Вы правы, да, я их спутал. Отличное получилось подтверждение слов 0xd34df00d.
У вас ни в одном C++ проекте вообще нет никаких интерфейсов?
В адекватных конторах это обычно не проблема. Я на одном собеседовании просто сказал, что вот не помню порядок аргументов и точное название стандартного метода. Собеседователь сказал, что это вообще неважно, итак на псевдокоде пишем. Никаких проблем не было.
FizzBuzz же: выведите n строк — k-ая строка должна начинаться с числа k. Потом содержать Fizz, если k делится на 2 и/или Buzz, если k делится на 3:
Я не уверен. vershinin предъявляет это как свидетельство ужасных проблем "у них". Я решил не тратить энергию на развенчание этой проблемы, а вместо этого привести сравнение с проблемами в России.
Возвращаемся к основному посылу моего коментария:
Пытки в тюрьме, потому что товарищу милиционеру нужно было выполнить план по экстремистам vs. снижать качество образования, чтобы ни в ком случае не обидеть "меньшинства".
Везде одно и тоже. И там, и там — неудобства и неприятности [/sarcasm]