Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 140
Подозреваю, что есть математическая формула вывода текущего значения массива. Кто-нибудь может поделиться?
Все подстроки — дают прибавку на арифметическую прогрессию, так что формула (с 4-мя if) выводится однозначно
Прогрессия самая простая (1|1,2|2,3|3,4 и т.д.). Полчаса ушло на отладку. А вообще такие задачки бодрят :)
int max=9, r=1, x=0,y=0;
int[,] m=new int [max,max];
float border = max-0.6f;
for (int d = 0; d < 2*max-1; d++)
{
for (int i=0; i< Mathf.RoundToInt(border);i++) {m[d%4==1?x++:d%4==3?x--:x, d%4==0?y++:d%4==2?y--:y] = r++;}
border -= d==0?0f:0.5f;
}
m[x,y]=r;
А если ещё подумать, то можно уложиться чуть ли не в одну строчку:
int max=9, r=1, x=0,y=0;
int[,] m=new int [max,max];
float border = max-0.6f;
for (int d = 0; d < 2*max-1; border -= d++ ==0?0f:0.5f) {for (int i=0; i< Mathf.RoundToInt(border);i++)
{m[d%4==1?x++:d%4==3?x--:x,d%4==0?y++:d%4==2?y--:y]=r++;}}
m[x,y]=r;
Прошу прощения если надоел кому-то, но не давала покоя мысль, что можно сделать ещё короче:
int max=9, r=1, x= -1,y=0;
int[,] m=new int [max,max];
float border = max;
for (int d = 2; d <= 2*max+1; border = max+0.5f - 0.5f*d++) {for (int i=0; i< (int)(border);i++) {m[x+=(d%4-1)%2, y+=(d%4-2)%2] = r++;}}
Шикарно!!! Дёшево и сердито! )
Тогда уж так:
Никаких float…
int max=6,x=-1,y=0,r=1;
int[,] A=new int[max,max];
for(int d=1;d<=2*max;d++) for(int k=0;k<max-d/2;k++) A[y+=(d%4-1)%2,x-=(d%4-2)%2]=r++;
Никаких float…
Да, надо было от дробных избавиться. Ну, раз пошла такая пьянка:
int max=9; int[,] m=new int[max,max];
for(int d=1,r=1,x=-1,y=0,b=max;d<=2*max; b+=max-d+d++/2) while (r<=b) m[x-=(d%4-2)%2,y+=(d%4-1)%2]=r++;
Только сейчас заметил, что это решение уже можно отправлять в @TinyProof ;)
И правда…
int N=6,x=-1,y=0,r=1;
int[,] A=new int[N,N];
for(int d=1;d<2*N;d-=(N*d-d*d/4-r)>>31) A[y+=(d%4-1)%2,x-=(d%4-2)%2]=r++;
Или даже так — чтобы убрать зависимость от размера int:
int N=6,x=-1,y=0,r=1;
int[,] A=new int[N,N];
for(int d=1;d<2*N;d+=N*d-d*d/4<r?1:0) A[y+=(d%4-1)%2,x-=(d%4-2)%2]=r++;
Господа, если ряд ваших решений окажется сходящимся, спустя бесконечный промежуток времени вы докажете, что задача решается в 0 байт кода (но при этом все еще программно). Предлагаю сильно не увлекаться, дабы случайно не нарушить какой-нибудь фундаментальный закон природы.
А в целом — очень круто. Особенно круто в сравнении с трехэкранными листингами. Я правильно понимаю, что тут происходит все тот же спиральный обход матрицы по порядку, просто очень хитро описанный?
А в целом — очень круто. Особенно круто в сравнении с трехэкранными листингами. Я правильно понимаю, что тут происходит все тот же спиральный обход матрицы по порядку, просто очень хитро описанный?
Да, то же заполнение матрицы спиральным обходом.
Думаю, ещё один шаг природа всё-таки выдержит :)
110 байт
Думаю, ещё один шаг природа всё-таки выдержит :)
110 байт
int N=7,x=-1,y=0,r=0,d=1;
int[,] A=new int[N,N];
while((d+=r/(N*d-d*d/4))<2*N) A[y+=(d%4-1)%2,x-=(d%4-2)%2]=++r;
Одна оптимизация ох оптимальнее другой. Замена цикла очень кстати. Он перестал быть таким пугающим, а заодно перед глазами прекратила всплывать картинка с компилятором, умоляющим убрать это объявление или использовать C99.
Блестяще!!! Мне остаётся только засунуть всё это в единственный цикл и обфусцировать, чтобы никто точно ничего не понял :D
Кстати, а почему матрица должна быть обязательно квадратной?
for(int [,] s={{1,1,-1,0,6}}, A=new int[s[0,4],s[0,4]]; s[0,0]<2*s[0,4]; s[0,0]+=s[0,4]*s[0,0]-s[0,0]*s[0,0]/4<s[0,1]?1:0) A[s[0,2]-=(s[0,0]%4-2)%2,s[0,3]+=(s[0,0]%4-1)%2]=s[0,1]++;
Кстати, а почему матрица должна быть обязательно квадратной?
int Nx=9,Ny=6; int[,] m=new int[Nx,Ny];
for(int d=1,r=1,x=-1,y=0,b=Nx;1<=(d%2==0?Nx--:Ny--);b+=d++%2==0?Nx:Ny) while (r<=b) m[x-=(d%4-2)%2,y+=(d%4-1)%2]=r++;
Точно, точно, они уже впллотную подходят к пределу, заданному информационной энтропией данной постановки вопроса :-) Короче уже ни на одном человеческом языке не сформулируешь, пожалуй. Возможности лаконичного синтаксиса сишного ЯП пошли во благо… при умелом использовании.
Формула определенно есть. Но выводить ее абсолютно лень. Поэтому на скорую руку набросал код, считающий любой элемент матрицы наиболее очевидным образом.
x,y — координаты, s — сторона квадрата.
Рассчитывается только главная диагональ, от нее уже без проблем получается нужная величина.
Естественно, это далеко не оптимальный вариант. Но рассчитывает довольно шустро.
Осторожно, Python!
def spiral(x,y,s):
diag = list()
for i in getUnsortDiag(s):
diag[(len(diag)+1)//2:(len(diag)+1)//2] = [i]
x -= 1
y -= 1
halfS = math.ceil(float(s)/2)
if (x == y): return diag[x]
if (x > y <= s-x-1 and y+1 < halfS): return diag[y]+x-y
if (halfS <= x > y): return diag[x]-x+y
if (s-x-1 <= y >= halfS): return diag[y]-x+y
return diag[x+1]+x-y
def getUnsortDiag(s):
res, step, changeStep = 1, (s-1)*2, False
for i in range(s):
yield res
res += step
if changeStep:
step -= 4
changeStep = ~changeStep
x,y — координаты, s — сторона квадрата.
Рассчитывается только главная диагональ, от нее уже без проблем получается нужная величина.
Естественно, это далеко не оптимальный вариант. Но рассчитывает довольно шустро.
PS: иногда я сначала пишу код, потом просыпаюсь. Все упоминания halfS — лишние. Сравнения с этой величиной безболезненно убираются, равно как и ее вычисление. Это меня куда-то не туда понесло вдруг.
Вот медленное, но, кмк, самое очевидное и легко читаемое решение из всего, что мне пришло в голову. Клеточный автомат :)
#include <complex>
#include <vector>
#include <cstdio>
typedef std::vector<int> row;
typedef std::vector<row> matrix;
typedef std::complex<int> vec;
inline int & at(matrix &x, const vec &v) {
return x[v.real()][v.imag()];
}
inline bool is_illegal(matrix & x, const vec & p) {
return p.real() == x.size() || p.real() < 0
|| p.imag() == x.size() || p.imag() < 0
|| at(x, p) != 0;
}
inline void turn_right(vec & v) { v *= vec(0, -1); }
void fill(matrix &x) {
vec pos(0, 0), dir(0, 1);
for (int i = 1, e = x.size() * x.size(); i <= e; ++i) {
at(x, pos) = i;
if (is_illegal(x, pos + dir)) turn_right(dir);
pos += dir;
}
}
int main()
{
int n = 10;
row r(n, 0);
matrix x(n, r);
fill(x);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
std::printf("%4d", x[i][j]);
std::printf("\n");
}
return 0;
}
Собственно, то же самое, но без STL. Этакие очень Си-подобные плюсы:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
if ( argc < 2 ) {
printf("\n Usage: %s [dimension]\n\n", argv[0]);
return 0;
}
int dim = atoi(argv[1]); // FIXME: yeah, we need to check the upper bounds as well
if ( dim <= 0 ) {
printf("Dimension has to be > 0\n");
return 0;
}
// create and initialize the matrix
int **array = new int*[dim];
for (int i = 0; i < dim; ++i) {
array[i] = new int[dim];
for ( int j=0; j < dim; ++j ) {
array[i][j] = 0;
}
}
enum { Right = 0, Down = 1, Left = 2, Up = 3 };
int step[][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int count = dim * dim;
int row = 0, col = 0;
int dir = Right;
for (int c = 0; c < count; ++c ) {
array[row][col] = c+1;
// new coordinates
int col1 = col + step[dir][0];
int row1 = row + step[dir][1];
// check if valid
if ( col1 < dim && col1 >= 0 && row1 < dim && row1 >= 0 && array[row1][col1] == 0 ) {
col = col1;
row = row1;
}
else {
dir += 1;
if ( dir > Up ) {
dir = Right;
}
col += step[dir][0];
row += step[dir][1];
}
}
// print the result
for ( int i = 0; i < dim; ++i ) {
for ( int j = 0; j < dim; ++j ) {
printf("%3i ", array[i][j]);
}
printf("\n");
}
// clean up the memory
for (int i = 0; i < dim; ++i ) {
delete[] array[i];
}
delete[] array;
return 0;
}
C++, голый алгоритм
gist.github.com/ffoxin/8705982
size_t n = 100000;
volatile size_t ret;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (i > j)
{
if (i + j < n)
{
ret = (n - (j + 1)) * (j + 1) * 4 - (i - (j + 1));
}
else
{
ret = i * (n - i) * 4 - (i - (n - i)) - (j - n + i + 1);
}
}
else
{
if (i + j < n)
{
ret = i * (n - i) * 4 - (i - (n - i)) + i + j - n + 1;
}
else
{
ret = (n - (n - j - 1)) * (n - j - 1) * 4 + (j - (n - j)) + i + (j - n) + 3;
}
}
}
}
gist.github.com/ffoxin/8705982
Из интереса написал на Java класс Spiral — добавил медленную демонстрацию (за 1 шаг вычисляется 1 позиция), и для быстрого вывода ваше демо. Код на Pastebin
Респект! :-) Долго формулы выводили?
По коду на гите вопрос — результаты функции calc никуда не сохраняются, что ли?
Кстати, любопытная вещь получилась. Выходит, что наивная реализация по скорости очень близка «покоординатной». В один поток при сравнении у меня получились очень схожие цифры. Видимо, в первом случае время уходит на случайный доступ к памяти, а во втором — на арифметически более сложный расчёт содержимого клетки квадрата…
По коду на гите вопрос — результаты функции calc никуда не сохраняются, что ли?
Кстати, любопытная вещь получилась. Выходит, что наивная реализация по скорости очень близка «покоординатной». В один поток при сравнении у меня получились очень схожие цифры. Видимо, в первом случае время уходит на случайный доступ к памяти, а во втором — на арифметически более сложный расчёт содержимого клетки квадрата…
15 минут с ручкой и листком бумаги, чтобы расписать 10х10 и проанализировать верхнюю левую полудиагональ. Остальные полудиагонали выводятся довольно просто — по 5 минут на каждую.
Ага, не сохраняются. Раньше выводил в консоль, потом писал в файл, но так как писалось из чисто академического интереса «чей код будет быстрее» и «почему мой с++ медленнее твоего c#», то вывод результатов был убран.
Да, по скорости в один поток они будут близки. Координатная вырывается вперед если, к примеру, стоит задача вывести значения средней строчки.
Ага, не сохраняются. Раньше выводил в консоль, потом писал в файл, но так как писалось из чисто академического интереса «чей код будет быстрее» и «почему мой с++ медленнее твоего c#», то вывод результатов был убран.
Да, по скорости в один поток они будут близки. Координатная вырывается вперед если, к примеру, стоит задача вывести значения средней строчки.
I
nt Calc(int N,int x,int y){
int a=x>=y ? 0 : 3;
if(x+y>=N) a^=1;
x=2*x-N+1;
y=2*y-N+1;
int r=x*((2-a)%2)+y*((a-1)%2);
int m=x*((1-a)%2)+y*((2-a)%2);
return N*N-(r+1)*(r+1)+a*r+(m+r)/2;
}
На входе числа от 0 до N-1, на выходе — от 0 до N*N-1.
Сомневаюсь, что можно получить значение только по координатам (как, например, в симплекс-шуме). По такой таблице рисуется скатерть Улама, а наличие способа реверс-композиции без прохода до нулевой точки означало бы несколько нехороших свойств для простых чисел. Хотя, наверняка есть способ приближённого расчёта через экспоненцирование (см. график ряда
0 5 18 39 68 105..., по мере отдаления от 0 для соседних рядов действуют те же правила).Прекрасно получается значение по координатам. Если подумать — можно прийти к тому, что где-то внутри будет запрятана арифметическая прогрессия.
И тем не менее, в комментариях уже шесть решений (включая одно моё), ни одно из которых эту прогрессию не использует. Под экспоненцированием я имел в виду решение геометрической прогрессии, а не арифметической, а точных способов возведения в произвольную степень за константное время нет. Если вы тут видите арифметическую прогрессию, пожалуйста, завершите мысль и покажите, где она.
И тем не менее, над вашим комментарием висит мое решение, которое по сути считает значение клетки по заданной стороне квадрата и координатам. Более того, на гисте выложен распараллеленный вариант.
Чуть выше я приводил пример с вычислением элемента по опорной величине на главной диагонали. Вот выделил немного времени, чтобы определить зависимость величины элемента главной диагонали от его расположения:
Функция getDiag(x,n) выдает элемент x (отсчет с нуля) в матрице n*n. Формулы отличаются для первой и второй половины диагонали, но, в принципе, однозначно подставляются в return'ы основной функции.
Здесь уже никаких хитростей, никаких предварительных вычислений. Формула энного члена арифметической прогрессии используется в вычислении элемента диагонали, причем для второй половины — дважды. Нет ограничения на четность размерности, как в комментарии ниже.
Осторожно, снова Python!
def spiral(x,y,s):
x,y = x-1, y-1
if (x == y): return getDiag(x,s)
if (x > y <= s-x-1): return getDiag(y,s)+x-y
if (x > y): return getDiag(x,s)-x+y
if (s-x-1 <= y): return getDiag(y,s)-x+y
return getDiag(x+1,s)+x-y
getDiag = lambda x,n: (n-x)*4*x+1 if (x <= math.ceil(float(n)/2)-1) else (x)*(2+4*(n-x-1))+1+2*(n-x-1)Функция getDiag(x,n) выдает элемент x (отсчет с нуля) в матрице n*n. Формулы отличаются для первой и второй половины диагонали, но, в принципе, однозначно подставляются в return'ы основной функции.
Здесь уже никаких хитростей, никаких предварительных вычислений. Формула энного члена арифметической прогрессии используется в вычислении элемента диагонали, причем для второй половины — дважды. Нет ограничения на четность размерности, как в комментарии ниже.
Получить приглашение на интервью достаточно легко практически в любой серьёзной фирме при наличии более-менее адекватных навыков. Но это пока ещё не гарантия трудоустройства — в подобных фирмах интервью достаточно сложные.
PS: решение неплохое, хотя и далеко не оптимальное — c-style массив был бы уместнее.
PPS: когда-то давно, в школе, решал эту задачку на QBasic, который не поддерживал двумерные массивы.
PS: решение неплохое, хотя и далеко не оптимальное — c-style массив был бы уместнее.
PPS: когда-то давно, в школе, решал эту задачку на QBasic, который не поддерживал двумерные массивы.
Да, это еще не трудоустройство :) Написал эту статью для тех, кто говорит, что даже до интервью дойти не может.
Решение очень далеко от оптимального — это меня сильно и удивило, когда я получил ответ.
Можете вспомнить, как без двумерных массивов решили? Мне просто интересно почитать :)
Решение очень далеко от оптимального — это меня сильно и удивило, когда я получил ответ.
Можете вспомнить, как без двумерных массивов решили? Мне просто интересно почитать :)
Циклами. Начинал, помнится, с середины, затем раскручивал увеличивая счётчики. Как-то так, точнее не могу припомнить, увы. А садиться писать такой алгоритм охоты нет. Фишка была в том, что я не заполнял массив, а сразу выводил в нужное место на экране.
Спасибо! Здесь проблема была в том, что выводить числа нужно было последовательно в консоль. Вместо консоли я просто использовал WebView.
Я плох в плюсах, но, вроде как, там нельзя в кастомное место консоли выводить символ.
Я плох в плюсах, но, вроде как, там нельзя в кастомное место консоли выводить символ.
Не соглашусь. Может конечно у вас побольше опыта в получении приглашений на интервью. Мой опыт говорит мне — что это один из сложнейших этапов. Поэтому как это немалые затраты для компании — оплатить перелет и тому подобное.
ЗЫ: Был на он-сайт интервью в ARM (1 интервью + тестовое задание перед приглашением на сайт). Сейчас готовлюсь к он-сайт в одной компании из США (8 phone-screen интервью перед приглашением).
ЗЫ: Был на он-сайт интервью в ARM (1 интервью + тестовое задание перед приглашением на сайт). Сейчас готовлюсь к он-сайт в одной компании из США (8 phone-screen интервью перед приглашением).
У одного решение не скомпилилось, у другого простое консольное решение на плюсах, а у меня вот такой приятный глазу UI. Похоже, выбор был очевиден.Мне одному кажется, что выбор тут очевиден не в пользу автора?
Хайзенебргу нельзя отказывать. Потому, что он "… the one who knocks".
Возможно, нужно немного уточнить: под словом «простое» я имел ввиду «обычное» — как и у меня, собственно. Только на плюсах и без UI.
Видимо я уже совсем не в теме, но я не могу найти ни единой причины, зачем в такой задаче UI. Тут чистого C за глаза хватит с печатью в stdout.
И да, зачем вам динамический массив объектов, вы с C насколько хорошо знакомы?
И да, зачем вам динамический массив объектов, вы с C насколько хорошо знакомы?
С Си и Си++ я знаком очень поверхностно на уровне пары-тройки курсов по алгоритмике и структурам данных.
Это решение ни в коем случае не претендует на правильное, либо оптимальное. Я просто сумел «продать» красивый код, вместо правильного, и написал об этом статью :)
Это решение ни в коем случае не претендует на правильное, либо оптимальное. Я просто сумел «продать» красивый код, вместо правильного, и написал об этом статью :)
Works is better than perfect.
ayende.com/blog/165378/fail-can-impress-too
Забавно, что буквально вчера прочитал по этой теме в блоге ayende.
Забавно, что буквально вчера прочитал по этой теме в блоге ayende.
По всей видимости, при выборе оценили не столько качество алгоритма (это дело наживное), сколько энтузиазм.
Автор не просто решил поставленную задачу, а добавил к ней требований.
Наверно это то, что в последнее время называют модным словом «креативность».
Наверно по этим косвенным признакам можно судить о том, что человеку в радость решать задачки по программированию, он реально ими увлекается.
Да, можно сказать, что все эти bells-and-whistles ни к чему для достижения заданной цели, а только отвлекают и т.д. и т.п.
Но всё-таки, как мне кажется, такой подход на первоначальных этапах обучения искусству программирования дорогого стоит.
Автор делает правильно.
И задает правильные вопросы об улучшении качества алгоритма.
Задача поставлена -> задача решена в срок и с нужным качеством -> теперь можно подумать и об оптимизации.
Автор не просто решил поставленную задачу, а добавил к ней требований.
Наверно это то, что в последнее время называют модным словом «креативность».
Наверно по этим косвенным признакам можно судить о том, что человеку в радость решать задачки по программированию, он реально ими увлекается.
Да, можно сказать, что все эти bells-and-whistles ни к чему для достижения заданной цели, а только отвлекают и т.д. и т.п.
Но всё-таки, как мне кажется, такой подход на первоначальных этапах обучения искусству программирования дорогого стоит.
Автор делает правильно.
И задает правильные вопросы об улучшении качества алгоритма.
Задача поставлена -> задача решена в срок и с нужным качеством -> теперь можно подумать и об оптимизации.
В данном случае человек использует заведомо неэффективную структуру данных, что может говорить лишь о том, что он не понимает, как она работает (я про NSMutableArray объектов). Я не представляю требования, для которых это можно назвать «нужным качеством».
Не можете?
Вот Вам требования: «Реализуйте приложение, которое сможет наглядно показать людям, что такое циферки в спиральке.»
Вот Вам требования: «Реализуйте приложение, которое сможет наглядно показать людям, что такое циферки в спиральке.»
Программа работает? Да. Без ошибок? Да. Время выполнения приемлемое? Да. Вот все _достаточные_ требования.
Насчет эффективности можно далеко зайти.
Вот вы считаете реализацию на этой готовой структуре неэффективной, и наверно могли бы написать на с++, а я ваш код так же раскритикую и скажу, что вы написали плохо, потому что лучше написать на ассемблере.
Насчет эффективности можно далеко зайти.
Вот вы считаете реализацию на этой готовой структуре неэффективной, и наверно могли бы написать на с++, а я ваш код так же раскритикую и скажу, что вы написали плохо, потому что лучше написать на ассемблере.
Гхм. Вы уверены, что я не понимаю, как она работает? Я уже несколько раз писал, что решение заведомо не оптимальное, но делалось на скорость и на коленке. Это то, почему я и был удивлен приглашению на собеседование. Я нигде не говорил, что алгоритм и его реализация правильные.
>Мне одному кажется, что выбор тут очевиден не в пользу автора?
Мне одному кажется, что второго тоже скорее всего пригласили на собеседование? :)
Мне одному кажется, что второго тоже скорее всего пригласили на собеседование? :)
Задача про «квадратную спираль» похоже становится стандартом — в качестве одного из заданий она была предложена год назад при прохождении теста для поступления в школу разработчиков при headhunters
Меньшиков. «Олимпиадные задачи по программированию». Задача 2F.
Мой преподаватель, организовывавший пару 10ков лет (или больше, да он и сейчас этим занимается) олимпиады по программированию для школьников, всем рекомендовал эту книгу. «Достаточно просто прорешать её всю и будешь демонстрировать отличные результаты на олимпиадах среди вузов». Поскольку все остальные преподаватели обучались у него, то они для курса структурного программирования задачки брали из этой же книги. Так что я «Спираль» писал в вузе (2007-2012) раза три.
Мой преподаватель, организовывавший пару 10ков лет (или больше, да он и сейчас этим занимается) олимпиады по программированию для школьников, всем рекомендовал эту книгу. «Достаточно просто прорешать её всю и будешь демонстрировать отличные результаты на олимпиадах среди вузов». Поскольку все остальные преподаватели обучались у него, то они для курса структурного программирования задачки брали из этой же книги. Так что я «Спираль» писал в вузе (2007-2012) раза три.
Креативно!
Вспомнилось, как мы рисовали такие спирали во время лабораторных на военной кафедре. Прикол был не в спирали как таковой, а в том, что упражняться приходилось на эмуляторе процессора «большой» ЭВМ серии ЕС, запущенном на PC/XT (советском клоне, конечно). Надо было написать программу на ассемблере, вручную транслировать ее в коды и вбить в весьма симпатичный отладчик-эмулятор, который кроме регистров показывал еще и содержимое куска памяти, в котором и должна была появиться спираль. Причем работало это все со скоростью нескольких команд в секунду, так что спираль рисовалась весьма торжественно. Жаль, что тогда не то что Фейсбука, а еще и WWW не было, так что никто на собеседование не пригласил :)
О да, знакомая задача, в качестве лабораторной по си на первом курсе попалась :)
А я вчера был на собеседовании в компании, которую купили на днях IBM, так что если туда устроюсь — буду работать фактически в IBM.
Заданием было — реализовать простое бинарное дерево (не балансируемое даже). Вот так-то :) Вроде как приглашают на второе собеседование, так что все гуд (рекрутер (независимый агент который) сказал что хотят пригласить, но пока время не утрясли)
Заданием было — реализовать простое бинарное дерево (не балансируемое даже). Вот так-то :) Вроде как приглашают на второе собеседование, так что все гуд (рекрутер (независимый агент который) сказал что хотят пригласить, но пока время не утрясли)
В свое время мне очень понравилась другая задача — есть шахматная доска и один конь. Надо полностью «закрасить» шахматную доску ходами. решил еще в докомпьютерное время, а вот насчёт алгоритма было бы интересно узнать
Задача на backtracking. Из каждой позиции у коня восемь возможных ходов. Делам каждый из восьми ходов — если это было _безопасно_ идем дальше. Безопасно — значит (а) мы не ушли за пределы доски (б) мы тут еще не были.
Примерный скетч алгоритма за экспоненциальное время O(8^n)
void step(int x, int y) {
if (safe(x, y)) {
// красим ячейку
fill(x, y);
// шагаем дальше
step(x + 1, y - 2);
step(x + 2, y - 1);
// и остальные шесть ходов
}
}
void main() {
clearTable();
step(0, 0);
}
Для больших размеров доски нужно использовать Warnsdorff's rule: ходить в клетку, из которой можно сделать наименьшее число ходов. Работает за линию от числа клеток.
Вот я недавно решал на Прологе (B-Prolog): stackoverflow.com/questions/21066294/knights-tour-efficient-solution/21069014#21069014
Вот я недавно решал на Прологе (B-Prolog): stackoverflow.com/questions/21066294/knights-tour-efficient-solution/21069014#21069014
Товарищи, хабрачеловеки! Час назад у автора было 11.7 сами_знаете_чего, сейчас, как я вижу, 8.7. Давайте будем человечнее. И использовать минусы по делу. Я все сказал.
И мне нагадили… Ну спасибо
Хабр — саморегулирующееся сообщество. Не понравилась статья большинству — получай.
Судя по том, что статья на главной, большинству как раз понравилось. Но то меньшинство, которому не понравилось, имеет самые заряженные минусомёты
Ну, тут проблемка немного в другом: большинству, все-таки, понравилось. 91 плюс на 66 минусов. Просто Bringoff отметил, что минусы люди гораздо охотнее ставят :)
Да, к сожалению Хабр скор на расправу. Как тут не вспомнить про лигу зла с пикабу? ;)
У некоторых людей к backmeupplz есть личные претензии. Все его комментарии частенько методично проминусовываются.
К сожалению, FB не является моей приоритетной целью;
Я бы сказал, что к счастью…
Кстати о гуях. В интерфейсе кроме поля ввода и поля вывода нет больше никаких интерактивных элементов. Если в таком интерфейсе приходится явно дополнительно указывать на то, где находится поле ввода, то это не очень хороший интерфейс, мягко говоря. Уж лучше б консольный.
Ну так сначала сформировать матрицу, а потом построчно ее выводить же можно (это если вычислять элементы не последовательно).
Я плох в плюсах, но, вроде как, там нельзя в кастомное место консоли выводить символ.
Ну так сначала сформировать матрицу, а потом построчно ее выводить же можно (это если вычислять элементы не последовательно).
Да; и интерфейс, и алгоритм можно дорабатывать бесконечно :) Хотелось оставить некое подобие «Диалога» с ГГ из сериала «Во все тяжкие» — и, соответственно, дать пользователю возможность ответить на его вопрос. Это можно сделать лучше и креативнее, но самое решение я делал просто так, ради себя, а отправил рекрутеру email чтобы попытать удачу :)
(Господа минусующие! Пожалуйста, напишите, что не так со статьей. А то я просто поделился своим опытом, и сразу такой холодный и молчаливый прием)
Предположительно реакция из-за тезисов:
* Я красавчег!
* Мне все скучно!
* Нефигделать!
Суммируя: Пост хвастовства.
Кстати, ни минус ни плюс не ставлю, так как считаю тебя вполне нормальным амбициозным молодым человеком, у которого все впереди, ты далеко можешь пойти (в хорошем смысле), но стеклянного потолка не достанешь, так как будешь периодически падать.
А я думал, что парень вот так легко попал на интервью из какой-нибудь Калуги (просто первое, что вспомнил). А он, оказывается, даже ходит пиццу стрельнуть в фейсбук.
Как-то так. Думаю каждый из нас, у кого есть что-то на сегодня за плечами, может это преподнести по разному, и конечно когда у тебя компания, миллионные прибыли, тысячи сотрудников и тд, можно сказать так, типа проходил мимо встретил пару друзей, набросал код, туда-сюда и теперь мы крупная преуспевающая компания, всем будет ясно, что это такая ирония. Я же не хожу не трублю что у меня хостинг провайдер, лишь потому-что я администрирую десяток серверов, или что у меня студия веб дизайна, когда я при помощи товарища дизайнера и верстальщика запилил десяток сайтов. Хотя да, все большое зачастую начинается с чего-то малого.
Да я, вроде как, ничего сверхъестественного и не описал в статье. Я честно думал, что у всех все так просто получается — думал, что кто-нибудь узнает себя :)
А уж решения задач с Tech Talk от Facebook всем, по моему мнению, даются просто (30-40 секунд). Я уверен, что вы гораздо быстрее меня решите задачку из поста.
Я пытался подчеркнуть легкость «домашнего задания» (да и всего, что FB дает студентам), дабы показать, как просто попасть на собеседование.
А уж решения задач с Tech Talk от Facebook всем, по моему мнению, даются просто (30-40 секунд). Я уверен, что вы гораздо быстрее меня решите задачку из поста.
Я пытался подчеркнуть легкость «домашнего задания» (да и всего, что FB дает студентам), дабы показать, как просто попасть на собеседование.
«Как я выбил собеседование в Facebook»
Если сократить до сути: «я сделал тестовое задание, к нему — красивый интерфейс — и меня пригласили». Уникальная история, ни у кого таких нет!
Хотя может для кого-то пост и станет мотивационным. В этом его плюс. Так что ни стал ни плюс, ни минус ставить. В кои то веки нашлось применение черточке между ними…
Если сократить до сути: «я сделал тестовое задание, к нему — красивый интерфейс — и меня пригласили». Уникальная история, ни у кого таких нет!
Хотя может для кого-то пост и станет мотивационным. В этом его плюс. Так что ни стал ни плюс, ни минус ставить. В кои то веки нашлось применение черточке между ними…
Решение отвратительное. Надо было написать: решение школьной задачи алгоритмом уровня той же школы и без понятия о такой вещи, как алгоритмизация.
Несколько лет назад в универе препод заставил решить эту задачу вычисляя значения в зависимости от координат.
Python (для нечётных размеров):
N = 9
A, x, d = {0: N * N}, 1, 1j
for p in range(N * N - 1, 0, -1):
A[x] = p
if abs(x.imag) == abs(x.real):
x += (1 - 1j) * (d == 1)
d *= 1j
x += d
r = [[A[-x + N // 2 - (N // 2 - y) * 1j] for x in range(N)] for y in range(N)]
print('\n'.join(' '.join("%4d" % elem for elem in line) for line in r))
Начало довольно пафосное получилось. Или мне показалось? ;)
Несколько (не намного) более интересно было бы если задачу сформулировать так:
По поводу стиля написания соглашусь с marchelly что как-то хвастливо получилось. Сам в таком стиле люблю писать, но тут уж как-то через край.
А по существу довольно интересно, нестандартно подошли. Что правда не отменяет того что сам алгоритм утонул в куче boilerplate-кода, мне бы такое писать было не интересно. Может вас дизайнером пользовательских интерфейсов хотят взять? ;)
Кстати тоже похвастаюсь тогда уж. В понедельник у меня будет первый рабочий день в Facebook, сейчас вот чемоданы собираю. Собеседование показалось на удивление легким (в сравнении с гугловым), но всё же не настолько легким как задача из поста.
Дано N <= 10^18, row <= N, col <= N. Вывести число, находящееся в строке row, столбце col для квадрата со стороной N.
По поводу стиля написания соглашусь с marchelly что как-то хвастливо получилось. Сам в таком стиле люблю писать, но тут уж как-то через край.
А по существу довольно интересно, нестандартно подошли. Что правда не отменяет того что сам алгоритм утонул в куче boilerplate-кода, мне бы такое писать было не интересно. Может вас дизайнером пользовательских интерфейсов хотят взять? ;)
Кстати тоже похвастаюсь тогда уж. В понедельник у меня будет первый рабочий день в Facebook, сейчас вот чемоданы собираю. Собеседование показалось на удивление легким (в сравнении с гугловым), но всё же не настолько легким как задача из поста.
Дано N <= 10^18, row <= N, col <= N. Вывести число, находящееся в строке row, столбце col для квадрата со стороной N.
А длинную арифметику самому писать, или библиотеку дадут? Ответ может быть до 10^36.
Упс, лучше понизить ограничения до 10^9.
И кстати можно ещё и обратную задачу расммотреть. Дано N <= 10^9, и K <= N^2, найти где в квадрате будет расположено число K.
И кстати можно ещё и обратную задачу расммотреть. Дано N <= 10^9, и K <= N^2, найти где в квадрате будет расположено число K.
Над обратной задачей не думал, а изначальная дает результат за 0.0033 секунды в среднем. Это при N <= 10^18. Впрочем, при N в пределах 10 время выполнения то же. Вот после N<=10^115 время расчета вырастает до ~0.006.
Ну обратную тоже через диагональ можно решать. Только там придется квадратный корень аккуратно брать чтобы погрешности не охватить.
А так решение за O(1) — если считать что арифметические операции за константное время работают. Просто в C++ в отличие от Python длинной арифметики встроенной нет, поэтому для справедливости стоит понизить ограничение чтобы в uint64_t влезало.
Кстати у вас тут мне кусочек не нравится:
при больших числах наверняка не хватит мантиссы (сомневаюсь что в Python float тоже длинный).
А так решение за O(1) — если считать что арифметические операции за константное время работают. Просто в C++ в отличие от Python длинной арифметики встроенной нет, поэтому для справедливости стоит понизить ограничение чтобы в uint64_t влезало.
Кстати у вас тут мне кусочек не нравится:
x <= math.ceil(float(n)/2)-1
при больших числах наверняка не хватит мантиссы (сомневаюсь что в Python float тоже длинный).
И правильно делает, что не нравится. Когда писал, про длинную арифметику не думал. К счастью, тут без проблем должна встать замена на целочисленное деление с проверкой на нечетность n.
Полез исправлять и обнаружил, что для числа посредине диагонали для матриц с нечетной стороной справедливы обе формулы. Так что там достаточно (x <= n/2-1).
Обратная задача. Получилось не очень красиво:
Будет нормально работать для N<2^26, а для больших значений придётся ещё подкорректировать значение r, полученное после sqrt — боюсь, что из-за округления оно может отличаться на единицу в ту или другую сторону.
void CalcBack(int N,long long m,int &x,int &y){
m=(long long)N*N-m;
int r=(int)sqrt((double)m);
if((r+N)&1) r--;
if(r<0) x=y=(N+1)/2;
else{
long long dm=m-(long long)r*r;
int dmr=(int)(dm%(r+1));
int k=(N-r)/2;
switch(dm/(r+1)){
case 0: x=k; y=k+dmr+1; break;
case 1: x=k+dmr+1; y=N+1-k; break;
case 2: x=N+1-k; y=N-k-dmr; break;
case 3: x=N-k-dmr; y=k; break;
}
}
}
Будет нормально работать для N<2^26, а для больших значений придётся ещё подкорректировать значение r, полученное после sqrt — боюсь, что из-за округления оно может отличаться на единицу в ту или другую сторону.
Кому интересно, вот код, который рисует этот «Magic Square» на форме VB6:
Скрытый текст
Option Explicit
Dim N As Long
Dim V() As Long
Private Sub Form_Click()
Me.Cls
N = InputBox("N=?")
FillSquare
ShowSquare
End Sub
Private Sub FillSquare()
If N < 1 Then Exit Sub
ReDim V(1 To N, 1 To N)
Dim modeIsRow As Boolean, dirIsFromLeft As Boolean, iter&, i&, j&, r&, c&, r1&, rn&, c1&, cn&, try&
r1 = 1: rn = N: c1 = 1: cn = N: modeIsRow = True: dirIsFromLeft = True:
iter = 1
Do
try = try + 1
If modeIsRow Then
If dirIsFromLeft Then r = r1 Else r = rn
For i = IIf(dirIsFromLeft, c1, cn) To IIf(dirIsFromLeft, cn, c1) Step IIf(dirIsFromLeft, 1, -1)
V(r, i) = iter: iter = iter + 1
Next i
If dirIsFromLeft Then r1 = r1 + 1 Else rn = rn - 1
Else
If dirIsFromLeft Then c = cn Else c = c1
For i = IIf(dirIsFromLeft, r1, rn) To IIf(dirIsFromLeft, rn, r1) Step IIf(dirIsFromLeft, 1, -1)
V(i, c) = iter: iter = iter + 1
Next i
If dirIsFromLeft Then cn = cn - 1 Else c1 = c1 + 1
End If
If c1 > cn Or r1 > rn Then Exit Do
modeIsRow = Not modeIsRow
If try Mod 2 = 0 Then dirIsFromLeft = Not dirIsFromLeft
Loop
End Sub
Private Sub ShowSquare()
Dim i&, j&, s$
Me.Cls
Print vbNewLine
For i = 1 To N
s = vbTab
For j = 1 To N
s = s & (V(i, j) & vbTab)
Next j
Print s & vbNewLine
Next i
End Sub
C#
GitHub, DotNetFiddle
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Box
{
public interface IAsset
{
void Accept(IVisitor visitor);
}
public class MyBox : IAsset
{
public int[,] Arr;
public int Size;
public MyBox(int size)
{
this.Size = size;
Arr = new int[size, size];
}
public void Accept(IVisitor visitor)
{
visitor.Visit(this);
}
public override string ToString()
{
string s = "";
for (int i = 0; i < Size; i++)
{
for(int j = 0; j < Size; j++)
{
s += (" " + String.Format("{0:D2}", Arr[j, i]) + " ").Replace(" 00 ", " __ ");
}
s += "\r\n";
}
return s;
}
}
public interface IVisitor
{
void Visit(MyBox box);
}
public class MyVisitor : IVisitor
{
public enum Directions { Left, Right, Up, Down }
public class Rules
{
private int index = 0;
public Directions CurrentDirection
{
get
{
return rules[index];
}
}
private List<Directions> rules = new List<Directions>
{
Directions.Right,
Directions.Down,
Directions.Left,
Directions.Up
};
public void SwitchToNext()
{
index++;
if (index > 3)
index = 0;
}
}
private Rules rules = new Rules();
private bool isObstacle(MyBox box, Directions direction, int x, int y)
{
switch(direction)
{
case Directions.Right:
if (x + 1 >= box.Size)
return true;
return box.Arr[x + 1, y] != 0;
case Directions.Down:
if (y + 1 >= box.Size)
return true;
return box.Arr[x, y + 1] != 0;
case Directions.Left:
if (x - 1 < 0)
return true;
return box.Arr[x - 1, y] != 0;
case Directions.Up:
if (y - 1 < 0)
return true;
return box.Arr[x, y - 1] != 0;
default:
throw new NotSupportedException();
}
}
public void Visit(MyBox box)
{
int x = -1;
int y = 0;
int value = 1;
while(value < box.Size * box.Size + 1)
{
if(isObstacle(box, rules.CurrentDirection, x, y))
rules.SwitchToNext();
switch(rules.CurrentDirection)
{
case Directions.Right:
x++;
break;
case Directions.Down:
y++;
break;
case Directions.Left:
x--;
break;
case Directions.Up:
y--;
break;
}
box.Arr[x, y] = value;
value++;
}
}
}
class Program
{
static void Main(string[] args)
{
Console.Write("Type the size (enter for 8): ");
string str = Console.ReadLine();
if (String.IsNullOrWhiteSpace(str))
str = "8";
int size = Int32.Parse(str);
IVisitor visitor = new MyVisitor();
MyBox box = new MyBox(size);
box.Accept(visitor);
Console.WriteLine(box);
}
}
}
GitHub, DotNetFiddle
спасибо за разминку
Решение в лоб на python'e
def position(a):
x = 0
y = 0
minX, maxX = 1, a - 1
minY, maxY = 0, a - 1
xyz = 1
for count in range(1, a**2 + 1, 1):
yield x, y
if xyz == 1:
y += 1
if y == maxY:
xyz +=1
maxY -=1
elif xyz == 2:
x += 1
if x == maxX:
xyz +=1
maxX -=1
elif xyz == 3:
y -= 1
if y == minY:
xyz +=1
minY +=1
elif xyz == 4:
x -= 1
if x == minX:
xyz +=1
minX +=1
if xyz > 4:
xyz = 1
def PrintHelix(z):
a = len(z)
for x in range(a):
row = ""
for y in range(a):
row += " " + z[x][y]
print (row)
a = 3# len
z = [[0]*a for x in range(a)]
for index, (x,y) in enumerate(position(a), 1):
z[x][y] = str(index)
PrintHelix(z)
Цветной вариант: jsfiddle.net/cVGr3/1/
Всем неуд за лапшекод без документации и оопа в этом треде ^^
Документировать в моих 6 строках, в каждой из которых возвращается результат простейших арифметических операций, нечего. Единственный элемент документации, который мог бы там быть — описание того, что возвращает сама функция. Но эту роль прекрасно выполняет содержимое поста.
А неуда тут если за что и удостаивать, то только за стремление везде приткнуть ООП. Здесь оно ни к чему абсолютно.
А неуда тут если за что и удостаивать, то только за стремление везде приткнуть ООП. Здесь оно ни к чему абсолютно.
Вон выше ООП воткнули, так там простыня на 3.5 экрана получилась. Нафига оно тут вообще нужно, это ваше ООП? Это я вас как плюсовик/Qt-шник спрашиваю :)
#include<stdio.h>
void main(){
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
int k=2*i<N ? i : N-i;
for(int j=0;j<k;j++) printf("%4d ",4*j*(N-j-2)+4*N+(j-i)-3);
for(int j=k;j<N-k;j++) printf("%4d ",2*i<N ? 4*(N-i)*i+(j-i)+1 : 4*(N-i)*i+2*N-3*i-1-j);
for(int j=N-k;j<N;j++) printf("%4d ",(4*(N-j)-1)*(j+1)+i-2*N);
printf("\n");
}
}Вы бы взяли на работу человека, пишушего такой код? :)
А что не так? Чистый C.
При математическом подходе (с последовательным вычислением) формулы без теоретического приложения все равно не шибко интуитивны. Но что конкретно делает данный код, вполне ясно.
Кстати, ваш вариант с векторами, комплексными числами, пачкой функций и листингом в экран является полной противоположностью этого. Там ведь еще и обход по спирали был? Как раз получаются два примера, оттеняющих плюсы и минусы друг друга (=
При математическом подходе (с последовательным вычислением) формулы без теоретического приложения все равно не шибко интуитивны. Но что конкретно делает данный код, вполне ясно.
Кстати, ваш вариант с векторами, комплексными числами, пачкой функций и листингом в экран является полной противоположностью этого. Там ведь еще и обход по спирали был? Как раз получаются два примера, оттеняющих плюсы и минусы друг друга (=
Вы бы взяли на работу человека, пишушего такой код? :)
Думаю, да.
Если человек может заставить правильно работать этот код, значит, во-первых, он не испугается и других математических выкладок и их реализации; во-вторых, у него достаточно развита математическая интуиция, чтобы понять, в какой форме должен быть ответ, и когда имеет смысл искать/писать формулу, а когда лучше обратиться к итерациям или массивам. Ну, и в-третьих, есть хорошие шансы, что он и сам сможет читать подобный код и понимать, когда в нём имеет смысл разбираться, когда достаточно правдоподобности плюс проверки на примерах, а когда коду можно просто поверить.
Ок. К коду на самом деле претензий нет. Он во многом превосходит мой — по потреблению памяти (в т.ч. ассимптотике её использования), по размеру, по требованиям к компилятору (хотя вашей программе требуется поддержка C99).
Просто интересно было, какие качества вы выделяете в коде кандидатов. Я всегда стремлюсь писать максимально простой и понятный код, и от кандидатов всегда хочется того же самого. Интересна позиция других :)
Просто интересно было, какие качества вы выделяете в коде кандидатов. Я всегда стремлюсь писать максимально простой и понятный код, и от кандидатов всегда хочется того же самого. Интересна позиция других :)
Просто в проектах, которыми я сейчас занимаюсь (в моей части) непосредственно под архитектурой лежат алгоритмы, и уровня, собственно, кодирования по ТЗ практически нет. И часть «хорошо реализовать алгоритм и уметь его прочитать» несколько важнее, чем «написать код, понятный большинству».
А вот с кандидатами проблема — мы даже не можем сформулировать требования (PhD в математике или CS плюс хорошее понимание физики — то, что было написано для меня — это, как-то, чересчур). Любая задача, которую удаётся выделить, требует слишком глубокого погружения в проект. Попробую научить дочку. Там, хотя бы, время не ограничено.
А себя к себе я бы, конечно, взял. Даже если бы пришлось потратить время на погружение в проект. Мне сейчас хочется клонироваться в 3-4 экземплярах :)
А вот с кандидатами проблема — мы даже не можем сформулировать требования (PhD в математике или CS плюс хорошее понимание физики — то, что было написано для меня — это, как-то, чересчур). Любая задача, которую удаётся выделить, требует слишком глубокого погружения в проект. Попробую научить дочку. Там, хотя бы, время не ограничено.
А себя к себе я бы, конечно, взял. Даже если бы пришлось потратить время на погружение в проект. Мне сейчас хочется клонироваться в 3-4 экземплярах :)
Понятно, спасибо за детали. Вопроса «взяли бы вы на работу себя» не стояло, его надумал автор поста. Интересна просто разница в подходах к программированию. Я работаю в компании, где нужно писать очень много кода, и ещё больше читать. Вы — там, где нужно придумать сложный алгоритм, реализовать его и перейти к следующему проекту. Теперь всё прояснилось :)
Где-то читал про программистов-математиков вроде Кнута и программистов-писателей вроде Ларри Уолла.
Где-то читал про программистов-математиков вроде Кнута и программистов-писателей вроде Ларри Уолла.
Если не секрет, где вы работаете?
Всегда считал странными вопросы «Взяли ли бы вы себя работать к себе» :)
Лично я всегда отвечаю «Нет», потому что я лентяй, разгильдяй и недоучка :)
А если по сабжу, то я бы лично взял такого человека работать к себе, если он сможет мне подробно описать, как работает этот код. Да так, чтобы я понял.
Лично я всегда отвечаю «Нет», потому что я лентяй, разгильдяй и недоучка :)
А если по сабжу, то я бы лично взял такого человека работать к себе, если он сможет мне подробно описать, как работает этот код. Да так, чтобы я понял.
Код очень короткий и не хранит в памяти массив для вывода, поэтому будет работать даже на N=32766.
Отличное решение!
Сколько времени ушло на него?
Сколько времени ушло на него?
Два года назад собеседовался у них. Перед очным собеседованием был предварительный отсев HR-ом: надо было за час решить [несложную] задачу в какой-то автоматизированной системе тестирования, потом было 4 телефонных собеседования с написанием кода. Потом свозили в новый офис в Palo Alto, а потом сказали, что не подходжу :)
А насчет задачи: на одной из школных олимпиад больше 10 лет назад была задача построить скатерть Улама
А насчет задачи: на одной из школных олимпиад больше 10 лет назад была задача построить скатерть Улама
Здравствуйте, backmeupplz!
В посте вы спрашивали о том, почему задачка была такой легкой.
Вот, что пришло мне в голову, пока читал пост:
1) В целом для аудитории задача оказалась трудноватой (вы же сами сказали, что написали только 3 человека из 150)
2) В Facebook вас же приглашают (или пригласят после интервью) как New Grad, а это не то же самое, как если бы к ним пришел дядька лет 40 на конкретную позицию. Его бы уж там поспрашивали бы.
Вот как-то так)
Еще такой вопрос: и что теперь, неужели каждую программу для подобных компаний типа FB нужно заворачивать в графическое приложение???
Консольные приложения уже не рулят?
В посте вы спрашивали о том, почему задачка была такой легкой.
Вот, что пришло мне в голову, пока читал пост:
1) В целом для аудитории задача оказалась трудноватой (вы же сами сказали, что написали только 3 человека из 150)
2) В Facebook вас же приглашают (или пригласят после интервью) как New Grad, а это не то же самое, как если бы к ним пришел дядька лет 40 на конкретную позицию. Его бы уж там поспрашивали бы.
Вот как-то так)
Еще такой вопрос: и что теперь, неужели каждую программу для подобных компаний типа FB нужно заворачивать в графическое приложение???
Консольные приложения уже не рулят?
1. Я полагаю, что на 2-3 годах обучения на Computer Science любой может ее быстренько решить. Здесь вопрос стоял только в том, заморачиваться ли и отправлять рекрутеру получившийся код.
2. Даже не как New Grad, а еще ниже :) на Co-op программу (оплачиваемая интернатура).
В UI заворачивать не обязательно, да и консольные приложения все еще рулят — бояться нечего. Я просто решил немного выделиться из толпы и не прогадал :)
2. Даже не как New Grad, а еще ниже :) на Co-op программу (оплачиваемая интернатура).
В UI заворачивать не обязательно, да и консольные приложения все еще рулят — бояться нечего. Я просто решил немного выделиться из толпы и не прогадал :)
У меня на собесе в одну хорошую контору было такое задание. Только я ее в онлайн режиме делал, а человек сидел и смотрел как я при этом код пишу (через google docs). Всего было 5 вопросов, которые нужно было решить за 1 час. Эта задача была самой сложной в том списке и стояла под номером 3 (что мне кажется тоже было важно!), а не 5.
Получалось что задачу нужно было решить в некотором стрессовом режиме: время ограничено, человек делает code review и индусский код ему может не понравится даже если задача будет решена, и конечно же я приступил к ней 3-й по списку а за ней еще 2 задания было. Ну т.е. я испытал некий стресс и страх, что я не успею вовремя :) Уложился в 1.5 часа (в итоге задачу под номером 3 я делал последней после 4 и 5), этот результат все же засчитали как success на 5 баллов.
Получалось что задачу нужно было решить в некотором стрессовом режиме: время ограничено, человек делает code review и индусский код ему может не понравится даже если задача будет решена, и конечно же я приступил к ней 3-й по списку а за ней еще 2 задания было. Ну т.е. я испытал некий стресс и страх, что я не успею вовремя :) Уложился в 1.5 часа (в итоге задачу под номером 3 я делал последней после 4 и 5), этот результат все же засчитали как success на 5 баллов.
Python Я попытался сэмулировать поведение человека который решал бы эту задачку
gist.github.com/rmuslimov/8728898
gist.github.com/rmuslimov/8728898
Напомнило один из уровней питон челленджа, где на входе давали картинку-линию шириной в 1 пиксель и подсказку в виде булочки-рогалика чтоли) линию заворачиваешь в спираль и выходила картинка котэ
а тут в фейсбуке такое )
а тут в фейсбуке такое )
Боже, мои глаза!
Рисовать квадрат по мере возсрастания чисел верх-бок-низ-бок-повторить это подход дизайнера, а не программиста. Это подох человека который представляет как работает компьютер только по картинкам которые он показывает.
currentNumber++ четырежды в каждой итерации на каждую сторону, в рот мне ноги!..
Да в этом коде прекрасно решительно все, продолжать можно бесконечно.
Короче это красивые картинки и забавные слова, но с технической стороны это просто выстрел в ногу…
А про интервью, как уже правильно сказали — приглашают всех, hr скрининг тупо бреет всех кого только можно, а там уже разберуться. Но на позицию программиста с такими картинками обольщатся не стоит.
Рисовать квадрат по мере возсрастания чисел верх-бок-низ-бок-повторить это подход дизайнера, а не программиста. Это подох человека который представляет как работает компьютер только по картинкам которые он показывает.
currentNumber++ четырежды в каждой итерации на каждую сторону, в рот мне ноги!..
Да в этом коде прекрасно решительно все, продолжать можно бесконечно.
Короче это красивые картинки и забавные слова, но с технической стороны это просто выстрел в ногу…
А про интервью, как уже правильно сказали — приглашают всех, hr скрининг тупо бреет всех кого только можно, а там уже разберуться. Но на позицию программиста с такими картинками обольщатся не стоит.
Кажется, каждый считает необходимостью сказать о качестве кода, даже после того, как я подчеркнул, что код плохой, и что это и было причиной написать топик: мое удивление, почему после такого, заранее проваленного задания, меня пригласили на собеседование.
Я эту статью написал, чтобы люди как-раз поняли, что интервью выбить не проблема. Или я где-то зачел себе это в подвиги? :) Или я где-то написал, что код получился великолепным? :) Или я где-то хвастался качеством кода? :)
Уверен, вы напишите код гораздо лучше меня. А на позицию программиста я и не мечу. Я знаю, что любое интервью я провалю — поэтому я и начал сам проводить собеседования, а не ходить на них ;)
Еще раз, я не сомневаюсь в ваших умственных способностях, но откуда у вас поводы сомневаться в моих?
Я эту статью написал, чтобы люди как-раз поняли, что интервью выбить не проблема. Или я где-то зачел себе это в подвиги? :) Или я где-то написал, что код получился великолепным? :) Или я где-то хвастался качеством кода? :)
Уверен, вы напишите код гораздо лучше меня. А на позицию программиста я и не мечу. Я знаю, что любое интервью я провалю — поэтому я и начал сам проводить собеседования, а не ходить на них ;)
Еще раз, я не сомневаюсь в ваших умственных способностях, но откуда у вас поводы сомневаться в моих?
Дошли руки до этого поста в очереди Pocket,
и после прочтения некоторой части Learn you some Erlang for great good родилось такое решение
и после прочтения некоторой части Learn you some Erlang for great good родилось такое решение
-module(facebook).
-export([square/1, print_square/1]).
square(N)->square(1, N).
square(Start, 1)->[[Start]];
square(Start, 2)->[[Start, Start+1], [Start+3, Start+2]];
square(Start, N)->
TopRight = Start+N-1,
[lists:seq(Start, TopRight)]++
extend(square(TopRight+3*N-3, N-2), TopRight+3*N-4, TopRight+1, [])++
[lists:reverse(lists:seq(TopRight+N-1, TopRight+2*N-2))].
extend([H|T], Left, Right, Acc)->
extend(T, Left-1, Right+1, [[Left]++H++[Right]|Acc]);
extend([], _, _, Acc)->lists:reverse(Acc).
print_square(N)->
lists:foreach(fun(Row)->io:format("~w~n", [Row]) end, square(N)).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я выбил собеседование в Facebook