Це одна з тих задач які дає на своїх співбесідах google. А я знаю про неї тому що один мій знайомих ходив до них на співбесіду і отримав саме таку задачу.

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

Отже…

Задача

У нас є сейф який відкривається 4-значним набором з цифр від 0 до 9. Кожна нова введена цифра зсовує вже введений набір на одну позицію вліво – тобто послідовність 1234567 означає що було введено комбінації 1234, 2345, 3456, та 4567.

Треба реалізувати алгоритм який будує найкоротший рядок в якому були б усі можливі комбінації для відкриття сейфу.

Рішення

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

Щодо генерації комбінації моє рішення виглядає наступним чином:

  1. Для будь-якої початкової комбінації (візьмемо 0000 для простори) позначаємо її як використану і встановлюємо лічильник використаних комбінації в 1.
  2. Якщо знайдено всі комбінації – закінчити.
  3. До останніх трьох цифр згенерованої послідовності додаємо цифру від 0 до 9.
  4. Якщо знайдено комбінацію яку ще не використовували то позначаємо її і збільшуємо лічильник комбінацій на 1, переходимо на крок 2.
  5. Не вдалося знайти не використану комбінацію –  то беремо останні 4 цифри послідовності, знімаємо позначку з відповідної комбінації і зменшуємо лічильник комбінацій на 1. Далі збільшуємо останню цифру до 9.
  6. Якщо знайдено комбінацію яку ще не використано – позначаємо її, збільшуємо лічильник на 1, переходимо на крок 2.
  7. Не вдалося знайти не використану комбінацію і треба повертнутися ще на крок назад. Прибираємо останню цифру з послідовності (послідовність стає коротшою – вертання) і переходимо на крок 5.

Вище наведений алгоритм є алгоритмом з веранням коли ми для знайдення рішення маємо відміняти деякі раніше зроблені кроки. Інший приклад алгоритма з вертанням – задача про генерацію лабіринту.

Ну а тепер моя реалізація.

#include <assert.h>

#include <iostream>
#include <map>
#include <set>

using namespace std;

// Функція знаходить ще не використану комбінацію для останніх трьох цифр поточної послідовності
// і повертає true якщо таку комбінацію вдалося знайти.
// lastDigitStart - з якої цифри починати пошук останньої цифри.
// lastSequence - поточна остання комбінація.
// sequenceUsed - ознака чи використано вже комбінацію (сама комбінація і є індексом).
// sequence - згенерована послідовність.
// idx - індекс нової цифри у згенерованій послідовності.
bool findNewLastDigit(int lastDigitStart, int& lastSequence, bool *sequenceUsed, int* sequence, int& idx)
{
  int lastDigit = lastDigitStart;
  for (int newSequence = (lastSequence % 1000) * 10 + lastDigit; lastDigit <= 9; ++lastDigit, ++newSequence)
  {
    if (!sequenceUsed[newSequence])
    {
      sequenceUsed[newSequence] = true;
      sequence[idx++] = lastDigit;
      lastSequence = newSequence;
      return true;
    }
  }

  return false;
}


// Сам алгоритм.
// sequence - сюди буде записано знайдену послідовність.
void generateSequence(int* sequence)
{
  // позначаємо усі можливі комбінації як ще не використані
  bool sequenceUsed[10000] = { false };

  // перша комбінація у послідовності - 0000
  sequence[0] = sequence[1] = sequence[2] = sequence[3] = 0;
  sequenceUsed[0] = true;

  int foundSequences = 1; // усього знайдено комбінацій

  int lastSequence = 0; // остання знайдена комбінація

  for (int idx = 4; foundSequences < 10000;)
  {
    if (findNewLastDigit(0, lastSequence, sequenceUsed, sequence, idx))
    {
      ++foundSequences; // вдалося знайти нову комбінацію
      continue;
    }

    for (;;)
    {
      // тут ми опинилися бо не вдалося знайти нову комбінацію
      // додаванням цифри і тому треба повернутися до попередньої цифри і змінити її

      // останню комбінацію позначаємо як не використану
      sequenceUsed[lastSequence] = false;
      // зменшуємо лічильник знайдених комбінацій
      --foundSequences;

      // у послідовності переміщуємося на одну цифру вліво...
      lastSequence /= 10;
      --idx;
      lastSequence += sequence[idx - 4] * 1000;

      
      // ...і пробудемо знайти іншу останню цифру
      if (findNewLastDigit(sequence[idx] + 1, lastSequence, sequenceUsed, sequence, idx))
      {
        ++foundSequences; // знайшли іншу останню цифру
        break;
      }

    }
  }
}

int main()
{
  int sequence[10003] = { 0 };

  generateSequence(sequence);

  // прості перевірки далі
  map<int, int> counters;

  // підраховуємо кількість кожної зі знайдених комбінацій
  for (int idx = 3; idx < 10003; ++idx)
  {
    int seq = sequence[idx] + sequence[idx - 1] * 10 + sequence[idx - 2] * 100 + sequence[idx - 3] * 1000;
    counters[seq]++;
  }

  // усього їх має бути 10000
  cout << "Found sequences: " << counters.size() << endl;
  for (const auto &p : counters)
  {
    auto seq = p.first;
    auto count = p.second;

    if (seq < 0 || seq > 9999)
    {
      // комбінація має неприпустиме значення
      cout << "Sequence " << seq << " is illegal" << endl;
    }

    if (count != 1)
    {
      // комбінацію було використано більше одного разу
      cout << "Sequence " << seq << " was used " << count << " times" << endl;
    }

  }

    return 0;
}

 

Задача

Згенерувати лабіринт в якому можна було б дістатися у будь-яку клітину.

Рішення

Насправді існує більше одного алгоритму рішення цієї проблеми, деякі можна знайти ось тут – https://en.wikipedia.org/wiki/Maze_generation_algorithm. До того ж важливо знати що вимоги до лабіринту можуть бути змінені. Наприклад має бути необхідним щоб був лише один вхід та вихід, чи щоб вхід/вихід були у заданих точках. І так далі.

Спосіб який пояснюю далі на мою думку є найпростішим для розуміння, саме через те я на ньому і зупинився :)

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

Отже послідовність приблизно така:

  1. Вибираємо випадкову позицію в лабіринті, робимо її поточною та додаємо її в пройдений шлях, клітинку позначаємо як відвідану. Зменшуємо кількість невідвіданих клітин на одну.
  2. Якщо обробили усі клітини – ми завершили генерацію лабіринту.
  3. Для поточної клітини визначаємо напрямки у яких з неї можна переміститися: у напрямку (північ/вгору, південь/вниз, захід/вліво, схід/вправо) можна переміститися лише якщо там є невідвідана клітинка.
  4. Додаємо поточну клітину у пройдений шлях.
  5. Якщо можливих напрямків нема переходимо до кроку 9.
  6. З усих можливих напрямків випадковим чином вибираємо один і прибираємо відповідні стіни у поточної клітини та сусідньої для неї клітини у обраному напрямку. Наприклад, якщо вибрали йти вправо то у поточної клітини прибираємо східну стіну, а у клітини зправа від неї прибираємо ліву стіну.
  7. Робимо клітину до якої переходимо поточною і позначаємо її як відвідану.
  8. Повертаємося до кроку 2.
  9. Прибираємо останню клітину з пройдено шляху.
  10. Якщо у пройденому шляху ще лишилися клітини робимо останню з них поточною. <– Саме тут відбувається вертання звідки і походить назва алгоритму
  11. Повертаємося до кроку 2.

Реалізація

В моєму коді нижче я зберігаю кожну клітинку лабіринту у чарунці двомірного масиву цілих чисел. Значення числа показує які у клітинки є стіни. Навіть якусь кривеньку функцію відобреаження додав, але вона буде працювати лише з певними шрифтами (у мене Lucida Console).

#include "stdafx.h"

#include "time.h"

#include <array>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define WALL_NORTH 1
#define WALL_SOUTH 2
#define WALL_EAST  4
#define WALL_WEST  8
#define WALLS_ALL (WALL_NORTH | WALL_SOUTH | WALL_EAST | WALL_WEST)

#define DIR_NORTH 1
#define DIR_SOUTH 2
#define DIR_EAST  4
#define DIR_WEST  8

struct Cell
{
  Cell() : walls(WALLS_ALL), visited(false) {}

  int walls;
  bool visited;
};

struct CellCoords
{
  CellCoords(int _x, int _y) : x(_x), y(_y) {}
  int x, y;
};

class Maze
{
public:
  Maze(int w, int h)
  :
  w_(w), h_(h)
  {
    for (int x = 0; x < h; ++x)
    {
      cells_.push_back(vector<Cell>(w));
    }
  }

  void Generate()
  {
    int unvisited = w_ * h_;

    CellCoords currCell(rand() % h_, rand() % w_);

    stack<CellCoords> trail;
    trail.push(currCell);
    cells_[currCell.x][currCell.y].visited = true;
    --unvisited;

    while (unvisited > 0)
    {
      vector<int> dirs;

      if ((currCell.x > 0) && (!cells_[currCell.x - 1][currCell.y].visited))
      {
        dirs.push_back(DIR_NORTH);
      }
      
      if ((currCell.x < h_ - 1) && (!cells_[currCell.x + 1][currCell.y].visited))
      {
        dirs.push_back(DIR_SOUTH);
      }

      if ((currCell.y > 0) && (!cells_[currCell.x][currCell.y - 1].visited))
      {
        dirs.push_back(DIR_WEST);
      }

      if ((currCell.y < w_ - 1) && (!cells_[currCell.x][currCell.y + 1].visited))
      {
        dirs.push_back(DIR_EAST);
      }

      trail.push(currCell);

      if (!dirs.empty())
      {
        switch (dirs[rand() % dirs.size()])
        {
        case DIR_NORTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_NORTH;
          cells_[--currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          break;

        case DIR_SOUTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          cells_[++currCell.x][currCell.y].walls &= ~WALL_NORTH;
          break;

        case DIR_EAST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_EAST;
          cells_[currCell.x][++currCell.y].walls &= ~WALL_WEST;
          break;

        default: // case DIR_WEST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_WEST;
          cells_[currCell.x][--currCell.y].walls &= ~WALL_EAST;
          break;
        }

        cells_[currCell.x][currCell.y].visited = true;
        --unvisited;
      }
      else
      {
        trail.pop();

        if (!trail.empty())
        {
          currCell = trail.top();
          trail.pop();
        }
      }
    }

    // add random entrance and exit
    cells_[rand() % h_][0].walls &= ~WALL_WEST;
    cells_[rand() % h_][w_ - 1].walls &= ~WALL_EAST;
  }

  int GetWidth() const { return w_; }
  int GetHeight() const { return h_; }

  vector<Cell>& operator[](unsigned i) { return cells_[i]; }

private:
  int w_, h_;
  vector<vector<Cell>> cells_;
};

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// |c|d|
// -----
// where a, b, c, d are walls value for the cells.
char getWallChar(int a, int b, int c, int d)
{
  const char aWallChars[] = 
  { 
    ' ',    '\xb3', '\xc4', '\xda', 
    '\xb3', '\xb3', '\xc0', '\xc3', 
    '\xc4', '\xbf', '\xc4', '\xc2', 
    '\xd9', '\xb4', '\xc1', '\xc5' 
  };
  bool bWallToWest = (a & WALL_SOUTH) || (c & WALL_NORTH);
  bool bWallToNorth = (a & WALL_EAST) || (b & WALL_WEST);
  bool bWallToEast = (b & WALL_SOUTH) || (d & WALL_NORTH);
  bool bWallToSouth = (c & WALL_EAST) || (d & WALL_WEST);

  int nIndex = ((bWallToWest ? 1 : 0) << 3) |
    ((bWallToNorth ? 1 : 0) << 2) |
    ((bWallToEast ? 1 : 0) << 1) |
    (bWallToSouth ? 1 : 0);
  
  return aWallChars[nIndex];
}

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// where a, b are walls value for the cells.
char getVerticalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_EAST) || (b & WALL_WEST))
  {
    ch = '\xb3';
  }

  return ch;
}

// Finds out what wall character to draw for cells
// ---
// |a|
// ---
// |b|
// ---
// where a, b are walls value for the cells.
char getHorizontalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_SOUTH) || (b & WALL_NORTH))
  {
    ch = '\xc4';
  }

  return ch;
}

void drawMaze(Maze& a)
{
  int h = a.GetHeight();
  int w = a.GetWidth();

  // draw top row
  for (int y = 0; y < w; ++y)
  {
    if (0 == y)
    {
      // top left corner
      cout << getWallChar(0, 0, 0, a[0][y].walls);
    }
    cout << getHorizontalWallChar(0, a[0][y].walls);
    cout << getWallChar(0, 0, a[0][y].walls, (y == w - 1) ? 0 : a[0][y + 1].walls);
  }
  cout << endl;

  // for the rest of the matrix only draw walls on south, east and south-east
  for (int x = 0; x < h; ++x)
  {
    // draw vertical walls
    for (int y = 0; y < w; ++y)
    {
      if (y == 0)
      {
        // leftmost column
        cout << getVerticalWallChar(0, a[x][y].walls);
      }

      // labyrinth cell - just empty room
      cout << ' ';
      
      // cout << hex << a[x][y].walls; // show cell walls value

      cout << getVerticalWallChar(a[x][y].walls, (y == w - 1) ? 0 : a[x][y + 1].walls);
    }
    cout << endl;

    // draw bottom wall
    for (int y = 0; y < w; ++y)
    {
      bool bLastRow = x == h - 1;
      if (y == 0)
      {
        // leftmost column
        cout << getWallChar(0, a[x][0].walls, 0, bLastRow ? 0 : a[x + 1][0].walls);
      }

      cout << getHorizontalWallChar(a[x][y].walls, bLastRow ? 0 : a[x + 1][y].walls);
      
      bool bLastColumn = y == w - 1;
      cout << getWallChar(a[x][y].walls, 
                          bLastColumn ? 0 : a[x][y + 1].walls, 
                          bLastRow ? 0 : a[x + 1][y].walls,
                          (bLastColumn || bLastRow) ? 0 : a[x + 1][y + 1].walls);
    }
    cout << endl;
  }

  cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
  srand(time(NULL));

  int w = 10, h = 7;
  
  Maze m(w, h);
  m.Generate();
  
  drawMaze(m);

  return 0;
}

 

Приклад згенерованого лабіринту

┌───┬─┬─────────────┐
│   │ │             │
│ │ │ │ ┌───────┐ ──┤
│ │   │ │       │   │
│ └───┤ └─┐ ──┐ └─┬─┤
│     │   │   │   │ │
├───┐ ├── │ │ ├─┐ │ │
│   │ │   │ │ │ │ │ │
│ │ │ │ ──┴─┤ │ │ │ │
│ │   │     │ │   │ │
│ └───┴──── │ │ ──┘ │
│           │ │
│ ──────────┘ ├──── │
              │     │
──────────────┴─────┘

 

 

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

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

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

Перше що треба повторити це те що у великих компаніях типу 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 (мантиса, експонента, ну ви в курсі) та як можна реалізувати певні арифметичні операції з ними на платформі де нема підтримки такого формату “з коробки”. На цьому інтерв’ю той хто дав задачу пояснював усе включно з тим як числа представлено і як вони нормалізуються і просто треба було показати що розумієш як працювати з бітами та байтами та де можна зробити оптимізації.

 

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

Задача

Сама задача відома з прадавніх часів під назвою “задача Йосифа Флавія“. На співбесідах її можна почути в такому вигляді.

100 воїнів вишикувалися у замкнене коло. У першого воїна і лише у нього є меч. Він цим мечем вбиває наступного за ним (тобто другого) і передає меч наступному ще не вбитому (тобто третьому). Той хто отримує меч так само вбиває наступного і передає меч далі. І так доки не лишиться лише один живий воїн. Питання – який номер залишиться в живих.

В більш загальному випадку кількість воїнів може бути довільною так само як порядок вбивств.

Рішення

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

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

Для довільної кількості елементів N знайдемо найбільший ступінь двійки X такий що X <= N (це можна зробити, наприклад, модифікувавши алгоритм з Знайти найближчий ступінь двійки). Індекс з якого коло з N елементів перетвориться на коло з елементів кількість яких дорівнюватиме ступеню двійки і буде нашою відповіддю. Тобто нам треба знайти скільки елементів M треба пройти (половину з яких буде “вбито”) таких що M/2 + (N-M)=X. Просте рівняння з якого знаходимо що M=(N-X)*2.

Тобто для 100 воїнів (N=100) найближчим ступенем двійки не більшим за 100 буде 64 (X=64) і таким чином залишиться в живих 73-й воїн (M=(100-64)*2=72).

Задача

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

Як друзям гарантовано вижити?

Рішення

Перше на що треба звернути увагу це те що для виживання достатньо вгадувати лише одну з двох монет. Таким чином треба щоб кожна відповідь давала 50% шансів вгадати.

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

Виграшна стратегія в результаті виглядає так: один в’язень повторює результат своєї монети, а другий каже протилежний результат для своєї монети.

Табличка показує як це працює:

Монета 1 В'язень 1 каже: Монета 2 В'язень 2 каже: Результат
аверс аверс аверс реверс В'язень 1 вгадав монету 2
аверс аверс реверс аверс В'язень 2 вгадав монету 1
реверс реверс аверс реверс В'язень 1 вгадав монету 2
реверс реверс реверс аверс В'язень 2 вгадав монету 1

Задача, варіант 1

В одній країні діє закон за яким кожне подружжя коли народжує хлопчика не може мати більше дітей. А якщо народжується дівчинка то вони народжують ще одну дитину. Яке співвідношення хлопчиків та дівчаток у той країні? Вважаємо що немовлята обох статей народжуються з рівною імовірністю.

Рішення

Для N подружніх пар народиться N/2 хлопчиків (позначимо як A), та N/2 дівчат (позначимо як B). При цьому варіант A є остаточним, а для варіанту B далі можливі такі під-варіанти: у половини родин (N/4) народяться хлопчики (позначимо як B1), у другої половини (теж N/4) народяться дівчатка (позначимо як B2).

Таким чином матимемо:

  • хлопчиків: A + B1 = N/2 + N/4
  • дівчаток: B + B2 = N/2 + N/4

Тобто співвідношення буде 1:1.

Задача, варіант 2

Якщо умови змінити таким чином що пара народжує дітей доки у них не з’явиться хлопчик і на цьому зупиняється як зміниться співвідношення?

Рішення

На кожній ітерації половина родин народжує хлопчика і припиняє свої спроби. Інша ж половина відповідно має дівчат і на наступній ітерації знову ділиться навпіл. Таким чином на кожній ітерації кількість немовлят обох статей однакова.

Продемонструвати можна так:

ітерація 1 ітерація 2 ітерація 3 ітерація 4  …
хлопчиків: N/2(A) N/4(B1) N/8(B21) N/16(B221)
дівчаток: N/2(B) N/4(B2) N/8(B22) N/16(B222)

Таким чином кількість хлопчиків і дівчаток при скільки завгодно ітераціях буде однаковою і пропорція 1:1 зберігається.

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

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

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

Сам код:

   1:  year = ORIGINYEAR; /* = 1980 */
   2:  
   3:  while (days > 365)
   4:  {
   5:      if (IsLeapYear(year))
   6:      {
   7:          if (days > 366)
   8:          {
   9:              days -= 366;
  10:              year += 1;
  11:          }
  12:      }
  13:      else
  14:      {
  15:          days -= 365;
  16:          year += 1;
  17:      }
  18:  }

Цей код як бачите вираховує рік на основі лічильника днів (лічильник починається з 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).

Задача

Для N змінних типу bool треба знайти всі варіанти комбінацій їх значень.

Рішення

Ідея полягає в тому що після того як змінено значення однієї змінної в true (починаємо з останньої) встановлюємо усі що йдуть за нею в false. Кожна наступна ітерація починає з останнього зміненого значення.

   1:      bool* vals = new bool[N];
   2:      for (int i = 0; i < N; ++i) vals[i] = false;
   3:   
   4:      bool cont = true;
   5:      while (cont)
   6:      {
   7:          for (int j = 0; j < N; ++j) 
   8:          {
   9:              cout << (vals[j] ? "t" : "f") << ", ";
  10:          }
  11:          cout << 'b' << endl;
  12:   
  13:          cont  = false;
  14:   
  15:          for (int i = N - 1; i >=0; --i)
  16:          {
  17:              if (!vals[i])
  18:              {
  19:                  vals[i] = true;
  20:                  cont = true;
  21:   
  22:                  for (++i; i < N; ++i) vals[i] = false;
  23:   
  24:                  break;
  25:              }
  26:          }
  27:      }
  28:   
  29:      delete [] vals;

 

Оптимізація

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

   1:  template <class T>
   2:  unsigned getBit(size_t index, T* storage, size_t size)
   3:  {
   4:      auto position = index / (sizeof(T) * CHAR_BIT);
   5:      auto bit = index % (sizeof(T) * CHAR_BIT);
   6:      
   7:      return (storage[size - position - 1] >> bit) & 1;
   8:  }
   9:   
  10:  typedef unsigned char storageType;
  11:  const int bitsInPosition = sizeof(storageType) * CHAR_BIT;
  12:   
  13:  ...
  14:      auto positions = N / bitsInPosition;
  15:      if (N % bitsInPosition > 0) ++positions;
  16:      storageType* vals = new storageType[positions];
  17:      auto mask0Position = (1 << (N % bitsInPosition)) - 1;
  18:   
  19:      for (auto i = 0; i < positions; ++i) vals[i] = 0;
  20:   
  21:      for (size_t i = positions - 1; ;)
  22:      {
  23:          for (size_t j = 0; j < N; ++j) 
  24:          {
  25:              cout << getBit(j, vals, positions);
  26:          }
  27:          cout << endl;
  28:   
  29:          if ((++vals[i] == 0) ||
  30:              (i == 0 && ((vals[0] & mask0Position) == 0)))
  31:          {
  32:              if (i == 0)
  33:              {
  34:                  break;
  35:              }
  36:              
  37:              while (++vals[--i] == 0);
  38:              i = positions - 1;
  39:          }
  40:      }
  41:   
  42:      delete [] vals;
  43: