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

Задача

Для 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:  

 

Задача

Що буде виведено на екран в результаті виконання наступної програми,

char *c[]={
    "ENTER",
    "NEW",
    "POINT",
    "FIRST"

};
  
char **cp[]={c+3,c+2,c+1,c};
  
char ***cpp=cp;
  
main()

{
    printf("%s",**++cpp);
    printf("%s ",*--*++cpp+3);
    printf("%s",*cpp[-2]+3);
    printf("%sn",cpp[-1][-1]+1);

}

Рішення

Насправді не все так складно, спробуємо помалювати стрілочки.

Отже після ініціалізації усих змінних маємо приблизно таку картину:

Тепер дивимося що станеться в процесі виконання printf(“%s”,**++cpp): срр пересунеться на елемент [1], а після розіменування отримаємо рядок POINT:

При виконанні printf(“%s “,*–*++cpp+3) срр знову пересунеться на наступний елемент, далі вказівник на NEW на який тепер вказує cpp буде пересунуто на попередній елемент (ENTER), після чого буде виведено рядок починаючи з 3-го елемента. Отже матимемо тепер на екрані POINTER_:

Рядок printf(“%s”,*cpp[-2]+3) – відступаємо на 2 елементи назад від тієї позиції що на неї вказує cpp, розіменовуємо (маємо рядок FIRST) і виводимо текст з 3-го символа. Отже маємо PONTER ST:

Для printf(“%sn”,cpp[-1][-1]+1) відступаємо від поточної позиції cpp на одну назад (вказуємо на рядок POINT), відступаємо на рядок від нього назад (вказуємо на NEW), і виводимо з 1-го символа.

Отже остаточний рядок буде POINTER STEW.

Задача

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

– Скільки в тебе дітей?

– Троє.

– А який у них вік?

– Якщо перемножити їх вік то вийде 36.

– Потрібна підказка.

– Сума їх віку дорівнює кількості вікон он у тому будинку.

– Все одно потрібна підсказка.

– Найстарший з моїх дітей ходить в музичну школу.

– А, тепер точно знаю скільки їм років!

 

Відповідно треба визначити вік дітей і пояснити як це рішення знайдено.

Рішення

Почнемо з найспростішого

Якщо перемножити їх вік то вийде 36

Запишемо усі комбінації з трьох натуральних чисел результат множення яких дасть 36:

  1. 1*1*36
  2. 1*2*18
  3. 1*3*12
  4. 1*4*9
  5. 1*6*6
  6. 2*2*9
  7. 2*3*6
  8. 3*3*4

Сума їх віку дорівнює кількості вікон он у тому будинку

Спочатку просто обчислимо суми:

  1. 1+1+36=38
  2. 1+2+18=21
  3. 1+3+12=16
  4. 1+4+9=14
  5. 1+6+6=13
  6. 2+2+9=13
  7. 2+3+6=11
  8. 3+3+4=10

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

    1. 1+6+6=13
    2. 2+2+9=13

Найстарший з моїх дітей ходить в музичну школу

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

2 + 2 + 9.