Тестовые задания для программиста
1K #c++

Так случилось, что в марте 2011 года я потерял работу в связи с закрытием фирмы. Взгрустнулось. Недолго думая, накатал резюме и выложил его на разные сайты: hh.ru, habrahabr.ru, job.ru и dtf.ru. В течение месяца ответило довольно много работодателей. Некоторые высылали тестовые задания для проверки. Делал я их бесплатно, в свое личное время, так что имею полное право выложить решение.

Итак, погнали: решение тестового задания от фирмы «Saber Interactive».

Задача

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

Решение

 
#include <stdio.h>
#include <limits.h>
 
void BinaryPrint( long n )
{
    // Частный случай - n равно нулю
    if (n == 0)
    {
        printf("0\n");
        return;
    }
 
    unsigned long mask = 1 << (sizeof(n) * 8 - 1);
 
    // Пропускаем бесполезные нули слева
    int skipZero = 1;
 
    while (mask)
    {
        // Определим текущий бит
        unsigned char c = (n & mask) ? 1 : 0;
 
        // Отключим пропуск нулей в дальнейшем
        if (skipZero && c)
            skipZero = 0;
 
        if (!skipZero)
            printf("%d", c);
 
        // Сдвинем маску на один бит вправо
        mask >>= 1;
    }
    printf("\n");
}
 
int main()
{
    BinaryPrint(0);
    BinaryPrint(1);
    BinaryPrint(2);
    BinaryPrint(-2);
    BinaryPrint(-1);
    BinaryPrint(LONG_MAX);
    BinaryPrint(LONG_MIN);
    return 0;
}

Задача

Напишите функцию, удаляющую последовательно дублирующиеся символы в строке: («AAA BBB ААА» -> «A B А»)
void RemoveDups (char *pStr);

Решение

#include <stdio.h>
 
void RemoveDups( char * pStr )
{
    const char * src = pStr;
    char * dst = pStr;
 
    // Пока не дойдем до конца строки
    while (*src)
    {
        // Записываем в pStr текущий символ, если указатели разные
        if (dst != src)
            *dst = *src;
 
        // Сдвигаем dst вправо
        *dst++;
 
        // Пока не конец строки и следующий символ такой же
        while ((*src + 1) && *(src + 1) == *src)
        {
            // Сдвигаем указатель src вправо
            *src++;
        }
        *src++;
    }
    // Запишем ноль в конец строки
    *dst = 0;
}
 
int main()
{
    char s[] = "AAA BBB AAA";
    RemoveDups(s);
    printf("%s\n", s);
    return 0;
}

Задача

Предположим, Вам предстоит написать простенькое программное обеспечение для учета книг в библиотеке. По некоторым, не зависящим от Вас причинам, нужно, чтобы программа была написана на С++ без использования каких-либо баз данных. Вы прикинули предварительный
список требований, которым должна удовлетворять ваша программа, и у Вас получилось:

Вам нужно хранить информацию обо всех книгах из библиотеки — название, автор, год, количество экземпляров
— Вам нужно хранить базовую информацию о читателях — ФИО, адрес, телефон
— Вам нужно уметь быстро находить читателя по ФИО или только по части ФИО
— Вам нужно хранить информацию о том, какие книги взяты какими читателями и на какой срок
— Вам нужно уметь быстро находить информацию о книгах по автору и/или названию, а также выдавать информацию о том, есть ли свободные экземпляры, и у каких читателей находятся выданные книги, и когда они будут возвращены

Разработайте структуры хранения данных, наилучшим образом подходящие для реализации этой функциональности. Постарайтесь учесть непредвиденные ситуации, которые могут возникнуть, а также организовать доступ к данным наиболее быстрым и эффективным образом. Представьте ответ в виде .h файла. Вы можете использовать классы С++, а также контейнеры STL или их аналоги.

Решение

Исходники программы на C/C++
#ifndef _LIBRARY_H_
#define _LIBRARY_H_
 
/*
 Каждой книге и каждому читателю при регистрации присваивается уникальный 
 числовой идентификатор. Доступ к книгам и читателям происходит только 
 с помощью идентификаторов.
 
 База книг/читателей преставляет собой деревья, где ключи - это идентификатор,
 а значения - книга/читатель. 
 
 Для каждого поля, по которым мы можем осуществить поиск, создается
 индексная таблица. По образу и подобию индексных таблиц в mysql.
 
 Класс Index представляет собой обертку над std::multimap. 
 std::multimap выбран потому, что значения ключей могут повторяться.
 один автор -> много книг, одно название -> много книг и т.д.
 
 Все методы поиска возвращают список идентификаторов, поскольку ключевые поля не уникальны.
*/
 
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>
 
// Уникальный идентификтор объекта
typedef unsigned long Ident;
// Список идентификаторов
typedef std::vector<Ident> IdentVector;
 
namespace detail
{
    // Шаблонный класс для удобства работы с multimap
    template <class T>
    class Index
    {
    public:
        void append( const T & value, Ident ident )
        {
            m_values.insert(std::make_pair(value, ident));
        }
 
        void remove( Ident ident )
        {
            for (Values::const_iterator i = m_values.begin(); i != m_values.end();)
            {
                if (i->second == ident)
                {
                    i = m_values.erase(i);
                }
                else
                {
                    ++i;
                }
            }
        }
 
        IdentVector get( const T & value ) const
        {
            IdentVector result;
 
            Values::const_iterator i = m_values.find(value);
            while (i != m_values.end() && i->first == value)
            {
                result.push_back(i->second);
                ++i;
            }
 
            return result;
        }
 
    private:
        typedef std::multimap<T, Ident> Values;
        Values m_values;
    };
 
} // namespace detail
 
// Описание книги
struct Book
{
    // Автор
    std::string author;
    // Название
    std::string title;
    // Год выпуска
    size_t year;
    // Количество экземпляров
    size_t count;
 
    Book( const std::string & author, const std::string & title, size_t year, size_t count )
        : author(author), title(title), year(year), count(count)
    {
    }        
};
 
// База данных книг
class BookDatabase
{
public:
    BookDatabase()
        : m_nextIdent(0)
    {
    }        
 
    virtual ~BookDatabase() {}
 
    // Добавление книги в библиотеку (возвращает идентификатор)
    Ident registerBook( const Book & book )
    {
        Ident ident = getNextIdent();
        m_books.insert(std::make_pair(ident, book));
        m_authors.append(book.author, ident);
        m_titles.append(book.title, ident);
        return ident;
    }
 
    // Удаление книги из библиотеки 
    void unregisterBook( Ident ident )
    {
        Books::const_iterator i = m_books.find(ident);
        if (i != m_books.end())
        {
            i = m_books.erase(i);
        }
        m_authors.remove(ident);
        m_titles.remove(ident);
    }
 
    // Получение всех идентификаторов книг с заданным авторов
    IdentVector getBooksByAuthor( const std::string & author ) const
    {
        assert(!author.empty());
        return m_authors.get(author);
    }
 
    // Получение всех идентификаторов книг с заданным названием
    IdentVector getBooksByTitle( const std::string & title ) const
    {
        assert(!title.empty());
        return m_titles.get(title);
    }
 
    // Получение всех идентикаторов книг с заданным автором и названием
    IdentVector getBooksByAuthorAndTitle( const std::string & author, const std::string & title ) const
    {
        assert(!author.empty() && !title.empty());
 
        IdentVector authors = getBooksByAuthor(author);
        IdentVector titles = getBooksByTitle(title);
 
        IdentVector result;        
        std::set_intersection(authors.begin(), authors.end(), titles.begin(), titles.end(), result.begin());
        return result;
    }
 
    // Получение данных книги по идентификатору (возвращает false, если книга не найдена)
    bool getBook( size_t ident, Book & book ) const
    {
        Books::const_iterator i = m_books.find(ident);
        if (i != m_books.end())
        {
            book = i->second;
            return true;
        }
        return false;
    }
 
    // Увеличение кол-ва книг
    void increaseBooksCount( Ident ident )
    {
        Books::iterator i = m_books.find(ident);
        if (i != m_books.end())
        {
            i->second.count++;
        }
    }
 
    // Уменьшение кол-ва книг (возвращает false, если кол-во равно нулю
    bool decreaseBooksCount( Ident ident )
    {
        Books::iterator i = m_books.find(ident);
        if (i != m_books.end())
        {
            if (i->second.count > 0)
            {
                i->second.count--;
                return true;
            }                
        }
        return false;
    }
 
    // Вернуть список всех книг, которые можно взять в библиотеке
    IdentVector getFreeBooks() const
    {
        IdentVector result;
 
        for (Books::const_iterator i = m_books.begin(); i != m_books.end(); ++i)
        {
            if (i->second.count > 0)
            {
                result.push_back(i->first);
            }
        }
 
        return result;
    }
 
private:
    Ident getNextIdent()
    {
        return m_nextIdent++;
    }
 
    // Следующий идентификатор
    Ident m_nextIdent;
 
    // Список книг
    typedef std::map<Ident, Book> Books;
    Books m_books;
 
    // Индексная таблица по авторам
    detail::Index<std::string> m_authors;
    // Индексная таблица по названиям книг
    detail::Index<std::string> m_titles;
};
 
// Читатель
struct Reader
{
    // ФИО
    std::string fullName;
    // Адрес
    std::string address;
    // Телефон
    std::string phone;
 
    Reader( const std::string & fullName, const std::string & address, const std::string & phone )
        : fullName(fullName), address(address), phone(phone)
    {
    }        
};
 
// База читателей
class ReaderDatabase
{
public:
    ReaderDatabase()
        : m_nextIdent(0)
    {
    }
 
    virtual ~ReaderDatabase() {}
 
    Ident registerReader( const Reader & reader )
    {
        Ident ident = getNextIdent();
        m_readers.insert(std::make_pair(ident, reader));
        m_fullNames.append(reader.fullName, ident);
        return ident;
    }
 
    void unregisterReader( Ident ident )
    {
        Readers::const_iterator i = m_readers.find(ident);
        if (i != m_readers.end())
        {
            m_readers.erase(i);
        }
        m_fullNames.remove(ident);
    }
 
    IdentVector getReadersByFullName( const std::string & fullName ) const
    {
        return m_fullNames.get(fullName);
    }
 
    IdentVector getReadersByPartName( const std::string & partName ) const
    {
        IdentVector result;
        for (Readers::const_iterator i = m_readers.begin(); i != m_readers.end(); ++i)
        {
            const Reader & reader = i->second;
            if (reader.fullName.find(partName) != std::string::npos)
            {
                result.push_back(i->first);
            }
        }
        return result;
    }
 
    // Информация о читателе
    bool getReader( Ident ident, Reader & reader ) const
    {
        Readers::const_iterator i = m_readers.find(ident);
        if (i != m_readers.end())
        {
            reader = i->second;
            return true;
        }
        return false;
    }
 
private:
    Ident m_nextIdent;
 
    Ident getNextIdent()
    {
        return m_nextIdent++;
    }    
 
    typedef std::map<Ident, Reader> Readers;
    Readers m_readers;
 
    detail::Index<std::string> m_fullNames;
};
 
// Библиотека
class Library : public ReaderDatabase, public BookDatabase
{
    struct Rent
    {
        Ident book;
        Ident reader;
        size_t days;
    };
 
public:
    // Взять книгу bookIdent читателем readerIdent на days дней (возвращает false в случае неудачи)
    bool popBook( Ident bookIdent, Ident readerIdent, size_t days )
    {
        if (decreaseBooksCount(bookIdent))
        {
            Rent rent;
            rent.book = bookIdent;
            rent.reader = readerIdent;
            rent.days = days;
 
            m_rents.push_back(rent);
 
            return true;
        }
        return false;
    }
 
    // Вернуть книгу bookIdent читателем readerIdent
    void pushBook( Ident bookIdent, Ident readerIdent )
    {
        for (Rents::const_iterator i = m_rents.begin(); i != m_rents.end(); ++i)
        {
            if (i->book == bookIdent && i->reader == readerIdent)
            {
                m_rents.erase(i);
                increaseBooksCount(bookIdent);
                break;
            }
        }
    }
 
    // Через сколько дней будет возвращена книга bookIdent читателем readerIdent
    size_t getRentaDays( Ident bookIdent, Ident readerIdent ) const
    {
        for (Rents::const_iterator i = m_rents.begin(); i != m_rents.end(); ++i)
        {
            if (i->book == bookIdent && i->reader == readerIdent)
            {
                return i->days;
            }
        }
    }
 
    // Возвращает список читателей, взявший данную книгу
    IdentVector getReadersByBook( Ident bookIdent ) const
    {
        IdentVector result;
        for (Rents::const_iterator i = m_rents.begin(); i != m_rents.end(); ++i)
        {
            if (i->book == bookIdent)
            {
                result.push_back(i->reader);
            }
        }
        return result;
    }
 
private:
    typedef std::vector<Rent> Rents;
    Rents m_rents;
 
};
 
#endif // _LIBRARY_H_


Если допустить, что первые два теста написаны на языке C, смотри исправления тут.

Читайте также: «Вопросы программисту на собеседовании с ответами»

Блог Евгения Жирнова