Здравствуйте, Nose, Вы писали:

N>А можно на задачки глянуть? Если не хочешь публиковать то skeevee (at) gmail.com
N>И анкету тогда заодно, полюбопытствовать

60% приведенных вопросов и задач — от M$

Автор: alexanderfedin
Дата: 24.02.05

Здравствуйте, Tiamer, Вы писали:

T>Нам интересна стратегия тех кто прощел. (Например твоя).
T>Рассказ о том как ты старался отвечать, как правильно себя вести в случае если вопрос
T>ставит в тупик. В любом деле важна стратегия, как его выполнить успешно.
Стратегия такова: если вопрос ставит в тупик, то в этот тупик ни под каким видом не вставать. Думать, спрашивать, рассуждать вслух. Показывать, как вы можете решать проблему.

Здравствуйте, _ilich_, Вы писали:

__>Походу дела меня прокатили

__>Было всего 4 из 5ти, вопросы совершенно обычные, ничего хитрого или
__>того, над чем стоило бы серьезна подумать...

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

Здравствуйте, LaFlour, Вы писали:

LF>Здравствуйте, _ilich_, Вы писали:

__>>Походу дела меня прокатили

__>>Было всего 4 из 5ти, вопросы совершенно обычные, ничего хитрого или
__>>того, над чем стоило бы серьезна подумать...

LF>В последний день нас почемуто только 3е опросило, причина не ясна.
LF>Одного парня оставили он, у тестера проходил 4е интервью.
LF>По уровню задачки гдето на порядок сложнее были, деревья, графы, циклические списки.
LF>Может кто из присутсвующих сегодня еще что добавит.

Т.е. десетерых, которых взяли на дополнительное интервью
скорее всего возьмут... Мои им поздравления!
Пошел вешаться

Здравствуйте, _ilich_, Вы писали:

__>>>Было всего 4 из 5ти, вопросы совершенно обычные, ничего хитрого или
__>>>того, над чем стоило бы серьезна подумать...

LF>>В последний день нас почемуто только 3е опросило, причина не ясна.
LF>>Одного парня оставили он, у тестера проходил 4е интервью.

__>Т.е. десетерых, которых взяли на дополнительное интервью
__>скорее всего возьмут... Мои им поздравления!

А может отправили проверять, а стоит ли вообще брать? Или как тестером возьмут

__>Пошел вешаться

Да ну, читай книги, готовься к следующему

Был я вчера на этом интервью. Честно говоря, я ожидал худшего. Ни единой головоломки или вопроса из стиля techinterview. Интервьюировало 5 человек по 45 минут на каждого плюс перерывы. Я сначала волновался, но довольно быстро расслабился и начал получать удовольствие

Спрашивали разные задачки на алгоритмы, хотя временами довольно хитрые задачки. Не с первого раза, но на все задачи я нашел оптимальные алгоритмы. Если кому интересно, могу и задачки написать, которые пока еще помню.

Что интересно, в моей пятерке у двоих было только 4 интервью, а потом их закруглили. Даже не знаю, хорошо это или плохо...

S>Спрашивали разные задачки на алгоритмы, хотя временами довольно хитрые задачки. Не с первого раза, но на все задачи я нашел оптимальные алгоритмы. Если кому интересно, могу и задачки написать, которые пока еще помню.

Интересно, можно в форум можно в мыло.

Странно? а у нас у всех было 4 интервью.
Причём Рейчал сразу сказала что будет 3-4 интервью.
А что за задачи были интересно те же или другие?
Можно на мыло prog200500(собака)mail.ru

V>можно в мыло.
valmond::gmail.com

Здравствуйте, valmond, Вы писали:

S>>Спрашивали разные задачки на алгоритмы, хотя временами довольно хитрые задачки. Не с первого раза, но на все задачи я нашел оптимальные алгоритмы. Если кому интересно, могу и задачки написать, которые пока еще помню.

V>Интересно, можно в форум можно в мыло.
можно сюда

S>Спрашивали разные задачки на алгоритмы, хотя временами довольно хитрые задачки. Не с первого раза, но на все задачи я нашел оптимальные алгоритмы. Если кому интересно, могу и задачки написать, которые пока еще помню.

Надеюсь, эти задачки не считаются тайной переговоров, и мне за них бо-бо не сделают...

1. Написать ф-ю, реверсирующую слова в строке (char*) in-place. Не использовать дополнительной памяти. Я, когда написал, забыл про то, что слова разделяются не только пробелами и про то, что апостроф (') — в англ. языке тоже часть слова, а не разделитель.

2. Написать эффективную ф-ю поиска подстроки в строке, не используя стандартные функции C runtime. Тут можно несколько весьма полезных ухищрений предложить.

3. Дан массив целых чисел int A[N]. Напечатать все возможные перестановки (каковых будет N!). Алгоритмов можно придумать много, но меня еще дополнительно попросили алгоритм без выделений дополнительной памяти и in-place.

4. Дана матрица int A[N][N]. Среди чисел могут встречатся нули. Нужно обнулить строки и столбцы, на пересечении которых стоят эти нули. Опять же, после одного из решений попросили написать алгоритм без доп.памяти, не рекурсивный и in-place.

5. Есть ф-я void strupr(char* s), которая переводит строку в верхний регистр (коды символов неизвестны, т.к. для русских букв, например, бывают разные кодировки). Надо написать ф-ю void strlwr(char* s), которая переводит строку в нижний регистр, используя strupr.

6. Даны два числа: int n, m. Написать ф-ю возведения n в степень m, максимально эффективным образом.

Ко всем задачам, после 1-2 решений, просили написать оптимальный алгоритм, лишенный всех недостатков предыдущих решений (выделения доп.массивов, лишние копирования, большая сложность O(...) и т.д.). Некоторые задачи просили тут же на листочке и протестировать, предложить разнообразные test cases (видимо, проверяли креативность).

S>5. Есть ф-я void strupr(char* s), которая переводит строку в верхний регистр (коды символов неизвестны, т.к. для русских букв, например, бывают разные кодировки). Надо написать ф-ю void strlwr(char* s), которая переводит строку в нижний регистр, используя strupr.

Да наверно мне рано в MS, но я что то не понимаю как можно это сделать если коды неизвестны?
Ну с английскими — просто, насколько я помню для них гарантируется последовательное размещение, а смещение всегда 26. Для русcких же это не так даже в ASCII.

Ещё странно что каждый по 2 задачки задавал получается?
У нас каждый по одной задачи спрашивал, больше не успеть мне кажется.
45 мин интервью: 15-20 мин. болтали про опыт, получается если 2 задачи то 10-15 мин на задачу с написанием кода и обсуждением.

Здравствуйте, _ilich_, Вы писали:

__>Здравствуйте, LaFlour, Вы писали:

LF>>Здравствуйте, _ilich_, Вы писали:

__>>>Походу дела меня прокатили

__>>>Было всего 4 из 5ти, вопросы совершенно обычные, ничего хитрого или
__>>>того, над чем стоило бы серьезна подумать...

LF>>В последний день нас почемуто только 3е опросило, причина не ясна.
LF>>Одного парня оставили он, у тестера проходил 4е интервью.
LF>>По уровню задачки гдето на порядок сложнее были, деревья, графы, циклические списки.
LF>>Может кто из присутсвующих сегодня еще что добавит.

__>Т.е. десетерых, которых взяли на дополнительное интервью
__>скорее всего возьмут... Мои им поздравления!
__>Пошел вешаться

Additional interview is definitely good sign...

Здравствуйте, Prog2005, Вы писали:

S>>5. Есть ф-я void strupr(char* s), которая переводит строку в верхний регистр (коды символов неизвестны, т.к. для русских букв, например, бывают разные кодировки). Надо написать ф-ю void strlwr(char* s), которая переводит строку в нижний регистр, используя strupr.

P>Да наверно мне рано в MS, но я что то не понимаю как можно это сделать если коды неизвестны?
P>Ну с английскими — просто, насколько я помню для них гарантируется последовательное размещение, а смещение всегда 26. Для русcких же это не так даже в ASCII.

P>Ещё странно что каждый по 2 задачки задавал получается?
P>У нас каждый по одной задачи спрашивал, больше не успеть мне кажется.
P>45 мин интервью: 15-20 мин. болтали про опыт, получается если 2 задачи то 10-15 мин на задачу с написанием кода и обсуждением.

Влоб — строишь табличку low-high через strupr(), реверсишь и работаешь.
можно придумать и более экзотические методы...

Здравствуйте, Prog2005, Вы писали:

S>>5. Есть ф-я void strupr(char* s), которая переводит строку в верхний регистр (коды символов неизвестны, т.к. для русских букв, например, бывают разные кодировки). Надо написать ф-ю void strlwr(char* s), которая переводит строку в нижний регистр, используя strupr.

P>Да наверно мне рано в MS, но я что то не понимаю как можно это сделать если коды неизвестны?
P>Ну с английскими — просто, насколько я помню для них гарантируется последовательное размещение, а смещение всегда 26. Для русcких же это не так даже в ASCII.

Может дело в 7 бите? Как известно, если даже коды символов неизвестны, то таблицы строятся по правилам, при которых наличие этого бита означает upper case, а его отсутствие — lower case. Поэтому возможен такой вариант, когда мы вызываем strupr, получаем разницу и дальше с ней работаем. Сейчас попробую написать код :)

Здравствуйте, Roman Pushkin, Вы писали:

RP>Может дело в 7 бите? Как известно, если даже коды символов неизвестны, то таблицы строятся по правилам, при которых наличие этого бита означает upper case, а его отсутствие — lower case. Поэтому возможен такой вариант, когда мы вызываем strupr, получаем разницу и дальше с ней работаем. Сейчас попробую написать код :)

не получается для всех кодировок, только для стандартной виндовой, досовская уже бьется. Поэтому через таблицу подстановки скорее всего.

Здравствуйте, Roman Pushkin, Вы писали:

RP>Поэтому через таблицу подстановки скорее всего.

Конечно!

void strupr(char* str);

void strlwr(char* str)
{
    char upr[256];
    char lwr[256];
    for (char c='\x00';c<='\xFF';++c)
    {
        upr[c]=c;
        lwr[c]=c;
    }
    strupr(upr);
    for (char i='\x00';i<='\xFF';++i)
        if (i!=upr[i])
            lwr[upr[i]] = i;

    while (str)
    {
        *str = lwr[*str];
        ++str;
    }
}

Да надо мне читать учиться.
Я то подумал что надо обе функции написать.
Интересно а есть решение без построения таблицы?
Ведь наверняка хотели услышать не такое очевидное решение.

Здравствуйте, Starlight, Вы писали:

...

S>3. Дан массив целых чисел int A[N]. Напечатать все возможные перестановки (каковых будет N!). Алгоритмов можно придумать много, но меня еще дополнительно попросили алгоритм без выделений дополнительной памяти и in-place.

...

Алгоритм 3 без выделений дополнительной памяти и in-place показался тяжеловатым для интервью под стрессом. Вот что удалось придумать ничем не пользуясь:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    bool stop = argc < 2;
    for (int i = 1; !stop; ++i)
    {
//    output
        int j;
        for(j = 1; j < argc; ++j)
            cout << argv[j] << ((j == argc - 1)? "\n" : " ");

        j = 2;
        for (int buf = 2; 0 == (i % buf); buf *= (++j))
            ;
        j = argc - j;
        if (j < 1) 
        {
            j = 1;
            stop = true;
        }
        reverse(argv + j, argv + argc);
    }

    return 0;
}

Казалось бы просто, но пришлось-таки поломать голову. Непонятно, что, может, попроще, мог упустить и где?

Здравствуйте, WeCom, Вы писали:

WC>Здравствуйте, Roman Pushkin, Вы писали:

RP>>Поэтому через таблицу подстановки скорее всего.

WC>Конечно!

WC>

WC>void strupr(char* str);

WC>void strlwr(char* str)
WC>{
WC>    char upr[256];
WC>    char lwr[256];
WC>    for (char c='\x00';c<='\xFF';++c)
WC>    {
WC>        upr[c]=c;
WC>        lwr[c]=c;
WC>    }
WC>    strupr(upr);
WC>    for (char i='\x00';i<='\xFF';++i)
WC>        if (i!=upr[i])
WC>            lwr[upr[i]] = i;

WC>    while (str)
WC>    {
WC>        *str = lwr[*str];
WC>        ++str;
WC>    }
WC>}
WC>

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