какие вопросы по алгоритмам

[eman]

Деревья и графы всякие.

[John Smith]

Одноклассники ищут разработчиков на Java:
...

О, я даже поотвечал. Прислали письмо, что тест пройден успешно.

[Poryadok]

А у нас вопросы по аглоритмам не задают. По COM-у - да. По дотнету - да. По асинхронной работе с медлеными устойствами и процессами - да. По синхронизации процессов и thread-ов - да. А по аглоритмам - нет.

Софт, с которым доводилось сталкиваться, обычно медленно работает не потому, что двоичное дерево неоптимально обходится, а потому, что, обрабатывая список, после каждого шага запускает алгоритм пересчета всего списка. Ну, или подписывается на ивент в процедуре обработки ивента, что приводит к экспоненциальному росту объема вычислений и поедаемой памяти (что проявляется очень нескоро если ивенты приходят редко). При этом, непосредствено относящийся к проблеме код размазан по десяткам исходных файлов, и наличие глюка совершенно неочевидно. Эти глупые ошибки, как правило, появляются в результате оверенжиниринга, когда код на ровном месте усложняется до безобразия ради красивых парадигм. Ну и что толку, что программер алгоритмы знает? Меня больше беспокоит, чтобы у него не было склонности к over-engineering-у, о чем я на интервью стараюсь выяснить в первую очередь.

Это я к тому, что прежде чем налегать на задачи по алгоритмам - поинтересуйтесь, нужны ли они. У инсайдеров, у тех кто туда интервью уже проходил.

Я, кстати, друга к себе на работу на днях устроил. Подсунул его резюме куда нужно, и объяснил ему что будут спрашивать, и как отвечать. В общих чертах. Дальше он сам справился - он мужик умный.

[Sergunka]

он мужик умный.

Был бы умный, жил бы в Калифорнии

[Poryadok]

What kind of joke is that?

Глубокоуважаемый Сергунька. У нас в Орегоне - бабье лето, чудесная погода. А в Калифорнии - водители рефрижираторов дерут по 10 баксов с людей за то, чтобы тем 10 минут охладиться. (по крайней мере так нам говорит Орегонская пропаганда по радио)

Ну и куда умный человек поедет жить?

Если глобальное потепление будет продолжаться, на Аляске недвижимость будет самая дорогая, а Калифорния будет своим жителям доплачивать чтобы они только остались и не разъехались

[hogzie]

Глубокоуважаемый Сергунька. У нас в Орегоне - бабье лето, чудесная погода. А в Калифорнии - водители рефрижираторов дерут по 10 баксов с людей за то, чтобы тем 10 минут охладиться. (по крайней мере так нам говорит Орегонская пропаганда по радио)

Странный вы какой-то. Тут уже всех убедили, что в Калифорнии страшно холодно. Пропаганда неправильная какая-то. А если серьезно, то в Bay Area замечательная погода, последняя неделя была жаркая, но все в пределах нормы. А вот тем, кто живет в центральной Калифорнии не повезло, там под 110 было. Ну так кто там живет?

[Poryadok]

Вообще-то там речь была про LA. Там, как раз, живет достаточно много народу. Я им искренне сочувствую.

[mr. Hide]

С одной стороны "железячный", а с другой и алгоритмический тоже, вопрос для второклассников, примерно.

Дано: платформа с неизвестным порядком битов БАЙТОВ в "слове" процессора (unknown endianness). Самый значительный БАЙТ может быть как последним, так и первым, мы не знаем.

Как: написать код на C, который будет заведомо правильно упаковывать подряд в памяти и распаковывать назад в переменные (serialize-deserialize) целые числа произвольного размера (байт, слово, двойное слово, важен принцип).

Нечаянно (у меня не очень хорошо с puzzles, на 3+, не выше) на это последний раз ответил и код нарисовал. Видно, такое лежит достаточно далеко от паззлов а-ля фудзияма-нахрен-ее-двигать. А интервьюер говорит, давно никто не отвечал. Это в Силиконовой Долине.

Код тоже интересен, чтобы работал.

[crypto5]

Может я не совсем понял задачу, но чем простой memcpy(mem_ptr, &var, sizeof(var)) не подходит? Под упаковкой имеется в виду что то особенное?

Если где то явно сглупил, извините, к С и железу отношение имею опосредственное.

[mr. Hide]

Я там подправил условие, речь про порядок байтов в машинном слове.

Может я не совсем понял задачу, но чем простой memcpy(mem_ptr, &var, sizeof(var)) не подходит? Под упаковкой имеется в виду что то особенное?

Если где то явно сглупил, извините, к С и железу отношение имею опосредственное.

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

Code: Select all

SYSTEM1
BYTE                WORD                                MORE
1001 0001 -> 1100 1001 0000 0001  -> ...

BUFFER TO TRANSPORT
100100011100100100000001...

SYSTEM2
BYTE                WORD                               MORE
1001 0001  -> 0000 0001 1100 1001 -> ....

Сериализация - транспорт - десериализация. Обе переменные во второй системе равны своим источникам в первой. Но представлены по разному - это специфика их процессоров. Транспортный буфер и вовсе последовательность битов, алгоритм десериализации просто знает, где какая переменная, по какому битовому смещению (в реале пакуют и в 1 бит и в 7 и как вмещается диапазон целого, но в задаче сжатия нет, просто к слову). Да, переменные в памяти лежат обычно раздельно и по четным адресам, хотя могут быть нечетного размера.

http://en.wikipedia.org/wiki/Endianness

http://en.wikipedia.org/wiki/Serialization

[Асти]

Можно немного добавлю по следам прошедших интервью:

виртуальные функции
множественное наследование
виртуальное наследование
чисто виртуальные функции
какая чисто виртуальная функция обязана иметь имплементацию? почему? А какая часть процесса билда будет ругаться если пропустить?
sizeof пустого класса? А почему? а класса с одной переменной, с виртуальной функцией, при наследовании? А выравнивание? А упаковка?
static in C? А функция? А в плюсах? А в классе? А если в методе класса и у класса несколько инстансов, сколько раз будет инициализация? А когда вызываются деструкторы? А в каком порядке?
а в каком порядке инициализация глобальных переменных? А статических? А порядок уничтожения?
А синглтон, когда уничтожается? А как контролировать(тут я долго пытался понять, что хочет спрашивающий. Оказалось уничтожение и пересоздание его устраивает)?
А для чего виртуальный деструктор? А порядок вызова деструктора?
А может ли ссылка быть членом класса? А для чего список инициализации в конструкторе?
А какие методы у пустого класса?
А напишите сигнатуры всех методов пустого класса?
А напишите сигнатуру оператора ++? А задайте правильный вопрос к предыдущему и напишите оба? А реализацию скажем для класса с int x и double y? А вторую?
А что такое оптимизация return value? А что не гарантируется?
А какие STL контейнеры знаете? А какие времена они гарантируют? А всегда ли? А что плохо с вектором? А что с мапом? А с листом?
А напишите сортировку строк любым способом? А быстрее? А чисел? А еще быстрее? А что еще можно отсортировать за линейное время?
А за какое время можно обойти мап? А как он устроен? А может есть еще варианты как можно сделать мап?
А напишите процедуру хипизации кучи?
А какие свойства у кучи? Сбалансированного дерева? Красно-черного дерева?
А что будет если вернуть указатель на локальную переменную?
А как устроен дэк и что он не гарантирует в отличии от вектора?
А какие контейнеры допускают реаллокацию элементов а какие нет? А что произойдет с итераторами?
А какое максимальное число в double?
А минимальное положительное?
А что происходит если минимально положительное число умножить на 0.1? А что вы назвали минимально положительным числом? А почему если числа стали сильно маленькими то программа безбожно начинает тормозить (как минимум на х64)? А что надо сказать в опциях компилятору? А после того как окажется что исключения тут не причем? (этот вопрос мне не задавали-)
А переставить буквы в строке местами? А слова?
А чем отличается memmove от memcpy? А написать самому memmove (спрашивающий обычно не знает что написать это хорошо не так тривиально и с префечами не знаком).
А написать strcpy? А когда будут проблемы? А еще? А как задетектировать перехлест памяти и скопировать корректно даже в этом случае?
А что произойдет если exception в конструкторе? А если в конструкторе самого exception? А что с локальными переменными конструктора? А с членами? А если не все успели проинициализировать? А деструктор вызовится? А базового класса? А членов? А в каком порядке?
А что такое дружественные функции? А дружественные операторы? А почему конструктор копирования имеет доступ к приватным членам копируемого объекта?
А напишите сходу бинарное дерево? А список?
А обратите односвязный список?
А скопируйте односвязных список, члены которого могут иметь ссылки на члены этого же списка (в копии соответственно надо скорректировать ссылки на новый список).
А посчитайте длину односвязного списка? А когда это не будет работать? А как посчитать даже с учетом цикла? А какие условия на шаг итераторов, если хочется другой чем стандартные?
А какой ваш любимый патерн проектирования? А расскажите подробнее? А где вы его использовали?
А какой у вас был челенж в последнем проекте?
А что вас сподвигло интервьюироваться именно на эту позицию?
А почему вы ушли с последнего места работы? А что вас там не устраивало? А как должен звучать правильный ответ? А если потренироваться и сделать ответ не таким заученным, но более интересным для человека, который первый и второй вариант уже слышал раз сто?
А какой у вас опыт с линухом? А как скопировать файл с удаленной машины?
А сколько шариков в кубе с кубической решеткой параллельной граням и ребром 10? А сколько шариков во внешнем слое? А как считали?
А есть плоский прямоугольный торт с вырезаным в произвольном месте ромбом. А разрежьте его на две равные части?
А как бороться с дедлоками? А с мем ликами? А с четырех сантиметровыми тараканами в НЙской квартире?
За правильный ответ на последний вопрос готов спросить еще чего нибудь

[Komissar]

на последний вопрос правильный ответ - уехать из НЙ апартмента в отдельно стоящий дом.

[Sasha3091]

на последний вопрос правильный ответ - уехать из НЙ апартмента в отдельно стоящий дом.

Вариант ответа №2:

купить тараканам отдельный дом

[adda_]

на последний вопрос правильный ответ - уехать из НЙ апартмента в отдельно стоящий дом.

Вариант ответа №2:

купить тараканам отдельный дом

Уехать из НИ...

[hogzie]

Нечаянно (у меня не очень хорошо с puzzles, на 3+, не выше) на это последний раз ответил и код нарисовал. Видно, такое лежит достаточно далеко от паззлов а-ля фудзияма-нахрен-ее-двигать. А интервьюер говорит, давно никто не отвечал. Это в Силиконовой Долине.

Шутки шутите. Или Грэг (он этот вопрос всем задает для начала) вам такой комплимент отвесил? Да и вобще какой это на фиг паззл? Такой вопрос тем более для железячника должен отскакивать от зубов. Если htons()/ntohs() недоступны, то задача решается элементарно маской и Си-шным сдвигом, который от byte order независим.

[mr. Hide]

, то задача решается элементарно маской и Си-шным сдвигом, который от byte order независим.

Ну так дело в том, что еще и написать. Туда-обратно. Это очень смешно, да.

[hogzie]

, то задача решается элементарно маской и Си-шным сдвигом, который от byte order независим.

Ну так дело в том, что еще и написать. Туда-обратно. Это очень смешно, да.

Вполне себе нормальная задачка, никак не паззл. Даже если ее писать имплементацию, от чего она паззлом все равно не станет. Любому программист, знакомый с битами, байтами и endianness, - должно решаться за раз.

[mr. Hide]

Вполне себе нормальная задачка, никак не паззл. Даже если ее писать имплементацию, от чего она паззлом все равно не станет. Любому программист, знакомый с битами, байтами и endianness, - должно решаться за раз.

Так и не говорил, что это паззл. Что решается, как бы знаю, раз решил (еще раз). "Вопрос для второклассников, примерно" - себя цитирую.

[Sasha3091]

на последний вопрос правильный ответ - уехать из НЙ апартмента в отдельно стоящий дом.

Вариант ответа №2:

купить тараканам отдельный дом

Уехать из НИ...

Зачем уезжать, если у тараканов отдельный дом.

[shadow7256]

А почему вы ушли с последнего места работы?

вот с этим вопросом задолбали честно говоря. Каждый спрашивает по телефону, а почему ушли?

[fruit6]

А почему вы ушли с последнего места работы?

вот с этим вопросом задолбали честно говоря. Каждый спрашивает по телефону, а почему ушли?

это психологический тест. проверяют: пошлет - не пошлет :)

говорите, что контракт закончился. если на постоянке, то замените на "проект"

[M. Ridcully]

А почему вы ушли с последнего места работы?

вот с этим вопросом задолбали честно говоря. Каждый спрашивает по телефону, а почему ушли?

А что не так с этим вопросом?
По-моему, очень было бы странно, если бы такой вопрос не спросили.

[Sasha3091]

А почему вы ушли с последнего места работы?

вот с этим вопросом задолбали честно говоря. Каждый спрашивает по телефону, а почему ушли?

А что не так с этим вопросом?
По-моему, очень было бы странно, если бы такой вопрос не спросили.

Ответ - я продал компанию, в которой работал, а теперь ищу full-time.

[M. Ridcully]

Ответ - я продал компанию, в которой работал, а теперь ищу full-time.

Ну вот видете, у вас есть ответ.
А у shadow7256 - почему-то нет. Вот это и интересно.

[Sasha3091]

Ответ - я продал компанию, в которой работал, а теперь ищу full-time.

Ну вот видете, у вас есть ответ.
А у shadow7256 - почему-то нет. Вот это и интересно.

Уточнение:

- а вы продали компанию, в которой работали или свою компанию, в которой работали?