Как я выбил собеседование в Facebook

    imageЗдравствуйте, уважаемые читатели Хабрахабра!

    В этой статье я расскажу о том, как мне, ничем не примечательному студенту, без особых проблем удалось выбить собеседование в одной из компаний списка «Biggies» — Facebook.

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

    К сожалению, FB не является моей приоритетной целью; поэтому съезжу на интервью, посмотрю на вопросы и напишу следующую статью о том, что же спрашивали и что же я могу спросить на интервью в моей студии.

    Заинтересовавшихся прошу под кат.

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

    Шел вторник, мне нечего было делать после университета, я забежал на лекцию Facebook на кампусе за бесплатной пиццей. Кстати, я съел три куска, однако, самая вкусная пицца, на моей памяти, была на презентации Electronic Arts. Ребята от Цукерберга набили полный зал студентов, около 150 человек. Поговорили про процесс подачи заявки в FB, про серию интервью и решили пару-тройку простеньких задачек типа «Реализовать поиск дубликатов в массиве» — задачки уровня детского сада на 30-40 секунд подумать.

    Я было уже собирался уходить — пицца кончилась, а мне становилось сильно скучно. Тем более, я успел всем надоесть — поднимал руку раньше всех и всегда предлагал решение лучше. На середине лекции меня вообще перестали спрашивать и обращать на меня внимание, что, определенно, сильно меня расстроило. Однако, в завершение, нам дали «задачку на дом», а главный рекрутер сказал скинуть ему на email решение, если вдруг появится оное.

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

    image

    По началу, я забыл про эту задачку, но переписал ее на постер, который мне подарили за ответы. А другим раздавали футболки — ну за что меня так? За то, что много отвечал.

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

    На скорую руку накидал интерфейс программы и сделал его слегка тематическим — вдруг придет рекрутеру сотня решений, и все одинаковые? Здесь нужно как-то выделиться из толпы!

    image

    Ну, не суть важно. За основу матрицы я взял двумерный массив. В моем случае, NSArray из NSArray из NSNumber. И сразу же написал метод вывода этого массива в нужное окошко. Окошком был WebView — в нем можно удобно построить табличку на HTML:

    Осторожно, код!
    /**
     *  Метод, который показывает содержимое массива в WebView
     *
     *  @param result Массив массивов цифр
     */
    - (void)printResult:(NSArray *)result
    {
        // Простой css с нужным шрифтом, размером и положением текста в таблице
        NSString *css = @"<style>*{font-size:17px; font-family:\"Helvetica\";}  td{text-align:center;}</style>";
        
        // Создаем изменяемую строку с нужным css и начинаем таблицу
        NSMutableString *resultString = [NSMutableString stringWithFormat:@"%@<table>",css];
        
        // Итерируем по главному массиву
        for (NSArray *inner in result) {
            // Начинаем строку таблицы
            [resultString appendString:@"<tr>"];
            
            // Итерируем по внутреннему массиву
            for (NSNumber *number in inner) {
                // Начинаем столбец в строке
                [resultString appendString:@"<td>"];
                
                // Показываем цифру
                [resultString appendString:[number stringValue]];
                
                // Заканчиваем столбец в строке
                [resultString appendString:@"</td>"];
            }
            
            // Заканчиваем строку в таблице
            [resultString appendString:@"</tr>"];
        }
        
        // Заканчиваем таблицу
        [resultString appendString:@"</table>"];
        
        // Показываем наш HTML в WebView
        [self.resultWebView.mainFrame loadHTMLString:resultString baseURL:nil];
    }
    

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

    Осторожно, код!
    /**
     *  Метод для генерации массива с круговой матрицей
     *
     *  @param side Сторона матрицы (квадрата)
     *
     *  @return Массив массивов цифр, например, [[1,2,3],[8,9,4],[7,6,5]]
     */
    - (NSArray *)getNumbersArrayForSide:(int)side
    {
        // Инициализируем массив
        NSMutableArray *result = [NSMutableArray array];
        
        // Заполняем массив нужной длины нулями
        for (int i = 0; i < side; i++) {
            NSMutableArray *temp = [NSMutableArray array];
            for (int j = 0; j < side; j++)
                [temp addObject:[NSNull null]];
            [result addObject:temp];
        }
        
        // Текущая сторона квадрата, который мы рисуем
        int currentSide = side;
        // Текущее смещение квадрата
        int offset = 0;
        int currentNumber = 1;
        
        // Повторяем, пока не достигнем центра квадрата
        while (offset < (side/2.0)) {
            // Нарисуем верхнюю линию
            for (int i = 0; i < currentSide; i++) {
                result[offset][offset+i] = @(currentNumber);
                currentNumber++;
            }
            
            // Нарисуем правую линию
            for (int i = 0; i < currentSide-2; i++) {
                result[1+offset+i][side-1-offset] = @(currentNumber);
                currentNumber++;
            }
    
            // Нарисуем нижнюю линию
            if (side/2 - offset > 0) {
                for (int i = 0; i < currentSide; i++) {
                    result[side-1-offset][side-1-i-offset] = @(currentNumber);
                    currentNumber++;
                }
            }
    
            // Нарисуем левую линию
            for (int i = 0; i < currentSide-2; i++) {
                result[side-2-offset-i][offset] = @(currentNumber);
                currentNumber++;
            }
            
            // Увеличиваем смещение, уменьшаем текущую сторону
            offset++;
            currentSide-=2;
        }
        
        return result;
    }
    

    • Решил создать матрицу нужного размера, заполненную NSNull объектами; а после заполнять ее нужными числами.
    • Каждую итерацию сторона квадрата уменьшается на 2, потому что мы отрезаем по одному числу с двух сторон.
    • Смещение — это координата начала текущего квадрата (и «x», и «y» — они одинаковые).
    • У каждого квадрата сначала рисуется верх, потом правая сторона, потом низ, потом левая сторона.
    • В случае, если сторона квадрата равна 1, низ рисовать не нужно; иначе, центральное число будет на 1 больше. Почему? А вот и вам домашнее задание :)

    А вот и результат для стороны квадрата, равной восьми:

    image

    Благополучно закончив кодинг и тестинг, я отправил письмо с моим резюме и решением на email главного рекрутера. Сегодня вечером я обнаружил ответ: меня поблагодарили и пригласили на интервью в офис.

    Честно сказать, я был ошеломлен. Наверняка же, люди присылали решения получше: почему я? Оказалось, все просто. Из телефонного разговора я понял, что из 150 человек в лекционной отправили решение только трое (я в их числе). У одного решение не скомпилилось, у другого простое консольное решение на плюсах, а у меня вот такой приятный глазу UI. Похоже, выбор был очевиден.

    Очень часто слышу жалобы студентов, что им не перезванивают после отправки резюме в компанию. Вспоминается анекдот про Бога и лотерейный билет.

    Спасибо, что дочитали до конца! Вот так, при помощи решения задачки школьного уровня, у меня удалось заполучить собеседование в Facebook. Я уверен в том, что есть решение проще, и безумно сильно хочу о нем узнать! Пожалуйста, поделитесь своим способом решения в комментариях.

    По традиции, прошу обо всех найденных ошибках и опечатках сообщать в мой хабрацентр.
    Поделиться публикацией

    Комментарии 140

      0
      Подозреваю, что есть математическая формула вывода текущего значения массива. Кто-нибудь может поделиться?
        +4
        Все подстроки — дают прибавку на арифметическую прогрессию, так что формула (с 4-мя if) выводится однозначно
          +1
          Прогрессия самая простая (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;
          
            +2
            А если ещё подумать, то можно уложиться чуть ли не в одну строчку:
            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;
            
              +5
              Прошу прощения если надоел кому-то, но не давала покоя мысль, что можно сделать ещё короче:
              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++;}}
              
                +2
                Шикарно!!! Дёшево и сердито! )
                  +1
                  Спасибо, я старался :)
                  +1
                  Тогда уж так:
                      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…
                    +2
                    Да, надо было от дробных избавиться. Ну, раз пошла такая пьянка:
                    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++;
                    
                      0
                      Только сейчас заметил, что это решение уже можно отправлять в @TinyProof ;)
                        +1
                        И правда…
                        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++;
                        
                          +1
                          Или даже так — чтобы убрать зависимость от размера 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++;
                          
                            +2
                            Господа, если ряд ваших решений окажется сходящимся, спустя бесконечный промежуток времени вы докажете, что задача решается в 0 байт кода (но при этом все еще программно). Предлагаю сильно не увлекаться, дабы случайно не нарушить какой-нибудь фундаментальный закон природы.

                            А в целом — очень круто. Особенно круто в сравнении с трехэкранными листингами. Я правильно понимаю, что тут происходит все тот же спиральный обход матрицы по порядку, просто очень хитро описанный?
                              +2
                              Да, то же заполнение матрицы спиральным обходом.
                              Думаю, ещё один шаг природа всё-таки выдержит :)
                              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;
                              
                                +1
                                Одна оптимизация ох оптимальнее другой. Замена цикла очень кстати. Он перестал быть таким пугающим, а заодно перед глазами прекратила всплывать картинка с компилятором, умоляющим убрать это объявление или использовать C99.
                                  +2
                                  Блестяще!!! Мне остаётся только засунуть всё это в единственный цикл и обфусцировать, чтобы никто точно ничего не понял :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++;
                                  
                                  +1
                                  Точно, точно, они уже впллотную подходят к пределу, заданному информационной энтропией данной постановки вопроса :-) Короче уже ни на одном человеческом языке не сформулируешь, пожалуй. Возможности лаконичного синтаксиса сишного ЯП пошли во благо… при умелом использовании.
                                    0
                                    Интересно, насколько компактно это можно было бы написать на каком-нибудь APL или J.
                  +4
                  Формула определенно есть. Но выводить ее абсолютно лень. Поэтому на скорую руку набросал код, считающий любой элемент матрицы наиболее очевидным образом.
                  Осторожно, 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 — сторона квадрата.
                  Рассчитывается только главная диагональ, от нее уже без проблем получается нужная величина.

                  Естественно, это далеко не оптимальный вариант. Но рассчитывает довольно шустро.
                    +3
                    PS: иногда я сначала пишу код, потом просыпаюсь. Все упоминания halfS — лишние. Сравнения с этой величиной безболезненно убираются, равно как и ее вычисление. Это меня куда-то не туда понесло вдруг.
                      +3
                      Вот медленное, но, кмк, самое очевидное и легко читаемое решение из всего, что мне пришло в голову. Клеточный автомат :)
                      #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;
                      }
                      
                        +1
                        Собственно, то же самое, но без 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;
                        }
                        
                      +13
                      C++, голый алгоритм
                      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
                        +1
                        Из интереса написал на Java класс Spiral — добавил медленную демонстрацию (за 1 шаг вычисляется 1 позиция), и для быстрого вывода ваше демо. Код на Pastebin
                          0
                          Респект! :-) Долго формулы выводили?
                          По коду на гите вопрос — результаты функции calc никуда не сохраняются, что ли?
                          Кстати, любопытная вещь получилась. Выходит, что наивная реализация по скорости очень близка «покоординатной». В один поток при сравнении у меня получились очень схожие цифры. Видимо, в первом случае время уходит на случайный доступ к памяти, а во втором — на арифметически более сложный расчёт содержимого клетки квадрата…
                            0
                            15 минут с ручкой и листком бумаги, чтобы расписать 10х10 и проанализировать верхнюю левую полудиагональ. Остальные полудиагонали выводятся довольно просто — по 5 минут на каждую.

                            Ага, не сохраняются. Раньше выводил в консоль, потом писал в файл, но так как писалось из чисто академического интереса «чей код будет быстрее» и «почему мой с++ медленнее твоего c#», то вывод результатов был убран.

                            Да, по скорости в один поток они будут близки. Координатная вырывается вперед если, к примеру, стоит задача вывести значения средней строчки.
                              +1
                              Я просто подумал, что компилятор увидит, что ret нигде не сохраняется/не читается, и вообще уберёт цикл… :-)
                                +1
                                Ага, именно поэтому ret объявлена с volatile =)
                            0
                            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.
                            –1
                            Сомневаюсь, что можно получить значение только по координатам (как, например, в симплекс-шуме). По такой таблице рисуется скатерть Улама, а наличие способа реверс-композиции без прохода до нулевой точки означало бы несколько нехороших свойств для простых чисел. Хотя, наверняка есть способ приближённого расчёта через экспоненцирование (см. график ряда 0 5 18 39 68 105..., по мере отдаления от 0 для соседних рядов действуют те же правила).
                              +1
                              Прекрасно получается значение по координатам. Если подумать — можно прийти к тому, что где-то внутри будет запрятана арифметическая прогрессия.
                                +1
                                И тем не менее, в комментариях уже шесть решений (включая одно моё), ни одно из которых эту прогрессию не использует. Под экспоненцированием я имел в виду решение геометрической прогрессии, а не арифметической, а точных способов возведения в произвольную степень за константное время нет. Если вы тут видите арифметическую прогрессию, пожалуйста, завершите мысль и покажите, где она.
                                  0
                                  И тем не менее, над вашим комментарием висит мое решение, которое по сути считает значение клетки по заданной стороне квадрата и координатам. Более того, на гисте выложен распараллеленный вариант.
                                +2
                                Чуть выше я приводил пример с вычислением элемента по опорной величине на главной диагонали. Вот выделил немного времени, чтобы определить зависимость величины элемента главной диагонали от его расположения:
                                Осторожно, снова 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'ы основной функции.

                                Здесь уже никаких хитростей, никаких предварительных вычислений. Формула энного члена арифметической прогрессии используется в вычислении элемента диагонали, причем для второй половины — дважды. Нет ограничения на четность размерности, как в комментарии ниже.
                              +26
                              Получить приглашение на интервью достаточно легко практически в любой серьёзной фирме при наличии более-менее адекватных навыков. Но это пока ещё не гарантия трудоустройства — в подобных фирмах интервью достаточно сложные.

                              PS: решение неплохое, хотя и далеко не оптимальное — c-style массив был бы уместнее.
                              PPS: когда-то давно, в школе, решал эту задачку на QBasic, который не поддерживал двумерные массивы.
                                0
                                Да, это еще не трудоустройство :) Написал эту статью для тех, кто говорит, что даже до интервью дойти не может.

                                Решение очень далеко от оптимального — это меня сильно и удивило, когда я получил ответ.

                                Можете вспомнить, как без двумерных массивов решили? Мне просто интересно почитать :)
                                  0
                                  Циклами. Начинал, помнится, с середины, затем раскручивал увеличивая счётчики. Как-то так, точнее не могу припомнить, увы. А садиться писать такой алгоритм охоты нет. Фишка была в том, что я не заполнял массив, а сразу выводил в нужное место на экране.
                                    –1
                                    Спасибо! Здесь проблема была в том, что выводить числа нужно было последовательно в консоль. Вместо консоли я просто использовал WebView.

                                    Я плох в плюсах, но, вроде как, там нельзя в кастомное место консоли выводить символ.
                                      0
                                      Можно, но решение платформозависимо. Кстати, в WebView тоже ведь можно записывать не всё сразу, а поэлементно. Задать ячейкам таблицы id формата «cell_%d_%d», x, y — и вставлять javascript-ом. Тогда тоже можно обойтись без массива.
                                        –1
                                        Да, тогда ваше решение с VB можно даже портировать на JS+Obj-C :) и получиться оно должно короче
                                  +1
                                  Не соглашусь. Может конечно у вас побольше опыта в получении приглашений на интервью. Мой опыт говорит мне — что это один из сложнейших этапов. Поэтому как это немалые затраты для компании — оплатить перелет и тому подобное.

                                  ЗЫ: Был на он-сайт интервью в ARM (1 интервью + тестовое задание перед приглашением на сайт). Сейчас готовлюсь к он-сайт в одной компании из США (8 phone-screen интервью перед приглашением).
                                    +1
                                    У всех в этом отношении разный опыт. И опять же — на какую позицию? Если джуна — то просто, а чем выше — тем сложнее. Хотя да, всяко бывает…
                                  +43
                                  У одного решение не скомпилилось, у другого простое консольное решение на плюсах, а у меня вот такой приятный глазу UI. Похоже, выбор был очевиден.
                                  Мне одному кажется, что выбор тут очевиден не в пользу автора?
                                    0
                                    Хайзенебргу нельзя отказывать. Потому, что он "… the one who knocks".
                                      –8
                                      Возможно, нужно немного уточнить: под словом «простое» я имел ввиду «обычное» — как и у меня, собственно. Только на плюсах и без UI.
                                        +18
                                        Видимо я уже совсем не в теме, но я не могу найти ни единой причины, зачем в такой задаче UI. Тут чистого C за глаза хватит с печатью в stdout.

                                        И да, зачем вам динамический массив объектов, вы с C насколько хорошо знакомы?
                                          –4
                                          С Си и Си++ я знаком очень поверхностно на уровне пары-тройки курсов по алгоритмике и структурам данных.

                                          Это решение ни в коем случае не претендует на правильное, либо оптимальное. Я просто сумел «продать» красивый код, вместо правильного, и написал об этом статью :)

                                          Works is better than perfect.
                                            +5
                                            ayende.com/blog/165378/fail-can-impress-too
                                            Забавно, что буквально вчера прочитал по этой теме в блоге ayende.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                –3
                                                Насколько я знаю, не объект добавить в NSArray нельзя — возможно, ошибаюсь.
                                                  +2
                                                  Как раз в том-то и дело, что следовало использовать обычный C-массив.
                                                    –2
                                                    Ну так я изначально хотел решить эту задачку на Objective-C :)
                                            +13
                                            По всей видимости, при выборе оценили не столько качество алгоритма (это дело наживное), сколько энтузиазм.
                                            Автор не просто решил поставленную задачу, а добавил к ней требований.
                                            Наверно это то, что в последнее время называют модным словом «креативность».
                                            Наверно по этим косвенным признакам можно судить о том, что человеку в радость решать задачки по программированию, он реально ими увлекается.
                                            Да, можно сказать, что все эти bells-and-whistles ни к чему для достижения заданной цели, а только отвлекают и т.д. и т.п.
                                            Но всё-таки, как мне кажется, такой подход на первоначальных этапах обучения искусству программирования дорогого стоит.
                                            Автор делает правильно.
                                            И задает правильные вопросы об улучшении качества алгоритма.
                                            Задача поставлена -> задача решена в срок и с нужным качеством -> теперь можно подумать и об оптимизации.
                                              –2
                                              В данном случае человек использует заведомо неэффективную структуру данных, что может говорить лишь о том, что он не понимает, как она работает (я про NSMutableArray объектов). Я не представляю требования, для которых это можно назвать «нужным качеством».
                                                +6
                                                Не можете?
                                                Вот Вам требования: «Реализуйте приложение, которое сможет наглядно показать людям, что такое циферки в спиральке.»
                                                  +7
                                                  Программа работает? Да. Без ошибок? Да. Время выполнения приемлемое? Да. Вот все _достаточные_ требования.
                                                  Насчет эффективности можно далеко зайти.
                                                  Вот вы считаете реализацию на этой готовой структуре неэффективной, и наверно могли бы написать на с++, а я ваш код так же раскритикую и скажу, что вы написали плохо, потому что лучше написать на ассемблере.
                                                    0
                                                    Гхм. Вы уверены, что я не понимаю, как она работает? Я уже несколько раз писал, что решение заведомо не оптимальное, но делалось на скорость и на коленке. Это то, почему я и был удивлен приглашению на собеседование. Я нигде не говорил, что алгоритм и его реализация правильные.
                                                  +9
                                                  >Мне одному кажется, что выбор тут очевиден не в пользу автора?

                                                  Мне одному кажется, что второго тоже скорее всего пригласили на собеседование? :)
                                                  +1
                                                  Задача про «квадратную спираль» похоже становится стандартом — в качестве одного из заданий она была предложена год назад при прохождении теста для поступления в школу разработчиков при headhunters
                                                    +1
                                                    Меньшиков. «Олимпиадные задачи по программированию». Задача 2F.
                                                    Мой преподаватель, организовывавший пару 10ков лет (или больше, да он и сейчас этим занимается) олимпиады по программированию для школьников, всем рекомендовал эту книгу. «Достаточно просто прорешать её всю и будешь демонстрировать отличные результаты на олимпиадах среди вузов». Поскольку все остальные преподаватели обучались у него, то они для курса структурного программирования задачки брали из этой же книги. Так что я «Спираль» писал в вузе (2007-2012) раза три.
                                                    –1
                                                    Креативно!
                                                      +13
                                                      Вспомнилось, как мы рисовали такие спирали во время лабораторных на военной кафедре. Прикол был не в спирали как таковой, а в том, что упражняться приходилось на эмуляторе процессора «большой» ЭВМ серии ЕС, запущенном на PC/XT (советском клоне, конечно). Надо было написать программу на ассемблере, вручную транслировать ее в коды и вбить в весьма симпатичный отладчик-эмулятор, который кроме регистров показывал еще и содержимое куска памяти, в котором и должна была появиться спираль. Причем работало это все со скоростью нескольких команд в секунду, так что спираль рисовалась весьма торжественно. Жаль, что тогда не то что Фейсбука, а еще и WWW не было, так что никто на собеседование не пригласил :)
                                                        +3
                                                        О да, знакомая задача, в качестве лабораторной по си на первом курсе попалась :)
                                                          +2
                                                          Тоже решал такую задачку на первом или втором курсе на лабораторных. Думаю, такое дают в большинстве университетов.
                                                          +5
                                                          А я вчера был на собеседовании в компании, которую купили на днях IBM, так что если туда устроюсь — буду работать фактически в IBM.
                                                          Заданием было — реализовать простое бинарное дерево (не балансируемое даже). Вот так-то :) Вроде как приглашают на второе собеседование, так что все гуд (рекрутер (независимый агент который) сказал что хотят пригласить, но пока время не утрясли)
                                                            +2
                                                            В свое время мне очень понравилась другая задача — есть шахматная доска и один конь. Надо полностью «закрасить» шахматную доску ходами. решил еще в докомпьютерное время, а вот насчёт алгоритма было бы интересно узнать
                                                              +1
                                                              Задача на 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);
                                                              }
                                                              

                                                                +1
                                                                Работает не всегда, кстати, алгоритм из этого поста — обход по кругу получается оптимальнее.
                                                                я помню что у меня получилось далеко не с десятого варианта, пока не пошел по входящей внутрь спирали
                                                                0
                                                                Для больших размеров доски нужно использовать Warnsdorff's rule: ходить в клетку, из которой можно сделать наименьшее число ходов. Работает за линию от числа клеток.

                                                                Вот я недавно решал на Прологе (B-Prolog): stackoverflow.com/questions/21066294/knights-tour-efficient-solution/21069014#21069014
                                                                  0
                                                                  Видимо я этот принцип и применил, делая спираль от внешнего радиуса в центр своим решением, чем ближе к центру тем вариантов ходов не так много
                                                                –3
                                                                Товарищи, хабрачеловеки! Час назад у автора было 11.7 сами_знаете_чего, сейчас, как я вижу, 8.7. Давайте будем человечнее. И использовать минусы по делу. Я все сказал.
                                                                  –5
                                                                  И мне нагадили… Ну спасибо
                                                                    +6
                                                                    Хабр — саморегулирующееся сообщество. Не понравилась статья большинству — получай.
                                                                      +1
                                                                      Судя по том, что статья на главной, большинству как раз понравилось. Но то меньшинство, которому не понравилось, имеет самые заряженные минусомёты
                                                                        –7
                                                                        И мой хабрапульс это подтверждает…
                                                                        –2
                                                                        Ну, тут проблемка немного в другом: большинству, все-таки, понравилось. 91 плюс на 66 минусов. Просто Bringoff отметил, что минусы люди гораздо охотнее ставят :)
                                                                        0
                                                                        Да, к сожалению Хабр скор на расправу. Как тут не вспомнить про лигу зла с пикабу? ;)
                                                                        –1
                                                                        У некоторых людей к backmeupplz есть личные претензии. Все его комментарии частенько методично проминусовываются.
                                                                          –2
                                                                          Да я уж не думаю, что я такой особенный, чтобы специально меня минусовать :)

                                                                          Кстати, на текущий момент 66 минусов… и 66 добавлений в избранное! :) Похоже, минусующие решили сохранить статью на «потом почитать».
                                                                            0
                                                                            Соотношение минусов и добавлений в избранное остаётся стабильным… Сейчас 96/95 :)
                                                                            Впрочем, я подобный эффект уже заметил на опросах. Проценты, полученные после нескольких сотен ответов, дальше уже не меняются.
                                                                        +11
                                                                        К сожалению, FB не является моей приоритетной целью;

                                                                        Я бы сказал, что к счастью…
                                                                          +3
                                                                          Кстати о гуях. В интерфейсе кроме поля ввода и поля вывода нет больше никаких интерактивных элементов. Если в таком интерфейсе приходится явно дополнительно указывать на то, где находится поле ввода, то это не очень хороший интерфейс, мягко говоря. Уж лучше б консольный.

                                                                          Я плох в плюсах, но, вроде как, там нельзя в кастомное место консоли выводить символ.

                                                                          Ну так сначала сформировать матрицу, а потом построчно ее выводить же можно (это если вычислять элементы не последовательно).
                                                                            0
                                                                            Да; и интерфейс, и алгоритм можно дорабатывать бесконечно :) Хотелось оставить некое подобие «Диалога» с ГГ из сериала «Во все тяжкие» — и, соответственно, дать пользователю возможность ответить на его вопрос. Это можно сделать лучше и креативнее, но самое решение я делал просто так, ради себя, а отправил рекрутеру email чтобы попытать удачу :)
                                                                            +39
                                                                            (Господа минусующие! Пожалуйста, напишите, что не так со статьей. А то я просто поделился своим опытом, и сразу такой холодный и молчаливый прием)

                                                                            Предположительно реакция из-за тезисов:
                                                                            * Я красавчег!
                                                                            * Мне все скучно!
                                                                            * Нефигделать!
                                                                            Суммируя: Пост хвастовства.

                                                                            Кстати, ни минус ни плюс не ставлю, так как считаю тебя вполне нормальным амбициозным молодым человеком, у которого все впереди, ты далеко можешь пойти (в хорошем смысле), но стеклянного потолка не достанешь, так как будешь периодически падать.
                                                                              +12
                                                                              А я думал, что парень вот так легко попал на интервью из какой-нибудь Калуги (просто первое, что вспомнил). А он, оказывается, даже ходит пиццу стрельнуть в фейсбук.
                                                                                +3
                                                                                Как-то так. Думаю каждый из нас, у кого есть что-то на сегодня за плечами, может это преподнести по разному, и конечно когда у тебя компания, миллионные прибыли, тысячи сотрудников и тд, можно сказать так, типа проходил мимо встретил пару друзей, набросал код, туда-сюда и теперь мы крупная преуспевающая компания, всем будет ясно, что это такая ирония. Я же не хожу не трублю что у меня хостинг провайдер, лишь потому-что я администрирую десяток серверов, или что у меня студия веб дизайна, когда я при помощи товарища дизайнера и верстальщика запилил десяток сайтов. Хотя да, все большое зачастую начинается с чего-то малого.
                                                                                –4
                                                                                Да я, вроде как, ничего сверхъестественного и не описал в статье. Я честно думал, что у всех все так просто получается — думал, что кто-нибудь узнает себя :)
                                                                                А уж решения задач с Tech Talk от Facebook всем, по моему мнению, даются просто (30-40 секунд). Я уверен, что вы гораздо быстрее меня решите задачку из поста.
                                                                                Я пытался подчеркнуть легкость «домашнего задания» (да и всего, что FB дает студентам), дабы показать, как просто попасть на собеседование.
                                                                                  +2
                                                                                  я думаю что не у многих так просто получается, увы иногда не хватает знаний или смекалки, но чаще всего не хватает решительности, но это уже вопрос другого порядка, тут дело не в области применения а в технике.
                                                                                +16
                                                                                «Как я выбил собеседование в Facebook»
                                                                                Если сократить до сути: «я сделал тестовое задание, к нему — красивый интерфейс — и меня пригласили». Уникальная история, ни у кого таких нет!

                                                                                Хотя может для кого-то пост и станет мотивационным. В этом его плюс. Так что ни стал ни плюс, ни минус ставить. В кои то веки нашлось применение черточке между ними…
                                                                                  0
                                                                                  Этот пост адресован, в основном, студентам, которые постоянно жалуются, что им не перезванивают после отправки резюме.

                                                                                  Выше уже написал, что пытался подчеркнуть, насколько просто попасть на собеседование в Facebook.
                                                                                    +6
                                                                                    Тысяча чертей! Так она, оказывается, нажимается!
                                                                                    +3
                                                                                    Решение отвратительное. Надо было написать: решение школьной задачи алгоритмом уровня той же школы и без понятия о такой вещи, как алгоритмизация.
                                                                                      +1
                                                                                      Так я же нигде и не претендую на хорошее решение. Наоборот, я подчеркиваю, что удивлен, как такое плохое решение дало мне возможность съездить в офис FB на собеседование.
                                                                                        0
                                                                                        На будущее: сей алгоритм сортировки называется улитка.
                                                                                      +1
                                                                                      Несколько лет назад в универе препод заставил решить эту задачу вычисляя значения в зависимости от координат.
                                                                                        –2
                                                                                        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))
                                                                                        
                                                                                          +8
                                                                                          А для четных N будете выводить ошибку «Число N должно быть нечетным»?
                                                                                          +9
                                                                                          Начало довольно пафосное получилось. Или мне показалось? ;)
                                                                                            –8
                                                                                            Мне казалось, что все так же рассуждают на различных Tech Talks :) разве нет? Они же и вправду скучные! А задачки простые.
                                                                                              +2
                                                                                              не только начало
                                                                                              +3
                                                                                              Несколько (не намного) более интересно было бы если задачу сформулировать так:

                                                                                              Дано N <= 10^18, row <= N, col <= N. Вывести число, находящееся в строке row, столбце col для квадрата со стороной N.


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

                                                                                              А по существу довольно интересно, нестандартно подошли. Что правда не отменяет того что сам алгоритм утонул в куче boilerplate-кода, мне бы такое писать было не интересно. Может вас дизайнером пользовательских интерфейсов хотят взять? ;)

                                                                                              Кстати тоже похвастаюсь тогда уж. В понедельник у меня будет первый рабочий день в Facebook, сейчас вот чемоданы собираю. Собеседование показалось на удивление легким (в сравнении с гугловым), но всё же не настолько легким как задача из поста.
                                                                                                +1
                                                                                                Дано N <= 10^18, row <= N, col <= N. Вывести число, находящееся в строке row, столбце col для квадрата со стороной N.

                                                                                                А длинную арифметику самому писать, или библиотеку дадут? Ответ может быть до 10^36.
                                                                                                  +1
                                                                                                  Упс, лучше понизить ограничения до 10^9.

                                                                                                  И кстати можно ещё и обратную задачу расммотреть. Дано N <= 10^9, и K <= N^2, найти где в квадрате будет расположено число K.
                                                                                                    0
                                                                                                    Над обратной задачей не думал, а изначальная дает результат за 0.0033 секунды в среднем. Это при N <= 10^18. Впрочем, при N в пределах 10 время выполнения то же. Вот после N<=10^115 время расчета вырастает до ~0.006.
                                                                                                      +2
                                                                                                      Ну обратную тоже через диагональ можно решать. Только там придется квадратный корень аккуратно брать чтобы погрешности не охватить.

                                                                                                      А так решение за O(1) — если считать что арифметические операции за константное время работают. Просто в C++ в отличие от Python длинной арифметики встроенной нет, поэтому для справедливости стоит понизить ограничение чтобы в uint64_t влезало.

                                                                                                      Кстати у вас тут мне кусочек не нравится:
                                                                                                      x <= math.ceil(float(n)/2)-1
                                                                                                      

                                                                                                      при больших числах наверняка не хватит мантиссы (сомневаюсь что в Python float тоже длинный).
                                                                                                        0
                                                                                                        И правильно делает, что не нравится. Когда писал, про длинную арифметику не думал. К счастью, тут без проблем должна встать замена на целочисленное деление с проверкой на нечетность n.
                                                                                                          0
                                                                                                          Полез исправлять и обнаружил, что для числа посредине диагонали для матриц с нечетной стороной справедливы обе формулы. Так что там достаточно (x <= n/2-1).
                                                                                                        0
                                                                                                        Обратная задача. Получилось не очень красиво:

                                                                                                        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 — боюсь, что из-за округления оно может отличаться на единицу в ту или другую сторону.
                                                                                                    0
                                                                                                    Кому интересно, вот код, который рисует этот «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
                                                                                                    

                                                                                                      0
                                                                                                      Ха-ха, возникла мысль о некоем обобщении в 3-мерном пространстве. Кто рискнёт написать визуализацию такого «куба с цифрами» на directX? :-)
                                                                                                      –5
                                                                                                      C#

                                                                                                      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
                                                                                                        +6
                                                                                                        Вы забыли 15 паттернов.
                                                                                                          –1
                                                                                                          +100 :-)
                                                                                                        0
                                                                                                        спасибо за разминку
                                                                                                        Решение в лоб на 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)
                                                                                                        
                                                                                                          +1
                                                                                                          Цветной вариант: jsfiddle.net/cVGr3/1/
                                                                                                            –3
                                                                                                            Всем неуд за лапшекод без документации и оопа в этом треде ^^
                                                                                                              +1
                                                                                                              Документировать в моих 6 строках, в каждой из которых возвращается результат простейших арифметических операций, нечего. Единственный элемент документации, который мог бы там быть — описание того, что возвращает сама функция. Но эту роль прекрасно выполняет содержимое поста.
                                                                                                              А неуда тут если за что и удостаивать, то только за стремление везде приткнуть ООП. Здесь оно ни к чему абсолютно.
                                                                                                                +2
                                                                                                                Вон выше ООП воткнули, так там простыня на 3.5 экрана получилась. Нафига оно тут вообще нужно, это ваше ООП? Это я вас как плюсовик/Qt-шник спрашиваю :)
                                                                                                                +3
                                                                                                                #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");
                                                                                                                	}
                                                                                                                }

                                                                                                                  –2
                                                                                                                  Вы бы взяли на работу человека, пишушего такой код? :)
                                                                                                                    0
                                                                                                                    А что не так? Чистый C.

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

                                                                                                                    Кстати, ваш вариант с векторами, комплексными числами, пачкой функций и листингом в экран является полной противоположностью этого. Там ведь еще и обход по спирали был? Как раз получаются два примера, оттеняющих плюсы и минусы друг друга (=
                                                                                                                      +1
                                                                                                                      Вы бы взяли на работу человека, пишушего такой код? :)

                                                                                                                      Думаю, да.
                                                                                                                      Если человек может заставить правильно работать этот код, значит, во-первых, он не испугается и других математических выкладок и их реализации; во-вторых, у него достаточно развита математическая интуиция, чтобы понять, в какой форме должен быть ответ, и когда имеет смысл искать/писать формулу, а когда лучше обратиться к итерациям или массивам. Ну, и в-третьих, есть хорошие шансы, что он и сам сможет читать подобный код и понимать, когда в нём имеет смысл разбираться, когда достаточно правдоподобности плюс проверки на примерах, а когда коду можно просто поверить.
                                                                                                                        +3
                                                                                                                        Ок. К коду на самом деле претензий нет. Он во многом превосходит мой — по потреблению памяти (в т.ч. ассимптотике её использования), по размеру, по требованиям к компилятору (хотя вашей программе требуется поддержка C99).
                                                                                                                        Просто интересно было, какие качества вы выделяете в коде кандидатов. Я всегда стремлюсь писать максимально простой и понятный код, и от кандидатов всегда хочется того же самого. Интересна позиция других :)
                                                                                                                          0
                                                                                                                          Просто в проектах, которыми я сейчас занимаюсь (в моей части) непосредственно под архитектурой лежат алгоритмы, и уровня, собственно, кодирования по ТЗ практически нет. И часть «хорошо реализовать алгоритм и уметь его прочитать» несколько важнее, чем «написать код, понятный большинству».
                                                                                                                          А вот с кандидатами проблема — мы даже не можем сформулировать требования (PhD в математике или CS плюс хорошее понимание физики — то, что было написано для меня — это, как-то, чересчур). Любая задача, которую удаётся выделить, требует слишком глубокого погружения в проект. Попробую научить дочку. Там, хотя бы, время не ограничено.
                                                                                                                          А себя к себе я бы, конечно, взял. Даже если бы пришлось потратить время на погружение в проект. Мне сейчас хочется клонироваться в 3-4 экземплярах :)
                                                                                                                            0
                                                                                                                            Понятно, спасибо за детали. Вопроса «взяли бы вы на работу себя» не стояло, его надумал автор поста. Интересна просто разница в подходах к программированию. Я работаю в компании, где нужно писать очень много кода, и ещё больше читать. Вы — там, где нужно придумать сложный алгоритм, реализовать его и перейти к следующему проекту. Теперь всё прояснилось :)
                                                                                                                            Где-то читал про программистов-математиков вроде Кнута и программистов-писателей вроде Ларри Уолла.
                                                                                                                              0
                                                                                                                              Если не секрет, где вы работаете?
                                                                                                                                +1
                                                                                                                                Фирма Basis Software, разработка лазерного сканера Surphaser.
                                                                                                                          0
                                                                                                                          Всегда считал странными вопросы «Взяли ли бы вы себя работать к себе» :)

                                                                                                                          Лично я всегда отвечаю «Нет», потому что я лентяй, разгильдяй и недоучка :)

                                                                                                                          А если по сабжу, то я бы лично взял такого человека работать к себе, если он сможет мне подробно описать, как работает этот код. Да так, чтобы я понял.
                                                                                                                            –1
                                                                                                                            Код очень короткий и не хранит в памяти массив для вывода, поэтому будет работать даже на N=32766.
                                                                                                                            0
                                                                                                                            Отличное решение!

                                                                                                                            Сколько времени ушло на него?
                                                                                                                              0
                                                                                                                              Довольно много — минут 15. Сначала написал какие-то формулы, более-менее похожие на то, что должно быть, потом смотрел на результаты и подбирал коэффициенты. Примерно с пятой попытки получилась правильная картинка.
                                                                                                                            0
                                                                                                                            Два года назад собеседовался у них. Перед очным собеседованием был предварительный отсев HR-ом: надо было за час решить [несложную] задачу в какой-то автоматизированной системе тестирования, потом было 4 телефонных собеседования с написанием кода. Потом свозили в новый офис в Palo Alto, а потом сказали, что не подходжу :)

                                                                                                                            А насчет задачи: на одной из школных олимпиад больше 10 лет назад была задача построить скатерть Улама
                                                                                                                              +3
                                                                                                                              Здравствуйте, backmeupplz!

                                                                                                                              В посте вы спрашивали о том, почему задачка была такой легкой.
                                                                                                                              Вот, что пришло мне в голову, пока читал пост:

                                                                                                                              1) В целом для аудитории задача оказалась трудноватой (вы же сами сказали, что написали только 3 человека из 150)
                                                                                                                              2) В Facebook вас же приглашают (или пригласят после интервью) как New Grad, а это не то же самое, как если бы к ним пришел дядька лет 40 на конкретную позицию. Его бы уж там поспрашивали бы.

                                                                                                                              Вот как-то так)
                                                                                                                              Еще такой вопрос: и что теперь, неужели каждую программу для подобных компаний типа FB нужно заворачивать в графическое приложение???
                                                                                                                              Консольные приложения уже не рулят?
                                                                                                                                0
                                                                                                                                1. Я полагаю, что на 2-3 годах обучения на Computer Science любой может ее быстренько решить. Здесь вопрос стоял только в том, заморачиваться ли и отправлять рекрутеру получившийся код.
                                                                                                                                2. Даже не как New Grad, а еще ниже :) на Co-op программу (оплачиваемая интернатура).

                                                                                                                                В UI заворачивать не обязательно, да и консольные приложения все еще рулят — бояться нечего. Я просто решил немного выделиться из толпы и не прогадал :)
                                                                                                                                0
                                                                                                                                У меня на собесе в одну хорошую контору было такое задание. Только я ее в онлайн режиме делал, а человек сидел и смотрел как я при этом код пишу (через google docs). Всего было 5 вопросов, которые нужно было решить за 1 час. Эта задача была самой сложной в том списке и стояла под номером 3 (что мне кажется тоже было важно!), а не 5.

                                                                                                                                Получалось что задачу нужно было решить в некотором стрессовом режиме: время ограничено, человек делает code review и индусский код ему может не понравится даже если задача будет решена, и конечно же я приступил к ней 3-й по списку а за ней еще 2 задания было. Ну т.е. я испытал некий стресс и страх, что я не успею вовремя :) Уложился в 1.5 часа (в итоге задачу под номером 3 я делал последней после 4 и 5), этот результат все же засчитали как success на 5 баллов.
                                                                                                                                  0
                                                                                                                                  Python Я попытался сэмулировать поведение человека который решал бы эту задачку

                                                                                                                                  gist.github.com/rmuslimov/8728898
                                                                                                                                    0
                                                                                                                                    Напомнило один из уровней питон челленджа, где на входе давали картинку-линию шириной в 1 пиксель и подсказку в виде булочки-рогалика чтоли) линию заворачиваешь в спираль и выходила картинка котэ
                                                                                                                                    а тут в фейсбуке такое )
                                                                                                                                      +1
                                                                                                                                      Боже, мои глаза!
                                                                                                                                      Рисовать квадрат по мере возсрастания чисел верх-бок-низ-бок-повторить это подход дизайнера, а не программиста. Это подох человека который представляет как работает компьютер только по картинкам которые он показывает.
                                                                                                                                      currentNumber++ четырежды в каждой итерации на каждую сторону, в рот мне ноги!..
                                                                                                                                      Да в этом коде прекрасно решительно все, продолжать можно бесконечно.
                                                                                                                                      Короче это красивые картинки и забавные слова, но с технической стороны это просто выстрел в ногу…
                                                                                                                                      А про интервью, как уже правильно сказали — приглашают всех, hr скрининг тупо бреет всех кого только можно, а там уже разберуться. Но на позицию программиста с такими картинками обольщатся не стоит.
                                                                                                                                        +1
                                                                                                                                        Кажется, каждый считает необходимостью сказать о качестве кода, даже после того, как я подчеркнул, что код плохой, и что это и было причиной написать топик: мое удивление, почему после такого, заранее проваленного задания, меня пригласили на собеседование.

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

                                                                                                                                        Уверен, вы напишите код гораздо лучше меня. А на позицию программиста я и не мечу. Я знаю, что любое интервью я провалю — поэтому я и начал сам проводить собеседования, а не ходить на них ;)

                                                                                                                                        Еще раз, я не сомневаюсь в ваших умственных способностях, но откуда у вас поводы сомневаться в моих?
                                                                                                                                        +1
                                                                                                                                        Дошли руки до этого поста в очереди Pocket,
                                                                                                                                        и после прочтения некоторой части 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)).
                                                                                                                                        

                                                                                                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                                                                        Самое читаемое