Facebook

[АццкоМото]

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

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

[АццкоМото]

В одной из контор где я работал был CMMI lvl 3. До сих пор вспоминаю с теплотой. Все работало как часы.

Я несколько лет работал в CMM(не-I) Level 4 на клиента с CMMI Level 5 Да и собственно выросли мы с никакого уровня до 4го при моем непосредственном участии. И точно те же ощущения остались: все просто работает, как часы. Четко, предсказуемо. Правда долго и медленно. Примерно, как в заголовке сайта одной малоизвестной Студии: http://www.artlebedev.ru/

[dotcom]

За 3-4 месяца, может быть, и можно, но не за 1М. API на столько разросшийся, что пока отладишь на клиенте, год пройдет не меньше.

Можно было бы зарубиться, если бы были шансы проверить

Ну пошли подрядимся в fb, деньги поделим, а исполнителем Интеррапта назначим.

[АццкоМото]

Ну пошли подрядимся в fb, деньги поделим, а исполнителем Интеррапта назначим.

sounds like a plan

[Интеррапт]

Ну пошли подрядимся в fb, деньги поделим, а исполнителем Интеррапта назначим.

sounds like a plan

Так, ща я выскажусь по поводу этого плана и самозабанюсь.

[АццкоМото]

dotcom, мне показалось, или Интеррапт требует +20% ?

[dotcom]

Так, ща я выскажусь по поводу этого плана и самозабанюсь.

Уже торгуется.

[wassup]

А какие идеи у вас по первой задаче были?

Ну вот... сейчас гуглер раскатает как тузик грелку.
Ну принимать два вектора* как множество key-value pairs ненулевых значений (ключ - индекс), потом брать пересечение множеств ключей, потом идем по множеству пересекающихся ключей и делаем sum+=vector1.getValue(key)*vector2.getValue(key)

wut?

А какой формат входных данных? Линейный массив? Тогда нету ничего лучше чем обычный цикл:

for (int i = 0; i < SIZE; i++) { sum += a*b; }

[АццкоМото]

А какой формат входных данных? Линейный массив?

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

Тогда нету ничего лучше чем обычный цикл:

for (int i = 0; i < SIZE; i++) { sum += a*b; }

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

[wassup]

Обожаю читать ваши комментарии.

А какой формат входных данных? Линейный массив?

Формат разрешено выбирать самостоятельно.

<irony>Ну это несколько меняет дело</irony>. Можно хранить разреженный вектор в виде динамического списка отсортированного по индексу. В таком случае алгоритм их перемножения будет O(M+N) где M и N - количество элементов в списке. Написание алгоритма (~10 строчек) оставляю вам.

[АццкоМото]

Можно хранить разреженный вектор в виде динамического списка отсортированного по индексу. В таком случае алгоритм их перемножения будет O(M+N) где M и N - количество элементов в списке.

Можно и это тоже достаточно очевидно. Более того, crypto5 это даже упоминал.

Написание алгоритма (~10 строчек) оставляю вам.

Спасибо, я воздержусь. Потому что это не лучший вариант. O(min(M,N)) меня устраивает больше

[wassup]

Спасибо, я воздержусь. Потому что это не лучший вариант. O(min(M,N)) меня устраивает больше

Если вы напишете алгоритм который находит пересечение двух отсортированных множеств быстрее чем O(M+N) то facebook для вас слишком мелок - вы смело можете расчитывать на Филдсовскую премию (я вполне серьезно).

[АццкоМото]

Спасибо, я воздержусь. Потому что это не лучший вариант. O(min(M,N)) меня устраивает больше

Если вы напишете алгоритм который находит пересечение двух отсортированных множеств быстрее чем O(M+N) то facebook для вас слишком мелок - вы смело можете расчитывать на Филдсовскую премию (я вполне серьезно).

Я не понимаю, чего вы пытаетесь доказать? Что я дурак? Ну так скажите прямо, я не легкоранимый человек. В крайнем случае скажу "сам дурак"
Если же вы хотите зачем-то разобрать по косточкам эту довольно простую задачу - причем простую даже для меня, а я прекрасно понимаю, что я не гений алгоритмических задач, то давайте разберемся. Как мы находим пересечение двух множеств наиболее простым и наивным способом? Мы перебираем элементы в меньшем из них и проверяем есть ли такой же элемент в большем. Сложность проверки в классическом HashSet считается О(1). (Понятно, что тут есть множество оговорок, но тем не менее). Элементы меньшего множества нам всяко придется перебрать абсолютно все. O(min(M,N))
Давайте уже свою филдсовскую премию. Ой, у вас ее нет, потому что вы - еще меньший гений алгоритмических задач, чем я, хотя казалось бы - куда ж. Упс. No profit this time.

[ki]

Как мы находим пересечение двух множеств наиболее простым и наивным способом? Мы перебираем элементы в меньшем из них и проверяем есть ли такой же элемент в большем. Сложность проверки в классическом HashSet считается О(1). (Понятно, что тут есть множество оговорок, но тем не менее). Элементы меньшего множества нам всяко придется перебрать абсолютно все. O(min(M,N))

HashSet.add() complexity O(1). Добавить все элементы в HashSet: O(N)
Так надо, так-что O(M+N) и премии не будет

Peace

[wassup]

Сложность проверки в классическом HashSet считается О(1).

Что в корне не верно. worst case - O(N), average - O(N). Константное время достигается только когда количество элементов в контейнере значительно меньше hashtable size.
Эта же оценка верна и для добавления элементов в hashtable. Так чтобы просто положить все элементы в контейнер от вас уже потребуется O(N^2). Ну или в лучшем случае O(N), если initialCapacity зададите значительно больше кол-ва элементов и вам повезет с хеш-функцией.

[АццкоМото]

[
HashSet.add() complexity O(1). Добавить все элементы в HashSet: O(N)
Так надо, так-что O(M+N) и премии не будет

Простите, не понял, что вы хотели сказать

[ki]

Простите, не понял, что вы хотели сказать

Имелось ввиду что создание HashSet -- O(N), итерация по второй Collection/Array/List -- O(M), HashSet.contains -- O(1)
total: O(N) + O(M) + M * O(1) = O(N) + 2*O(M) = O(N) + O(M) = O(N+M)
Премии не будет.

[fruit6]

всю тему нечитал, с этим не согласен.

O(N) + O(M) = O(N+M)

O(N) + O(M) = O(max(N,M))

[crypto5]

Простите, не понял, что вы хотели сказать

Имелось ввиду что создание HashSet -- O(N), итерация по второй Collection/Array/List -- O(M), HashSet.contains -- O(1)
total: O(N) + O(M) + M * O(1) = O(N) + 2*O(M) = O(N) + O(M) = O(N+M)
Премии не будет.

Поскольку мы сами выбираем формат входных данных,можно сказать что хеши уже предпосчитаны и премия будет

[АццкоМото]

Сложность проверки в классическом HashSet считается О(1).

Что в корне не верно. worst case - O(N), average - O(N).

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

Константное время достигается только когда количество элементов в контейнере значительно меньше hashtable size.

Собственно, я об этом же, только вы все-таки несколько перевираете. Элементов в контейнере для константного среднего времени может быть сколько угодно. Хоть в миллион раз больше размера хэштаблицы. Главное, чтобы размер хэша линейно зависел от N. Как только мы зафиксировали этот размер, но отпустили N в свободное плавание, то таки да, мы получим O(N)

Эта же оценка верна и для добавления элементов в hashtable. Так чтобы просто положить все элементы в контейнер от вас уже потребуется O(N^2). Ну или в лучшем случае O(N), если initialCapacity зададите значительно больше кол-ва элементов и вам повезет с хеш-функцией.

А вот это уже БСКВЛН чистой воды: добавление элемента в хэштаблицу - константное время вне зависимости от прочих допущений (пруф: http://en.wikipedia.org/wiki/Hashtable а то ж на слово не поверите)
Если бы нам надо было при каждом добавлении проверять, а нет ли такого элемента там уже, то могло бы быть О(Н)
К тому же вы очень весело оперируете буковкой N. Она у вас означает то размер входных данных, то размер их пересечения по индексу.

[АццкоМото]

Простите, не понял, что вы хотели сказать

Имелось ввиду что создание HashSet -- O(N), итерация по второй Collection/Array/List -- O(M), HashSet.contains -- O(1)
total: O(N) + O(M) + M * O(1) = O(N) + 2*O(M) = O(N) + O(M) = O(N+M)
Премии не будет.

crypto5 уже ответил
last time i checked затраты caller'a на полготовку входных данных никогда не взодили в оценку вычислительной сложности алгоритма

[crypto5]

Эта же оценка верна и для добавления элементов в hashtable. Так чтобы просто положить все элементы в контейнер от вас уже потребуется O(N^2). Ну или в лучшем случае O(N), если initialCapacity зададите значительно больше кол-ва элементов и вам повезет с хеш-функцией.

А вот это уже БСКВЛН чистой воды: добавление элемента в хэштаблицу - константное время вне зависимости от прочих допущений (пруф: http://en.wikipedia.org/wiki/Hashtable а то ж на слово не поверите)
Если бы нам надо было при каждом добавлении проверять, а нет ли такого элемента там уже, то могло бы быть О(Н)
К тому же вы очень весело оперируете буковкой N. Она у вас означает то размер входных данных, то размер их пересечения по индексу.

В джава хештаблица с ресайзом и проверкой на наличие элементов, поэтому вставка O(N).

[АццкоМото]

В джава хештаблица с ресайзом и проверкой на наличие элементов, поэтому вставка O(N).

А кто говорил про стандартную джавовскую хэштаблицу? Я оперировал исключительно Map<KeyT, ValueT> map = new ConcreteMap<KeyT, ValueT>(); и Set<T> set = new ConcreteSet<T>();
С такой прикидкой, что если интервьюеру захочется обсудить, что мы предполагаем о данной реализации, то мы и обсудим. Не захотел

Кстати, даже в джавовской реализации O(n) - это worst case. Вот кому-то не лень было объяснять, почему:

Hash tables are O(1) average and amortized case complexity, however is suffers from O(n) worst case time complexity. [And I think this is where your confusion is]

Hash tables suffer from O(n) worst time complexity due to two reasons:

If too many elements were hashed into the same key: looking inside this key may take O(n) time.
Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].
However, it is said to be O(1) average and amortized case because:

It is very rare that many items will be hashed to the same key [if you chose a good hash function and you don't have too big load balance.
The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

[crypto5]

В джава хештаблица с ресайзом и проверкой на наличие элементов, поэтому вставка O(N).

А кто говорил про стандартную джавовскую хэштаблицу? Я оперировал исключительно Map<KeyT, ValueT> map = new ConcreteMap<KeyT, ValueT>(); и Set<T> set = new ConcreteSet<T>();

Вы вроде несколько раз ссылались на HashMap здесь

Кстати, даже в джавовской реализации O(n) - это worst case. Вот кому-то не лень было объяснять, почему

С таким предположением да:

which are all assumed O(1)

но оно высосано из пальца

[АццкоМото]

Вы вроде несколько раз ссылались на HashMap здесь

Ну, строго говоря - да. Но тут все как-то так нестрого обсуждается, что переночевать негде. Map и Set используются практически взаимозаменяемо, N - то одна величина, то другая, и так далее.
(А главное, я вообще не понимаю, что тут обсуждать. Вариантов не так много, они все тривиальны, со своими очевидными плюсами и минусами)

С таким предположением да:

which are all assumed O(1)

но оно высосано из пальца

Да нет, вполне нормальное утверждение. Если по мере роста таблицы делается resize/rehash, то как раз так и должно быть, как сказано. Т.е. я допускаю, что в джавовской реализации могут быть существенные нюансы, но в общем случае, если мы хотим добиться O(1) on average, то нам не нужен rocket science. Вот если бы нам возжелалось константного worst case, то, пожалуй, был бы облом