Как я завалил собеседование в Twitter

http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
  • Перевод
image


До 28 октября я должен был принять решение, буду ли я работать в Amazon по окончанию стажировки. Оставалось совсем немного времени, но мой друг Дэниел убедил меня, что если я попробую попасть в Twitter, то как раз успею пройти все интервью. Я не смог устоять.

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.

Не знаю, как вы, а я обычно сильно нервничаю перед собеседованиями — всегда боюсь, что интервьюер может подумать, что я недостаточно сообразителен. Поэтому в среду к 17:20 на моем опустевшем столе уже лежали 2 остро заточенных карандаша и блокнот, а сам я был в полной боевой готовности… Наступило 17:30, и ничего не произошло. Прождав еще пятнадцать минут, я полез в Google выяснить, правильно ли рассчитал разницу во времени и который час в Калифорнии. Ошибки не было — я отписался на почту Джуди, попросив ее разобраться с ситуацией.

Спустя десять минут раздался звонок из Сан-Франциско. Джуди извинилась за возникшую путаницу и сказала мне, что Джастин может провести со мной интервью прямо сейчас.

Глубокий вздох

«Отлично, я готов!»

Джастин также извинился за ошибку в расписании и сразу перешел к программированию.

Взгляните на следующую картинку:

image

На этой картинке у нас есть стены различной высоты. Картинка представлена массивом целых чисел, где индекс — это точка на оси X, а значение каждого индекса — это высота стены (значение по оси Y). Картинке выше соответствует массив [2,5,1,2,3,4,7,7,6].

Теперь представьте: идет дождь. Сколько воды соберется в «лужах» между стенами?

image

Мы считаем единицей объема воды квадратный блок 1х1. На картинке выше все, что расположено слева от точки 1, выплескивается. Вода справа от точки 7 также прольется. У нас остается лужа между 1 и 6 — таким образом, получившийся объем воды равен 10.


Для самых нетерпеливых
Ссылка на гист с правильным решением задачи, которое подробнее разъясняется в конце поста. Остальные могут спокойно читать дальше — спойлеров не будет.


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

Я вслух произнес: «Что, если мы найдем все локальные максимумы и посчитаем заполненное водой пространство между ними — это сработает?»

«Да, это должно сработать», ответил Джастин.

После такого ответа я решил, что пошел в верном направлении, и закодил свое решение. Следом Джастин попросил меня написать несколько тестов, что я также проделал. Все тесты, о которых мы говорили, вроде бы отработали.

«Будут еще какие-либо вопросы ко мне?», спросил Джастин. «Ну и как я вам?» «Достаточно неплохо, хотя ваше решение делает 2 прохода, но есть другой интересный алгоритм, который делает всего один проход».

Затем мы немного пообщались на тему жизни в Twitter.

И, в тот самый момент, когда я повесил трубку, я вдруг понял: мое решение было неверным.

Возьмем следующие входные данные:

image

Мое решение искало всю воду между локальными максимумами и выглядело следующим образом:

image

Но результатом должна была быть одна «лужа» между двумя высокими башнями:

image

На следующий день я показал эту задачу знакомому аспиранту, занимающемуся теоретическим computer science. После 40 минут размышлений у него также ничего не получилось.

Но сегодня утром я после пробуждения меня осенило — решение оказалось красивым и простым.

Я спрашиваю себя: чему я научился в итоге? На самом деле — немногому. Я слегка расстроен из-за того, что интервьюер не задал мне направляющего вопроса. Я не знаю, почему Джастин сказал мне, что это «должно сработать», когда на самом деле мое решение было неправильным. Знаю, что это должно было вылезти в тестах, которые он просил провести, но поскольку я упустил один важный момент во время разработки алгоритма, то и протестировать его не смог догадаться.

Следующим летом я иду работать в Amazon, что не может меня не радовать, но вопрос «а что, если бы?» по-прежнему не оставляет меня.



Правильное решение: gist.
Посмотреть
/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6}; 
		System.out.println(calculateVolume(myIntArray));
	}
	
	public static int calculateVolume(int[] land) {
		
		int leftMax = 0;
		int rightMax = 0;
		int left = 0;
		int right = land.length - 1;
		int volume = 0;
		
		while(left < right) {
			if(land[left] > leftMax) {
				leftMax = land[left];
			}
			if(land[right] > rightMax) {
				rightMax = land[right];
			}
			if(leftMax >= rightMax) {
				volume += rightMax - land[right];
				right--;
			} else {
				volume += leftMax - land[left];
				left++;
			}
		}
		return volume;
	}
}

Логика следующая:

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

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

Решение в приведенном гисте работает в один проход, избегая поиска максимума проходом двух «указателей» навстречу друг другу с противоположных концов массива. Если наибольшее значение, найденное слева от левого указателя меньше, чем наибольшее значение найденное справа от правого указателя, то мы сдвигаем левый указатель на один индекс вправо. В противном случае, двигаем правый указатель на один индекс влево. Повторяем до тех пор, пока два указателя не пересекутся. (На словах звучит запутанно, код на самом деле очень простой)

Оригинал поста: Q & What?.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 313
  • +34
    Красивая задача
    • +137
      Но имхо абсолютно бестолковая в определении скила программера. Такое гденить на олимпиаде или соревновании по программированию, не очень понимаю уместность этой задачи по отношению к твиттеру.
      • –30
        Надо уметь мыслить нестандартно и уметь искать красивые и изящные решения, а не только сортировать разными методами.
        Ведь красивое решение задачи не только приносит удовольствие (что уже само по себе немаловажно для разработчика), но и потом упрощает поддержку кода и уменьшает количество багов как если бы это просто набыдлокодить как попало.
        • +23
          Красивые решения зачастую специфичны и требуют понимания. Т.е можно конечно сделать красиво, но скорее всего программист который первый раз видит решение, будет некоторое время разбирать как же это решение работает. Я бы не сказал что красивое решение обязательно упрощает поддержку кода и уменьшает количество возможных багов. Можно накодить хорошо но стандартно, без красивого решения. К тому же красивое решение в какой то момент времени может прекратить работать, когда надо будет чуть чуть подправить логику работы например.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +2
              Поддерживаю, тоже не в восторге от таких задачек, но когда надо «лампочка загорается»
            • +8
              Красота вещь субъективная, кто-то считает красотой обмен значений двух переменных без использования третьей.
              • 0
                Особенно это впечатляет, когда они вещественные. Или указатели.
                Хотя есть же и xor-list…
                • 0
                  Для вещественных (во всяком случае для float) должно же прокатить побитовое преобразование в целое, а дальше уже xor и обратно?
                  • +1
                    Смущает, что в промежутке число может иметь некорректное значение. И, к сожалению, компилятор не оценит этой изобретательности, ему проще когда обмен идёт через переменную. Он её соптимизирует до регистра. А на
                    *(long long *)&a^=*(long long *)&b; точно придётся отводить место на стеке.
                • +3
                  Все очень сильно зависит от языка, в Lua обмен значений делается так: x, y = y, x.
                  И обмен через третью переменную, наоборот, выглядит странно.
                  • +1
                    Я думаю все поняли, что я не о подобных языках.
                • +18
                  В реальной работе за красивые решения оторвут ноги. Код должен быть простым и понятным, потому что его еще нужно поддерживать куче народу.
                  • +5
                    Даёшь n2 и n3 для любых задач, только пузырек только хардкор. Человек в любом случае должен уметь понимать сложность алгоритма и уметь ее понижать. Иначе никакого масштабирования не получится.
                    В тёмный век предела возможностей кремния нет возможности на порядок производительность каждые 5 лет
                    • 0
                      И как это связано с тезисом mynameco?
                    • 0
                      Верно. Под красотой я как раз подразумеваю понятность и лёгкость в поддержке, а не цветочки и галочки.
                  • +5
                    какого скила? это задача на интеллект, не можете справиться, значит скорее всего будете тупить и в другом случаи даже если дело касается только кода. не можете решить простую задачу на интеллект, значит и в спецификация jvm, css, html, xml разобраться на 100% не сможете (потому что это сложно и требует наличие интеллекта), и автором какой-нибудь новой технологии вы скорее всего тоже не будете. Вот дайте эту задачу тем кто сам webkit пишет, или что-то другое по настоящему сложное (а не просто конект к базе — результаты на страничку) — он с такой задачей наверняка справиться.
                    не решили — не расстраивайтесь, для вас и так достаточно работы, просто в твиттере она посложнее будет и «просто знаний» что как надо делать там не хватит, ну или не всегда хватит
                    • 0
                      … но положа руку на ногу — в подавляющей большинстве работы можно достигать успешного результата без 100% понимания. Это печально с точки зрения самосовершенствования, перфекционизма и много чего ещё, но это факт.
                    • 0
                      Почему вы считаете эту задачу олимпиадной? Вполне приличная задача на «закодировать без ошибок».
                      • +4
                        Потому что такие задачи действительно бывают на олимпиадах районного-городского-областного уровней.
                      • +6
                        Реалии таковы, что именно такие задачи задают на собеседованиях. И если честно, на них пройти шанс выше, чем на задачах проектирования. Эта задача хороша, потому что она не требует от Вас умения писать что-то «олимпиадное», просто логика, тесты и умение кодировать. На работе очень много кода будет строиться из таких маленьких задачек.

                        По своему опыту собеседований, люди не отвечают на серьезные вопросы дизайна. Да и после этих вопросов мне очень сложно оценить кандидата. Я трачу все собеседование на один вопрос. И это может быть очень плохо для кандидата, так как он может затупить и тогда все, второго шанса нет. С маленькими задачами лучше, так как их можно сделать 2-3 за интервью. (Когда я проходил в Фейсбук я успевал сделать 3). И если у кандидата возникли проблемы с одной задачей, вторая может его реабилитировать. Плюс, если кандидат не может написать решение в 30-50 строк, тогда простите, почему я должен поверить, что он способен написать большую работающую систему? Если человек не придумал решение, тогда почему я должен поверить, что он может их придумывать? В Твиттере решаются сложные задачи на всех уровнях. Говорить, что какая то задача плохо отражает скилл… Просто нужно решать их и все.

                        Эти задачи не идеальны, но компании уровня Твиттера просто нет времени проводить собеседование по 10 часов с каждым. Ведь каждое интервью — это время одного инженера, которое стоит денег. Однако, по-моему, спрашивать про фишки языка — вот это глупость, или про то, кто такой Дейкстра и что он сделал для мира программирования. Или что такое Mock тестирование? (Это вопросы реальные и мне их задавали). Эти вопросы вообще бесполезны, так как если вы напишете решение задачи, предложенной выше с верной асимптотикой и проходящее все тесты, тогда, с большое долей вероятности, вы способны освоить технологии быстро и качественно.
                        • –1
                          А почему тогда потом работники на компьютере код пишут? Пусть дальше на бумажках рисуют! Ведь именно этот скилл у них на собеседовании проверяется. Эта дурость уже полностью зафейлена, можно надрочиться на подобных задачках на ресурсах типа глассдора, при этом абсолютно не обязательно быть специалистом, достаточно просто эту хрень решать. Тем более что в 90% случаев эти задачки из одного пула берутся.
                          • +2
                            Пока практика показывает, что этот метод работают. У нас работают крутые инженеры и фейлов не много. Метод не идеален, однако лучше нет. Почему Вы думаете, что что-то изменится, если будете писать на компе? Он Вам решение нашепчет? Время интервью хотите экономить? Так Вам же хорошо, если дольше будете писать одну задачу. Вопросы не нравятся? Что тогда спрашивать? Как реализовать систему? Так это тоже спрашивают. Если откроете книгу «Cracking coding interview», то увидите, что про это есть глава. Только кандидатам хуже от этих вопросов — они намного сложнее. Спрашивать про язык? А зачем? Допустим Вы спец по с++. «Надрочились», так сказать. А завтра надо будет на python писать, и вы скажете — я не умею… Не хорошо. Может быть спрашивать про технологии? Про SDK? Про инструменты? Ну совсем странно. Хм… А можно ли спрашивать что-то не требующее специальных знаний, чтобы кандидат показал, что он может учиться, что у него есть соображалка? Ах да, мы это и спрашиваем.

                            Я провел много интервью, и почему-то «надрочившихся» не видел. Зато видел, как люди думают, умеют ли писать код, а не жать «Generate method». Свои задачи я придумываю сам. Мои коллеги тоже. Но проблема в том, что я спрашивал «из пула» — не ответили…
                            • 0
                              Я действительно не могу придумать другого метода. Но и в этом вижу недостатки.

                              Я принципиально почти никогда не готовлюсь к собеседованиям (как и к экзаменам), считая что подготовка исказит результаты.

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

                              И вот ещё, всегда было интересно, почему на собеседованиях спрашивают задачи такого рода? Что проверяется?
                              1) Наличие мозга? Ну тогда надо давать задачи, к которым невозможно подготовиться, а не какие-то общеизвестные алгоритмы.
                              2) Знание базовых алгоритмов (dfs/bfs/dijkstra/беллман-форд и т.д.)? Зачем? Ведь в реальной работе они хоть и встречаются — но не часто. Знать их ради тех редких случаев, когда они понадобятся?

                              Интуитивно я согласен, по какой-то причине работать с людьми, знающими эти вещи приятнее. Но вот обосновать я это не могу.

                              Ну и тут извечный спор о полезности спортивного программирования для работы. Получается что вопросы на собеседовании (речь идёт не о задаче из данного поста, конечно, она тривиальна) требуют уровня СП, но на самой работе делаешь другое (хотя и не менее интересное). В процессе работы учишься, получаешь опыт, но при этом он не увеличивает твои шансы пройти новое собеседование. Так что же человек должен днём повышать свой профессиональный скилл, а вечерами заниматься СП, чтобы уметь проходить через всё более сложные собеседования? Двойная жизнь какая-то получается. А если мне спортивное программирование уже надоело, т.к. на работе задачи интереснее? Или же СП всё-таки помогает достигать лучших результатов в работе, даже если напрямую и не связан с ней? Как вот это всё измерить?
                              • +1
                                Вообще давать задачу на Топологическую сортировку не хорошо — я согласен. То есть с первым пунктом я полностью согласен. И частично не согласен со вторым. Понимаете, когда я, собеседуя человека, на вопрос о сложности алгоритма получаю ответ, что алгоритм не сложный… Мне кажется это сразу отказ! Это основа. Если вы хотите работать в Google или компании такого рода — это нужно знать. Вопросов почему здесь быть не может. Потому что это Google. DFS, BFS — тоже. Так как просто понимать что такое граф — необходимо. Значит базовую работу с ними нужно уметь делать. DFS помогает в понимании рекурсии, что очень важно. BFS в знании очереди, то есть базовой структуры данных, которые тоже знать необходимо. А вот алгоритм Дейкстры, Форда-Беллмана, потоки и т.п. спрашивать на интервью не нужно — это и правда спец знания. Хотя… Если вы допустим хотите работать с графами (ну например в ФБ в соц. графе) наверное спросить про алгоритмы путей можно.

                                Готовиться к собеседованию можно, но даже если вы видели задачу, то каков шанс, что вы мне ее объясните и напишите без ошибок? Я спрашивал задачу, которая была во многих местах для эксперимента. Мне говорили ответ. Но когда я слегка ее модифицировал (просто добавил размерность) — почти никто не мог ответить. Те, кто жалуются на вопросы, просто не понимают альтернативы. Проектировать сложнее, чем решать. На вопросы дизайна ответить сложнее, чем накодить задачу.

                                Теперь про СП.
                                Я все еще участвую в контестах, так как это помогает мне думать быстрее. Я стал намного продуктивнее в разработке (не кодировании, а именно в разработке — то есть дизайн, проектирование, организация и т.д.), когда снова стал решать. Может быть это только у меня так. Не знаю.

                                Но еще небольшой момент. У меня много знакомых программистов олимпиадников. И я, если честно, затрудняюсь сказать, кто из них не устроился работать в крутую компанию. Кто не захотел уехать — те в Яндексе или в самых лучших местах в родном городе. И все они работают хорошо — то есть получают повышения, интересные проекты. Я ни в коем случае не говорю, что СП — это единственное. У меня также много знакомых, которые прекрасно работают, не занимаясь СП. Это ответ на ваши вопросы. Как измерить? Я просто вижу живые примеры.

                                • –1
                                  Понимаете, когда я, собеседуя человека, на вопрос о сложности алгоритма получаю ответ, что алгоритм не сложный… Мне кажется это сразу отказ!

                                  А дело всего-то в том, что в тех книжках, по которым человек учился, это называлось worst time, или как-нибудь ещё… Ну ничего, повезёт другому работодателю.
                                  • –1
                                    «Algorithm Complexity» или «Big-O notation» — то что я знаю и использую и меня всегда понимали на работе, на интервью, на формах и т.д. С «Worst time» я бы не согласился. К тому же я сделал скидку на волнение кандидата и свой кривой английский, и переформулировал вопрос несколько раз. Другому работодателю не повезет.
                                    • 0
                                      К тому же я сделал скидку на волнение кандидата и свой кривой английский, и переформулировал вопрос несколько раз.

                                      Разве это называется «сразу отказ»?
                                      Интересно, что бы сделали с кандидатом, который не помнит, какой из многочисленных алгоритмов сортировки называется сортировкой пузырьком. Или какой из обходов графа принято называть обходом в глубину, а какой — в ширину (т.е. какая компонента динамики обхода используется в названии — быстрая или медленная). Мне это так и не удалось запомнить :(
                                      • 0
                                        Я уже говорил выше, что я не люблю терминологию в интервью. Но не знание, что такое сложность алгоритма — это сразу отказ (не термина сложность, а сути).

                                        А что такое быстрая или медленная компонента динамики обхода? Вообще обход в глубину и в ширину сами как бы в названии говорят как они работают. Если вы знаете как они работают, то перепутать их сложно.

                                        Вообще по-моему вы сейчас больше придираетесь, так как ясно, что интервью гибкий процесс со множеством подсказок. Я очень рад, если кандидат начинает диалог — например, «хм… я знаю обходы графа, но совершенно не помню термины. Обход с использованием очереди, когда мы проходим граф слой за слоем, как он называется?» Тогда я отвечу: «В ширину!» и даже не подумаю, что это минус. А если вопрос будет: «Граф? А что это?». Тут сложнее что-то ответить.
                                        • 0
                                          Быстрая или медленная компонента (в моём понимании, тут я опять не знаю терминов) — это так: мы быстро и много раз обходим граф «в ширину» и при этом медленно продвигаемся «в глубину». Или наоборот — часто проходим его «в глубину» до конца, медленно заметая его «в ширину». Перепутать очень легко, тем более, что вариантов названия всего два, и ни у одного нет логического преимущества перед другим.
                                          А уж запомнить аббревиатуры DFS и BFS может только тот, кто узнал их до того, как начал использовать эти алгоритмы. Потому что лучше тратить ресурсы на изучение новых алгоритмов, чем выяснять и запоминать, что «мы говорим прозой».
                                          • 0
                                            Хм… В каждом алгоритме мы пройдем все ребра один раз. Сложность одинаковая. O(E). Много раз мы ничего не проходим. Везде все тоже самое. Перепутать два варианта с учетом названий сложно. Но это мое субъективное мнение. Я поверю, что возможно это сложно.

                                            Вообще можно без терминологии жить и разрабатывать что-то с помощью чего-то при помощи какого-то там. Но без терминов вас не поймут. Неужели так сложно выучив и поняв новый алгоритм еще заодно запомнить как он называется? В математике вы учили теоремы с названиями. Тоже зачем? Ну чтобы вас понимали и понимали о чем вы говорите. Почему я должен поверить на интервью, что кандидат знает алгоритм, но не знает название? Особенно таких стандарных вещей, как обходы графов. Это, к сожалению, уже проблемы кандидата. И то, что какой-то компании повезет — может быть, но я лучше перестрахуюсь и не поверю.
                                            • 0
                                              Значит, надо запомнить, что с графами — не так, как с матрицами. Когда мы обходим матрицу «по строчкам», то просматриваем первую строчку целиком, потом вторую… Когда обходим граф «в ширину» — просматриваем первый уровень глубины, потом второй… Если не встретится ещё какой-нибудь структуры, у которой будет своя логика названий, то запомнить, наверное, удастся.

                                              Неужели так сложно выучив и поняв новый алгоритм еще заодно запомнить как он называется?

                                              Если название узнал лет через 10 после того, как стал работать с этим алгоритмом, то может оказаться сложно их связать. В конце концов, обходы графов и поиск кратчайшего пути действительно очевидны. А название… можно выучить, как новое иностранное слово, когда действительно придётся пользоваться им в разговорах.
                                              • 0
                                                Проще всего — представить, как алгоритмы обойдут полный граф (т.е. граф, где между любыми двумя вершинами есть ребро).

                                                Обход в ширину сделает из этого графа звезду, поскольку дойдет до всех вершин из первой. А обход в глубину пройдет все вершины последовательно, сделав из графа длинную цепочку. Лично мне этот способ запоминания казался всегда наглядным.
                        • 0
                          Такое гденить на олимпиаде или соревновании по программированию,

                          Скажите, такие задачи разве дают на олимпиадах? Я плохой программист и не олимпиадник, но алгоритм решение этой задачи по принципу описанному в конце пришел моментально. Даже не особо понял что он там напридумывал с локальными максимумами.
                          • 0
                            Подтверждаю, дают на олимпиаде подобное, даже на областных.
                            • –1
                              Поправка: не выше областных.
                          • 0
                            А еще это называется Water filling algorithm. Но зачем такое знать человеку, который в Твитере работать собрался?
                        • +2
                          Почему-то сразу вспомнилось решение для Convex Hull.
                          • 0
                            Это, пожалуй, самое интересное. Получается, что выпуклую оболочку можно искать без стека вершин, двигаясь от крайних точек навстречу друг другу? Не знал.
                            • 0
                              Нет, так ее искать нельзя.
                              Но существует алгоритм Грехема, работающий за время O(NK), где K — число вершин в оболочке. Этот алгоритм не требует стека вершин.
                        • +71
                          Задачка интересная.
                          Я вот только одного не понимаю — каким образом навык быстрого решения подобных задач хоть как-то характеризует разработчика?
                          Ну ок, ладно, можно как-то оценить, как человек ищет решение. Каким образом это характеризует разработчика?
                          Как это расскажет, пишет ли он читаемый код, правильно ли выделяет уровни абстракции, хорошо ли понимает чужой код, точно ли декомпозирует задачи?
                          • –32
                            Они ищут лучших из лучших.
                            • +51
                              Какой скучный ответ.
                              • –4
                                Суть вашего комментария с его содержимым несомненно сильнее связана чем ваше замечание о моём. Более того, мой комментарий отражает моё мнение о статье, ваш же комментарий — просто оффтоп.

                                Рискую опять быть заминусованым, но ничего, мне не в первой. Буду продолжать отстаивать своё мнение.
                                • +6
                                  На самом деле не правильно думаете. forgotten правильные вещи говорит.

                                  Главное в разработчике это то как он пишет код и взаимодействует с командой, да хотя бы банально умеет ли пользоваться гитом, у человека надо узнать тип его мышления и то как этот тип может доперать до решения задачи. А эту задачка реально уровня школьника для олимпиад, если надр<...>ся на на них будешь фигачить пачками, а когда тебе дадут задачу сделать какой-нибудь заумный сервис, голова тупо не сможет осилить, не то что реализовать, так как для этого нужно как раз то что я написал вначале: культура кода, умение работать в команде.

                                  Мораль такова, умение щелкать задачки по олимпиаде еще не означает, что ты крутой разработчик.

                                  Мне кажется, что интервьюеру было лень разбираться, таких много. У обязанности такие, начальство выбирает нескольких девелоперов на собеседование, те ставят оценку, этому было влом.
                                  • +3
                                    Знание гита — не критично, и гиту можно обучить в будущем.
                                    Эта же задача как раз была на тип мышления, в частности обратить внимание на то, что просто на локальных максимумах код будет работать неправильно. Кроме того, автор сделал ошибку, спрашивая Джастина будет ли работать или нет, да еще и обвиняет в статье, что тот сказал будет. Задача была как раз на то, чтобы автор заметил что работать не будет. Ну и кроме того, отсылает то задачу он сырцом. По нему я думаю можно определить спагетти код это или нет.
                                    Я считаю такую задачу оправданной в качестве задачи для собеседования. Только мне кажется им надо было подготовить все таки несколько задач, потому что по одной сфейленой задаче сложно оценить человека.
                              • +47
                                Человек, решающий такую задачу, вовсе не «лучший из лучших», а хороший олимпиадник.
                                Он может совершенно легко писать жутчайший спагетти-код.

                                И, кстати, далеко не факт, что «лучшие из лучших» захотят работать на фирму, чья единственная цель состоит в увеличении энтропии Вселенной.
                                • +4
                                  Вы наивно полагаете, что это олимпиадное задание — ключевое. Однако оно раскрывает только часть знаний будущего сотрудника. На этом этапе отсеиваются все со средним интеллектом. Обучить человека писать чистый код гораздо проще, чем научить придумывать хорошие алгоритмы.
                                  • +20
                                    Вы наивно полагаете, что олимпиадное задание способно отсеять человека со средним интеллектом.
                                    Можно подумать, высокий интеллект означает умение решать олимпиадные задачи.

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

                                    Это просто разные вещи.
                                    • 0
                                      Вы сравниваете разные вещи. Прыжки со скакалкой связаны с занятием штангой никак не связаны, кроме того, что это оба занятия спортом.

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

                                      Это совсем не разные вещи.
                                      • +3
                                        Понимаете, это же вопрос мнений.

                                        Мой опыт подсказывает обратное.
                                        Я даже не совсем понимаю где здесь «нестандартное» мышление. Дана задача, даже чем-то похожая на реальность (вода, стены). Её надо решать. В чём нестандартность?..
                                        • +4
                                          <sarcasm>Нестандартность в том, что нужно посчитать объем по плоской картинке, да еще без учета поверхностного натяжения.</sarcasm>
                                          • +1
                                            Может быть, правильным решением было напечатать 0?
                                            • 0
                                              Кстати да!!! Я тоже об этом подумал.
                                      • 0
                                        Пример со скакалкой и атлетом не в тему.
                                        Вполне может, более того, часто, скакалка одно из необходимых упражнений.
                                        Вы давно на скакалке прыгали? Попробуйте хотя б минут 10 поскакать.
                                        Первая же ссылка из гугла про скакалку
                                        • 0
                                          Вы придираетесь к примеру так, словно он только и удерживает исходный тезис. Ну давайте наоборот, пусть у нас будет девушка, которая занимается художественной гимнастикой. Как у неё со штангой?..
                                          • 0
                                            Простите, просто я практически из-под скакалки был, когда писал комментарий.
                                            По сути примера вопросов нет, тезисы ясны, а придрался я к конкретике.
                                        • +4
                                          Вас не спрашивают олимпиадные задачи! Почитайте задачи с финала Mail.Ru, или с opencup.ru. Вот это олимпиадные задачи. Там надо тренироваться, знать алгоритмы, оценивать время работы, знать хаки языка, быстро придумывать, строить из заготовок и многое другое.

                                          Эта задача не сложная. Я не полагаю, я знаю, что вас спросят не одну это задачу, а 3-4. И они в сумме покажут много чего. Знание гита, с++ или предыдущий опыт мне ничего не скажут. Я не работал с Вами, я не буду в шоке от того, как вы круто манипулируете клавиатурой со скоростью набора 200 символов в минуту. Я скажу — этот кандидат решил поставленную задачу, задал верные вопросы, знает как оценивать сложность решения и пишет код умно (то есть не сажает тупых ошибок, которые потом не найти).

                                          Я не занимаюсь штангой, но перед каждым занятием Muay Thai я должен прыгать на скакалке. Кстати видел как разминаются штангисты на днях :) догадаетесь?
                                          • –2
                                            Опять штанга! А наоборот, девочки с секции худ. гимнастики штангой разминаются что ли? :)

                                            Не, ради бога, каждый пытается измерять интеллект своим способом. Можно такими задачами. А можно тестами Айзенка, дело хозяйское.
                                      • +2
                                        О, вам тоже не нравится Твиттер? :)
                                        • –2
                                          Ви хотите об этом поговорить?
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Вот там классное показано собеседование.
                                      • +2
                                        Не смог удержаться:
                                      • –2
                                        Да впринципе никак, таким компаниям это вообще не надо, для них главное умение нестандартно мыслить :)
                                        • +54
                                          Нестандартно мыслить? Главное для разработчика в Твиттере? А зачем?
                                          • –1
                                            Это просто идеология компании такая. Они к разработчикам относятся, как к ключевым людям в компании. Они ждут от разработчиков идей, которые помогут развивать продукт и бизнес компании. Делать то, что раньше никто не делал. Это не та компания, где разработчик приходит на работу, а у него на столе талмуд от Product Manager с подробным описанием следующей фичи, а разработчику надо только аккуратно закодить, то что требуется. Это просто разные подходы к должности.
                                            • +2
                                              Тем не менее, это не ответ на вопрос «зачем».
                                              • +1
                                                Почему это не ответ? Если ты хочешь чтобы твоя компания выигрывала у конкурентов, тебе надо делать то, что никто больше не делает, а для этого тебе нужны люди, которые мыслят не стандартно и умют эти мысли вополщать в дело.
                                                • 0
                                                  Безусловно, нужны люди, которые способны мыслить нестандартно и абстрактно. Но для реализации этих идей отлично подходят хорошие исполнители: им дали задачу, они сделали качественное решение. Как-то по-другому думать при этом вовсе не нужно.
                                                  • +3
                                                    В твиттере считают, что реализовывать идею лучше доверить автору этой идеи. В этом если подумать есть смысл. Иногда реализация идеи важнее самой идеи и в процессе реализации могут возникать очень сложные проблемы требующие опять же не стандартных подходов. Если отдавать такую реализацию людям которые умеют только кодить по шаблонам программирования и код лесенкой оформлять, то лучше даже и не браться. Программирование, как известно это не стрижка газонов, и если ты хочешь толкать индустрию и возможности железа туда где еще никто не был, то мелочей которые можно доверить кому-то другому почти не остается.
                                                  • +1
                                                    Не так: тебе нужны и люди, которые мыслят нестандартно, и люди, которые умеют эти мысли воплощать в дело. Очевидно, в компаниях чуть более, чем из одного человека, это должны быть разные люди; притом первым не обязательно уметь программировать, а вторым решать задачки на скорость. Весь опыт человечества как бы подсказывает нам, что разделение труда в этом месте рулит; непонятно, зачем софтверные компании регулярно на эти грабли наступают — в условиях кадрового голода, ага — и притом в результате нанимают каких-то невнятных индусов.
                                                    • +2
                                                      Не знаю как насчет опыта всего человечества, но мой личный опыт мне говорит, что чем меньше людей которые не умеют программировать и пишут хорошие алгоритмы трогают код, тем лучше он в результате оказывается.
                                                      • +2
                                                        Я ничего не понял.
                                                        • 0
                                                          Ок. Поясняю. Твиттер нанимает программиста. Ему дают задачку на программирование. Задачка хорошая. Красивая. Решение предлагается не правильное. Человек не нанимается. Что не так? Нет у твиттера разделения труда на классы программистов. Все должны мочь делать все.
                                                          • 0
                                                            Ага. А зачем?
                                                            • 0
                                                              Чтобы не тратить время и силы на перевод с языка алгоритмиста на язык кодера? И сохранить возможность алгоритмисту разобраться, правильно ли кодер воплотил его идеи.
                                                              • +2
                                                                Пара «алгоритмист с неплохим навыком кодирования» и «кодер с неплохим пониманием алгоритмов», очевидно, гораздо сильнее пары посредственных кодероалгоритмистов. Это ж типичный маговоин выходит.
                                                                • +2
                                                                  А как насчет «отличный алгоритмист и отличный кодер» в одном флаконе? Я лично знаю таких людей и производительность одного (!) такого человека не возможно сравнить с командой из 50 средних прогаммистов. Потому, что то что напишут они, команда из 50 обычных разработчиков не напишет никогда.
                                                                  • +4
                                                                    50? А что так мало?
                                                                    • 0
                                                                      Напишите сколько Вас устроит :)
                                                                    • +1
                                                                      «Проблема в том, что супер-суперпрограммисты тоже иногда пишут код» :D
                                                              • 0
                                                                Потому что программировать этот человек, может быть, умеет, а вот алгоритм придумать не может. Так что он не попадает в «чем меньше людей, которые...» по обоим признакам — и его надо брать. Даже два раза :)
                                                              • 0
                                                                Я тоже. С терминами «умеют программировать» и «пишут хорошие алгоритмы» что-то случилось. Либо они обозначают одно и то же — и тогда получаем противоречие, либо «пишут» надо заменить на «разрабатывают» — и получаем разделение труда, противоречащее предыдущим комментариям.
                                                • +1
                                                  Видится мне, что одного без другого не бывает.
                                                  • +17
                                                    Бывает, знаю вагон примеров. Если уж на то пошло, то способность человека нестандартно мыслить в стрессовой ситуации вообще абсолютно ничегошеньки не имеет общего со способностью нестандартно мыслить в рабочей ситуации.
                                                    • 0
                                                      Ну почему все сразу негативно относятся к такому виду собеседования?

                                                      Лично я тоже даю на собеседованиях такие задачи, но я смотрю на другое.
                                                      Мне важны следующие параметры в порядке приоритета:

                                                      1) Решена ли задача (задача несложная, решить ее как угодно можно за 5 минут)
                                                      Если задача не решена — разговаривать просто не о чем. Лучше решение за O(N^2), чем вообще никакого.
                                                      2) Безопасность решения (зависит от сферы применения: thread safe, race condition etc) Частично вложено в п. 1
                                                      3) Читабельность/гибкость
                                                      4) Оптимальность
                                                      5) Элегантность
                                                      etc

                                                      Этот чел предложил неправильное решение (это ОК; кто не ошибается — тот ничего не делает), но он не смог протестировать свое решение и отдал решение на проверку собеседователю (фактически он отдал нерабочий код в продакшен). Вы же в голову к человеку не залезете? А если он так будет подходить к коду, который потом попадет в реальный продакшен? Лучше лишний раз подстраховаться и не взять хорошего разраба, чем взять плохого.
                                                      • +3
                                                        Ну а мне в первую очередь важно, как человек умеет работать с абстракциями, насколько он хорошо себе их представляет, насколько он может читать код и насколько он понимает, как писать читаемый код самому. Кажется, ни один из этих навыков предложенное задание не тестирует.
                                                        • +1
                                                          Собеседователь плохо отревьюил решение.
                                                          Не протестированное решение поехало в продакшн.
                                                          А весь workflow выглядит так: сам придумал, сам написал, сам протестировал, сам закомитил, сам выкатил.
                                                          • 0
                                                            Мне кажется, что нельзя конструктивно обсуждать это конкретное собеседование.
                                                            Мы знам версию только одной стороны и она может быть сильно искажена.
                                                            Просто весь вайн начался на тему: «Вот опять олимпиадные задачи на интервью»

                                                            ИМХО такой способ проверки не так плох, как кажется. Просто надо его правильно использовать. Именно об этом я написал выше.

                                                            Опять же автор не знает, на чем именно он завалился. Возможно интервьюер уже сказал себе НЕТ на раннем этапе — просто из вежливости дослушал ну или что-то в этом роде. Ну или сомневался или все что угодно.
                                                          • +4
                                                            Ещё проблема (для меня) — в стрессовых ситуациях. Не раз бывало, что на собеседовании задача не решена, или решена совсем плохо — по пути домой в голову приходит отличное решение. Но уже увы.
                                                      • +1
                                                        Мне кажется, что провалом было не неверное перво решение, а то, что не было тестов, которые бы значительно отличались от первого. Не было продумано «а в каких ещё условиях может работать этот код».
                                                        • 0
                                                          Автор оригнального поста является еще студентом и собеседовался на позицию стажёра. Очевидно, что опыта промышленной разработки ПО скорее всего у него очень мало, потому имеет смысл посмотреть как человек решает такие задачки.
                                                          • +1
                                                            Я тоже противник подобных «олимпиадных» задач на собеседованиях — действительно, они не выявляют наличие или отсутствие скиллов хорошего разработчика.

                                                            Однако мне кажется на данный вопрос нужно взглянуть с другой стороны: а почему Twitter задаёт такие задачи? Может быть, они ищут не очередного фронт-ендщика, а кого-то другого. Может быть, кандидат будет работать в области, где нужно решать по какому алгоритму распределять пользователей по серверам БД, опираясь на специфику нагрузки именно на twitter.com. И при их объёмах, разница во времени обработки запроса в жалкие 10 мс — критична в плане нагрузки на CPU. Среднестатистический веб-разработчик, имеющий опыт работы с кучей систем контроля версий, умеющий верстать с закрытыми глазами, имеющий опыт построения сложных enterprise-систем, гуру ООП и декомпозиции — не выжмет эти 10 мс. «Олимпиадник» — возможно (хотя бы, сэкономив на кол-ве вызовов функций во время работы данного алгоритма, игнорируя SRP, абстракции и превратив код в трудновоспринимаемую лапшу).

                                                            А может быть они и просто выкаблучиваются на ровном месте, т.к. поток собеседований бесконечен и тратить по 2 часа на очередного кандидата слишком неэффективно :))
                                                            • 0
                                                              Они могут себе такое позволить, обычно такие задачки идут на потоковые вакансии, на которые можно брать вообще любого и он справится, но так неспортивно, поэтому устравается этот бег в мешках, чтобы отсеять 90% кандидатов. С тем же успехом можно было выбирать случайно из кандидатов человека и нанимать.

                                                              А вот когда целевая вакансия на конкретного специалиста, тут начинаются уже настоящие собеседования, на правильные темы с правильной оценкой.
                                                          • +5
                                                            Может я что-то упустил, но на какую вакансию автор оригинального поста устраивался в Twitter? Так как задачка, скажем так, специфическая.
                                                            • +1
                                                              На архитектора зданий!
                                                              • –1
                                                                Или на проектировщика ливневой канализации?
                                                            • –21
                                                              «Следом Джастин попросил меня написать несколько тестов»
                                                              Что за нелепые тесты вы написали? Если бы вы нормально написали тесты, то сразу бы поняли свою ошибку. Тест как на последней картинке как раз бы и не прошел. Только из-за этого я бы вас и не взял на работу, а то что ошиблись — бывает.
                                                              • +6
                                                                Когда тесты пишутся после реализации алгоритма, такое часто бывает.
                                                                • +10
                                                                  Это перевод и автор топика, в общем-то, ни при чем. Но полностью согласен с Вашим недоумением, контртест для решения с локальными минимумами придумывается на раз.
                                                                  • +9
                                                                    Вряд ли что-нибудь изменилось, если бы переводчик написал тесты :)

                                                                    PS опять не обновил комменты…
                                                                  • +4
                                                                    Я немного не понял второго решение, разве оно правильно сработает на массиве [2,5,3,3,7,2,7,6], т.е. когда у нас 2 лужы…

                                                                    Upd. это оказывается второй комментарий на gist :)
                                                                    • 0
                                                                      Суть остается той же, надо просто запоминать когда правая граница стала больше или равной правой границе — записать объем воды и дальше считать правую границу новой левой.
                                                                    • +1
                                                                      Есть ощущение, что ваше решение не будет работать в случае, если в середине массива есть «высокая стена», а крайние «башенки» имеют не одинаковую высоту.
                                                                      • 0
                                                                        Если он находит предварительно максимум, то это уже не один проход.
                                                                        Мне кажется, нужно идти одновременно с двух концов и корректировать объём по мере прохода.
                                                                        • +72
                                                                          Вот из-за таких вопросов на собеседовании и понижается самооценка. Ты можешь писать код, который работает и даже неплохо работает, ты будешь хотеть устроиться на работу, где хотят от тебя то же самое что ты и делал перед этим, но обязательно кто-то должен спросить «как спуститься с квадратного люка имея лишь Х метров круглого и какой из них догорит быстрее?». Потом после заваленного интервью посмотришь форумы, где сотни людей спорят как это лучше решить — через индексы Миклухо-МакКлая или Неопределенный Бульбулятор Фримана и ощущаешь себя таким ничтожеством — потому что не только не знаешь все эти методы, но даже не понимаешь где и кому все эти навыки могут пригодиться.
                                                                          • –15
                                                                            Ну почему. Задача прежде всего показала невнимательное отношение человека к решению.
                                                                            • +3
                                                                              Или поведение в стрессовой ситуации. Тут вобще сколько людей, столько будет и мнений что она показала. Например, если т.н. «правильный» вариант является официальным ответом Twitter'а, то он тоже показывает невнимательное отношение к решению, только с другой стороны.
                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                              • +2
                                                                                Как спуститься за один проход в колодец с квадратной дыркой с весами для взвешивания горы Фудзи, имея лишь две верёвки, которые поджигаются и горят с разной скоростью?
                                                                              • –2
                                                                                решил закодить эту задачу
                                                                                int sum(int *m,int count,int s)       //s играет роль локальной переменной, минус одна строка
                                                                                {
                                                                                    for(int i=1;i<count;i++)
                                                                                        if(m[i]<m[0]) s+=m[0]-m[i];
                                                                                        else return s+sum(&m[i],count-i,0);
                                                                                    return 0;
                                                                                }
                                                                                

                                                                                вызывать так
                                                                                int m[]={1,5,3,3,5,2,1,8};
                                                                                int s=sum(m,sizeof(m)/sizeof(int),0);
                                                                                
                                                                                • +11
                                                                                  > //s играет роль локальной переменной, минус одна строка

                                                                                  А в for-е слабо объявить?

                                                                                  for (int i = 1, s = 0;…
                                                                                  • 0
                                                                                    А в for-е слабо объявить?

                                                                                    и правда, не подумал, так ещё короче
                                                                                  • 0
                                                                                    int m[]={1,0,2,0,1,0,1};
                                                                                    int s=sum(m,sizeof(m)/sizeof(int),0);
                                                                                    printf(«RES: %i», s);
                                                                                    RES: 1
                                                                                    ANSWER: 3
                                                                                    • 0
                                                                                      нашел ошибку, да решение не правильное
                                                                                  • –9
                                                                                    Задача плохо поставлена. Не сказано, какой уровень воды. Я могу вообще сказать, что он затопит все вокруг (см. картинку 3), а значит будет просто myarr.Select(x=>maxlevel-x).Sum();

                                                                                    image
                                                                                    image
                                                                                    image
                                                                                    • 0
                                                                                      То есть можно догадаться о том, что имелось ввиду, но догадываться от постановки задачи сильно отличается. например, почему лужа не между тройкой и семеркой, а между пятеркой? для точки [4] локальными максимумами будут 3 и 2, но мы заливаем между 5 и 7.
                                                                                      • +17
                                                                                        «На картинке выше все, что расположено слева от точки 1, выплескивается. Вода справа от точки 7 также прольется.»

                                                                                        Вас бы тоже не взяли.
                                                                                        • +2
                                                                                          Стен -1 и 10 нету. Вода сливается к нулю по краям. А насчет «недолива», в условии и не оговорено время, которое идет дождь, про его остановку ничего не сказано, так что вполне логично предположить что он зальет по максимуму. Ну мне кажется все именно так.
                                                                                          • 0
                                                                                            Такие вопросы кандидат должен задать интервьюеру, никаких «логично предположить» — это тест на правильное понимание ТЗ.
                                                                                        • +35
                                                                                          > «Будут еще какие-либо вопросы ко мне?», спросил Джастин

                                                                                          Всегда в этот момент хочется попросить интервьюера решить в ответ задачу аналогичной сложности. Может это самооправдание, но уверен, что 99.9999% интервьюеров будут не в состоянии это сделать. А тех, кто спрашивает на интервью по сути выдержки из документации (c MSDN например), да еще и с заранее подготовленной бумажки — просто хочется ударить сапогом по лицу.

                                                                                          Есть мнение, самый действенный метод понять какой человек программист — это ~месяц испытательного срока. Все предварительные интервью должны быть направлены только на осознание его опыта, некоторых человеческих качеств, и что он совсем не дебил.
                                                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                                                            • +5
                                                                                              Нестандартное мышление и инновационный подход.
                                                                                              • 0
                                                                                                Стресс-интервью для работодателя
                                                                                              • +2
                                                                                                >>Всегда в этот момент хочется попросить интервьюера решить в ответ задачу аналогичной сложности.

                                                                                                Блин-блинский!
                                                                                                Да ведь это же отличный способ поглумиться, когда ты идешь на пяток интервью чисто для тренировки перед Самым Главным Интервью :)
                                                                                                • +21
                                                                                                  Так и представляю:
                                                                                                  — Ну вроде все, у вас ко мне вопросы есть?
                                                                                                  — Конечно есть! Напишите мне, пожалуйста, алгоритм нормализации бинарного дерева :)

                                                                                                  И такой сидишь:
                                                                                                  — Только один вариант? Херовенько, херовенько :)
                                                                                                • +10
                                                                                                  Про сапогом по лицу — Вы случаем не это в виду имеете: www.youtube.com/watch?v=XfpLwPe1Ik4?
                                                                                                  • +2
                                                                                                    Посмеялся сам, а потом и вместе с женой. Спасибо.
                                                                                                    • 0
                                                                                                      Присвятые фотоны, это уморительно!
                                                                                                    • 0
                                                                                                      99% интервьюеров в свое время прошли аналогичное собеседование, так что они заведомо в состоянии решить вашу задачу :)
                                                                                                      PS. Сапогом по лицу — это слишком мягко в указанном случае.
                                                                                                      • 0
                                                                                                        Поверьте, перед подготовкой каждой такой задачи, она проходит проверку на коллегах :)
                                                                                                      • –10
                                                                                                        Вау, а задачка-то отличная, даже в этом посте уже можно запросто отличить людей, которые настроены на решение проблем, от тех, кто настроен на нытье на надуманные темы:
                                                                                                        — это не для программистов, а для олимпиадников,
                                                                                                        — у меня ничего ни работает, условия некорректные
                                                                                                        — нихаачуууу…
                                                                                                        и т.п.
                                                                                                        А то что после решения требуют оформить почти как в настоящий продакшен с юнит-тестами и т.п., позволит сразу оценить и чистоту кода и подход к декомпозиции на подзадачи и т.п. Почти все, что можно рассчитывать узнать о кандидате в такой короткий срок.
                                                                                                        • +4
                                                                                                          Кстати, не всегда важно правильное решение, а важен ход рассуждений. Если человек делает логичные выводы, рассуждает здраво, то он вполне может приглянуться допрашивающим.
                                                                                                        • +4
                                                                                                          Интересно, а как дела с собеседованиями на вконтакте? Вроде бы, там сплошные олимпиадники и всё такое.
                                                                                                          • +6
                                                                                                            Решение на J

                                                                                                            Не судите строго — основной текст и заморочка — это обрезание краёв. Пойду спрошу у гуру как это сделать.

                                                                                                                  f =: 3 : '>. /> +/ each (<@((-.@((i.@{.@I. , (({:@I.) + i.@(# - {:@I.))) (4 : ''1 x } y'') ]))@(1&>) # ]))("1) (-/~) y'
                                                                                                                  f 2 5 1 2 3 4 7 7 6
                                                                                                            10
                                                                                                                  f 2 5 1 3 1 2 1 7 7 6
                                                                                                            17
                                                                                                            


                                                                                                            Интересно было бы узнать у автора — а чем twitter лучше чем амазон? Дилетанский взгляд конечно: но в амазоне какие-то новые технологии делают, a что делают в твиттере — я не известно.
                                                                                                            • +3
                                                                                                              Понимаю тех, кто минусует — жуткое решение.

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

                                                                                                              для пояснения пишу с комментариями:

                                                                                                              w =: 0 5 3 5 1 2     NB. исходные данные
                                                                                                              s =: >./\ - [        NB. функция для подсчёта "дыр" слева-направо.
                                                                                                              +/ (f w) <. f&.|. w
                                                                                                              
                                                                                                              NB. >. - это поиск максимума.
                                                                                                              NB. / - это between, т.е. вставка максимума между всеми элементами списка - т.е. по сути поиск глобального максимума.
                                                                                                              NB. но если мы пишем /\ - то это between, но с сохранением промежуточных результатов, т.е. бегущий максимум.    >./ w это 5, а >./\ w  это 0 5 5 5 5 5 . всё отлично, но только данный подход считает так, как будто стены нет слева, а вот справа есть. для этого ниже делается реверс.
                                                                                                              
                                                                                                              NB. &. - это применение одной функции, потом глагола, потом инверсной.
                                                                                                              NB. |. - revers списка.
                                                                                                              NB. т.е. f&.|. w - это будет: развернуть список, потом применить к нему f, а потом ещё раз развернуть. т.е. в данном случае, чтобы подсчитать впадины справа налево.
                                                                                                              NB. в итоге: считаем дырки слева направо, потом справа-налево и берём меньшие значение для каждой дырки.
                                                                                                              
                                                                                                              


                                                                                                              • +9
                                                                                                                Что это за язык?
                                                                                                                Я на всякий случай вычислил md5 из решения. baa63d9e9d0e7be8661817ea7b07db3b
                                                                                                                Текст изменился и я делаю вывод, что это не perl.
                                                                                                                • +3
                                                                                                                  Решение на perl было бы так:
                                                                                                                  perl -nE '
                                                                                                                  1 while s/([#-]) ( *)([#-])/\1-\2\3/g; $sum+=s/-/x/g;}END{say $sum
                                                                                                                  
                                                                                                                  ' task.txt

                                                                                                                  Где задача в файле task.txt:
                                                                                                                           #       
                                                                                                                   #       #       
                                                                                                                   #    #  #       
                                                                                                                   #    #  #       
                                                                                                                   # #  #  #       
                                                                                                                  ## ## #  #       
                                                                                                                  ##############
                                                                                                                  
                                                                                                                  • 0
                                                                                                                    вот это здорово, можно сказать прямо в прямом смысле заливается водой :) очень понравилось решение.
                                                                                                                  • +1
                                                                                                                    Даю ссылку с упоминаниями на этот сайт:

                                                                                                                    habrahabr.ru/tag/j

                                                                                                                    А зачем нужен md5 решения?

                                                                                                                    Кстати позже закинул эту задачу в рассылку по этому языку и получил решение от профессионалов:
                                                                                                                       +/@(-~ >./\ <. >./\.) 2 5 1 3 1 2 1 7 7 6
                                                                                                                    17
                                                                                                                    


                                                                                                                    • 0
                                                                                                                      А можно пояснить? Что такое md5 от решения? md5 от исходного кода? Зачем его вычислять? Как при этом может измениться текст и причём тут perl?
                                                                                                                      • 0
                                                                                                                        <sarcasm>Ну это же общеизвестный факт: программы на perl обладают столь высокой энтропией, что неподвержены алгоритмам хеширования.</sarcasm>
                                                                                                                        • +1
                                                                                                                          Все равно не понял(

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

                                                                                                                          А вот как энтропия связана с хешированием? Считается что хэш от текста с высокой энтропией равен исходному тексту? Но ведь это неправда, я даже не вижу повода такое предположить.
                                                                                                                • 0
                                                                                                                  Какое хитрое решение. Вот написал на js логически простое, два цикла и максимальная сложность 2n.
                                                                                                                  • 0
                                                                                                                    «Достаточно неплохо, хотя ваше решение делает 2 прохода, но есть другой интересный алгоритм, который делает всего один проход».


                                                                                                                    Решение в два прохода находится достаточно быстро :) Сложнее уложиться ровно в один проход
                                                                                                                    • 0
                                                                                                                      Я попробовал сделать в один проход строго слева направо. Получилось ужасно — потребовался стек индексов.
                                                                                                                      • 0
                                                                                                                        ну как-то так. Или это и есть «стек индексов»?
                                                                                                                      • 0
                                                                                                                        Решил в один проход. Не хотел двигать стенки как в оригинальном решении из поста. Решал сначала геометрически на бумажке — не уверен что без листка будет понятно.
                                                                                                                        Скрытый текст
                                                                                                                        var calculate = function( arr ){ // one cycle solution
                                                                                                                            var minMax, 
                                                                                                                                sum = 0, 
                                                                                                                                fullSum = 0,
                                                                                                                                el, 
                                                                                                                                maxMax,
                                                                                                                                i, _i = arr.length - 1;
                                                                                                                                
                                                                                                                            minMax = arr[0]; // first item is the current left max
                                                                                                                            maxMax = arr[_i]; // last item is the current right max
                                                                                                                            
                                                                                                                            for( i = 0; i <= _i; i++ ){
                                                                                                                                el = arr[ i ];
                                                                                                                                if( minMax < el ){ // if the wall is getting higher
                                                                                                                                    sum += ( el - minMax ) * i; //add rectangular currentHeight-lastHeight x distanceFromStart
                                                                                                                                    fullSum += ( el - minMax ) * i; //add such rectangular to the whole avaliable free space
                                                                                                                                    minMax = el;
                                                                                                                                }else{ // if we are getting down
                                                                                                                                    fullSum += minMax - el; // add down delta to the whole avaliable free space sum
                                                                                                                                }
                                                                                                                                el = arr[ _i - i ];
                                                                                                                                if( maxMax < el ){ // same from the right side
                                                                                                                                    sum += ( el - maxMax ) * i; 
                                                                                                                                    maxMax = el;
                                                                                                                                }
                                                                                                                            }
                                                                                                                            return fullSum - sum; // here we get whole avaliable space and reversed space that would be filled with water
                                                                                                                        };
                                                                                                                        
                                                                                                                        // testing
                                                                                                                        [
                                                                                                                            [[0,0,0,10,0,0,0,0,0],0],
                                                                                                                            [[0,1,0,10,0,0,0,0,0],1],
                                                                                                                            [[1,0,1], 1],
                                                                                                                            [[5,0,5], 5],
                                                                                                                            [[0,1,0,1,0], 1],
                                                                                                                            [[1,0,1,0,1,0,1,0], 3],
                                                                                                                            [[1,0,1,0], 1],
                                                                                                                            [[1,0,1,2,0,2], 3],
                                                                                                                            [[2,5,1,2,3,4,7,7,6], 10],
                                                                                                                            [[5,1,0,1],1],                 //# thanks https://news.ycombinator.com/item?id=6640085
                                                                                                                            [[2,5,1,2,3,4,7,7,6,3,5], 12] //# thanks https://news.ycombinator.com/item?id=6640105
                                                                                                                        ].forEach(function( el ){
                                                                                                                            if( calculate( el[0] ) !== el[1] ) throw( el );
                                                                                                                        });
                                                                                                                        

                                                                                                                    • 0
                                                                                                                      Решение «в лоб»:
                                                                                                                      use strict;
                                                                                                                      use warnings;
                                                                                                                      
                                                                                                                      my @list = (2, 5, 1, 2, 3, 4, 7, 7, 6);
                                                                                                                      my $max = (sort { $a <=> $b } @list)[-1];
                                                                                                                      
                                                                                                                      my $vol = 0;
                                                                                                                      
                                                                                                                      for (my $y = $max; $y >= 0; $y--) {
                                                                                                                          my $left = 0;
                                                                                                                          my $right = 0;
                                                                                                                      
                                                                                                                          for (my $x = 0; $x < @list; $x++) {
                                                                                                                             next if $list[$x] < $y;
                                                                                                                             $left = $x + 1;
                                                                                                                             last;
                                                                                                                          }
                                                                                                                      
                                                                                                                          for (my $x = $#list; $x > $left; $x--) {
                                                                                                                             next if $list[$x] < $y;
                                                                                                                             $right = $x - 1;
                                                                                                                             last;
                                                                                                                          }
                                                                                                                      
                                                                                                                          for (my $x = $left; $x < $right; $x++) {
                                                                                                                             $vol++ if $list[$x] < $y;
                                                                                                                          }
                                                                                                                      }
                                                                                                                      
                                                                                                                      print "Volume = $vol\n";
                                                                                                                      
                                                                                                                      

                                                                                                                      • 0
                                                                                                                        йа тупой.
                                                                                                                        правильное решение:

                                                                                                                        use strict;
                                                                                                                        use warnings;
                                                                                                                        
                                                                                                                        my @list = (2, 5, 1, 2, 3, 4, 7, 7, 6);
                                                                                                                        my $max = (sort { $a <=> $b } @list)[-1];
                                                                                                                        
                                                                                                                        my $vol = 0;
                                                                                                                        my $y = 1;
                                                                                                                        
                                                                                                                        while(1) {
                                                                                                                            my ($left, $right);
                                                                                                                            my $linevol = 0;
                                                                                                                            for (@list) {
                                                                                                                                if (!$left && $_ >= $y) {
                                                                                                                                    $left = 1;
                                                                                                                                    next;
                                                                                                                                }
                                                                                                                                if ($left && $_ >= $y) {
                                                                                                                                    $vol += $linevol;
                                                                                                                        	    $linevol = 0;
                                                                                                                                    $right = 1;
                                                                                                                                    next;
                                                                                                                                }
                                                                                                                                $linevol++ if $left && $_ < $y; 
                                                                                                                            }
                                                                                                                            last unless $right;
                                                                                                                            $y++;
                                                                                                                        }
                                                                                                                        
                                                                                                                        print "Volume = $vol\n";
                                                                                                                        
                                                                                                                        
                                                                                                                        • +1
                                                                                                                          Еще вариант:

                                                                                                                          use strict;
                                                                                                                          use warnings;
                                                                                                                          
                                                                                                                          my @list = (2, 5, 1, 2, 3, 4, 7, 7, 6);
                                                                                                                          
                                                                                                                          my $vol = 0;
                                                                                                                          my $y = 1;
                                                                                                                          my $do = 1;
                                                                                                                          
                                                                                                                          while($do) {
                                                                                                                              $do = 0;
                                                                                                                              my $linevol = 0;
                                                                                                                              for (my $x = 1; $x < @list; $x++) {
                                                                                                                                  next if $list[$x - 1] < $y;
                                                                                                                                  if ($list[$x] < $y) {
                                                                                                                                      $list[$x] = $y;
                                                                                                                                      $linevol++;
                                                                                                                                      next;
                                                                                                                                  }
                                                                                                                                  $vol += $linevol;
                                                                                                                                  $linevol = 0;
                                                                                                                          	$do = 1;
                                                                                                                              }
                                                                                                                              $y++;
                                                                                                                          }
                                                                                                                          
                                                                                                                          print "Volume = $vol\n";
                                                                                                                          
                                                                                                                          
                                                                                                                          • +1
                                                                                                                            Или так (без вложенного цикла):
                                                                                                                            use strict;
                                                                                                                            use warnings;
                                                                                                                            
                                                                                                                            my @list = (2, 5, 1, 2, 3, 4, 7, 7, 6);
                                                                                                                            
                                                                                                                            my @copy = @list;
                                                                                                                            
                                                                                                                            my $vol = 0;
                                                                                                                            my $tmpvol = 0;
                                                                                                                            
                                                                                                                            for (my $x = 1; $x < @copy; $x++) {
                                                                                                                                if ($copy[$x] < $copy[$x - 1]) {
                                                                                                                                   $tmpvol += $copy[$x - 1] - $copy[$x];
                                                                                                                                   $copy[$x] = $copy[$x - 1];
                                                                                                                                   next;
                                                                                                                                }
                                                                                                                                $vol += $tmpvol;
                                                                                                                                $tmpvol = 0;
                                                                                                                            }
                                                                                                                            
                                                                                                                            my $level = 0;
                                                                                                                            if ($tmpvol) {
                                                                                                                               for (my $x = @list - 1; $x > 0; $x--) {
                                                                                                                                   last if $list[$x] >= $copy[$x];
                                                                                                                                   $level = $list[$x] if $list[$x] > $level;
                                                                                                                                   $tmpvol -= $copy[$x] - $level;
                                                                                                                               }
                                                                                                                               $vol += $tmpvol;
                                                                                                                            }
                                                                                                                            
                                                                                                                            print "Volume = $vol\n";
                                                                                                                            
                                                                                                                            

                                                                                                                      • +9
                                                                                                                        На следующий день я показал эту задачу знакомому аспиранту, занимающемуся теоретическим computer science. После 40 минут размышлений у него также ничего не получилось.
                                                                                                                        О боже…
                                                                                                                        • +16
                                                                                                                          Я вот все думаю, почему так отличаются подходы если ты сам ищеш себе сотрудника или если ищет тот кого назначили искать.
                                                                                                                          Формальные тесты на сообразительность просто глупы в условии стресса если Вы ищете не оператора боевого дрона. Почему если я ищу сотрудника то мне гораздо важнее узнать что он за человек, чем живёт и интересуется, а сторонний человек начинает тестировать сообразительность итп. Профи видит профи через 10 минут простого, доброжелательного общения по теме. Остальные 50 минут потрать узнавая что за человек, как легко будет с ним работать, видиш ли ты в нём партнера. Все хочу молодёже пожелать искать работу в боевых конторах, которые вынуждены выживать и конкурировать, там можно расти как специалисту. А в фейсбуках и гуглах больших конторах очень велика вероятность что похороните Вы свои таланты и поростёте мхом. Будете микроскопом гвозди забивать. Да и платят они не бог весть как много, если только плюшками халявными коспенсируют. Всякая большая контора обрастает со временем кучей ненужных проверяльщиков и надзирателей талант которых не без основания можно поставить под сомнение. Их отличие от Вас только в том, что те вопросы они сначала в спокойной обстановке сами обсосали, без стресса, за чашкой халявного кофе и булкой. Они вряд ли умнее Вас, просто им повезло когда то в этой лотерее. Не рвитесь сразу к ним, начните с меньшего но интересного, а то, есть вероятность, что ничего стоящего в жизни так и не попробуете.
                                                                                                                          • НЛО прилетело и опубликовало эту надпись здесь