Embedded C: вопросы на собеседованиях

Ха-ха, где это видел проекты с -Werror ?

А суть проста: С стал основой для крестов. Так что утверждение про подмножество как минимум некорректно.

А суть проста, так тут пыжился, и обкакался одним предложением. Расписался в своем абсолютном непонимании множеств и логики.

Вы тоже растианин как и я?

Владимир

Еще я пишу стихотворение про раст, но вот с рифмой как- то не заладилось

с рифмой вроде все как раз нормально.

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

какие-нибудь двухсвязные списки или словари.

Попросите односвязный список реверснуть, in-place. Хороший вопрос - многое становится понятно.

Ну давай ты просвети всех.

Ну вот просвещаю всех. Ты все еще обосраный. Ты даже не можешь понять текст из 2-х предложений. Как ты вообще ТЗ осиливаешь? Я не утверждал что С это подмножество С++, я утверждал (и утверждаю) что у тебя низкий IQ, вследствии чего проблемы с математикой (логика и множества).

и в комитете С не стесняются писать C/C++.

… в фразе «конференция по совместимости C/C++». А на ЛОРе линуксоиды не стесняются писать Windows/Linux. Это значит, что Linux подмножество Windows? Или наоборот?

Это С++, там это ошибка, а не предупреждение.

Это более сильная типизация в C++.

Если это пшик, то тогда и отличия С от Rust, - тоже пшик.

односвязный список реверснуть, in-place

Чет совсем для школоты. Я если односвязный список в проде увижу, конечно, проникнусь к писателю уважением, только вот не увижу :)

Отличия это сколько часов ручного труда на тысячу строк типового кода ты потратишь чтобы портировать с одного языка на другой. В случае C - C++ это будет условно час на тысячу строк кода (реально скорей всего ещё меньше). В случае C - Rust это будет раз в 10 больше.

Гораздо интереснее просить написать пересечение 2х массивов включая дупликаты. Тут без подготовки крыша закипит.

Я не утверждал что С это подмножество С++

Тяжело жопой вилять, когда тебя за нее схватили, да?

Тут без подготовки крыша закипит.

Какая подготовка нужна для наивной реализации?

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

Мы Вам перезвоним.

Если до кандидата очень быстро не дойдет, что массивы надо сначала отсортировать

Можно и без сортировки.

Для каждого элемента из первого: 
  - есть в результате -- пропускаем
  - нет во втором -- пропускаем
  - есть во втором -- считаем, сколько в первом, сколько во втором, минимальное количество пишем в результат

очень медленно

самое быстрое решение без всяких там хешмапов (на сишке врятли кто-то станет писать свою мапу прям на месте) это отсортировать оба массива за O(nlogn + mlogm) и потом классический проход на intersection.

Конечно, можно вместо хешмапы сделать еще один массив длиной максимальное значение из обоих изначальных массивов, но это, имхо чрезмерный расход памяти.

очень медленно

не очень. max(O(N^2), O(N*M)) чтений против O(nlogn + mlogm) записей.

А если массив char’ов и N + M > 256, то O(N+M), так как считать можно для всего массива разом.

отсортировать

В условии не сказано, что элементы можно сравнивать на больше/меньше, есть отношение порядка.

И вообще, пересечение имеет смысл только для множеств, где по определению нет дубликатов. Так что, стоило бы дать определение для твоего «пересечения», что должно произойти с дубликатами.

на сишке врятли кто-то станет писать свою мапу прям на месте

Так и сортировку прям на месте тоже писать то ещё удовольствие.

А если есть libc, то там есть hsearch и tsearch.

Тут сразу можно второй вопрос не задавать, где надо merge sort реализовать :)

Бегать по массивам с каждым элементом и высчитывать сколько его инкарнаций в каждом из них? Это бред. А если массивов 20?

Ну а ты предлагаешь каждый массив предварительно скопировать. А если они суммарно больше половины ОЗУ?

Можно пройтись по меньшему массиву, результат собрать в бинарное дерево значение/количество, затем элементы второго массива ищем в бинарном дереве, если находим, количество уменьшаем на единицу, записываем в результат. Получаем (N+M) log N. Даже лучше, чем с сортировкой.

Я не предлагал ничего копировать. И зачем дерево, когда хешмап быстрее, если уж полезли в сундучек со структурами данных.

А ты вкурсе, что это неполное условие?

Конечно. Поэтому там и есть второй вопрос «почему». Ответ на первый вопрос сам по себе неинтересен. В задачку заложены два не самых популярных факта из стандарта Си, которые уважаемый fsb4000 с лёгкостью раскусил, и один довольно популярный факт, который многие тем не менее привыкли игнорировать, и на котором fsb4000 таки погорел.

Какой-то садизм, если честно. Многие очень хорошие спецы сыпятся на таких собеседованиях банально из-за стресса.

Какой-то садизм, если честно.

Так тема про садизм, «если честно»: надо завалить кандидата, а не искать спеца. Вот ищут «пересечения массивов».

Ок тогда. Прочитал жопой, извиняюсь.

Чет совсем для школоты.

Казалось бы. Но Вы будете сильно удивлены насколько немного людей способно написать «на бумажке» рабочую / безглючную версию с первого раза.

Я если односвязный список в проде увижу,

Односвязный - возможно не увидите. А вот двух-связные используются налево-направо, посмотрите на тот же Linux kernel.

конечно, проникнусь к писателю уважением, только вот не увижу :)

Кстати, то что в ядре - написано очень и очень неплохо, если бы мне нужна была сишная реализация я наверное пи^wбрал бы именно оттуда.

если бы мне нужна была сишная реализация я наверное пи^wбрал бы именно оттуда.

Сможешь написать «на бумажке с первого раза» на собеседовании?

Гораздо интереснее просить написать пересечение 2х массивов включая дупликаты. Тут без подготовки крыша закипит.

Это плохая задачка для интервью. Конечно в предположении что Вы ищете ответ на вопрос «а может ли человек сделать для нас что-то полезное», а не «валите неадеквата» как здесь уже предлагали, и время интервью сильно ограниченно (30-60 минут). «Завалить» можно всегда - достаточно пройтись по узким областям в которых сам «собаку съел», но ведь цель то не в этом. И конкретно эту задачку имеет смысл обсуждать только в контексте «а как бы Вы решали», требовать от соискателя рабочего кода для этой задачи за время интервью абс бессмысленно. Да и постановка не полна - оптимальное решение будет требовать кучу дополнительных вводных, как то: ожидаемый размер массивчиков или хотя бы их соотношение, отсортирован ли хотя бы один из них, какова вероятность совпадений (хотя бы по шкале «почти никогда», «редко», «50/50», «часто», «почти всегда»), нужна ли Вам avg performance или worst case, нужна ли вам «стабильность», как именно должны обрабатываться дупликаты (что делать с последовательностями «1.1, 2.1, 2.3, 3.0» и «1.0, 2.2», то что после точки в сравнении не учавствует), итд.

если бы мне нужна была сишная реализация я наверное пи^wбрал бы именно оттуда.

Сможешь написать «на бумажке с первого раза» на собеседовании?

Признайтесь - вы пьяны? Оно годами вылизывалось…

Оно годами вылизывалось…

А «безглючные односвязные списки на бумаге»?

А «безглючные односвязные списки на бумаге»?

Реверснуть? Легко. Но очевидно - я не в первый раз об этом думаю и все «подводные камни» уже знаю, так что это не показатель.

Конечно, можно вместо хешмапы сделать еще один массив длиной максимальное значение из обоих изначальных массивов,

Господи, боже мой. Я то надеялся что я с адекватом разговариваю. Растворился в тумане. Делайте что хотите. Удачи в поиске!

все «подводные камни» уже знаю

Молодец.

все «подводные камни» уже знаю

Молодец.

Акцент должен стоять на

так что это не показатель

Я не предлагал ничего копировать.

А как ещё сортировать? Портить входящие данные?

И зачем дерево, когда хешмап быстрее

Совсем не всегда быстрее. Чтобы было быстрее, в хешмапе количество корзин должно быть значительно больше числа элементов. Идеальный вариант даже не дерево, а что-то вроде кучи. Или сортированного массива с элементами { значение; количество вхождений }.

Это плохая задачка для интервью.

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

требовать от соискателя рабочего кода для этой задачи за время интервью абс бессмысленно

Это разумеется.

Вот, видишь, ты сразу отсеял самый быстрый по времени вариант решения. Не смотря на дикое потребление памяти, по скорости лучше не сделать. А ведь ситуации бывают разные.

Я в курсе про ядерный список. Там эталон и вполне оправданный.

Односвязный же могу представить только где-нибудь в авионике на древнейшем (зато штабильном) железе с 8кб памяти. Но и разворачивать его это дичь какая-то. Вообще, в принципе, в боевых действиях использовать односвязный список и разворачивать его это дичь из 60ых.

требовать от соискателя рабочего кода для этой задачи

расскажи это фаангам

Односвязный же могу представить только где-нибудь в авионике

односвязный используется там, где стратегия извлечения либо fifo, либо lifo. для очередей и стеков. двусвязный там избыточен, и положить/извлечь в двусвязный вдвое примерно дольше.

разворот односвязного - строчки три-четере кода на Цэ.

Ага, только в боевом проде свои fifo/lifo не пишут, а используют имеющиеся библиотеки. Я поэтому и написал про авионику.

Ага, только в боевом проде свои fifo/lifo не пишут, а используют имеющиеся библиотеки. Я поэтому и написал про авионику.

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

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

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

а в прикладном проде - всегда полный угар и содомия

или вот - сортированный список. он односвязный по природе.

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

В случае C - C++ это будет условно час на тысячу строк кода

Если в результате будет идиоматичный C++ код, а не тупо перекомпиляция сишного кода C++ компилятором, то никак ни час, а на порядок как минимум больше. На раст примерно столько же времени нужно будет.