Sergunka wrote: ↑28 Jan 2018 18:16
...
Так же я с сыном старшим поиграл в олимипийские игры по програмированию где надо за 4 часа попытаться решить 3 задачи... мне это особо ничего не дало - сыну очень много дало для учебы в Беркли на CS. В Беркли все построенно на тайм меджменте дают очки за каждую задачу сделанную чуть раньше ну и тд.
...
А не могли бы Вы дать ссылку на какие-нибудь ресурсы по олимпийским задачкам? Хочу сына тоже начать учить.
Какого возраста был Ваш сын когда Вы эти задачки решали?
Sergunka wrote: ↑28 Jan 2018 18:16
...
Так же я с сыном старшим поиграл в олимипийские игры по програмированию где надо за 4 часа попытаться решить 3 задачи... мне это особо ничего не дало - сыну очень много дало для учебы в Беркли на CS. В Беркли все построенно на тайм меджменте дают очки за каждую задачу сделанную чуть раньше ну и тд.
...
А не могли бы Вы дать ссылку на какие-нибудь ресурсы по олимпийским задачкам? Хочу сына тоже начать учить.
Какого возраста был Ваш сын когда Вы эти задачки решали?
Мальчик-Одуванчик wrote: ↑29 Jan 2018 21:50
Если рекурсия с хвостом - то как бы наоборот.
Что за рекурсия с хвостом? Вы про хвостовую рекурсию? И что там наоборот? Сидеть и молиться, что компилятор интерпретирует ее как набор последующих вызовов, почистит стек и не завалит аппу уже на 1000000 вызове? Вместо того чтобы вызвать цикл? Поясните плз.
Sergunka wrote: ↑28 Jan 2018 18:16
...
Так же я с сыном старшим поиграл в олимипийские игры по програмированию где надо за 4 часа попытаться решить 3 задачи... мне это особо ничего не дало - сыну очень много дало для учебы в Беркли на CS. В Беркли все построенно на тайм меджменте дают очки за каждую задачу сделанную чуть раньше ну и тд.
...
А не могли бы Вы дать ссылку на какие-нибудь ресурсы по олимпийским задачкам? Хочу сына тоже начать учить.
Какого возраста был Ваш сын когда Вы эти задачки решали?
В 10 классе попробовали Гугл Джем - не пошел... потом олимпиаду usaco.org там проще с уровнем вхождения там разные дивизионы начинаешь с бронзы. Мы выбрались до золотого. Играли пару лет, но после золотого это просто вынос мозга... в общем завязали.
"A patriot must always be ready to defend his country against his government." Edward Abbey
Falcon wrote: ↑28 Jan 2018 22:40
Большинство работы в современном программировании сводится к достаточно стандартным вещам.
Ну вот вам пример. Индус просит написать код на любоя языке (я выбрал C#), который сливает и сортирует 2 линкованных листа в один.
Я пишу код из 1 строчки. Индус недоволен, говорит, что надо на низкому уровне.
var resultList = list1.Concat(list2).OrderBy(e => e).ToList();
Вопрос. Как часто на работе нам приходится изобретать колесо ? И нужны ли такие изобретатели ?
По моему вы придуриваетесь. Из условия задачи (любой язык) ясно, что от вас просят алгоритм. Выбрать библиотеку, в котором алгоритм уже реализован, это читерство.
А писать велосипед, чуствительный к памяти и быстродействию приходится очень часто.
Скорее всего, задачу сформулировали здесь не так, как на собеседовании. На собеседовании, вероятно, была осмысленная задача слить два сортированных списка в один опять же сортированный. То есть реализовать один из шагов сортировки слияния, который действительно может понадобиться и в других приложениях.
Между прочим, в шарпе ToList() возвращает вовсе не "линкованный лист", а массив.
Ion Tichy wrote: ↑28 Jan 2018 23:50
Последняя моя задача: у Вас есть бездонный кошелек с монетами из конечного множества целых номиналов (напр. пени, дайм, никель, квотер или копейка, двушка, алтын, пятак). Вам дается (а) массив номиналов и (б) целое положительное число Д. Ваша программа должна напечатать кол-во способов набора Д Вашими монетами. Час времени. Я не успел, завяз в граничных условиях рекурсии.
У меня уже 2 индуса подобное спрашивали. Одному я решил, но из дома. На лету у доски не вышло. Но туда и не захотел поступать. А второму индусу переслал решение после интервью. Ну я просто не помнил наизусть, что я там написал 2 месяца тому назад.
Моя идея решения было проста. Каждому номиналу приписываем двоичный вес, а потом крутим цикл по количеству номиналов, по всем двоичным единицам цепляем соответсвующий номинал и прибавляем к сумме. Как бы двоичные веса маппируются на номиналы. Если количество номиналов укладывается в стандартную разрядную сетку (32 или 64), то можно обойтись родными целыми числами. Иначе придётся имитировать двоичную разрядную сетку массивом из bool, например.
Это классическая задача на динамику. Если знать, что она на динамику, то придумать алгоритм можно за минуту, еще минут 5-40 на реализацию и отладку, по обстоятельствам.
Sergunka wrote: ↑28 Jan 2018 21:59
Все таки хотя они просили 2 часа на проект и мы договорились, что я вышлю в конце дня вычищать блох особо не имело смысла там тестирование заняло больше часа.
Не так давно я провалил довольно простое интервью в очень интересной компании:
пришлось судорожно создавать проект, искать депенденси, вместо того чтобы подумать и сделать интересный код.
В итоге компания потеряла уникальную возможность нанять возможно одного из лучших кандидатов.
Чтобы избежать таких недоразумений я создал темплейт, на случай если опять попросят покодить на компе.
И уже в скоре пригодилось, последний раз дали всего 40 минут, а я им и REST API и тесты и сам код.
я им честно сказал что форкнул свою рыбу, но это даже оказалось плюсом для них.
В итоге сделали офер от которого я не смог отказаться. Начинаю в среду (но это не те про которых я спрашивал)
Т.е что я всем советую, не только практиковаться для подготовки к интервью, но и выкладывать все это в свой репо, пригодится.
Ух ты, хорошая идея, тоже так сделаю с GitHub-ом. Меня Spotofy зовет в Google Hangout на техническое, думаю ихние юникорны меня завалят, ну хоть потренируюсь.
The best things in life either make you fat, drunk, or pregnant.
John Smith wrote: ↑29 Jan 2018 22:53
а всякие tree traversal чем делать, чтоб не моветон?
Итераторами наверное.
Был в гугле такой вопрос.
Как сравнить 2 BST - то есть если элементы совпадают то они равны.
Ответ предполагает не использовать дополнительную память.
John Smith wrote: ↑29 Jan 2018 22:53
а всякие tree traversal чем делать, чтоб не моветон?
Итераторами наверное.
Был в гугле такой вопрос.
Как сравнить 2 BST - то есть если элементы совпадают то они равны.
Ответ предполагает не использовать дополнительную память.
В сложных алгоритмах думать рекурсией легче, чем с помощью итераторов. Из собственных экспериментов вижу что рекурсивный C++ код быстрее, чем алгоритмы которые не рекурсивные но все равно отлеживают ход дела с помощью stack<T> (это не про 2 BST).
Для глубоко-рекурсивных алгоритмов можно анализировать оставшееся количество стека и, когда его мало, останавливаться и прыгать на новый thread (взять из отведенного на это pool-a). На новой нити будет новый стек. Продолжить свою рекурсию. Первичная нить ждет сигнала когда вторичная выйдет из рекурсии.
John Smith wrote: ↑29 Jan 2018 22:53
а всякие tree traversal чем делать, чтоб не моветон?
Итераторами наверное.
Был в гугле такой вопрос.
Как сравнить 2 BST - то есть если элементы совпадают то они равны.
Ответ предполагает не использовать дополнительную память.
В сложных алгоритмах думать рекурсией легче, чем с помощью итераторов. Из собственных экспериментов вижу что рекурсивный C++ код быстрее, чем алгоритмы которые не рекурсивные но все равно отлеживают ход дела с помощью stack<T> (это не про 2 BST).
Для глубоко-рекурсивных алгоритмов можно анализировать оставшееся количество стека и, когда его мало, останавливаться и прыгать на новый thread (взять из отведенного на это pool-a). На новой нити будет новый стек. Продолжить свою рекурсию. Первичная нить ждет сигнала когда вторичная выйдет из рекурсии.
В данном случае я имею ввиду не итераторы С++ а итераторы в C# (coroutine).
Решение через итераторы-корутины эффективное по памяти и скорости (линейное время без дополнительной памяти).
Larsonsager wrote: ↑30 Jan 2018 01:39
На собеседовании, вероятно, была осмысленная задача слить два сортированных списка в один опять же сортированный.
Обычно в таких заданиях не дают так много информации предполагают что кандидат спросит являются ли списки сортированными.
Larsonsager wrote: ↑30 Jan 2018 01:39
Между прочим, в шарпе ToList() возвращает вовсе не "линкованный лист", а массив.
Если быть более точным - динамический массив. Аналог std::vector в C++.
Andriy777 wrote:
Для глубоко-рекурсивных алгоритмов можно анализировать оставшееся количество стека и, когда его мало, останавливаться и прыгать на новый thread (взять из отведенного на это pool-a). На новой нити будет новый стек. Продолжить свою рекурсию. Первичная нить ждет сигнала когда вторичная выйдет из рекурсии.
Похожим методом делал портирование рекурсивного кода на Palm у которого стек был... 2 Kb. В лоб код быстро падал. После переделки работал, при этом оставался рекурсивным.
Not everyone believes what I believe but my beliefs do not require them to.
John Smith wrote: ↑29 Jan 2018 22:53
а всякие tree traversal чем делать, чтоб не моветон?
Итераторами наверное.
Был в гугле такой вопрос.
Как сравнить 2 BST - то есть если элементы совпадают то они равны.
Ответ предполагает не использовать дополнительную память.
В сложных алгоритмах думать рекурсией легче, чем с помощью итераторов. Из собственных экспериментов вижу что рекурсивный C++ код быстрее, чем алгоритмы которые не рекурсивные но все равно отлеживают ход дела с помощью stack<T> (это не про 2 BST).
Для глубоко-рекурсивных алгоритмов можно анализировать оставшееся количество стека и, когда его мало, останавливаться и прыгать на новый thread (взять из отведенного на это pool-a). На новой нити будет новый стек. Продолжить свою рекурсию. Первичная нить ждет сигнала когда вторичная выйдет из рекурсии.
Хотя это плохой стиль но почему если уж так нравится рекурсия не эмулировать вызов функции с помощью goto и использовать stack<T> для хранения аргументов вызова?
Из плюсов то не будет stackoverflow и не надо создавать отдельные потоки.
Falcon wrote: ↑28 Jan 2018 22:40
Большинство работы в современном программировании сводится к достаточно стандартным вещам.
Ну вот вам пример. Индус просит написать код на любоя языке (я выбрал C#), который сливает и сортирует 2 линкованных листа в один.
Я пишу код из 1 строчки. Индус недоволен, говорит, что надо на низкому уровне.
var resultList = list1.Concat(list2).OrderBy(e => e).ToList();
Вопрос. Как часто на работе нам приходится изобретать колесо ? И нужны ли такие изобретатели ?
а это вопрос не о изобретении колеса, а насколько вы хорошо знаете его устройство. У меня была достаточно интересная беседа с большим дядькой из большой конторы на этот счет. Напару повздыхали, что сейчас народ даже и не задумывается, что проиходит за вызовом той или иной функции. (P.S. это камень не в ваш огород, а ответ на ваш вопрос зачем это спрашивают)
Спасибо что ответили за меня
Хочу дополнить что такие изобретатели нужны. Каждый на своём уровне должен знать основы. А то нынче половина людей не может binary search написать. О чем я могу дальше с ними говорить?
Sergunka wrote: ↑28 Jan 2018 18:16
...
Так же я с сыном старшим поиграл в олимипийские игры по програмированию где надо за 4 часа попытаться решить 3 задачи... мне это особо ничего не дало - сыну очень много дало для учебы в Беркли на CS. В Беркли все построенно на тайм меджменте дают очки за каждую задачу сделанную чуть раньше ну и тд.
...
А не могли бы Вы дать ссылку на какие-нибудь ресурсы по олимпийским задачкам? Хочу сына тоже начать учить.
Какого возраста был Ваш сын когда Вы эти задачки решали?
Falcon wrote: ↑28 Jan 2018 22:40
Большинство работы в современном программировании сводится к достаточно стандартным вещам.
Ну вот вам пример. Индус просит написать код на любоя языке (я выбрал C#), который сливает и сортирует 2 линкованных листа в один.
Я пишу код из 1 строчки. Индус недоволен, говорит, что надо на низкому уровне.
var resultList = list1.Concat(list2).OrderBy(e => e).ToList();
Вопрос. Как часто на работе нам приходится изобретать колесо ? И нужны ли такие изобретатели ?
а это вопрос не о изобретении колеса, а насколько вы хорошо знаете его устройство. У меня была достаточно интересная беседа с большим дядькой из большой конторы на этот счет. Напару повздыхали, что сейчас народ даже и не задумывается, что проиходит за вызовом той или иной функции. (P.S. это камень не в ваш огород, а ответ на ваш вопрос зачем это спрашивают)
Спасибо что ответили за меня
Хочу дополнить что такие изобретатели нужны. Каждый на своём уровне должен знать основы. А то нынче половина людей не может binary search написать. О чем я могу дальше с ними говорить?
О бабах?
Если мы говорим о массовом промышленном программировании бизнес-аппов, то там насрайт на байнари сёрчи, там надо вовремя пройти КуА и сдать код. _Все_ велосипеды уже изобретены и _все_ Америки уже открыты. Мы должны максимально быстро найти подходящий велосипед, достать его с полки и встроить в аппу. На досуге в своих хобби проектах мы можем полировать свой код хоть до морковкиного заговенья, но там и интервьюев нет с задачками.
Но кстати даже с уже изобретенными велосипедами бывают приколы. Пример из меня. На очередном фейс-то-фейс дали задачку что-то типа разместить Н ящиков размеров Р1...РН по М складам вместимости В1...ВМ. Я даже дергаться не стал - "Робя, берете античные фортрановские либы с линейным програмированием и золотой ключик ваш" - "С каким програмированием?" - "С линейным. Методы оптимизации... Задача о комивояжере... Ничего вспыхивает в моске?..." - ...и тишина (с) Неуловимые. А такие кул хацкеры сидели-спрашивали
Как же это вы без гравицаппы пепелац выкатываете из гаража? Это непорядок...
Ion Tichy wrote: ↑31 Jan 2018 05:37
Но кстати даже с уже изобретенными велосипедами бывают приколы. Пример из меня. На очередном фейс-то-фейс дали задачку что-то типа разместить Н ящиков размеров Р1...РН по М складам вместимости В1...ВМ. Я даже дергаться не стал - "Робя, берете античные фортрановские либы с линейным програмированием и золотой ключик ваш" - "С каким програмированием?" - "С линейным. Методы оптимизации... Задача о комивояжере... Ничего вспыхивает в моске?..." - ...и тишина (с) Неуловимые. А такие кул хацкеры сидели-спрашивали
Смешно, конечно. Надо было в ответ спросить что вы будете делать когда эти античные либы антично загнутся при Н размером побольше.
(P.S. это камень не в ваш огород, а ответ на ваш вопрос зачем это спрашивают)
