Про те як мій знайоми пройшов співбесіду в Гугл

Одразу скажу – ні, це не я, це справді знайомий з яким ми недалеко сидимо одне від одного. Я поки йти нікуди не збираюся, але в майбутньому звісно усе можливо.

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

Звісно ми з ним обговорювали як проходив весь процес, що питали і таке інше. І я згадав що недавно тут у блозі мене питали як проходять інтерв’ю в американських софтверних компаніях, що питають, які вміння очікують. Отже можна знову трошки про це поговорити.

Перше що треба повторити це те що у великих компаніях типу Microsoft, Google, Amazon, тощо вас не беруть за те що ви добре знаєте якусь мову чи якийсь фреймворк. У якихось дуже окремих випадках вас можуть взяти за якісь специфічні знання типу вміння писати компілятори чи менеджер пам’яті в ОС. Але у більшості випадків компанії шукають просто розумних людей які б могли розв’язувати проблеми та знаходити рішення. Бо мови, фреймворки та проекти виникають і зникають, а продукти клієнтам треба продовжувати продавати.

Тому коли ви починаєте процес інтерв’ю з тим же гуглом то не очікуйте що у вас будуть питати знання хоч якоїсь мови чи технології (знову ж таки якщо ви не в команду компілятор/ядро/залізо йдете) і задачі які вам будуть давати можна розв’язувати будь-якою мовою якою вам зручно. Також дуже важливо те що це не процес прийнятий в гуглі в цілому – може бути що у кожної команди чи офіса свій процес, я просто переказую те що почув.

Так ось цей мій знайомий він переважно С++ програміст, місцями щось робив на Java, але ніколи її не вчив. Гумор ситуації в тому що співбесіда проходила в офісі в Кікрланді, а працювати він буде в іншому штаті де і буде його команда. І коли він питав які мови/інструменти і таке інше треба буде використовувати йому відповідали “а звідки ми знаємо? на місці і спитаєш”. Скоріше за все проте буде Java бо це внутрішній проект, ну та то таке. Це я до того щоб в черговий раз повторити що софтверні компанії які знають як писати софт і вміють це робити наймають людей не на задачу чи проект, а в компанію в цілому – тобто людей яких можна буде при необхідності використати будь-де.

Ну а тепер до самого інтерв’ю та питань.

Звісно спочатку було телефонне інтерв’ю де ХР задають питання по своїй якійсь внутрішній анкеті щоб відсіяти зовсім безнадійних. Ну може бути ще інтерв’ю з представником команди що наймає, але оскільки це телефонне інтерв’ю то там або писати код не треба взагалі, або писати щось дуже умовне у вікні чату. Для такого інтерв’ю треба знати основні алгоритми пошуку/сортування/обходу графу і структури даних як вектор, список, бінарне дерево, черга, стек, хеш-таблиця і так далі. Також треба розуміти що таке “О велике”, як воно вимірюється і що означає.

Після проходження телефонного інтерв’ю (називається “скріннінг” – screening) запрошують on site. Тепер інтерв’ю проходять в кімнатах з дошками де інтерв’юери дають задачі, а ви їх розв’язуєте. Усього відбувається 5 інтерв’ю по 45 хвилин кожне з перервою на обід та 15 хвилин відпочинку між зустрічами. За ці 45 хвилин треба зрозуміти задачу, задати уточнюючі питання, знайти рішення, написати його на дошці і обговорити додаткові питання стосовно рішення. Повторюся що оцінюють ваші вміння розв’язувати задачі в принципі і написання 100% працюючого коду не є гарантією найму. Краще не дописати щось чи написати умовно, але показати що ви на шляху до правильного рішення і розумієте усі недоліки, переваги та обмеження рішення яке пропонуєте.

Тепер безпосередньо до задач.

Перша задача така. У нас є сейф з кодом з чотирьох цифр. Кожна наступна введена цифра зміщує введену комбінацію на одну позицію вліво (тобто старша цифра втрачається). Перше питання – якої мінімальної довжини має бути послідовність цифр щоб гарантовано відкрити сейф? Ну тут треба зрозуміти що з наявного коду ми можемо взяти три останні цифри і додати до них четверту щоб утворилася нова комбінація. Тобто для 10000 можливих комбінацій нам треба усього 10003 цифри.

А друге питання – згенерувати таку послідовність. Тут думайте самі :)

Друга задача. Згенерувати лабіринт заданого розміру так щоб у нього був гарантований вхід і вихід і вони були б поєднані. Існує багато алгоритмів генерації лабіринтів, мабуть найпростіший буде модифікований пошук в глибину з поверненням до попередніх позицій (backtracking), щось типу такого – https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search. Якщо не хвилюватися і спокійно подумати то цей алгоритм можна “винайти” самостійно доволі швидко. Ну або можна уявити кожну позицію в лабіринті як вузол у дереві і почати будувати зв’язки між ними.

Третя задача. Реалізувати BigInt. Це такий тип даних де розмір числа не обмежений. Тобто треба скажімо створити клас, додати підтримку усіх арифметичних операції, конвертацію типів, конвертацію в/з рядка. Але додаткова вимога – реалізувати операцію додавання довільної кількості BigInt’ів (наприклад вектору) у найбільш ефективний спосіб. Теж нічого надзвичайного, але якщо ви знаєте якісь хитрощі цілочисельних операцій для якоїсь платформи то це дуже стане у нагоді і допоможе позитивно вразити інтерв’юера.

Четверта задача. Спроектувати архітектуру (ніякого кодінгу) сервісу обміну повідомленнями: клієнти, повідомлення що десь зберігаються і їх можна шукати і таке інше. Тобто усе включно з тим як і де зберігаються дані, як усе це передається та підтверджується, і усі інші нюанси про які можна подумати. Звісно тут є великий простір для обговорень усього що завгодно. До того ж таке питання показує область знань та інтересів кандидата. І мабуть як і в Microsoft четверте і п’яте інтерв’ю проводять лише якщо три попередні пройшли добре, хоча компанії кажуть що це не так :)

П’ята задача. Тут я не всі деталі зловив, але склалося таке враження що інтерв’ю це було вже не надто обов’язкове. Задача як така стосувалася внутрішнього представлення чисел типу double (мантиса, експонента, ну ви в курсі) та як можна реалізувати певні арифметичні операції з ними на платформі де нема підтримки такого формату “з коробки”. На цьому інтерв’ю той хто дав задачу пояснював усе включно з тим як числа представлено і як вони нормалізуються і просто треба було показати що розумієш як працювати з бітами та байтами та де можна зробити оптимізації.

Ну ось таке от :)

CppCon 2014

Короткий звіт про тиждень що я його провів на зльоті представників комітету зі стандартизації С++, розробників компіляторів та бібліотек, розробників що займаються оптимізацією коду та “промислових” представників галузі: розробників ігор, дослідників ведучих наукових закладів та представники найвідоміших компаній.

Усього було присутньо більше 600 людей. Щодня сесії на різні теми починалися 0 9 ранку, закінчувалися о 6 вечора з 2-годинною перервою на обід. О 8 вечора починалися воркшопи (класи) де можна було поговорити скажімо з авторами бібліотек boost, представниками комітету зі стандартизації С++ або іншими видатними людьми. Паралельно доповіді тривалістю в 1-1.5 години читалися у шести аудиторіях проіменаваних на честь видатних вчених: Паскаль, Ньютон, Ферма, Лейбніц, Декарт та Ейлер.

Цього року більшість доповідей було присвячено паралельному програмуванню (~80%) на відміну від попередніх років коли акцент робився на метапрограмування (шаблони).

Багато також говорили про новий стандарт С++14 в який увійде все те що було недороблено в С++11. А вже в С++17 буде багато нових змін які будуть підкориговані в С++20.

Ну і декілька речей які особисто мені запам’яталися.

Всюди auto

Сучасна рекомендація полягає в тому щоб використовувати auto де тільки можна. І суть в тому що це не лише коротший запис, але і безпечніший: скажімо при зміні типів в алгоритмах/інтерфейсах/структурах данних на відбувається прихованого приведення типів. Тому замість

for (list:const_iterator it = l.begin(); it != l.end(); ++it) {...use(*it);...}

В С++11 можна (і треба) писати

for (const auto& i: l) {...use(i);...}

А в С++14 стане можливим навіть

for (i: l) {...use(i);...}

Але авто-виведення корисне не лише для циклів та ітераторів, але і для лямбд, які за новим стандартом можуть повертати лямбди як результат:

auto plus = [](auto x){ retur [](auto y){ return x + y; } };
auto plus4 = plus(4);

auto s6 = plus4(2);
auto s10 = plus(4)(6);

Правила виведення типів

Через додання авто-виведення типів в мову довелося додати правила за якими це виведення відбувається. Усього цих правил більше 10 зараз і тим хто розробляє бібліотеки треба їх усі знати і розуміти дуже добре. І в цілому тенденція така що мова для тих хто пише біблітетеки мова стає складнішою і дозволяє робити тонкіші речі, а для тих хто користується бібліотеками мова навпаки стає простішою.

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

Нові рекомендації для програмістів:

  • для обов’язкових параметрів які не будуть змінюватися використовувати const &
  • для обов’язкових параметрів які будуть змінюватися використовувати &
  • для необов’язкових параметрів використовувати *
  • для оптимізаційних трюків і передачі прав володіння використовувати && та  std::move(). Але при цьому важливо на 100% розуміти що робиш бо такий код майже гарантовано вбиває всю оптимізацію яку міг би зробити компілятор.

 

Ніяких new/delete

Залиште new/delete людям які пишуть біблітотеки та аллокатори, почніть використовувати unique_ptr/shared_ptr. І не забувайте що unique_ptr є фактично безкоштовним і фактично це голий вказівник, але безпечний! А shared_ptr використовуйте коли у об’єкта може бути лише один власник.

Наприклад замість

widget* f();

void n(){
  widget* w = f();
  gadget* g = new gadget();
  use(*w, *g);
  delete g;
  delete w;
}

Треба писати

unique_ptr<widget> f();
void n(){
  auto w = f();
  auto g = make_unique>gadget>();
  use(*w, *g);
}

Небезпечний код

Це була довга доповідь з трьох частин що зайняла майже весь день і була присвячена тому як писати небезпечний код.

У короткому підсумку код

 

do_something();

cleanup();

Не є небезпечним через те що в ньому ніяк не перехоплюються та не оброблюються виключення і не даються гарантії що алоковані ресурси буде звільнено у правильному порядку. Із застосуванням методіки RAII (Resource Acquisition Is Initialization) небезпечний код має виглядати так:

do_something();

Досягається це дотриманням простих правил:

  • конструктор ніколи не кидає виключення та не викликає код який може кинути виключення само собою
  • так само і деструктор ніколи не кидає виключення
  • оператор присвоєння ніколи не кидає виключення і має бути транзакційним. Досягається це створенням тимчасового об’єкту який і ініціалізують як копію, а потім просто замінюють, щось типу такого:
class A {
  A& operator=(const A& a)
  {
    A tmp(a);
    using std::swap;
    swap(tmp);
    return *this;
}

До речі звернічть увагу що swap рекомендується використовувати саме так і не викликати std::swap() на випадок якщо swap() перевантажено для типу.

Ну і взагалі там неймовірно багато усього було. Наприклад розбір того чому код

f(shared_ptr(new A()), shared_ptr(new B());
}

є небезпечним. Ось тут https://github.com/CppCon/CppCon2014/blob/master/Presentations/Exception-Safe%20Code/Exception-Safe%20Code%20-%20Jon%20Kalb%20-%20CppCon%202014.pdf?raw=true файл з усіма слайдами з цієї доповіді.

С++ на Марсі

Виступав ведучий програміст проекту Куріосіті (http://mars.jpl.nasa.gov/msl/) і розповідав в основному те як працює система руху цієї машини. Той С++ що вони там використовують це дуже порізана мова: нема шаблонів, виключень, потоків, множинного успадкування, перевантаження операторів, тощо.

У них там кожна підсистема незалежна і продубльована. Наприклад система руху на останньому марсоході побудувана на платі з процесором PowerPC RAD750 (133 MHz), має 128 Мб пам’яті, використовує ОС VxWorks. В цій ОС є пакетна обробка задач і розділена пам’ять, тому вони написали свій менеджер пам’яті.

Взагалі цікаво що 4 з 19 камер марсоходу належать системі руху (по 2 на кожен комп’ютер) і використовуються майже як людина використовує очі. Максимальна швидкість складає 1.5 см на секунду, але після цього треба зупинитися, зробити стерео-фото двома камерами, розбити катринку на сітку врахувавши перспективу і оцінити кожну клітинку після чого вибрати оптимальний/найнебезпечніший маршрут. Прикол ще в тому що колеса можуть або крутитися, або повертати, одночасно і те і інше не можливо робити. За день марсохід може зробити максимум 100 метрів.

Прикольні баги там у них. Наприклад коли машинці довірили самостійно проїхати кілька десятків метрів вона зупинилася і відмовилася їхати далі тільки коли прокручування (сковзання) колес перевищило допустимий показник. З’ясувалося що заїхали в пісчану дюну і наступні 2 місяці витратили щоб вручну вивести машину з ловушки (так, кожну команду відсилали на Марс окремо). Тобто за 2 місяці щоденної роботи проїхали назад 20 метрів.

Ну і був у них там якийсь баг з пам’яттю через який комп’ютер почав перевантажуватися невпинно. На той момент коли баг знайшли і пофіксали Марс сховався за Сонцем і довелося чекати кілька місяців доки з’явиться пряма видимість Smile

 

С++ в іграх

Представники галузі говорили в основному про оптимізацію коду і на кожен слайд з С++ кодом у них було по 3-5 слайдів з асемблером. Всякі хитрі трюки оптимізації що вимагають знання принципів роботи заліза і таке інше.

Але ось вам кілька цікавих фактів: в коді Assassin’s Creed 6.5 мільйонів (!) рядків коду на С++ самої гри плюс 9 мільйонів рядків С++ інструментів (це різні редактори, пакувальники і таке інше) та 5 мільйонів рядків на С#. При цьому в коді гри нема RTTI, виключень, шаблонів (ні STL, ні boost).

 

Кілька нових фіч

Це все або ось-ось з’явиться, або вже підтримується деякими компіляторами (читайте у вікіпедії подробиці):

  • constexpr  дозволяють писати код який виконується в процесі компіляції.
  • бар’єри пам’яті (дуже складна тема сама по собі) неймовірно спрощують написання програм у паралельному стилі і є набагато дешевшими за синхронізацію: lock_guard, conditional_variable, atomic, compare_exchange_weak/compare_exchange_strong. Про це все треба читати, воно не те щоб складне, але треба якісь приклади писати для пояснення.
  • atomic<T> можна буде використовувати для shared_ptr. Звучить це як щось звичайне, але насправді така підтримка дозволить уникнути багатьох проблем у реалізації lock-free алгоритмів та значно скоротити і спростити код.
  • обмеження шаблонів – можна буде вказати що шаблон чи функція призначені, наприклад, лише для колекцій які можна сортувати:
template<typename S, typename T>

requires Sequence<S> &&

  Sortable<S> &&

  Equality_compare<Value_type<S>, T>

Iterator<S> sort(S& seq);
...
sort(vector{ 5, 4, 1 }); //Ok
sort(list{5, 4, 1 }); // Error: not Sortable

Ну або скоротити все це до

auto sort(Sortable& seq);

Можна буде писати свої обмеження якось ось так:

 

requires(C x){ { f(x)} –> int }

що означає “має бути можливим викликати функцію f для об’єкту типу С і потім привести результат до типу int”.

Зараз комітет працює над визначенням списку стандартних обмежень.

 

Звісно при всьому бажанні я не можу переказати всього що там було, ось вам кілька посилань щоб почитати самостійно:

  • відеозаписи доповідей буде викладено на http://cppcon.org/. Якщо ви будете дивитися усього по 2 доповіді на тиждень то якраз завершите перегляд перед початком CppCon 2015
  • слайди презентацій доступні на https://github.com/CppCon/CppCon2014
  • Книга Effective Modern C++ добре описує всі нововведення та механізми С++ – http://shop.oreilly.com/product/0636920033707.do
  • Нова книга Страуструпа дуже коротко описує сучасний С++ усього на 180 сторінках (офіційний опис стандарту мови зараз складає понад 800 сторінок) – http://www.stroustrup.com/Tour.html

Баг що призвів до зависання Zune 30

Zune 30 – перше покоління MP3-плеєрів від Microsoft. Випускалися пристрої з 2006 року, а у 2011 випуск усієї лінійки припинився. Усього було 4 покоління: 1) Zune 30, 2) Zune 4, 8, 80, 3) Zune 16, 120, 4) Zune HD.

Баг про який йде мова був лише в коді Zune 30.

Сам код:

year = ORIGINYEAR; /* = 1980 */

while (days > 365)
{
    if (IsLeapYear(year))
    {
        if (days > 366)
        {
            days -= 366;
            year += 1;
        }
    }
    else
    {
        days -= 365;
        year += 1;
    }
}

Цей код як бачите вираховує рік на основі лічильника днів (лічильник починається з 1/1/1980).

Тепер слідкуємо за руками.

Уявимо що у нас останній день 2008-го року:

  1. У рядку 3 код перевіряє кількість днів, умова виконується (366 > 365)
  2. У рядку 5 функція IsLeapYear() повертає true бо 2008 високосний рік
  3. Умова у рядку 7 не виконується (366 > 366)
  4. Переходимо до рядка 3

Ну от ми і в нескінченному циклі!

Таким чином усі пристрої у першу секунду 2009-го року перетворилися на тикви, тобто перестали реагувати на будь-що.

Справедливості заради треба сказати що це був код не Microsoft, а Freescale – драйвер для їхнього годинника. Були і інші пристрої що зловили точно таку ж проблему, наприклад медіа-плеєр від Toshiba. Інші моделі Zune мали інший чіп і там цієї проблеми не виникло.

Офіційно рекомендованим способом вирішити проблему було розрядити остаточно батарею і поставити пристрій на зарядку (таким чином 1 січня 2009-го було б 367-мим днем якщо рахувати від 1/1/2008).

Тренінг Windows OS Internals

П’ять днів у несамовитому темпі – інформація про “як воно там зроблено всередині”, про те які зміни були від версії до версії (Windows NT 4, XP, 2000, 2003, Vista/2008, 7/2008 R2). Перемикання між windbg, Process Explorer, Process Monitor та ще парою десятків інструментів… Доволі виснажливо треба сказати.

Обсяг інформації такий що ідея запам’ятатизаписати усе відпадає в перший же день – усим цим треба користуватися щодня, запам’ятовувати сенсу нема. Добре що на всих тренінгах видають роздруковані матеріали зі змістом курсу до яких потім можна звернутися коли знадобиться.

В цілому вражає які дива можна творити умілими руками використовуючи начебто давно знайомі інструменти.

По суті весь курс є швидким і стислим викладенням книги Windows Internals (http://technet.microsoft.com/en-us/sysinternals/bb963901). Але таку товстелезну і не саму легку для читання книгу навряд чи хто подужає за тиждень. Тим більше що останнє 6-те видання взагалі у двох томах – перший щойно вийшов, другий з’явиться у продажу в найближчий час.

Курс покриває такі теми як: інструменти, загальна архітектура ОС, архітектура ядра, процеси і потоки, пам’ять, системні об’єкти, безпека та аналіз крешів. Взагалі програмування ніякого – тобто жодного написаного рядка коду. Тут все навпаки – у нас вже є весь написаний і скомпільований код і треба розібратися що, де і чому йде не так.

Власне через цей тренінг я нічого і не писав останні дні. Ну та з наступного тижня продовжу Smile

.NET Multithreading

Оце на такий цікавий тренінг я зараз ходю – 2 повні дні, веде Джефрі Ріхтер. Дуже, просто надзвичайно цікаво!

Розказує він просто заслухаєшся. Саме цінне що не просто технічна інформація яку в документації можна знайти, а чому саме так свого часу зробили, до яких проблем це приводило, і як їх вирішували.

Головні поради і висновки: можеш писати однопоточно – так і роби, уникай синхронізації, уникай створення нових потоків (реюзай старі), уникай синхронних операцій. І знову ж таки усе з прикладами коду.

Сильно дістається критики і Windows, і Офісу, і деяким іншим. Дуже хвалить .Net і в захваті від WinRT (нова версія WIN API для Windows 8).

Всьо, похвалився Smile

Gale Laakhman. Cracking the coding interview

 

Авторка працювала програмістом у головних компаніях софтверної індустрії – Microsoft, Apple, Google, Yahoo та Amazon, а також у декількох менш відомих компаніях.

 

Книга по суті є задачником (з рішеннями) питань які найбільше зустрічаються на інтерв’ю в перелічені компанії. Задачі поділені на групи (рядки, списки, математика, многопоточність, головоломки, тощо).

 

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

 

Хороша книга коротше.

 

І у авторки зараз своя компанія яка займається кар’єрою програмістів – http://www.careercup.com/. На сайті є обговорення різних задачок і рішень, сервіси щодо покращення резюме та імітації процесу інтерв’ювання.