Amazon AWS Kiev recruiting event at March 4-7th

[АццкоМото]

тем не менее уровень амазновских интервьюеров относительно высок.

ээээ.... относительно чего?

по крайне мере то что они спрашивают они понимают. это уже роскошь!

Тут не поспоришь. Попадались гении, которые на интервью несли такую чушь, что хоть святых выноси. Причем они меня интервьюировали, а не я их

[8K]

mr boombastic, и от меня спасибо.
очень повеселили супер-омозоноффские-перцы, которых озадачивает if(!root) - понятно, конечно, что джава головного мозга влияет, но не настолько же

Ну, по C++ спецы-то, положим, не в Амазоне сидят. Кстати, за этот STL я бы, скорее, зарубил кандидата. Но в facebook'е, наверное, одобрили б.

[Леонид Ильич Брежнев]

Они чего уже все на джаву переписали? Там же должно быть массу еще испокон-векового перлового и с++ кода.

[Alexandr]

тем не менее уровень амазновских интервьюеров относительно высок. по крайне мере то что они спрашивают они понимают. это уже роскошь!
может я не прав и мне кажется,но мне иногда попадались интервьюеры которые спрашивали вещи которые они походу дело 10 минут назад сами прочитали. причем в желтой прессе. до них не доходит что не все что написанно на stackoverflow есть верно.

можете еще рассказать о том что спрашивали, интересно?

[mr boombastic]

Они чего уже все на джаву переписали? Там же должно быть массу еще испокон-векового перлового и с++ кода.

насколько я понял так и есть. но они это либо переписывают на джаву либо не трогают(если работает). туда куда я шёл, там java/jsp/ruby on rails/perl. On Call там не было. из этого набора имел дела с перлом последний раз 2 года назад и с core-джавой 4 года назад.ruby-я даже sample code не видел никогда.
но в этом то и прелесть, что на языки программирования они не особо внимание обращают. кстати,удивило что про малтитрэдинг ничего не спросили.

[Alexandr]

понятно, т.е. заточка только под алгоритмы

[mr boombastic]

я вообще заметил что про внутренности языка очень любят спрашивать в конторах где основной язык это С++. не дай Бог мне придти на такое интервью не выспавшимся. засну моментально от очередного вопроса в стиле - "а что такое {}". {} можно заменить на виртуальный деструктор, виртуальную функцию,....

[Alexandr]

я вообще заметил что про внутренности языка очень любят спрашивать в конторах где основной язык это С++. не дай Бог мне придти на такое интервью не выспавшимся. засну моментально от очередного вопроса в стиле - "а что такое {}". {} можно заменить на виртуальный деструктор, виртуальную функцию,....

пффф... вы, видимо, не были там, где реально спрашивают по внутренностям языка, но тему развивать эту я не буду

можете еще описать какие алгоритмы спрашивали, интересно... f2f был уже?

[mr boombastic]

я вообще заметил что про внутренности языка очень любят спрашивать в конторах где основной язык это С++. не дай Бог мне придти на такое интервью не выспавшимся. засну моментально от очередного вопроса в стиле - "а что такое {}". {} можно заменить на виртуальный деструктор, виртуальную функцию,....

пффф... вы, видимо, не были там, где реально спрашивают по внутренностям языка, но тему развивать эту я не буду

можете еще описать какие алгоритмы спрашивали, интересно... f2f был уже?

это было почти год назад когда я был у них на f2f. меня не взяли. не было такого что бы написать какой нибудь алгоритм.
с фон скрина помню был такой вопрос,
есть n-ary дерево.
struct node
{
node* next; //изначально равен нулю
list<node*> children;
}
все указатели next нужно выставить на следующий node на этом же уровне.
n1
n21 n22 n23 n24
n31 n32 n33 ........

то есть n21->next должен указывать на n22. n22->next на n23 и тд.

суть в том что если человек на память не помнит как вообще по такому дереву пройти,именно таким способом каким нужно,вряд ли у него чего то поулчится.
это задача была на кодинг.время 15-20 минут на все про все.

были вопросы что нибудь в массиве найти. вот приммер: как найти k-ый элемент в не отсортированном массиве? опять же,если вы не знакомы с определенными трюками то вряд ли даже кодить выйдите. да и еще без багов. [решение отсортировать и вернуть к-ый элемент можно на помойку сразу. не кошерно].

было много всяких задачек. где то 16 за весь процесс. меня даже тот интервьер который на ланч водил на обратном пути спросил какую то задачку про бинарное дерево на поговорить.я ему отвечаю,он такой-ну вроде будет работать.выходим из лифта,заходим в конференс зал(через 2 минуты следующий должен был зайти).он мне-давай ты быстренько закодируешь это.я закодил,заходит другой интервьер а тот перец в это время ошибку нашёл.поправил её он сам .смотрит на доску и говорит-ну так наверное лучше.достал телефон, с фоткал код, сказал гуд лак и убежал. даже вазелина не оставил! на лице у второго который уже нетерпеливо ждал появилась улыбка в стиле-"наконец то я могу тебя сейчас иметь"!

[Medium-rare]

суть в том что если человек на память не помнит как вообще по такому дереву пройти,именно таким способом каким нужно,вряд ли у него чего то поулчится.
это задача была на кодинг.время 15-20 минут на все про все.

Хорошая задача. Легче получится, если не пытаться забить весь tree traverse в одну функцию. Помогает iterator, как pattern.

[mr boombastic]

там помоему не больше 15-ти строчек выходило

[mr boombastic]

я вообще заметил что про с,
как найти k-ый элемент в не отсортированном массиве?

к-ый по величине.

[АццкоМото]

были вопросы что нибудь в массиве найти. вот приммер: как найти k-ый элемент в не отсортированном массиве? опять же,если вы не знакомы с определенными трюками то вряд ли даже кодить выйдите. да и еще без багов. [решение отсортировать и вернуть к-ый элемент можно на помойку сразу. не кошерно].

Ну это типа классика, тоже попадалось на энторвью.
или так:
http://pine.cs.yale.edu/pinewiki/QuickSelect
или чуть другое, но близкое:
http://en.wikipedia.org/wiki/Partial_sorting
http://en.wikipedia.org/wiki/Selection_algorithm

Единственное, что я не могу понять... НАФИГА? Нафига это помнить? Гуглится же за 5 секунд.
А если чел решил сам в рамках интервью, не имея готового зазубренного решения от более умных людей, то он цукко гений, ему не программки надо писать, а в науку идти

[АццкоМото]

с фон скрина помню был такой вопрос,
есть n-ary дерево.
struct node
{
node* next; //изначально равен нулю
list<node*> children;
}
все указатели next нужно выставить на следующий node на этом же уровне.
n1
n21 n22 n23 n24
n31 n32 n33 ........

то есть n21->next должен указывать на n22. n22->next на n23 и тд.

Кстати, и это тоже классика Типа depth first vs breadth first traversal и связанные проблемы.

[АццкоМото]

засну моментально от очередного вопроса в стиле - "а что такое {}". {} можно заменить на виртуальный деструктор, виртуальную функцию,....

Вооо, это мои самые ненавистные вопросы Если еще объяснить про виртуальные деструкторы довольно легко, то про виртуальную функцию - отвал башки. Все-таки правило хорошего тона - объяснять так, будто интервьюер сам не знает, что это такое. И вдруг выясняется, что для такого простейшего вопроса все нужные слова куда-то подевались. И короткого классического ответа по-видимому тупо нет: приходится абиснять, как компилятор разруливает обычные методы, а как виртуальные, как устроена таблица виртуальных хункцый... долго, нудно и ненужно
Отдельно доставляют вопросы типа "в каком порядке вызываются конструкторы или деструкторы". Хочется спросить, как так через задницу вы проектируете, что вам это становится важным? А если вдруг какая-то специфика, что этот нюанс важен оправданно - ну блин проверяется экспериментально + теоретически с гуглением стандартов быстрее, чем вы этот вопрос задавали. ЗАЧЕМ ВАМ ЭТО??? Так и хочется сказать, "ну вот и все, спасибо за внимание, а мне, пожалуй, пора наваливать"

[Tarasik]

я вообще заметил что про с,
как найти k-ый элемент в не отсортированном массиве?

к-ый по величине.

Делается похоже на quick sort в том плане что используется partitioning. Берем pivot и перебрасываем влево от него то что больше и вправо то что меньше (partitioning).
Если pivot оказывается в позиции больше k то делаем то же самое с левой частью от pivot и продолжаем искать элемент k.
Если меньше - то в правой части таким образом ищем элемент indexOf(pivot) - k. И так рекурсивно продолжаем искать пока pivot не совпадет с k

Удивительно но это займет линейное время (если считать используя master method).

[mr boombastic]

до QuickSelect можно догадатся если знать и понимать как работает QuickSort. там даже код одинаковый. добавляется только if и else и ещё одна мелочь.
вот для этого и нужно наверное всё таки базовые алгоритмы знать.

а для любителей спросить про порядок вызовов конструкторов/деструкторов, вот такая задачка (прямиком из ада)
красные стрелочки - виртуальное наследование
черные - обычное наследование.

вопрос- в каком порядке будут вызыватся конструктора?или деструктора.

[mr boombastic]

а если кандидат ответит правильно а очень хотелось завалить??? как тут быть?
думаю надо заставить написать их код -
дано - inheritance graph. и нужно написать программу на доске которая обойдя это граф выведит на экран правильную последовательность вызова конструкторов!
и придератся при этом к каждой забытой ';'. и при этом тыкать-ну видишь-у тебя даже не компилируется..

[АццкоМото]

до QuickSelect можно догадатся если знать и понимать как работает QuickSort. там даже код одинаковый. добавляется только if и else и ещё одна мелочь.
вот для этого и нужно наверное всё таки базовые алгоритмы знать.

Нууууу.... Мне кажется, нужно не просто знать quicksort, а чтобы это знание занимало весьма важное место в голове. Просто прочитав и осознав quicksort дойти своим умом, быстро и в стресовой ситуации до kth-largest - это очень круто. А что код практически одинаковый я в курсе, хотя прямо щяз не подзыривая никуда не смогу воспроизвести.

а для любителей спросить про порядок вызовов конструкторов/деструкторов, вот такая задачка (прямиком из ада)

Ну, тут только стебаться остается

[Интеррапт]

вопрос- в каком порядке будут вызыватся конструктора?или деструктора.

Да проще простого E - E - G - B - C - E - H - E - G - B - D - A

[mr boombastic]

Нууууу.... Мне кажется, нужно не просто знать quicksort, а чтобы это знание занимало весьма важное место в голове. Просто прочитав и осознав quicksort дойти своим умом, быстро и в стресовой ситуации до kth-largest - это очень круто. А что код практически одинаковый я в курсе, хотя прямо щяз не подзыривая никуда не смогу воспроизвести.

с подсказками конечно. но и это не поможет если некоторые базовые алгоритмы не сидят в голове в полной боеготовности.

[mr boombastic]

Удивительно но это займет линейное время (если считать используя master method).

master method тут бессилен. он больше для divide and conquer типов алгоритмов подходит.
где то я видел очень елегантное доказательство о running time QuickSort через математическое ожидание и linearity of expectations. по моему coursera.org.

а с наследованиям если кому интересно,тут решения http://rsdn.ru/article/cpp/graphwalk.xml

[Tarasik]

Удивительно но это займет линейное время (если считать используя master method).

master method тут бессилен. он больше для divide and conquer типов алгоритмов подходит.
где то я видел очень елегантное доказательство о running time QuickSort через математическое ожидание и linearity of expectations. по моему coursera.org.

а с наследованиям если кому интересно,тут решения http://rsdn.ru/article/cpp/graphwalk.xml

Я аж подпрыгнул как прочитал - неужели квиксорт это не разделяй и властвуй! Но проверил и таки да - Quicksort is a divide and conquer algorithm. http://en.wikipedia.org/wiki/Quicksort
Мы же в результате partition разбиваем массив на части (divide) а потом части сортируем (conquer).
Master Method как средство вычисления времязатрат алгоритма подходит везде где используется рекурсия. И здеся получится быстрей чем QuickSort потому что нужно делать partition только одной части в итоге O(n)

Это я к тому что когда пойдете на собеседование чтоб вас не подловили Амазоновцы.

[mr boombastic]

Удивительно но это займет линейное время (если считать используя master method).

master method тут бессилен. он больше для divide and conquer типов алгоритмов подходит.
где то я видел очень елегантное доказательство о running time QuickSort через математическое ожидание и linearity of expectations. по моему coursera.org.

а с наследованиям если кому интересно,тут решения http://rsdn.ru/article/cpp/graphwalk.xml

Я аж подпрыгнул как прочитал - неужели квиксорт это не разделяй и властвуй! Но проверил и таки да - Quicksort is a divide and conquer algorithm. http://en.wikipedia.org/wiki/Quicksort
Мы же в результате partition разбиваем массив на части (divide) а потом части сортируем (conquer).
Master Method как средство вычисления времязатрат алгоритма подходит везде где используется рекурсия. И здеся получится быстрей чем QuickSort потому что нужно делать partition только одной части в итоге O(n)

Это я к тому что когда пойдете на собеседование чтоб вас не подловили Амазоновцы.

Это я к тому что когда пойдете на собеседование чтоб вас не подловили Амазоновцы.[/quote]

насчёт divide and conquer я не прав но мой пойнт был в том что через master theorem нельзя доказать randomized версию quicksort в чистом виде. если посмотреть то они там предполагают что в наихудшем случае это разбиение будет на 0 и (n-1) и оттуда уже пляшут. но в randomized версии эти разбиения случайные.

[mr boombastic]

Master Method как средство вычисления времязатрат алгоритма подходит везде где используется рекурсия.

везде?