Тестовые задания

[cd_riper]

Я всегда с интересом относился к всевозможным тестовым заданиям, которыми мучают программистов на собеседованиях.

Во-первых, потому что сам часто ломал голову, о чем говорить с человеком при его попытке устроиться на работу.
Во-вторых, потому что периодически бываю и по обратную сторону баррикад.

Этот пост я решил сделать интеграционным -- в него я собрал все свои старые записи по теме, плюс бонус: решение FizzBuzz (извините... не знаю зачем я его писал) и работу с однонаправленным связанным списком (смотри постскриптум).

Из того, что нарыл в прошлых записях.

Двоичный поиск (кошерная реализация на питоне)
http://cd-riper.livejournal.com/280524.html

Про задачу циклического сдвига массива (коварная штука)
http://cd-riper.livejournal.com/267218.html

Что касается моего отношению к подобным задачкам (много раз писал уже об этом, но еще раз)...
Значительная часть такого рода штучек (из серии "головоломка") меня обычно раздражают, потому что они низкоуровневые (а хороший программист, это программист-стратег), потому что в них больше математики, чем программирования, потому что нет смысла засорять голову этой ерундой -- все задачки подобного рода уже давно решены, и потому, что на практике очень редко приходится их решать (ну а помимо всего прочего, есть куча соответствующих книг и справочников по алгоритмам -- все уже украдено до нас).
Признаюсь честно -- я не смогу самостоятельно написать рекурсивный quick sort и пояснить как это алгоритм работает. И совершенно не комплексую по этому поводу.

Чтиво по теме.

Физики и лирики
http://cd-riper.livejournal.com/177735.html

Про найм программистов (пунт #2)
http://cd-riper.livejournal.com/312463.html

зы. код переворота списка и FizzBuzz.
Что интересно, рекурсивная версия поворота пришла в голову быстрее итеративной. Кста, написание кода создания самого списка по сложности равна функции поворота.

Настоящие программисты, где же вы? (про связанный список):
http://habrahabr.ru/blogs/htranslations/112561/

FizzBuzz, или почему программисты не умеют программировать:
http://habrahabr.ru/blogs/htranslations/111843/



Copy Source | Copy HTML
namespace Test
{

class ReverseList
    {

class List : boost::noncopyable
        {
            struct Node
            {
                Node *pNext;
                int Value;

Node(int value) : Value(value), pNext( 0)
                {
                }
            };

static Node* Create(int count)
            {
                int currValue =  0;
                Node *pFirst =  0;
                Node *pPrev =  0;

while(currValue < count)
                {
                    Node *p = new Node( currValue++ );

if (pPrev ==  0)
                    {
                        pFirst = p;
                    }
                    else
                    {
                        pPrev->pNext = p;
                    }

pPrev = p;
                }

return pFirst;
            }

static void Free(Node *p)
            {
                while(p !=  0)
                {
                    Node *pFree = p;
                    p = p->pNext;
                    delete pFree;
                }
            }

// not optimal in specific cases 
            static bool Verify(Node *p, int from, int to)
            {
                if (p ==  0) return true;

int step = (from <= to) ? 1 : -1;

while(true)
                {
                    if (p->Value != from) return false;

p = p->pNext;
                    if (p ==  0)
                    {
                        if (from != to) return false;
                        break;
                    }

from += step;
                }

return true;
            }

static Node* ReverseRecursive(Node *p)
            {
                struct X
                {
                    static Node* Reverse(Node *p, Node *pTo)
                    {
                        Node *pNext = p->pNext;
                        p->pNext = pTo;
                        if (pNext ==  0) return p;
                        return Reverse(pNext, p);
                    }
                };

if (p ==  0) return  0;

return X::Reverse(p,  0);
            }

static Node* ReverseIter(Node *p)
            {
                if (p ==  0) return  0;

Node *pPrev =  0;

while(true)
                {
                    Node *pNext = p->pNext;
                    p->pNext = pPrev;
                    pPrev = p;
                    p = pNext;
                    if (p ==  0) return pPrev;
                }

// next goes here
                return  0;
            }

const int m_size;
            Node *m_pHead;

public:

List(int size) : m_size(size)
            {
                m_pHead = Create(size);
            }

~List()
            {
                Free(m_pHead);
            }

void Verify(bool asDirect)
            {
                bool res;
                if (asDirect) res = Verify(m_pHead,  0, m_size-1);
                         else res = Verify(m_pHead, m_size-1,  0);

ESS_ASSERT(res);
            }

void ReverseRecursive()
            {
                m_pHead = ReverseRecursive(m_pHead);
            }

void ReverseIter()
            {
                m_pHead = ReverseIter(m_pHead);
            }

};

public:

static void Do()
        {
            List list(4);
            list.Verify(true);

list.ReverseIter();
            list.Verify(false);

list.ReverseRecursive();
            list.Verify(true);
        }
    };

class FuzzBuzz
    {
    public:

// выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, 
        // программа должна выводить слово «Fizz», а вместо чисел, кратных 
        // пяти - слово «Buzz». Если число кратно и 3, и 5, то программа должна 
        // выводить слово «FizzBuzz»

static void Do()
        {
            using namespace std;

for(int i = 1; i < 101; ++i)
            {
                bool mod3 = ((i % 3) ==  0);
                bool mod5 = ((i % 5) ==  0);

if (mod3 && mod5) std::cout << "FuzzBuzz" << std::endl;
                else if (mod3) std::cout << "Fuzz" << std::endl;
                else if (mod5) std::cout << "Buzz" << std::endl;
                else std::cout << i << std::endl;
            }
        }
    };

} // namespace Test