Тест для соискателей вакансии программист
| Уважаемый соискатель, перед Вами тест на вакансию программист в компании Saber Interactive. Индустрия видеоигр, в которой работает компания Saber, предъявляет высокие требования к качеству, эффективности и удобству восприятия программного кода. Поэтому мы предлагаем выполнить Вам 3 несложных задания, чтобы Вы могли продемонстрировать Вашу способность писать такой код. Просьба не использовать в первых двух задачах библиотечные функции и классы, являющиеся решением этих задач (например stl::bitset). |
Фамилия, имя, отчество выполнившего тест: Гусев Дмитрий Викторович
Дата выполнения: 8 августа 2015
Примерное количество времени, затраченного на выполнение теста: 3 часа
Задачи
1. Напишите функцию, которая принимает на вход знаковое целое число и печатает его двоичное представление, не используя библиотечных классов или функций.
2. Напишите функцию, удаляющую последовательно дублирующиеся символы в строке:
("AAA BBB ААА" -> "A B А")
void RemoveDups (char *pStr);
3. Реализуйте функции сериализации и десериализации двусвязного списка, заданного следующим образом:
struct ListNode {
ListNode * prev;
ListNode * next;
ListNode * rand; // указатель на произвольный элемент данного списка
std::string data;
};
class List {
public:
void Serialize(std::ostream & stream); // сохранение в файл
void Deserialize(std::istream & stream); // загрузка из файла
private:
ListNode * head;
ListNode * tail;
int count;
};
Примечание: сериализация подразумевает сохранение и восстановление полной структуры списка, включая взаимное соотношение его элементов между собой.
Спасибо за уделенное время и выполнение нашего теста!
#include <iostream>
#include <assert>
#include <vector>
#include <map>
#include <string>
using namespace std;
void PrintBinary (int a) //puts binary representation of a to standard output
{
static const unsigned int_size_in_bits = sizeof(int) * 8; //size of int in bits
unsigned b = static_cast<unsigned int>(a); //convert a to unsigned in order to consider sign bit of a
unsigned mask = 1 << (int_size_in_bits - 1); //most significant bit is set
while (mask != 0)
{
std::cout << ((b & mask)? 1 : 0); //if bit of b is set, print 1, otherwise print 0
mask = mask >> 1; //shift mask to the right in order to test next bit of b
}
std::cout << std::endl;
}
void RemoveDups (char *pStr)
{
char current_char = pStr[0]; //character which is tested on repeat
if (current_char == '\0') //string is empty
return;
unsigned read_position = 1, //position in string which is read (analysed)
write_position = 1; //position in string where to move next not repeated string character
while (pStr[read_position] != '\0') //while not the end of the string
{
if (pStr[read_position] != current_char) //new (not repeated) character is found
{
current_char = pStr[read_position]; //now we will test new character
pStr[write_position++] = pStr[read_position]; //new character moves to write_position in string
}
read_position++; //increment position in which string is analysed
}
pStr[write_position] = '\0'; //end-of-string character
}
struct ListNode {
ListNode * prev;
ListNode * next;
ListNode * rand; // указатель на произвольный элемент данного списка
std::string data;
};
class List {
public:
void Serialize(std::ostream & stream); // сохранение в файл
void Deserialize(std::istream & stream); // загрузка из файла
private:
ListNode * head;
ListNode * tail;
int count;
};
void List::Serialize(std::ostream & stream) //saves list in stream
{
std::map<ListNode*, int> nodes_map; //container for list nodes and their numbers
ListNode* ln = head;
int i = 0;
while (ln != NULL)
{
nodes_map[ln] = i; //place list node and its number in the map
ln = ln->next; //move to next node
i++;
}
ln = head;
while (ln != NULL)
{
std::map<ListNode*, int>::iterator it = nodes_map.find(ln->rand); //find linked item for this node
int link_index = (it == nodes_map.end())? -1 : it->second; //and its number or -1 if linked item doesn't exist
stream << ln->data.length() << endl << ln->data.c_str() << std::endl << link_index << std::endl; //save data and linked item number in file
ln = ln->next;
}
}
void List::Deserialize(std::istream & stream) //loads list from stream
{
std::vector<ListNode*> nodes; //container for list nodes
std::map<ListNode*, int> linked_nodes; //container for list nodes and numbers of linked items
head = NULL; //TODO: clear list before deserialization would be a great idea
count = 0;
ListNode* ln;
ListNode* ln_prev = NULL;
int link_index;
int length;
while (!stream.eof())
{
stream >> length;
if (stream.eof())
break;
char* s = new char[length + 1];
stream >> s;
if (stream.eof())
break;
stream >> link_index;
if (stream.eof())
break;
ln = new ListNode;
ln->data = s;
delete s;
ln->prev = ln_prev;
if (ln_prev != NULL)
ln_prev->next = ln;
ln_prev = ln;
if (head == NULL)
head = ln;
nodes.push_back(ln);
linked_nodes[ln] = link_index;
}
tail = ln;
tail->next = NULL;
count = nodes.size();
for (std::map<ListNode*, int>::iterator it = linked_nodes.begin(); it != linked_nodes.end(); ++it)
{
link_index = it->second;
ln = it->first;
if (link_index >=0 && link_index < count)
ln->rand = nodes[link_index];
else
ln->rand = NULL;
}
}
int main()
{
PrintBinary(10);
PrintBinary(20);
PrintBinary(-1);
PrintBinary(-3);
char* s = "AAA BBB AAA";
RemoveDups(s);
std::cout << s << endl;
List list;
list.Deserialize(std::cin);
list.Serialize(std::cout);
return 0;
}