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

[Сабина]

Еще я недавно для себя открыла что когда идешь на интервью в амбициозный стартап или recent ipo с замашками на второй гугол или твиттер нужно не просто знать про что их бизнес но и серьезно заучить назубок их компетиторов. Вот здесь например - https://www.g2crowd.com/" onclick="window.open(this.href);return false;

[mynameiszb]

когда идешь на интервью в амбициозный стартап

У меня одного ощущение, что между "амбициозный стартап" и "набитые дурью ..удаки" стоит ставить безусловный знак равенства?

[mynameiszb]

Заодно бы и disaster recovery plan бы проверили...

Я когда базы саппортил, у одних клиентов видел классную штуку. Отпечатанный документ на основные отказы. Т.е. - recovery для одного случая, другого, контакты, последовательность действий и пр. И гоняли админов по этой штуке на тестовых серверах раз в 3-4 месяца. Народ периодически что-то находил еще из возможных реальных проблем, тоже обкатывали.

С ними - ни разу проблем не было, чтобы упало что-то и с концами...

Огромная редкость в наши дни, однако.

[x.angie]

нужно не просто знать про что их бизнес но и серьезно заучить назубок их компетиторов.

Как так?

[x.angie]

Я когда базы саппортил, у одних клиентов видел классную штуку.

RunBook, да.

Отпечатанный документ на основные отказы.

Только я видел в электронном виде.

Т.е. - recovery для одного случая, другого, контакты, последовательность действий и пр.

Да, именно так.

И гоняли админов по этой штуке на тестовых серверах раз в 3-4 месяца. Народ периодически что-то находил еще из возможных реальных проблем, тоже обкатывали.

Не уверен, что это было.

Огромная редкость в наши дни, однако.

Ну так...

[mynameiszb]

И гоняли админов по этой штуке на тестовых серверах раз в 3-4 месяца. Народ периодически что-то находил еще из возможных реальных проблем, тоже обкатывали.

Не уверен, что это было.

Было, я на паре прогонов участвовал. Попутно еще обсуждали, какие засады могут случиться в процессе восстановления и "а вот тут все пошло не так".

[Сабина]

Вот еше задачка, вроде простая но мнения как сделать лучше разошлись что называется.

Допустим у вас 100 листочков бумаги, с индексами от 1 до 100, вы по ним проходите первый раз и каждый второй листик помечаете крестиком. Во втором цикле проходите только по тем что не eliminated и тоже помечаете каждый второй крестиком и так далее .... Из метода надо вернуть индекс элемента который останется последним в результате этого процесса. Можно ли быстрее чем lоgN ?

[Krys-Krys]

Вот еше задачка, вроде простая но мнения как сделать лучше разошлись что называется.

Допустим у вас 100 листочков бумаги, с индексами от 1 до 100, вы по ним проходите первый раз и каждый второй листик помечаете крестиком. Во втором цикле проходите только по тем что не eliminated и тоже помечаете каждый второй крестиком и так далее .... Из метода надо вернуть индекс элемента который останется последним в результате этого процесса. Можно ли быстрее чем lоgN ?

Похожая задача есть в книжке Craking the Coding Interview. И эта задача мне кажется там есть. Но не уверена. Мне кажется проходиться не надо вообще, а следует вывести формулу куда на вход идет N а на выход индекс. А если формулой не выйдет - думать в сторону рекурсии.
Я думаю на Джаве ответ будет

Code: Select all

System.out.println(Math.pow(2,(int)log2(N)));

Значит для 100 - индекс будет 64. Я правда вычеркивала каждое 1е число из 2х (т е из 1 2 3 4 5 я помечаю 1 3 и 5 а потом 2 4 остаются и я помечаю 2), но для вычеркивания каждого 2го можно тоже вывести формулу. Вроде бы как ответ всегда будет просто 1. И формула не нужна.

task1.tiff

[helg]

Какой останется невычеркнутым? №1, конечно - и считать ничего не надо. А все чётные номера, в том числе и 64, будут помечены крестиком на самом первом проходе.

Возможно, задача немного не такая. За круглым столом сидят 100 гостей. На стол запрыгивает хозяин и, показывая на гостей последовательно по кругу говорит им поочерёдно: "сиди" и "вон". Гость, которому сказали "вон", выходит из-за стола. Какой из гостей останется последним?

[Krys-Krys]

Какой останется невычеркнутым? №1, конечно - и считать ничего не надо. А все чётные номера, в том числе и 64, будут помечены крестиком на самом первом проходе.

Возможно, задача немного не такая. За круглым столом сидят 100 гостей. На стол запрыгивает хозяин и, показывая на гостей последовательно по кругу говорит им поочерёдно: "сиди" и "вон". Гость, которому сказали "вон", выходит из-за стола. Какой из гостей останется последним?

64 останется если вычеркивать каждое 1е число из 2х. Так же интересней.
Пусть например в вашей задаче

На стол запрыгивает хозяин и, показывая на гостей последовательно по кругу говорит им поочерёдно: "вон" и "сиди".

Тогда 1й самый 1м свалит.

[helg]

64 останется если вычеркивать каждое 1е число из 2х. Так же интересней.

Ну не настолько, как с круглым столом. Тут на первом круге вычеркиваются все числа у которых самый младший бит двоичной записи ненулевой, на втором - у которых второй ненулевой, и так далее. Понятно, что последней останется максимальная степень двойки: у неё больше всех нулей справа.

А вот со столом с гостями (кольцевым счётчиком) такой простой трюк не проходит.

[Сабина]

64 останется если вычеркивать каждое 1е число из 2х. Так же интересней.

Ну не настолько, как с круглым столом. Тут на первом круге вычеркиваются все числа у которых самый младший бит двоичной записи ненулевой, на втором - у которых второй ненулевой, и так далее. Понятно, что последней останется максимальная степень двойки: у неё больше всех нулей справа.

А вот со столом с гостями (кольцевым счётчиком) такой простой трюк не проходит.

То же самое если он крутится в одну сторону и говорит "вон" каждому второму.

Да получается за пять проходов или можно вывести формулу для обоих случаев.
Но как эту формулу вывести не написав нечто вроде того что внизу на доске?

Code: Select all

1, 1+(2*1), 1+(2*2), 1+(2*3), 1+(2*4),.....
1, 1+(4*1), 1+(4*2), 1+(4*3), 1+(4*4), 1+(4*5), ....
1, 1+(8*1), 1+(8*2), 1+(8*3), 1+(8*4), ..... 1+(8*9)
1, 1+(16*1), 1+(16*2), 1+(16*3), 1+(16*4), 1+(16*5), 1+(16*6)
1, 1+(32*1), 1+(32*2), 1+(32*3)
1, 1+(64+1)
1


(2*1), 1+(2*2), 1+(2*3), 1+(2*4),.....
(4*1), 1+(4*2), 1+(4*3), 1+(4*4), 1+(4*5), ....
(8*1), 1+(8*2), 1+(8*3), 1+(8*4), ..... 1+(8*9)
(16*1), 1+(16*2), 1+(16*3), 1+(16*4), 1+(16*5), 1+(16*6)
(32*1), 1+(32*2), 1+(32*3)
(64+1)

Было сказана что задачка из Гугла и решать ее надо у белой доски "в голове" и за пять минут максимум
Так что кто в Гугол пойдет мотайте на ус

[AndreyT]

Возможно, задача немного не такая. За круглым столом сидят 100 гостей. На стол запрыгивает хозяин и, показывая на гостей последовательно по кругу говорит им поочерёдно: "сиди" и "вон". Гость, которому сказали "вон", выходит из-за стола. Какой из гостей останется последним?

Эта задача - Josephus problem - как раз таки очень заезжена в литературе.

[Kirpidonych]

вот тут книжку нашел может кому пригодится
http://www.amazon.com/Cracking-Coding-I ... QSFPWTKPVK" onclick="window.open(this.href);return false;

[assazello]

Сколько прямоугольников можно нарисовать на сетке NxM ? рисовать по линиям сетки, конечно.
Можно еще попросить написать алгоритм, перебирающий все прямоугольники.

Задачку задали в нашей middle school, кстати.

[helg]

Сколько прямоугольников можно нарисовать на сетке NxM ?

Любая пара узлов на сетке взаимно однозначно определяет прямоугольник. А пар всего N*M * (N*M - 1) / 2.

[John Smith]

Сколько прямоугольников можно нарисовать на сетке NxM ?

Любая пара узлов на сетке взаимно однозначно определяет прямоугольник. А пар всего N*M * (N*M - 1) / 2.

Это неверно, рассмотрите случай 2x2

[helg]

Сколько прямоугольников можно нарисовать на сетке NxM ?

Любая пара узлов на сетке взаимно однозначно определяет прямоугольник. А пар всего N*M * (N*M - 1) / 2.

Это неверно, рассмотрите случай 2x2

Точно! Надо, чтобы пара точек не лежала на одной горизонтальной или вертикальной прямой. Да и каждый прямоугольник считается не 2, а 4 раза. Стало быть, N*M * (N-1)*(M-1)/4.

[John Smith]

bingo! какая то нехилая задачка для миддл скулера

[Pantigalt]

Sum(1..N)*Sum(1..M)
(N*(N+1)/2) * (M*(M+1)/2)

[Сабина]

Кстати хозяйке на заметку ...
Иногда бывает ходишь по интервиеш и если несколько неудачных то начинаешь думать что вот де недотягиваю и все такое. А на деле может быть просто какая то мелочь и один человек из 5-ти не проголосовал за вас и все. Ведь если задуматься выбирают чаще одного из толпy ? What are the odds что должны выбрать именно вас?

[Vladimir1440]

750+ интервью за 20+ лет то. И все нормально по жизни.

В одном из наших рекрутинговых агенств 19 моиx разныx резюме.

Кто больше?

[Сабина]

750+ интервью за 20+ лет то. И все нормально по жизни.

В одном из наших рекрутинговых агенств 19 моиx разныx резюме.

Кто больше?

И какой процент из них успешные? Где вам давали офер или хотя бы говорили we chose you ?

[tau]

Одно интервью за последние 15 лет работы.
Кто меньше?

[Sergunka]

Одно интервью за последние 15 лет работы.
Кто меньше?

Ага и два поста на привете Да Вы, батенька, немногословны