Re: Вопросы на собеседовании (в очередной раз)
От: turbocode  
Дата: 10.04.17 10:21
Оценка:
M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
M>Мне: Нет, и так много времени потратили.
M>Ну, и вообще, всё норм с собеседованием?

Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
Re[5]: Вопросы на собеседовании (в очередной раз)
От: Silver_S Ниоткуда  
Дата: 10.04.17 10:41
Оценка:
Здравствуйте, ·, Вы писали:

M>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы

·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
Отредактировано 10.04.2017 10:42 Silver_S . Предыдущая версия .
Re: Вопросы на собеседовании (в очередной раз)
От: Silver_S Ниоткуда  
Дата: 10.04.17 10:59
Оценка:
Здравствуйте, Marty, Вы писали:

M> Здравствуйте!


M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.


M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)

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

Может он тупо чего-то примитивное в инете вычитал. Google что-то выдает про проблемы:
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Можно заметить, что F(3) вычисляется три раза. Если рассмотреть вычисление F(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений.

Re[2]: Вопросы на собеседовании (в очередной раз)
От: Marty Пират  
Дата: 10.04.17 11:05
Оценка:
Здравствуйте, turbocode, Вы писали:

M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?

M>>Мне: Нет, и так много времени потратили.
M>>Ну, и вообще, всё норм с собеседованием?

T>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.


Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть
Вам как-бы показали сцыкливое мурло российской оппозиции — вот оно
Автор: Министр Промышленности
Дата: 17.10.19
!
Re[6]: Вопросы на собеседовании (в очередной раз)
От: · Великобритания  
Дата: 10.04.17 11:08
Оценка:
Здравствуйте, Silver_S, Вы писали:

M>>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы

S_S>·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
S_S> Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
На практике я бы при таких требованиях плавучку бы и не использовал — во избежание.

Но это я так... в качестве этюда интересуюсь — возможно ли. Например, отсортировать оба массива по убыванию, а потом сделать алгоритм напоминающий sorted merge join — брать и прибавлять элементы первого или вычитать элементы второго массивов в зависимости от знака текущей суммы. Сработает?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[3]: Вопросы на собеседовании (в очередной раз)
От: turbocode  
Дата: 10.04.17 11:14
Оценка:
T>>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
M>Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть

"солдат спит служба идет" — игра на собеседовании в одни ворота это всегда провал.
Re[7]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 19:19
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.


Я взял в качестве дерева просто LinkedList<int> из .Net :D
Складываем элементы списка.
Тестировал итеративный алгоритм и два варианта рекурсии. Собиралось все с таргетом x86.
Результаты у меня такие:
Started!
Iterative: 38 ms, recursiveSimple: 80 ms, recursiveAcc: 92 ms


  Код
    class Program
    {
        static void Main(string[] args)
        {
            var runner = new Thread(Run, 1000 * 1024 * 1024);
            runner.Start();
            runner.Join();
        }

        static void Run()
        {
            var T = new Stopwatch();

            var src = Generate(10);

            SumIterative(src.First);
            SumRecursiveSimple(src.First);
            SumRecursiveAcc(src.First);

            src = Generate(10000000);

            Console.WriteLine("Started!");

            int count = 100;

            var iterative = 0l;
            var recursiveSimple = 0l;
            var recursiveAcc = 0l;

            for (int i = 0; i < count; i++)
            {
                T.Restart();
                SumIterative(src.First);
                T.Stop();

                iterative += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveSimple(src.First);
                T.Stop();

                recursiveSimple += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveAcc(src.First);
                T.Stop();

                recursiveAcc += T.ElapsedMilliseconds;
            }

            Console.WriteLine($"Iterative: {iterative/count} ms, recursiveSimple: {recursiveSimple/count} ms, recursiveAcc: {recursiveAcc/count} ms");
        }

        static LinkedList<int> Generate(int size)
        {
            var r = new LinkedList<int>();
            var random = new Random();

            for (int i = 0; i < size; i++)
            {
                r.AddLast(random.Next());
            }

            return r;
        }

        static int SumIterative(LinkedListNode<int> e)
        {
            var r = 0;
            for (var curr = e; curr != null; curr = curr.Next)
                r += curr.Value;

            return r;
        }

        static int SumRecursiveAcc(LinkedListNode<int> e, int curr = 0)
        {
            if (e == null)
                return curr;

            return SumRecursiveAcc(e.Next, e.Value + curr);
        }

        static int SumRecursiveSimple(LinkedListNode<int> e)
        {
            if (e == null)
                return 0;

            return e.Value + SumRecursiveAcc(e.Next);
        }
    }
Re[8]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 10.04.17 19:41
Оценка: +1
Здравствуйте, StatujaLeha, Вы писали:

SL>
SL>        static int SumRecursiveSimple(LinkedListNode<int> e)
SL>        {
SL>            if (e == null)
SL>                return 0;

SL>            return e.Value + SumRecursiveAcc(e.Next); /// Вызван не тот метод
SL>        }
SL>


А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.
Re[9]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 19:53
Оценка:
Здравствуйте, samius, Вы писали:

Пофиксил.
Результаты:
Iterative: 39 ms, recursiveSimple: 138 ms, recursiveAcc: 84 ms

  Код
    class Program
    {
        static void Main(string[] args)
        {
            var runner = new Thread(Run, 1000 * 1024 * 1024);
            runner.Start();
            runner.Join();
        }

        static void Run()
        {
            var T = new Stopwatch();

            var src = Generate(10);
            SumIterative(src.First);
            SumRecursiveSimple(src.First);
            SumRecursiveAcc(src.First);

            src = Generate(10000000);

            Console.WriteLine("Started!");

            int count = 100;

            var iterative = 0l;
            var recursiveSimple = 0l;
            var recursiveAcc = 0l;

            for (int i = 0; i < count; i++)
            {
                T.Restart();
                SumIterative(src.First);
                T.Stop();

                iterative += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveSimple(src.First);
                T.Stop();

                recursiveSimple += T.ElapsedMilliseconds;

                T.Restart();
                SumRecursiveAcc(src.First);
                T.Stop();

                recursiveAcc += T.ElapsedMilliseconds;
            }

            Console.WriteLine($"Iterative: {iterative/count} ms, recursiveSimple: {recursiveSimple/count} ms, recursiveAcc: {recursiveAcc/count} ms");
        }

        static LinkedList<int> Generate(int size)
        {
            var r = new LinkedList<int>();
            var random = new Random();

            for (int i = 0; i < size; i++)
            {
                r.AddLast(random.Next());
            }

            return r;
        }

        static int SumIterative(LinkedListNode<int> e)
        {
            var r = 0;
            for (var curr = e; curr != null; curr = curr.Next)
                r += curr.Value;

            return r;
        }

        static int SumRecursiveAcc(LinkedListNode<int> e, int curr = 0)
        {
            if (e == null)
                return curr;

            return SumRecursiveAcc(e.Next, e.Value + curr);
        }

        static int SumRecursiveSimple(LinkedListNode<int> e)
        {
            if (e == null)
                return 0;

            return e.Value + SumRecursiveSimple(e.Next);
        }
    }


S>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.


Да, согласен. Но есть надежда на JIT-compiler.
Ну и разница во времени работы между двумя алгоритмами есть.
Re[10]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 10.04.17 20:40
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:


S>>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.


SL>Да, согласен. Но есть надежда на JIT-compiler.

Нету, т.к. надежда JIT-compiler-а — OpCode.Tailсall. А без него он делать ничего сам не будет.

SL>Ну и разница во времени работы между двумя алгоритмами есть.


вот разница у меня

Iterative: 17 ms, recursiveSimple: 31 ms, recursiveAcc: 33 ms
FSharp: 17 ms


где
module FsModule1

    let rec sumRec (n : System.Collections.Generic.LinkedListNode<int>) sum =
        if obj.ReferenceEquals(n, null) then sum
        else sumRec n.Next (sum + n.Value)
Re[11]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 10.04.17 20:51
Оценка:
Здравствуйте, samius, Вы писали:

Ясно.
Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
Пример же с обходом полноценного дерева лень делать.
Re[12]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 10.04.17 20:59
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:


SL>Ясно.

SL>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
А разве есть другие?
Re[11]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 10.04.17 21:41
Оценка:
Здравствуйте, ·, Вы писали:


·>Бред, дело не в рекурсии, а в алгоритме. Без рекурсии тоже можно тупой алгоритм написать. А вот рекурсия без "промежуточных" результатов:

·>
·>int fib(int term, int val = 1, int prev = 0)
·>{
·> if(term == 0) return prev;
·> if(term == 1) return val;
·> return fib(term - 1, val+prev, val);
·>}
·>


Да, как раз то что я просил сделать. Хорошее решение, с передачей через стек промежуточных результатов (через val).
Re[11]: Вопросы на собеседовании (в очередной раз)
От: Iso12  
Дата: 10.04.17 22:08
Оценка:
Здравствуйте, landerhigh, Вы писали:


I>>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.


L>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.

То что я просил сделать, сделали вот здесь
Автор: ·
Дата: 09.04.17
.

В вашем коде:
return fibonacci(index - 1) + fibonacci(index - 2);

Код, который привёл ".":
return fib(term - 1, val+prev, val);

разницу видно?

I>>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.

L>Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.
Я только повторил ваш тезис, с которым я согласился. Все претензии по декламированию только к себе.

I>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.


L>Ошибку исправил.

После этого примера
Автор: ·
Дата: 09.04.17
, пожалуй соглашусь.
Re[10]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 10.04.17 22:10
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Ну и разница во времени работы между двумя алгоритмами есть.


Что доказывает, что при должном рвении все, что угодно можно сделать через одно место

А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.
www.blinnov.com
Re[12]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 10.04.17 22:25
Оценка:
Здравствуйте, Iso12, Вы писали:

L>>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.

I>То что я просил сделать, сделали вот здесь
Автор: ·
Дата: 09.04.17
.


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

I>В вашем коде:

I>
I>return fibonacci(index - 1) + fibonacci(index - 2);
I>


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

I>>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.

L>>Ошибку исправил.
I>После этого примера
Автор: ·
Дата: 09.04.17
, пожалуй соглашусь.


Числа Фибоначчи — просто такой странный пример, когда определение понятия является определениеам алгоритма, который можно один-в-один перенести в реализацию и оно даже будет работать. Но определение не обязано быть ни алгоритмом, ни оптимальным алгоритмом.
www.blinnov.com
Re[13]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 11.04.17 19:24
Оценка:
Здравствуйте, samius, Вы писали:


S>А разве есть другие?


В смысле? Возможны ли алгоритмы, где нельзя tail-call?
В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
Re[11]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 11.04.17 20:34
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Что доказывает, что при должном рвении все, что угодно можно сделать через одно место


Само собой, это ничего не доказывает.

Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.
И именно поэтому это что-то доказывает.

А фраза "все, что угодно можно сделать через одно место" — это вода

В моем примере используется стандартный контейнер из широко используемого фреймворка.
Выбранная задача проще некуда.
Реализации тоже проще некуда.

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

L>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.


Так ждем

Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).
Сначала можно рекурсивно, а потом, так и быть, итеративно.
И даже больше! Можно сначала итеративно, а потом рекурсивно! :D
Re[12]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 11.04.17 21:20
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Само собой, это ничего не доказывает.


Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.

SL>Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.

SL>И именно поэтому это что-то доказывает.

SL>А фраза "все, что угодно можно сделать через одно место" — это вода


Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.

SL>В моем примере используется стандартный контейнер из широко используемого фреймворка.

SL>Выбранная задача проще некуда.

И бессмысленнее тоже некуда

SL>Буду рад хоть какому-то подтверждению указанных слов.


Каких именно?

L>>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.

SL>Так ждем

Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).

SL>Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).


Да, а змея — это частный случай крокодила.
www.blinnov.com
Re[14]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 12.04.17 06:33
Оценка: +1
Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, samius, Вы писали:



S>>А разве есть другие?


SL>В смысле? Возможны ли алгоритмы, где нельзя tail-call?

Угу
SL>В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
SumRecursiveSimple — это не алгоритм, а частная реализация. Алгоритмом здесь является что-то вроде "значение каждого элемента списка прибавить к результирующей сумме". Таким образом, SumRecursiveSimple, SumRecursiveAcc, ... ForeachSum, AggregateSum, ParallelForSum — формы записи одного алгоритма. Способы обхода и итерирования — специфичные особенности каждой реализации. И среди всех способов записи обязательно (на сколько я понимаю) найдется рекурсивная с потенциальной возможностью tail-call оптимизации. В данном случае такой является SumRecursiveAcc.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.