Задачи на собеседовании в одну небезызвестную контору

[CDR]

Цитата:

Сообщение от blokva

А по моему гораздо проще:
"Какова вероятность того что Вы встретите на улицах города динозавра? Ответ: 1/2 Либо встречу, либо нет!" (с)

Соответственно пассажир номер n (в данной задаче это 71 просто уловка ИМХО) либо сядет на свое место либо нет!

[e@gle]

Цитата:

Сообщение от oip

Уверены?

Нет. Теперь уверен в обратном.
Поспешил-с

[TGL]

Задача про бочки решается так: Если в первой бочке после манипуляций оказалось Х красной краски, то так как объемы бочек до и после манипуляций равны, то соответственно во второй бочке находится Х синий краски.

А первые 2 задачи решить тривиально сходу у меня не получается и думаю не возможно. Например, 2ю задачу я свел к такому перебору: Любое число >1 до 100 можно представить в виде a**k или a**k x b**m или a**k x b**m х с**n, где a,b,c - простые и разные числа > 1; k,n,m - натуральные числа > 1. Например: 70 = 2**1 х 5**1 х *7**1;
99 = 3**2* х 11**1. Так вот, если некое число представимо в виде a**k x b**m х с**n, то соотв. выключатель "щелкнут"
(k+1)x(n+1)x(m+1) раз. Поэтому если это число будет нечетным - то лампочка в итоге будет гореть. Например, 70-ю лампочку "щелкнут" 2х2х2 = 8 раз => она гореть не будет. Короче будут гореть все лампочки с номерами у которых в упомянутом выше представлениях все числа k,n,m - четные плюс 1я лампочка. Например, 100я лампочка (=2**2х5**2 щелкнется 9 раз) будет гореть. 5 класс это сделает только на спец.кружке по математике

[avf]

Первая задачка решается логически. Ведь у кааждого чела, оказавшегося в ситуации, что его место занято, есть выбор - либо разобраться в ситуации и сесть на первое место, предотвратив тем самым дальнейший пересорт по местам, либо забить болт и занять любое другое свободное место. Таким образом вероятность, действительно, 50 на 50.
Формулировка с сумашедшей старушкой в самолете выглядит забавней: ))

[Andrew Akhmetov]

100 лампочек:
включены будут номера 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

до пол второго не спал из-за этой задачи (нечетное число делителей у чисел с полным квадратом)

[ivas]

нашел решение задачи про перестановки оказывается все просто нужно в начале элементы отсортировать)
взято отсюда:
http://xpoint.ru/forums/programming/...ad/28625.xhtml

#include <stdio.h>
#include <string.h>
                                                                                                                                                                      
int main()
{
        char str[20];
        int n,k,t,y;
        int ttt=1;
        strcpy(str,"111223");
        printf ("%s\n",str);
        n=strlen(str)-1;
while(1)
{
        k=n-1;
        while ((str[k]>=str[k+1])&&(k>=0)) k--;
        if (k<0) {return(0);}
        t=k+1;
        while ((t<n)&&(str[t+1]>str[k])) t++;
        y=str[k];
        str[k]=str[t];
        str[t]=y;
        t=0;
        while (t<(int)((double)(n-k)/2.0))
        {
                y=str[n-t];
                str[n-t]=str[k+1+t];
                str[k+1+t]=y;
                t++;
        }
        printf ("%s\n",str);
}
}

[avf]

перестановки: Всё гениальное - простынь)
Произвольную перестановку можно представить в виде суперпозиции транспозиций соседних элементов. [[Липский] Комбинаторика_для программистов.] Т.е. достаточно n! раз последовательно попарно переставить соседние элементы:

#define.CONDATA([' a', ' b', ' c'])
static void Transpositions(Args _args)
{
    Container       con = #CONDATA;
    Int             pos = 1,
                    len = conlen(con),
                    transCount = factorial(len);

    boolean anyMoreTrans()
    {;
        transCount--;
        return transCount;
    }

    void swap(int _i, int _j)
    {
        AnyType tmp = conpeek(con, _i);
        ;
        con = conpoke(con, _i, conpeek(con, _j));
        con = conpoke(con, _j, tmp);
    }

    void swapNextPair()
    {
        Int nextPos = (pos == len) ? 1 : pos+1;
        ;
        swap(pos, nextPos);
        pos = nextPos;
    }
    ;

    setprefix("Перестановки:");
    info(con2Str(con));
    while (anyMoreTrans())
    {
        swapNextPair();
        info(con2Str(con));
    }
}

[dn]

Ещё один вариант...

BMRandom    bmrandom = new bmRandom();
    container   a = ['a','b','c','d'];
    container   b;
    int         i,L,N;
    set         result = new set(types::Container);
    set         exception;
    int random(int _max)
    {
        int ret;
        ;
        ret =  bmrandom.num(_max,1);
        if (exception.in(ret))
        {
            ret = random(_max);
        }
        else
        {
            exception.add(ret);
        }
        return ret;
    }
    container fillcon()
    {
        container c;
        ;
        exception = new set(types::Integer);
        for (i = 1;i<=L;i++)
        {
            c=conins(c,conlen(c)+1,conpeek(a,random(L)));
        }
        return c;
    }
    ;
        L = conlen(a);
        N = factorial(L);
        result.add(a);
        info(con2str(a));
        do
        {
            b = fillcon();
            if(!result.in(b))
            {
                result.add(b);
                info(con2str(b));
            }
        }
        while (result.elements() < N);

[CDR]

Цитата:

Сообщение от avf

перестановки: Всё гениальное - простынь)
Произвольную перестановку можно представить в виде суперпозиции транспозиций соседних элементов. [[Липский] Комбинаторика_для программистов.] Т.е. достаточно n! раз последовательно попарно переставить соседние элементы:

Хм... Не плохой вариант, основной недостаток - алгоритм не работает для n>3 .

Цитата:

Сообщение от dn

Ещё один вариант...

BMRandom    bmrandom = new bmRandom();
    container   a = ['a','b','c','d'];
    container   b;
    .......
    while (result.elements() < N);

Ура! Это решение вроде как работает для всех n!
Единственный серьезный минус - количество проходов цикла. В лучшем случае цикл делает в 2 раза больше проходов, чем нужно для поиска всех перестановок. У меня этот алгоритм выдал следующие результаты:

• Для n = 3 количество решений 6, количество проходов цикла 12
• Для n = 5 количество решений 120, а количество проходов цикла уже 696

И еще желательно в решении не используются нестандартные типы данных: контейнер, множество. Лучше все-таки обойтись стандартными типами данных - целые и вещественные числа, строки, а так же их массивы.
Небольшая оптимизация цикла и используемых типов данных - и решение получится идеальным .

[HorrR]

Про 4ех беглецов. Задача решается очень просто, если понять как оптимизировать процесс. Надо что бы 3ий и 4ый( 5, 10 минут перехода - самые медленные) бежали вместе и не возвращались(условно вместо 15ти получаем 10ть - пересечение скорости). Итак перебегают 1ый и 2ой, 1ый возвращается, неся фонарик 3ему и 4му( 2минуты+1 минута на возвращение 1го, итого: 3) 5 и 10 бегут за 10 минут и передают фонарик второму, который возвращается за первым(2 минуты) и они оба перебегают за 2 минуты. Итого: 3+10+2+2=17.


З.Ы Не перебегут эти 4ро за 17 минут. Только думать минут 10 будут)

[dn]

Цитата:

Сообщение от CDR

Ура! Это решение вроде как работает для всех n!
Единственный серьезный минус - количество проходов цикла.

...
И еще желательно в решении не используются нестандартные типы данных: контейнер, множество. Лучше все-таки обойтись стандартными типами данных - целые и вещественные числа, строки, а так же их массивы.
Небольшая оптимизация цикла и используемых типов данных - и решение получится идеальным .

Задачу можно решить либо быстро, либо красиво... Решение с "бросанием костей" изначально не претендует на минимизацию кол-ва проходов цикла, но зато не надо долго ломать голову над алгоритмом.
Теперь насчет стандартных типов данных. Все правильно, но только для программиста на X++ container и set, являются более стандартными типами, чем массив, ИМХО. Я не припомню что-то практических задач в Axapta, где мне бы потребовалось использовать массив...
А на закуску "красивое" решение, вообще без циклов

#define.N(5)
static void job001(Args _args)
{
    str 1 a[#N];
    void init()
    {
        a[1] = 'a';
        a[2] = 'b';
        a[3] = 'c';
        a[4] = 'd';
        a[5] = 'e';
    }
    str makestr(str 1 b[#N], int level = 1)
    {
        return (level<#N)?b[level]+makestr(b,level+1):b[level];
    }
    void show (str 1 b[#N])
    {
        ;
        //info(b[1]+b[2]+b[3]+b[4]+b[5]);
        info(makestr(b));
    }
    void f(str 1 b[#N], int level=1, int shift=1)
    {
        str 1   c[#N];
        ;
        if (level < #N-1)
        {
            f(b,level+1,1);
        }
        if(shift <= #N-level)
        {
            c=b;
            c[level] = b[level+shift];
            c[level+shift] = b[level];
            show(c);
            f(c,level,shift+1);
        }
    }
    ;
    init();
    show(a);
    f(a);
}

[CDR]

Цитата:

Сообщение от dn

Задачу можно решить либо быстро, либо красиво... Решение с "бросанием костей" изначально не претендует на минимизацию кол-ва проходов цикла, но зато не надо долго ломать голову над алгоритмом.
Теперь насчет стандартных типов данных. Все правильно, но только для программиста на X++ container и set, являются более стандартными типами, чем массив, ИМХО. Я не припомню что-то практических задач в Axapta, где мне бы потребовалось использовать массив...
А на закуску "красивое" решение, вообще без циклов
***

Эта, однозначно, пять! "Респект и уважуха" (с).
Что бы вы не делали, всегда нужно стремиться сделать это красиво! Ведь "красота спасет мир" (С) .
Позволю себе небольшое исправление вашего "шедевра"

#define.N(5)
static void job001(Args _args)
{
    str 1   a[#N];
    str     resource = 'abcdefghijklmnopqrstuvwxyz';
    
    Set     validateSet; // Автоматическая проверка
    
    void init(Int _idx)
    {
        if (_idx == 0)
            return;

        a[_idx] = substr(resource, _idx, 1);
        init(_idx - 1);
    }

    str makestr(str 1 b[#N], int level = 1)
    {
        return (level<#N)?b[level]+makestr(b,level+1):b[level];
    }

    void show (str 1 b[#N])
    {
        str result;
        ;

        result = makestr(b);

        if (validateSet.in(result))// Автоматическая проверка
        {
            error('Doubling!');
        }
        else
        {
            info(result);
            validateSet.add(result);
        }
    }
    void f(str 1 b[#N], int level=1, int shift=1)
    {
        str 1   c[#N];
        ;

        if (level < #N-1)
        {
            f(b,level+1,1);
        }
        if(shift <= #N-level)
        {
            c=b;
            c[level] = b[level+shift];
            c[level+shift] = b[level];
            show(c);
            f(c,level,shift+1);
        }
    }
    ;

    validateSet = new Set(Types::String);  // Автоматическая проверка
    
    init(#N);
    show(a);
    f(a);

    info(strfmt('Total: %1 elements.', validateSet.elements()));  // Автоматическая проверка
}

Ну, собственно, на этом можно считать DAX-сообщество подготовленным к собеседованию в Goooogle .

[MikeR]

вот куда стремимся попасть на работу

[Qaz Qwerty]

Вот же, не работать мне в Гугле. Все понимаю, кроме вероятности 1/2. Ну почему 1/2 а не 1/71, кто-нибудь может объяснить?

[Qaz Qwerty]

Ага, вот здесь: http://kasparovchess.crestbook.com/v...287&action=new нашлось понятное объяснение.