о простых задачах (программистское)

[avva]

Хорошая задача для интервью: взять квадратный двумерный массив и повернуть его на 90 градусов.

Хорошая в том смысле, что она отделяет возможных агнцев от несомненных козлищ. Если кандидат может это уверенно сделать, это еще ничего не значит; но если не знает даже, как подойти (см. описание по ссылке), то это уже о многом говорит.

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

Comments

[moon-aka-sun.livejournal.com]

Главное - язык правильно выбрать!

   a =. i.4 4
   a
 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15
   |:|.a
12  8 4 0
13  9 5 1
14 10 6 2
15 11 7 3

[labor-lobby.livejournal.com]

Странно, обычно положительным поворотом считается "против часовой" :)

[spamsink.livejournal.com]

Какая досада, я как раз сегодня интервьюировал одного кандидата. Как за линейное время удалять из вектора числа, обладающие определенным свойством, он так и не догадался.

[kondybas.livejournal.com]

За линейное? Не догадался? Гггг...

[labor-lobby.livejournal.com]

В самом деле зависит от контекста. Если массив - сетка высот, имеет смысл написать общий алгоритм поворота на произвольный угол, для преобразований, например, скопированного участка terrain.

[object.livejournal.com]

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

[ded_flint.livejournal.com]

транспонировать, отразить по вертикали, затем по горизонтали

[sleeping-death.livejournal.com]

только по вертикали ;)

[reut.livejournal.com]

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

[sleeping-death.livejournal.com]

без использования второго массива интереснее.

[http://users.livejournal.com/_bigbrother_/]

Я чего-то не понимаю?

Использование второго массива разрешено?

Если да, то это... как мне кажется, это просто не задача. Всё абсолютно и совершенно очевидно.

Более того, оно не так сложно и в случае ровно одного массива... но вот это я с листа так, чтобы заработало, могу и не написать :).

[ivan-gandhi.livejournal.com]

Это нам очевидно, а им, кандидатам - смертельный номер.

BUG!!!!!

[iratus.livejournal.com]

решение:
http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx

' For LEFT turns
For Y = 0 to 3
For X = 0 to 3
Destination(Y,X) = Source(X,Y)
Next
Next

Я ошибаюсь, или левый поворот - фигня полная.?????
например элемент(0,0) так и останется (0,0) после трансформации a должен стать (0,3)

Это не поворот, а отражение через диагональ или я не выспался с утра :-)

Re: BUG!!!!!

[ded_flint.livejournal.com]

это называется транспонирование

[kondybas.livejournal.com]

Я давно на беседах с кандидатами всерьез задаю только один вопрос: какие три материала по специальности вы прочитали последними? Если помнит хоть один - на сегодня это уже хорошо.

[iratus.livejournal.com]

это хорошо, когда специальность так четко можно определить :-)

[bazanovv.livejournal.com]

Вопрос не в тему - а для не-программиста в Гуголь вообще реально попасть работать?

[avva.livejournal.com]

Конечно, здесь же все-таки не только программисты работают.

[vasja-iz-aa.livejournal.com]

А я бы данные не трогал, а сменил бы код вызываемый по Get(i,j). Ну, это так, первая мысль по первому впечатлению.

[malaya-zemlya.livejournal.com]

Комбинирование данных (например, рисование повернутых спрайтов на неповернутом фоне) тогда превращается в веселую задачу.

[dzz.livejournal.com]

Если кандидат не знает, как подойти к этой задаче, он вообще зря считает себя программистом ;)

[psilogic.livejournal.com]

Веселее бывает с кандидатами, которые якобы все могут и со всем имели дело... :]

[ivan-gandhi.livejournal.com]

Вот такого я и интеврьюировал сегодня.

[janatem.livejournal.com]

Не понял в чем смысл задачи (как для задачи для собеседования). Вроде любое тупое решение, которое можно помыслить, всего лишь в константу хуже оптимального (невероятно, чтобы существовало решение лучше чем O(числа элементов)?).

Да, можно явно потребовать, чтобы всё происходило in place. Но тогда это требование будет подсказкой -- достаточно увидеть, что орбита каждого элемента имеет длину 4 и устроена однообразно (за исключением центра матрицы нечетного размера). Остается только правильно перебрать все орбиты и циклически переставить элементы каждой из них.

Можно, кончено, побороться за минимизацию операций в циклической перестановке; пять операций -- тривиально, а как сделать за четыре, я не вижу. Пусть это будет отдельной задачей (доказать, что невозможно). ;)

А, ну еще подзадача -- придумать cache-frienly последовательность перебора орбит...

[valez.livejournal.com]

вариант с орбитами, например, менее красив, чем вариант с транспонированием и последующим отражением. Хорошая, в принципе, задача, чтобы понять как кандидат думает:)

[wildernesscat.livejournal.com]

Does is say "rotate in place", or not? I couldn't find any such requirement. The problem becomes trivial.

[volk007.livejournal.com]

Я для разогрева спрашиваю "reverse single-linked list". Хороший кандидат пишет за 5 минут, средний за 15, во время мучений плохого можно спокойно попивать чаек и смотреть в окно, потом, что бы заполнить необходимый час, попросить написать тест к этой функции (хорошие и средние, естественно, получают сложные вопросы).

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

[valez.livejournal.com]

Нас, например, этому в 9м классе школы еще учили. Наверное такое интервью касается больше вопросов быстрой квалификации совершенного человека с улицы, не глядя в его резюме? Типа как вопрос "что такое операционная система и почему ее нет в стиральной машине" на экзамене по курсу "Операционные системы", который я задавал сходу всем экзаменуемым на ВМиК МГУ?

[valez.livejournal.com]

А насколько нормально будет выглядеть кандидат, который утверждает, что сможет запрограммировать что угодно на чем угодно, но только если ему дадут книжку с описанием синтаксиса языка? И действительно сможет это сделать? Или знание синтаксиса (т.е. то, что человек совсем недавно серьезно на этом языке программировал) не менее важно?

[avva.livejournal.com]

Наверное, зависит от интервьюера.

С моей точки зрения, знание синтаксиса вторично, но тем не менее, если у человека в резюме написано, что он знает C, то скобки ставить в правильных местах и определять переменные он по идее должен уметь. Если он, скажем, не помнит, что обозначается &, а что |, или писать надо ~ABC::ABC или ABC:::~ABC, но помнит, что это за штуки и зачем нужны, меня это не смущает.

[woodshy.livejournal.com]

поворот без использования дополнительной матрицы для произвольной NxN матрицы:


void rotateContour(int top, int len){
for(int i=0; i<len-1; i++){ int tmpval = arr[top][top+i]; arr[top][top+i]=arr[top+len-1-i][top]; arr[top+len-1-i][top]=arr[top+len-1][top+len-1-i]; arr[top+len-1][top+len-1-i]=arr[top+i][top+len-1]; arr[top+i][top+len-1]=tmpval; } } void rotate90CW(){ for(int i=0; i<N/2; i++) rotateContour(i,N-i*2); } arr - массив rotate90CW() - функция, осуществляющая поворот. Хочу в Гугл! :)

вот мое решение consle app. на С#

[pavelm123.livejournal.com]

идея была в сдвиге четырех чисел по очереди (функция Switch4). Вроде бы получилось.

class Program
{
//static int[,] A = new int[4,4]{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
//static int N = 4;

static int[,] A = new int[5,5]{{1, 2, 3, 4, 5}, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}};
static int N = 5;

static void Main(string[] args)
{
Print();
Console.WriteLine();

Rotate();
Print();
Console.WriteLine();

Rotate();
Print();
Console.WriteLine();

Rotate();
Print();
Console.WriteLine();

Rotate();
Print();
Console.WriteLine();

Console.ReadLine();
}

static void Rotate()
{
for (int i = 0; i < N / 2; i++)
{
for (int j = i; j < N - i - 1; j++)
{
Switch4(i, j);
}
}
}

static void Switch4(int row, int col)
{
int n=N-1;
int leftUpper = A[row, col];
A[row, col] = A[n - col, row];
A[n - col, row] = A[n - row, n - col];
A[n - row, n - col] = A[col, n-row];
A[col, n - row] = leftUpper;
}

static void Print()
{
for(int i=0;i<N;i++) { for (int j = 0; j < N; j++) Console.Write(A[i, j].ToString() + " "); Console.WriteLine(); } } }

Re: вот мое решение consle app. на С#

[woodshy.livejournal.com]

ну это для фиксированного N... так не интересно ;)

[dimrub.livejournal.com]

> Once you can write the answer on the whiteboard by heart without even thinking, you get annoyed by anyone who takes more than a few seconds thinking about it.

Да, есть такое дело. Пожалуй, действительно пора менять вопросы.

[woodshy.livejournal.com]

выше я уже писал, но там не срослось с разметкой :)
поправил.
Хочу в Гугл :)

я всё-таки его заборол! :)

arr - массив
rotate90CW() - функция, осуществляющая поворот.

void rotateContour(int top, int len){
    for(int i=0; i&tl;len-1; i++){
        int tmpval = arr[top][top+i];
        arr[top][top+i]=arr[top+len-1-i][top];
        arr[top+len-1-i][top]=arr[top+len-1][top+len-1-i];
        arr[top+len-1][top+len-1-i]=arr[top+i][top+len-1];
        arr[top+i][top+len-1]=tmpval;
  }
}

void rotate90CW(){
    for(int i=0; i<N/2; i++)
        rotateContour(i,N-i*2);
}

[valez.livejournal.com]

ну, наверное решившим такую задачу не в Гугл надо, а сдавать контрольную в школе на уроке информатики:)

Лично меня ваш код пугает и я не хочу в нем разбираться:) Мне кажется это хороший пример того, когда каждая строчка кода должна быть подробно закомментирована

Поворот квадратной матрицы NxN

[zuber.livejournal.com]

Ячейки заданы парой координат i, j со значениями 0 до N-1. Выделяем в матрице 1/4 часть "треугольную" часть, которая покажет индексы для обхода (b1; b1). Из индексов первой части легко найти соответствующие индексы в других частях (a2; b2), (a3; b3), (a4; b4) и сделать обмен через переменную.

Деление матрицы наглядно показано на рисунке, исходная часть показана красным, вторая -- синим, третья -- зелёным, четвёртая -- жёлтым.



Центр при нечётном N в повороте не нуждается, отсеивается как отбрасывание целой части N/2.

for(j = 0; j < N/2; j++)
{
b1 = j;
a2 = N - b1 - 1;
b3 = a2;
a4 = b1;

for(i = j; i < N - j - 1; i++)
{
a1 = i;
b2 = a1;
a3 = N - a1 - 1;
b4 = a3;

swap = m[a4][b4];
m[a4][a4] = m[a3][a3];
m[a3][a3] = m[a2][a2];
m[a2][a2] = m[a1][a1];
m[a1][a1] = swap;
}
}

P.S. Поправил расчёт координат.

Re: Поворот квадратной матрицы NxN

[zuber.livejournal.com]

Конечно же, "отбрасыванием дробной части".

немецкий Google

[(Anonymous)]

Анатолий, оффтоп.

Простите, вопрос.
Мне вот интересно возится с алгоритмами.
У меня 4 последних года стажа в AI логических игр.
Деревянный английский (пассивный, говорю безграмотно) и хороший немецкий.
Знаю только Windows.

Мне стоит подавать в немецкий Google или дохляк?

Re: немецкий Google

[avva.livejournal.com]

Я даже не знаю, набирает ли немецкий Гугл программистов сейчас. Но если набирает, то попробовать по-моему всегда можно. Правда, как минимум часть интервью почти наверняка будет по-английски, тут уж ничего не поделать.

[samlazy.livejournal.com]

Я зная зачем в Гугле спрашивают на интервью подобную хрень. Когда кто-то один раз за 20 лет программирования сталкивается на практике с такой задачей то он первым делом спрашивает Гугл. Так надо, что бы был кто-то, кто может сразу подогнать решение.
:)

[avva.livejournal.com]

Задача из Майкрософта вообще-то :)