программистское

[avva]

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

Comments

[leonid-b.livejournal.com]

Да, про Ломоносова хорошая задачка. пойду-ка я с работы, подумаю.

[avva.livejournal.com]

Думаю, надо начать с телефона, так как-то.

[enemyreader.livejournal.com]

Почему с телефона?

Это скорее аналог бумажной почты и газет.

[avva.livejournal.com]

Чтобы установить критически сложное для понимания свойство мгновенной передачи информации.

[strangest.livejournal.com]

Часть этих задачек (плюс другие) рассмотрена в книге "Как сдвинуть гору Фудзи" Уильяма Паундстоуна. Там и про процесс приема на работу в Майкрософт есть. :)

Раньше лежала в электронном виде на русском языке на lib.aldebaran.ru, но сейчас ее почему-то убрали. Оригинала на английском не искал.

[ex-ex-annut.livejournal.com]

используется стандартная кодировка английского алфавита (a 1 b 2 )
найти английское слово произведения букв которого максимально близко к миллиону

[enemyreader.livejournal.com]

Давно установлено всякими хрустальными шарами и говорящими зеркалами :)

[avva.livejournal.com]

curing.

Мои пять копеек

[raccoon.livejournal.com]

Please write code to answer the following problems. Answers will be scored based on correctness, efficiency, and readability. You may only use C/C++ programming language reference materials.
Please don't use CRT, STL, etc. library functions.

1. Implement the C runtime library function strstr. strstr returns a pointer to the first occurrence of strSearch in string, or NULL if strSearch does not appear in string. If strSearch points to a string of zero length, the function returns string. The search does not include terminating null characters.



const char *strstr(const char *string, const char *strSearch)

{

// Insert your implementation here

}



2. Implement the following function for sorting a linked list of integers in ascending order. The function takes a pointer to the head of the list, and returns a pointer to the head of the sorted list. Your function should use only a constant amount of memory. It's prohibited to change the value of ListNode, instead ListNodes must be rearranged.



struct ListNode

{

int value() { return _value; }

ListNode *pNext;

private:

int _value;

};



ListNode* SortList(ListNode *pHead)

{

// Insert your implementation here

}



3. Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array. You may be able to do this in less than linear time.



int FindSortedArrayRotation(int *array, int arrayLength)

{

// Insert your implementation here

}

[siludin.livejournal.com]

Если можно имена (и вообще все что угодно из /usr/share/dict/words :), то 'tetty' дает ровно миллион.

[leonid-b.livejournal.com]

Сложность не в описании техники, а в концепции так называемой "информации". Эта концепция в восемнадцатом веке... сами понимаете...

[avva.livejournal.com]

Самое близкое из того, что есть в моём файле словаря, хотя tetty, упоминаемого ниже, там нет.

[dimrub.livejournal.com]

У Джоэла тоже интересные статьи были про процесс интервьюирования.

[lezze.livejournal.com]

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

[simonff.livejournal.com]

Извините, тогда уж жаргонное 'titty' окажется впереди.

[gde-moi-17-let.livejournal.com]

В копилку - мои три копейки: задачки с древнего интервью в Интеле.

***
В ряд построены 100 електрических лампочек с пуговкой выключателя on/off.
Изначально все лампочки выключены.
По очереди бегут 100 гномиков.
1-й включает каждую лампочку.
2-й выключает каждую вторую лампочку.
3-й - меняет нажимает н каждый третий выключатель.
...
Что будет когда все 100 гномиков пробегут?

***
В комнате 3 выключенные лампочки: 1л, 2л, 3л.
Снаружи - три выключателя: 1в, 2в, 3в.
Как, выйдя из комнаты один раз, узнать какой
выключатель соответствует какой лампочке?

[avva.livejournal.com]

В каком смысле? :)

[avva.livejournal.com]

Хорошие, да. Помню их :)

[breqwas.livejournal.com]

http://breqwas.homeip.net:8000/ftp/fudzi.rar

[109.livejournal.com]

первый называет checksum, все остальные вычисляют свой цвет как diff.

[109.livejournal.com]

работает с любым количеством гномиков :-)

[109.livejournal.com]

спасутся все, кроме одного (он тоже может, если случайно совпадёт).

[avva.livejournal.com]

А, вот вы о чём. Но всё равно ж придётся со словарём сравнивать, чтобы найти настоящие слова. Нет, не думал об этом. Наверное, есть эффективные алгоритмы, не требующие разложения на множители в общей форме (потому что множество искомых множителей у нас сильно ограничено).

[109.livejournal.com]

решение я только что сказал... :-)

троичная система, каждому цвету своё значение.

checksum = сумме всех шапок.

[besm6.livejournal.com]

По нему не надо восстанавливать всю последовательность. Надо - недостающий элемент. Для этого одного разряда вполне достаточно. Младшего, естественно, AKA остатка от деления на 3.

[109.livejournal.com]

ну йолы палы, ты чё, не понимаешь решение задачи, которую сам задал? я не знаю уж, куда подробнее разжёвывать. rolling over checksum, нужной разрядности. в нашем случае - один троичный разряд. каждый гномик, слыша названную шапку, вычитает её из checksum. для вычисления своей шапки нужно вычесть checksum впереди себя из предыдущей (которая включает твою шапку). дошло теперь?

[109.livejournal.com]

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

[109.livejournal.com]

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

отстаньте от меня с такими примитивными вопросами, ради бога :-)

[109.livejournal.com]

он не запоминает, он апдейтит чексумму когда слышит шапку.

сумма шапок до себя и шапка после никак не помогут вычислить свою шапку.

[besm6.livejournal.com]

У второй задачи условие сформулировано полностью? Тогда "берем картину мироздания и тупо смотрим, что к чему". Ключевое слово - "смотрим".

[gde-moi-17-let.livejournal.com]

На что смотрим? Номера лампочек и выключателей надо поставить в соответствие. Когда вы снаружи, лампочек вам не видно.

[besm6.livejournal.com]

Вот последнего утверждения в задаче не стояло... Потому я и спросил про полноту условия.

[besm6.livejournal.com]

Гм, продолжение допроса с пристрастием. Оговаривается ли в условии:

1. где я сначала нахожусь? (подозреваю, что наивные авторы имели в виду именно это)

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

3. управляет ли каждый выключатель ровной одной лампочкой, причем из находящихся в комнате, и различными ли лампочками управляют выключатели?

[gde-moi-17-let.livejournal.com]

Ага - условия нормальные - как в школьных задачах по физике.
(ну типа, температура не -1000, планета - Земля и т.п.)
В том же ключе:

1. В комнате. Потом вышел. Делал что хотел с выключателями.
Вернулся. Ответил.

2. Нет. (Никого, даже самого наивного интервьюера). Адын, совсем адын.

3. Да, однозначное соответствие выключателей лампочкам есть.
Иначе его не просили бы найти. Никаких наёбок в задаче нет.

[besm6.livejournal.com]

П.1 отчетливо не относится к условиям типа "планета - Земля". Это надо оговаривать. Равно как и ответ на предыдущий вопрос. Два других пункта спрашивались, понятно, по правилу тринадцатого удара.

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

[gde-moi-17-let.livejournal.com]

Я - не интервьюер, вам ничего не должна, и никакого решения не вижу.
Впрочем, мне оно и не нужно - я его знаю.
Мне кажется, вы со мной говорите не подобающе; по-снобски как-то;
я вас не знаю, и никаких основаной к тому вам не давала.
Задачки я кинула авве, полагая что он их знает (что так и есть) и
чтобы напомнить славные старые технионовские дни.
А вас я ни о чём не спрашивала. Смените, пожалуйста, тон.

Re: Мои пять копеек

[(Anonymous)]

Dear Sir,

Did you get an answer to your question?