Facebook onsite System design vs Product Design

[BigSpender]

Phone screen - medium
Behaviour - easy
Round 1: medium + hard (only portion of this problem due to time restriction)
Round 2: easy + medium
Topics: strings, arrays, trie (сама задачка была очень простая, но уметь разглядеть prefix tree aka trie case а так же написать эту структуру данных нужно уметь), graph
Запускать код не нужно, и во всяких edge cases ковыряются тоже (если только время останется). Код нужно писать быстро. Это очень важно как я поняла.
Я думаю требования по кодинг к джуниорам намного выше, и задачи дают сложнее. Таких тертых калачей как мы дрючат больше по дизайну. Считается что на более высоком сеньор уровне ты уже не обязательно очень часто и много пишешь код, т к занимаешься дизайн работой в том числе.

Спасибо большое за детальный ответ

Topics: strings, arrays, trie (сама задачка была очень простая, но уметь разглядеть prefix tree aka trie case а так же написать эту структуру данных нужно уметь), graph

Получается структуры данных тоже самому с нуля нужно писать или можно использовать готовые библиотечные версии?
Я знаю в Java нету в стандартных библиотеках структуры Trie, ее в любом случае нужно самому имплементировать, но при это есть Linked List, Stack, Queue, Red-Black tree и т.д.
В таком случае можно пользоваться библиотечными структурами данных?

[Krys-Krys]

Получается структуры данных тоже самому с нуля нужно писать или можно использовать готовые библиотечные версии?
Я знаю в Java нету в стандартных библиотеках структуры Trie, ее в любом случае нужно самому имплементировать, но при это есть Linked List, Stack, Queue, Red-Black tree и т.д.
В таком случае можно пользоваться библиотечными структурами данных?

Можно пользоваться библиотечными структурами данных, кроме тех случаев где задача подрузумевает что вам нужно самому это реализовать, например задача "Удалить элемент из линкед листа".

[valchkou]

Могу только сказать следующие:
1)Запись в БД будет редкой. То что там хранится - создаётся 1 раз и каждая запись обновляется в среднем 1-2 раза в год. Типа как информация о бизнесах на районе. Да, появляются новые, старые иногда уходят, временами обновляются, но это не часто.
2)100 млн главных entities.
3)Весь объём данных - около 1 Тб. Данные все ценные, потерять нельзя. Транзакционность на запись важна.
4)читать из базы будем много. 100 тыщ QPS, но очень простых. Select by ID. Ну естественно и кэш прикрутим. Как же без этого. С кэшем уже не миллиард должно стать а поменьше.
Я предложила остановится на обычной SQL DB, replication, и если что просто прошардить. Как прошардить было очевидно вполне по условию задачи, т к мы будем по select by mainEntityId делать запросы, то по ней и прошардить, остальное все что там есть привязано к этой ID и ни к чему другому.

ну понятно, по условиям сложилось ощущение что ожидалось типа монгадб.

[Big W]

...
Могу только сказать следующие:
1)Запись в БД будет редкой. То что там хранится - создаётся 1 раз и каждая запись обновляется в среднем 1-2 раза в год. Типа как информация о бизнесах на районе. Да, появляются новые, старые иногда уходят, временами обновляются, но это не часто.
2)100 млн главных entities.
3)Весь объём данных - около 1 Тб. Данные все ценные, потерять нельзя. Транзакционность на запись важна.
4)читать из базы будем много. 100 тыщ QPS, но очень простых. Select by ID. Ну естественно и кэш прикрутим. Как же без этого. С кэшем уже не миллиард должно стать а поменьше.

"Транзакционность на запись важна" - как бы намек на NoSQL, с др. стороны "Запись в БД будет редкой", т.е. не суть важно ...
"100 тыщ QPS, но очень простых. Select by ID" - просится какая-нибудь key-value nosql db типа Redis, но Redis это in-memory, хороша в качестве кэша, справится ли с 1 Тб
Просто мысли вслух ...

[valchkou]

...
Могу только сказать следующие:
1)Запись в БД будет редкой. То что там хранится - создаётся 1 раз и каждая запись обновляется в среднем 1-2 раза в год. Типа как информация о бизнесах на районе. Да, появляются новые, старые иногда уходят, временами обновляются, но это не часто.
2)100 млн главных entities.
3)Весь объём данных - около 1 Тб. Данные все ценные, потерять нельзя. Транзакционность на запись важна.
4)читать из базы будем много. 100 тыщ QPS, но очень простых. Select by ID. Ну естественно и кэш прикрутим. Как же без этого. С кэшем уже не миллиард должно стать а поменьше.

"Транзакционность на запись важна" - как бы намек на NoSQL, с др. стороны "Запись в БД будет редкой", т.е. не суть важно ...
"100 тыщ QPS, но очень простых. Select by ID" - просится какая-нибудь key-value nosql db типа Redis, но Redis это in-memory, хороша в качестве кэша, справится ли с 1 Тб
Просто мысли вслух ...

скорее всего справится но дорого. 1TB RAM например в амазоне влетит в копеечку.
монгодб же можно горизонтально скейлить на чтение сколько угодно

[uncle_Pasha]

но Redis это in-memory, хороша в качестве кэша, справится ли с 1 Тб

Можно идти от простого к сложному, но изначально надо нацеливаться на scalable solution. Потому как, даже если изначально сказано 1 TB, то follow-up будет 10 TB (если только изначально не скажут 100 TB).

[uncle_Pasha]

Я предложила остановится на обычной SQL DB, replication, и если что просто прошардить. Как прошардить было очевидно вполне по условию задачи

Если что - это не вариант. Речь идет о large scalable distributed systems.
Проиграйте вопрос еще раз, возможно упустили какой-то bottleneck, или возможность failover, вспомните CAP theorem, etc.
Удачи!

[BigSpender]

Получается структуры данных тоже самому с нуля нужно писать или можно использовать готовые библиотечные версии?
Я знаю в Java нету в стандартных библиотеках структуры Trie, ее в любом случае нужно самому имплементировать, но при это есть Linked List, Stack, Queue, Red-Black tree и т.д.
В таком случае можно пользоваться библиотечными структурами данных?

Можно пользоваться библиотечными структурами данных, кроме тех случаев где задача подрузумевает что вам нужно самому это реализовать, например задача "Удалить элемент из линкед листа".

Понял спасибо еще раз!

Вот кстати может пригодиться по System Design'у:
https://docs.google.com/document/d/1w3q ... 98ZQw/edit

[BigSpender]

Могу только сказать следующие:
1)Запись в БД будет редкой. То что там хранится - создаётся 1 раз и каждая запись обновляется в среднем 1-2 раза в год. Типа как информация о бизнесах на районе. Да, появляются новые, старые иногда уходят, временами обновляются, но это не часто.
2)100 млн главных entities.
3)Весь объём данных - около 1 Тб. Данные все ценные, потерять нельзя. Транзакционность на запись важна.
4)читать из базы будем много. 100 тыщ QPS, но очень простых. Select by ID. Ну естественно и кэш прикрутим. Как же без этого. С кэшем уже не миллиард должно стать а поменьше.
Я предложила остановится на обычной SQL DB, replication, и если что просто прошардить. Как прошардить было очевидно вполне по условию задачи, т к мы будем по select by mainEntityId делать запросы, то по ней и прошардить, остальное все что там есть привязано к этой ID и ни к чему другому.

ну понятно, по условиям сложилось ощущение что ожидалось типа монгадб.

Я тоже подумал про MongoDB судя по условию должно подойти под эту задачу.

[Krys-Krys]

Вот кстати может пригодиться по System Design'у:
https://docs.google.com/document/d/1w3q ... 98ZQw/edit

Это для тех кто по английски не понимает?
https://github.com/donnemartin/system-d ... start-here

[BigSpender]

Вот кстати может пригодиться по System Design'у:
https://docs.google.com/document/d/1w3q ... 98ZQw/edit

Это для тех кто по английски не понимает?
https://github.com/donnemartin/system-d ... start-here

Точно похоже у Donne Martin скопировали
Тогда конечно лучше первоисточник

[Krys-Krys]

Получается структуры данных тоже самому с нуля нужно писать или можно использовать готовые библиотечные версии?
Я знаю в Java нету в стандартных библиотеках структуры Trie, ее в любом случае нужно самому имплементировать, но при это есть Linked List, Stack, Queue, Red-Black tree и т.д.
В таком случае можно пользоваться библиотечными структурами данных?

Честно говоря я вообще нигде не видела Red-Black tree. Я была на 5 онсайтах за последний месяц. В целом у меня сложилось мнение что больше всего спрашивают/пригодятся это.
1)Строки. Нужно хорошо уметь их парсить, склеивать, отрезать и т д и т п. Это самые популярные задачи.
2)HashMap, HashSet, array, уметь решать рандомные задачи рекурсивно. 1 раз спросили про binary search - но писать его руками не просили, только уточнили что знаю что он есть.
3)Graphs, BFS, DFS. Именно графы а не деревья, почему-то про деревья совсем нигде ничего не спрашивали, не считая 1 раз про trie. А каком-то BST (binary search tree) or Red-Black tree речь вообще не идет. А вот на графы как-то у меня много задач было в разных компаниях. Так же сюда относятся задачи где нужно ходить по полю с клетками и там чего-то делать, как например в задаче номер 200 - "число островов" - спрашивали похожее.
4)Rate limiter. Не знаю что за мода такая новая - но просили написать код уже 2 раза!
5)Задачи из разряда "найти К самых больших чисел", "К самых популярных слов".
Одно время была очень популярна боянистая задача LRU Cache, у нас индусы ее любили на работе спрашивать, ее можно решить через Double LinkedList который написать самому руками. Но этой задачи у меня нигде никто не спрашивал.
В общем нигде особо нет ничего такого что нужно самому руками писать. Теже stack, queue, etc, PriorityQueue - есть уже готовые для использования в Джаве. Конечно если не спросят задачу "напиши сам стэк руками", ну а Trie как раз нет - ее нужно руками писать.

[valchkou]

Честно говоря я вообще нигде не видела Red-Black tree.

так к слову, TreeMap and TreeSet это имплементации данного дерева на яве.
Один раз меня попросили закодить какую то хрень в виде circular buffer используя как синхронный так и асинхронный доступ.
После часа мучений я был выставлен за дверь пинком.
И только после этого пинка мне вдруг пришла гениальная мысль, нужно было всего лишь обернуть BlockingQueue. Но было уже поздно.

[Krys-Krys]

Честно говоря я вообще нигде не видела Red-Black tree.

так к слову, TreeMap and TreeSet это имплементации данного дерева на яве.
Один раз меня попросили закодить какую то хрень в виде circular buffer используя как синхронный так и асинхронный доступ.
После часа мучений я был выставлен за дверь пинком.
И только после этого пинка мне вдруг пришла гениальная мысль, нужно было всего лишь обернуть BlockingQueue. Но было уже поздно.

Не знала, спасибо!

[BigSpender]

Получается структуры данных тоже самому с нуля нужно писать или можно использовать готовые библиотечные версии?
Я знаю в Java нету в стандартных библиотеках структуры Trie, ее в любом случае нужно самому имплементировать, но при это есть Linked List, Stack, Queue, Red-Black tree и т.д.
В таком случае можно пользоваться библиотечными структурами данных?

Честно говоря я вообще нигде не видела Red-Black tree. Я была на 5 онсайтах за последний месяц. В целом у меня сложилось мнение что больше всего спрашивают/пригодятся это.
1)Строки. Нужно хорошо уметь их парсить, склеивать, отрезать и т д и т п. Это самые популярные задачи.
2)HashMap, HashSet, array, уметь решать рандомные задачи рекурсивно. 1 раз спросили про binary search - но писать его руками не просили, только уточнили что знаю что он есть.
3)Graphs, BFS, DFS. Именно графы а не деревья, почему-то про деревья совсем нигде ничего не спрашивали, не считая 1 раз про trie. А каком-то BST (binary search tree) or Red-Black tree речь вообще не идет. А вот на графы как-то у меня много задач было в разных компаниях. Так же сюда относятся задачи где нужно ходить по полю с клетками и там чего-то делать, как например в задаче номер 200 - "число островов" - спрашивали похожее.
4)Rate limiter. Не знаю что за мода такая новая - но просили написать код уже 2 раза!
5)Задачи из разряда "найти К самых больших чисел", "К самых популярных слов".
Одно время была очень популярна боянистая задача LRU Cache, у нас индусы ее любили на работе спрашивать, ее можно решить через Double LinkedList который написать самому руками. Но этой задачи у меня нигде никто не спрашивал.
В общем нигде особо нет ничего такого что нужно самому руками писать. Теже stack, queue, etc, PriorityQueue - есть уже готовые для использования в Джаве. Конечно если не спросят задачу "напиши сам стэк руками", ну а Trie как раз нет - ее нужно руками писать.

Здорово спасибо за такой детальный ответ буду делать больше упор на Графы.

[liamkin]

Честно говоря я вообще нигде не видела Red-Black tree.

так к слову, TreeMap and TreeSet это имплементации данного дерева на яве.
Один раз меня попросили закодить какую то хрень в виде circular buffer используя как синхронный так и асинхронный доступ.
После часа мучений я был выставлен за дверь пинком.
И только после этого пинка мне вдруг пришла гениальная мысль, нужно было всего лишь обернуть BlockingQueue. Но было уже поздно.

Господи, ну что за низкий урвоень. Ну почему опять циклический буфер. Ведь все уже в готовых библиотеках. Расскажите им как семафор работает, как дэдлока избежать. Пусть отвяжутся.
Вот вам задачка - сдвиньте вектор на Н позиций. Без второго вектора. Скалярными средствами.
Или из той же оперы - поверните пиксельную картинку на произвольный угол, без второй матрицы под результат, чисто скалярно.

[8K]

буду делать больше упор на Графы.

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

[BigSpender]

буду делать больше упор на Графы.

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

В FAANGe такие вещи обычно не спрашивают, там даже вопросы про DeadLock и Race Conditions почти никогда не задают. Компании поменьше у которых не выстроены процессы обычно любят стращать низкоуровневыми вещами(думают это круто).

[Krys-Krys]

буду делать больше упор на Графы.

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

В FAANGe такие вещи обычно не спрашивают, там даже вопросы про DeadLock и Race Conditions почти никогда не задают. Компании поменьше у которых не выстроены процессы обычно любят стращать низкоуровневыми вещами(думают это круто).

Так и есть. Все 5 онсайт интервью на которых я была проходили по одному сценарию.
1)Несколько кодинг раундов - задачи на алгоритмы.
2)1-2 раундов разговоров о жизни.
3)1-2 дизайн раундов или слабая попытка ее иммитировать.
Про потоки спросили пару раз на каких-то совсем рандомных телефонных интервью, в одном месте я это интервью не прошла, в другом места прошла но попросили сделать домашнее задание "которое должно занять не больше 6 часов" на многопоточность - я отказалась и собеседоватся дальше там не стала.

[8K]

буду делать больше упор на Графы.

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

В FAANGe такие вещи обычно не спрашивают, там даже вопросы про DeadLock и Race Conditions почти никогда не задают. Компании поменьше у которых не выстроены процессы обычно любят стращать низкоуровневыми вещами(думают это круто).

Так и есть.

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

[M. Ridcully]

буду делать больше упор на Графы.

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

В FAANGe такие вещи обычно не спрашивают, там даже вопросы про DeadLock и Race Conditions почти никогда не задают. Компании поменьше у которых не выстроены процессы обычно любят стращать низкоуровневыми вещами(думают это круто).

Гугл, помнится, как-то спрашивал про многозачность чуток.
Справедлимвости ради, в зависимости от области, в которой работаешь - это может быть намного более практичной и показательной темы поговорить, чем тупые "задизайнь мне FB messenger" или какие-нить key-value stores. И намного ближе к общепрограммистским знаниям и навыкам.
Всякая эта "БИГДАТА" и scalability довольно нишевая хрень, и если с этим не сталкивался, то почему непременно я должен об этом знать?

[8K]

Наверное, от сиюминутной моды тоже зависит. Идешь в реляционную базу данных, а народ интересуется преимуществами и недостатками column store. Вроде и не совсем за уши притянуто, но все равно как-то неожиданно.

[mikeG]

Гугл, помнится, как-то спрашивал про многозачность чуток.

У меня в Г целое интервью было на написание многопоточных очередей и поиск сопутствующих дедлоков и рейс кондишнс.

[BigSpender]

Гугл, помнится, как-то спрашивал про многозачность чуток.

У меня в Г целое интервью было на написание многопоточных очередей и поиск сопутствующих дедлоков и рейс кондишнс.

А в каком году это было ?

[Krys-Krys]

По поводу дизайна - вот нашла дельный калан на Ютюбе. Ведущий не индус, а наш соотечественник.
https://www.youtube.com/channel/UC9vLsn ... 51njmIooCQ