Cracking the coding interview - study group, East Bay

[Andriy777]

Binary _search_ tree => keys are distinct?

Вот так можно написать, чтобы понятней было:

Code: Select all

int num_bst(int n_keys) {
    assert(n_keys >= 0);
    if (n_keys == 0 || n_keys == 1) {
        return 1;
    }
    int n = 0;
    for (int n_left = 0; n_left < n_keys; n_left++) {
        int n_right = n_keys - 1 - n_left;
        n += num_bst(n_left) * num_bst(n_right);
    }
    return n;
}

А чтобы быстро работало - нужно итеративно заполнить массив от 0 до n_keys, чтобы num_bst(n) считалось всего один раз для кажлого n - классическое динамическое программирование.

Чота не знаю... Наверное, я сегодня тупой. Вроде и логика понятна, но интуитивно кажется неверной.

В любом случае, спасибо, есть над чем подумать

Интересно также, что интервьюер принимает как "проходной бал".

а) Интересные мысли на доске от человека, который в первый раз думает над такой проблемой (включая, а нафига это надо и почему оценка "дофига" не достаточна).

б) Человек математик, знает про числа Каталана и как это все доказать.

в) Человек читал недавно (давно) и просто знает ответ.

г) Отвечает "да ну его нафиг эту комбинаторику" и пишет код, как показан выше.

Анекдот в тему. На границе США офицер О опрашивает приезжего P.

O: So you are arriving on H1-B visa as a software engineer, right?

P: Yes, sir.

O: Can you tell me how many edges are in a tree with N nodes?

P: Can I use StackOverflow.com?

O: Welcome to the United States!

Честно говоря, я не уверен, что понял, что вы имели в виду. Но так кажется релевантным. Я как-то спрашивал на интервью молодого американца, как узнать, есть ли цикл в односвязном списке. Заранее абиснил, что если не знаешь ответа, то вряд ли допетришь сам, в рамках интервью как минимум. Он честно сказал, что ответ просто знает. Я секунд через 15 прервал его, было очевидно, что реально знает.

Глупость? Может быть. Но лично мне сказало о многом

Имелось ввиду, что ожидалось для именно этого вопроса. Код как предоставил Mr. R или математическое решение. Я про этот вопрос прочитал в 11 вечера вчера. Подумав 10 мин. решил, что не стоит оно бессонницы. Спросил у Wiki и там все написано . Математически.

[АццкоМото]

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

Я не понимаю этот язык, извините.

[Sergunka]

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

Я не понимаю этот язык, извините.

На самом деле вопрос довольно нетривиальный и имеет даже свое имя Числа Каталана

http://www.geeksforgeeks.org/g-fact-18/

С вот такой козырной картинкой

https://en.wikipedia.org/wiki/Catalan_n ... ions_5.svg

[АццкоМото]

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

Я не понимаю этот язык, извините.

На самом деле вопрос довольно нетривиальный и имеет даже свое имя Числа Каталана

http://www.geeksforgeeks.org/g-fact-18/

С вот такой козырной картинкой

https://en.wikipedia.org/wiki/Catalan_n ... ions_5.svg

Йопта, картинку можно использовать вместо слабого раствора перманганата калия для промывания желудка. Я с минуту разглядывал, а уже немного укачало. Сила мысли же!

[Alexander Troyansky]

Даже для неунылой групповушки маловато будет.

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

Для mock-interview вроде как нужно минимум два человека. Зато в списке отсутствует "рассмотрение лажовых примеров решений". Листал я ту книженцию, так вот пара решений мне показались весьма сомнительными.

А не помните, какие решения показались сомнительными...

значицца посмотрел я ту книжонку. Например, на странице 58-60, особенно в секции Error checking, аффтар рассказывает, как это важно проверять на ошибочный входные данные во время интервью при кодировании - с чем лично я согласен и с чем некоторые форумчане не согласны. Однако ж возврат "-1" в качестве ответа на ошибочный вход несколько удручает. Я уже не говорю про то, что банальные проверки на переполнение не производятся.

На странице 417, в качестве ответа на вопрос, заданный на странице 160 "You are given a class with synchronized method A and normal B..." -- даётся ответ, который на мой взгляд неполный в контексте демонстрации понимания темы на фоне неоднозначного вопроса: аффтар обисняет, что оказывается синхронизированные методы могут выполняться одновременно двумя потоками на разных объектах. Ну блин тогда следовало бы тему немного развить для статических методов.

Ещё одно сомнительное место, не запомнил страницу, кажется, в начале главы 14 Multi-threading, приведен пример проверка переменной, изменяемой в другом потоке, но синхронизация (ну там volаtile или Atomic) в примере не используется.

[АццкоМото]

Даже для неунылой групповушки маловато будет.

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

Для mock-interview вроде как нужно минимум два человека. Зато в списке отсутствует "рассмотрение лажовых примеров решений". Листал я ту книженцию, так вот пара решений мне показались весьма сомнительными.

А не помните, какие решения показались сомнительными...

значицца посмотрел я ту книжонку. Например, на странице 58-60, особенно в секции Error checking, аффтар рассказывает, как это важно проверять на ошибочный входные данные во время интервью при кодировании - с чем лично я согласен и с чем некоторые форумчане не согласны. Однако ж возврат "-1" в качестве ответа на ошибочный вход несколько удручает. Я уже не говорю про то, что банальные проверки на переполнение не производятся.

На странице 417, в качестве ответа на вопрос, заданный на странице 160 "You are given a class with synchronized method A and normal B..." -- даётся ответ, который на мой взгляд неполный в контексте демонстрации понимания темы на фоне неоднозначного вопроса: аффтар обисняет, что оказывается синхронизированные методы могут выполняться одновременно двумя потоками на разных объектах. Ну блин тогда следовало бы тему немного развить для статических методов.

Ещё одно сомнительное место, не запомнил страницу, кажется, в начале главы 14 Multi-threading, приведен пример проверка переменной, изменяемой в другом потоке, но синхронизация (ну там volаtile или Atomic) в примере не используется.

Примерно понятно, спасибо. У нас страницы не совпадают, к сожалению, под рукой только бумажное 6е издание. Кстати, скорей всего такие мелкие недочеты отлавливаются и исправляются в следующих изданиях. Все-таки книжка по размеру подходит для засолки капусты и просто не может в ней все быть идеально.

А нащот проверок - я обычно пишу сначала код без них, потом говорю, каких проверок не хватает и спрашиваю, добавить ли. Очень, кстати, порадовал последний ассессмент на кодилити - только начал было добавлять проверки, перечитываю assumptions about input data - yay! вообще ни одна проверка не нужна.

С мультитредингом тоже забавный случай был на днях. Русскоговорящий чел дает код, что-то очень простое, тупая манипуляция со списком. один метод по сути и main(), который его вызывает несколько раз с разными параметрами. Типа надо найти ошибки. Одна - очевидная. Он говорит - еще есть. Чесал жбан, чесал - ничего не вижу больше. Он такой - а ConcurrentModificationException тебе о чем-то говорит? Я такой - помилуйте, метод синхронно вызывается из main() никакого мультитрединга тут нет и быть не может. Он такой - не факт. Следующий вопрос

[Сабина]

жутко извиняюсь, тока прочла сообщения.

[8K]

Посмотрел 6-е издание. Некоторые ошибки в коде реально тупые. Часть примеров, похоже, надергана из реальных проектов и не до конца причесана.

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

[Sergunka]

Посмотрел 6-е издание. Некоторые ошибки в коде реально тупые. Часть примеров, похоже, надергана из реальных проектов и не до конца причесана.

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

Собственно говоря я не увидел в этой книжке ни одного эллегантно написаного примера (правда у меня уж совсем старое издание 5-е) Особую печаль вызвала секция по заяснению как писать программу для игры Ханойская Башня. Я понимаю, что когда Николас Вирт написал и опубликовал свой незамысловатый алгоритм

Code: Select all

   public void solve(int n, String start, String auxiliary, String end) {
       if (n == 1) {
           System.out.println(start + " -> " + end);
       } else {
           solve(n - 1, start, end, auxiliary);
           System.out.println(start + " -> " + end);
           solve(n - 1, auxiliary, start, end);
       }
   }

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

В пятом издании насколько я помню хвостовая рекурсия для чисел фиббоначи не раскрыта, что должно повергнуть ТС в смертельную тоску

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

[nyekimov]

Чота никак не могу нарыть, бывает электронный формат издания cracking the coding interview? На Амазон только бумажный вариант вижу, среди для kindle вижу издание для пм от этого автора. На каких то левых сайтах продают якобы пдф за 5$. Но попахивает разводом.

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

[8K]

Чота никак не могу нарыть, бывает электронный формат издания cracking the coding interview?

Бывает, бывает. В Греции все бывает: 4-е издание.

Потолще и посвежее ищите на либгене: 6-е издание.

[АццкоМото]

Да какие там два килограмма. 1364 грамма.

[nyekimov]

Да какие там два килограмма. 1364 грамма.

Так измерять лень, я на глаз. И ещё есть introduction to algorithms. Так как я хоть и молодой, но теорию уже не помню, первый курс таки давно был. А две книги в мой небольшой рюкзак тупо по толщине не влезут.

[АццкоМото]

Да какие там два килограмма. 1364 грамма.

Так измерять лень, я на глаз. И ещё есть introduction to algorithms. Так как я хоть и молодой, но теорию уже не помню, первый курс таки давно был. А две книги в мой небольшой рюкзак тупо по толщине не влезут.

А что, с утра решить, какую из двух книг сегодня в метрЕ читать — не?

[nyekimov]

Да какие там два килограмма. 1364 грамма.

Так измерять лень, я на глаз. И ещё есть introduction to algorithms. Так как я хоть и молодой, но теорию уже не помню, первый курс таки давно был. А две книги в мой небольшой рюкзак тупо по толщине не влезут.

А что, с утра решить, какую из двух книг сегодня в метрЕ читать — не?

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

[valchkou]

Да какие там два килограмма. 1364 грамма.

Так измерять лень, я на глаз. И ещё есть introduction to algorithms. Так как я хоть и молодой, но теорию уже не помню, первый курс таки давно был. А две книги в мой небольшой рюкзак тупо по толщине не влезут.

А что, с утра решить, какую из двух книг сегодня в метрЕ читать — не?

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

о что книги в электронном виде уже не модно? отстал я от жизни

[Херовимчик]

о что книги в электронном виде уже не модно? отстал я от жизни

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