Тесты для программистов

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

Задача 1. Табло бегущей справа налево строки вмещает до 20 символов. Сама строка может иметь размер до 60 символов. Вывести на экран бегущую строку (достаточно одной прокрутки и печати последовательных состояний табло).

Programming test 1

Задача 2. Информационное табло размером 8х7 состоит из ячеек. Текстовая строка по-прежнему ограничена 60 символами. Требуется пошагово запустить строку по спирали, начиная с левой нижней ячейки вверх, пока она не дойдет до конечной ячейки. Вывести на экран финальное состояние.

Programming test 2

Мои решения приведены ниже, не сомневаюсь, что их можно улучшить. Программирование заняло около 20 минут на первой задаче и почти час на второй (решил оформить код как для учебного примера). Таким образом первая задача годна для любого короткого теста, вторая должна укладываться в полутора-двухчасовое интервью. Необязательно давать соискателю обе задачки, можно предлагать сделать любую на выбор.

Решение 1.

#include <iostream>
 
using namespace std;
 
const int MAX_STR = 60;
const int MAX_PANEL = 20;
 
typedef char Panel[MAX_PANEL + 1];
 
int main(int argc, char* argv[])
{
  Panel panel;
  for (int i = 0; i < MAX_PANEL; i++)
    panel[i] = ' ';
  panel[MAX_PANEL] = 0;
  char s[MAX_STR] = "This is a scrolling text test\x0";
  int len = strlen(s);
  for (int i = 0; i < len + MAX_PANEL - 1; i++)
  {
    for (int j = 0; j < MAX_PANEL - 1; j++)
      panel[j] = panel[j + 1];
    panel[MAX_PANEL - 2] = s[i];
    cout << panel << endl;
  }
  getchar();
	return 0;
}

Решение 2.

#include <iostream>
 
using namespace std;
 
const int MAX_STR = 60;
const int MAX_X   = 8;
const int MAX_Y   = 7;
 
enum Direction
{
  dirUp,
  dirRight,
  dirDown,
  dirLeft
};
 
int main(int argc, char* argv[])
{
  char s[MAX_STR] = "The quick brown fox jump over the lazy dog\x0";
  char t[MAX_X][MAX_Y];
  // Clear table
  for (int i = 0; i < MAX_X; i++)
    for (int j = 0; j < MAX_Y; j++)
      t[i][j] = ' ';
 
  int len = strlen(s);
  int lim_s = len > MAX_X * MAX_Y ? len - MAX_X * MAX_Y : 0;
  for (int i = len - 1; i >= lim_s; i--)
  {
     // Shift the spiral and push back the character
     Direction dir = dirUp;
     int x = 0, y = 0;
     int lim_x0 = 1, lim_x1 = MAX_X - 1;
     int lim_y0 = 0, lim_y1 = MAX_Y - 1;
     char prev = ' ';
     for (int j = 0; j < MAX_X * MAX_Y; j++)
     {
       char curr = t[x][y];
       t[x][y] = prev;
       prev = curr;
//       cout << j << ": " << x << ", " << y << " Lim: " << lim_x0 << ".." << lim_x1 << ", " << lim_y0 << ".." << lim_y1 << " Dir: " << dir << endl;
       switch (dir)
       {
         case dirUp:
           if (y == lim_y1)
           {
             dir = dirRight;
             lim_y1--;
             if (x < lim_x1)
               x++;
           }
           else
             y++;
           break;
         case dirRight:
           if (x == lim_x1)
           {
             dir = dirDown;
             lim_x1--;
             if (y > lim_y0)
               y--;
           }
           else
             x++;
           break;
         case dirDown:
           if (y == lim_y0)
           {
             dir = dirLeft;
             lim_y0++;
             if (x > lim_x0)
               x--;
           }
           else
             y--;
           break;
         case dirLeft:
           if (x == lim_x0)
           {
             dir = dirUp;
             lim_x0++;
             if (y < lim_y1)
               y++;
           }
           else
             x--;
           break;
       }
     }
     t[0][0] = s[i];
  }
  // Print string and table
  cout << s << endl << endl;
  for (int y = 6; y >= 0; y--)
  {
    for (int x = 0; x < 8; x++)
      cout << t[x][y] << " ";
    cout << endl;
  }
  getchar();
	return 0;
}

Комментарии

Решение задачи

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

#include <iostream>
 
using namespace std;
 
// Task 1
/*
const int MAX_X = 10;
const int MAX_Y = 1;
char t[MAX_Y][MAX_X] = { {9, 8 ,7 ,6, 5, 4, 3, 2, 1, 0 } };
char s[] = "This is a scrolling text test\x0";
*/
 
// Task 2
const int MAX_X = 8;
const int MAX_Y = 7;
char t[MAX_Y][MAX_X] = {
	{ 6,  7,  8,  9, 10, 11, 12, 13	},
	{ 5, 30, 31, 32, 33, 34, 35, 14 },
	{ 4, 29, 46, 47, 48, 49, 36, 15 },
	{ 3, 28, 45, 54, 55, 50, 37, 16 },
	{ 2, 27, 44, 53, 52, 51, 38, 17 },
	{ 1, 26, 43, 42, 41, 40, 39, 18 },
	{ 0, 25, 24, 23, 22, 21, 20, 19 }
};
char s[] = "The quick brown fox jump over the lazy dog\x0";
 
 
 
int main()
{
	int symbol_index = 0;
	int text_size = strlen(s);
 
	// Count number of frames for one full roll: screen size + text size 
	int max_frames = MAX_X * MAX_Y + text_size;
 
	for (int frame_index = 0; frame_index < max_frames; frame_index++)
	{
		for (int y = 0; y < MAX_Y; y++)
		{
			for (int x = 0; x < MAX_X; x++) 
			{
 
				// Get symbol index for this position on screen
				symbol_index = frame_index - t[y][x];
 
				// Print symbol by index if index within the text string
				if (symbol_index >= 0 && symbol_index < text_size)
					cout << s[symbol_index] << " ";
				else // Print space for all other positions 
					cout << "  ";
			}
			cout << endl;
		}
 
		getchar();
	}
    return 0;
}

Изображение пользователя Serguei_Tarassov.

Вполне

Спасибо за пример. Да, в контексте теста такое решение вполне подходящее. В контексте конкретных задач надо будет смотреть требования. Например, если размеры массивов меняются, то всякий раз придется вручную перекодировать их "карту" или писать функцию перекодирования, которая, по сути, и реализует основную часть алгоритма.