Shit on you, shit on her, shit on me in the end

день четвёртый, Google
Сегодня был в Гугле. Скажу я вам. Во-первых, там классно, даже кафель в туалете с разноцветной крошкой. Во-вторых, у меня было три интервью подряд, по часу каждое. Одно - на английском. И все задачи были отнюдь не "перевернуть строку". Отвечал я не очень, но и не так, чтобы уж совсем плохо.

1. Массив целых положительных чисел представляет собой гистограмму. Надо найти вписаный в гистограмму прямоугольник максимальной площади. Решается за O(n) элегантным стеком.

2. Дана длинная строка и короткая, известной длины. Длинную строку можно предварительно обработать. Найти включение короткой строки в длинной. За О(1) хэшем.

3. Написать класс, реализующий сколь угодно большие числа, которые можно только инкрементировать и распечатывать. Связный список.
По ходу дела возник вопрос о средней сложности инкремента двоичного числа с N разрядами. Получил

пришли к выводу, что это О(1).

4. Для данного N определить, сколько нулей в конце N! Потом написать код для этого.
Ответ вот такой:

Ни на один из вопросов я не ответил самостоятельно, везде мне надо было показывать направление, иногда сильно лажался. Наверняка пролетел. Но для меня это было неплохо и я доволен, что съездил. Теперь я люблю Google ещё больше.