Как нанять грамотного индуса?

[Mic]

В чем тут подвох то?

A = 1 2 3 4 5, m = 2
->
3 2 1 4 5
3 4 1 2 5
3 4 5 2 1

Вроде неправильно получается..

Задача решается в 2 итерации путем переставления элементов от крайних со смещением к центру:
1 2 3 4 5
5 2 3 4 1
5 4 3 2 1

Бенефиты: быстро, не используется extra-память.

[jms]

В чем тут подвох то?

A = 1 2 3 4 5, m = 2
->
3 2 1 4 5
3 4 1 2 5
3 4 5 2 1

Вроде неправильно получается..

Задача решается в 2 итерации путем переставления элементов от крайних со смещением к центру:
1 2 3 4 5
5 2 3 4 1
5 4 3 2 1

Бенефиты: быстро, не используется extra-память.

Только вот в исходной задаче нужно сделать циклический сдвиг а не перевернуть масив

[Mic]

Только вот в исходной задаче нужно сделать циклический сдвиг а перевернуть масив

Сдвиг? На сколько? В одну сторону или в обе? Что делать если заданное количество сдвигов превысит размер массива?

Есть массив A1, A2, ..., Am, Am+1, Am+2, ..., An. Без использования дополнительного массива преобразовать в массив Am+1, Am+2, ..., An, A1, A2, ..., Am

В исходной задаче вообще ни хрена не понятно...

[jms]

Только вот в исходной задаче нужно сделать циклический сдвиг а перевернуть масив

Сдвиг? На сколько? В одну сторону или в обе? Что делать если заданное количество сдвигов превысит размер массива?

Есть массив A1, A2, ..., Am, Am+1, Am+2, ..., An. Без использования дополнительного массива преобразовать в массив Am+1, Am+2, ..., An, A1, A2, ..., Am

В исходной задаче вообще ни хрена не понятно...

А помоему там вполне четко описан циклический свдиг вправо на m.

Update: свдиг вправо на n - m.

[Bonny P.]

и не замкнуть через него кольцо (n-m)-кратного циклического сдвига?

Если чесно, не совсем понял что это..

for (i=0, i<(n-m), i++) {
for (j=0, j<n, j++)
a[n-j] = a[n-j-1];
a[0] = a[n];
}

[jms]

и не замкнуть через него кольцо (n-m)-кратного циклического сдвига?

Если чесно, не совсем понял что это..

for (i=0, i<(n-m), i++) {
for (j=0, j<n, j++)
a[n-j] = a[n-j-1];
a[0] = a[n];
}

Не знаю будет ли это работать, но сложность явно O(nm).

Update: у вас сложность O(n^2 - nm)

[Bonny P.]

Не знаю будет ли это работать, но сложность явно O(nm).

Что там может не работать?

[jms]

Не знаю будет ли это работать, но сложность явно O(nm).

Что там может не работать?

Какая разница. У вас в решении большая сложность O(n^2). Нужно O(n). То есть если n = 1 000 000 то ваше решение будет делать (1 000 000 - m) 1 000 000 циклов, а мое только 1 000 000.

[jms]

и не замкнуть через него кольцо (n-m)-кратного циклического сдвига?

Если чесно, не совсем понял что это..

for (i=0, i<(n-m), i++) {
for (j=0, j<n, j++)
a[n-j] = a[n-j-1];
a[0] = a[n];
}

И кстати увеличение масива на 1 обычно считается созданием нового масива, что противоречит условию задачи. Конечно можно завести переменную под лишний элемент, но тогда решение получится явно не такое простое.

[deve]

Че то как то я не уловил логики. Работающуюу программу я написал. Вопроса "о почему о других так плохо думаете или о себе слишком хорошо ?" я если чесно не понял. Я думаю о людях плохо когда они того заслуживают.

Так с логикой похоже тоже не лады. Ну ладно, расшифруем: с чего вы решили, что вы тут "один Д`Артаньян", а "правильное решение (за O(n)) подавляющее большинство местных гуру не напишет на собеседовании" ?

[Bonny P.]

Не знаю будет ли это работать, но сложность явно O(nm).

Что там может не работать?

Какая разница.

Ответ, достойный интервьюера!

[Kalifornian]

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

Боитесь, что мы переведем ваши вопросы на хинди и продадим детям ганга?

[adda_]

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

Боитесь, что мы переведем ваши вопросы на хинди и продадим детям ганга?

Это типа задача на зеркальную перестановку массива относительно центра?
Этому учат на первом курсе института правда не на С, а на Паскале..

[isartw]

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

немного думать != "а давайте перепишем все нафик". Вообще говоря, не гонять же человека, которого берут на позицию j2ee девелопера скажем, по 3-му тому Кнута. Не помню если честно, когда мне последний раз приходилось алгоритм топографической сортировки применять. А вот прогуглить и выбрать какой-нибудь open-source framework быстро и грамотно нужно все чаще и чаще.
На счет поменять концепрцию - скорее не соглашусь, это задача архитектора скорее, а его аутсорсить нужно в последнюю очередь, imho. Иначе мало ли чего эти киборги мумбайские надизайнят. Проходили уже, nafique

[John Smith]

Кстати о гугле, вот ответ на задачу o циклическом сдвиге (Внимание! кто хочет сам решить - туда не смотреть): http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position

Нарветесь на грамотного индуса - спеца по задачкам, вот он вам напрограммирует.

[Mic]

А помоему там вполне четко описан циклический свдиг вправо на m.

Тогда вот:

Code: Select all

   
public class Task
{
   // Есть массив A1, A2, ..., Am, Am+1, Am+2, ..., An. 
   // Без использования дополнительного массива преобразовать 
   // в массив Am+1, Am+2, ..., An, A1, A2, ..., Am
   public void LoopShifting()
   {
      int shift = 7;                   
      string[] arr = {"0","1","2","3","4"};

      for (int i = 0; i < shift; i++)
      {
         ShiftRight(arr);
         PrintResult(arr, i);
      }
   }

   private void ShiftRight(string[] arr)
   {
      if (arr == null)
         throw new ApplicationException("The parameter 'string[] arr' is null");

      if (arr.Length < 2)
         return;

      string last = arr[arr.Length - 1];
      for (int i = arr.Length - 1; i > 0; i--)
      {
         arr[i] = arr[i - 1];
      }
      arr[0] = last;
   }

   private void PrintResult(string[] arr, int step)
   {
      if (arr == null)
         throw new ApplicationException("The parameter 'string[] arr' is null");

      Debug.Write(String.Format("Step {0}: ", step));

      foreach (var a in arr)
      {
         Debug.Write(a + " ");
      }
      Debug.WriteLine("");
   }
}

Результат на каждый шаг:

Code: Select all

Step 0: 4 0 1 2 3 
Step 1: 3 4 0 1 2 
Step 2: 2 3 4 0 1 
Step 3: 1 2 3 4 0 
Step 4: 0 1 2 3 4 
Step 5: 4 0 1 2 3 
Step 6: 3 4 0 1 2 

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

[Mic]

Я только одного не понимаю - как такого рода задачки характеризуют меня как программера?...

[Sasha3091]

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

[KOT MATPOCKUH]

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

Кроме того, вот эта цель:

Придется нам набрать несколько индусов в Индии взамен Московской команды, что бы спихнуть на них саппорт, багфиксы

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

[Komissar]

В Америке индустрия (ИТ) уже слишком сильно проедена индусами. Индусов не исправишь, остается только менять профессию. Переквалифицироваться в управдома (лендлорда), например.

[jms]

А помоему там вполне четко описан циклический свдиг вправо на m.

Тогда вот:

Code: Select all

   
public class Task
{
   // Есть массив A1, A2, ..., Am, Am+1, Am+2, ..., An. 
   // Без использования дополнительного массива преобразовать 
   // в массив Am+1, Am+2, ..., An, A1, A2, ..., Am
   public void LoopShifting()
   {
      int shift = 7;                   
      string[] arr = {"0","1","2","3","4"};

      for (int i = 0; i < shift; i++)
      {
         ShiftRight(arr);
         PrintResult(arr, i);
      }
   }

   private void ShiftRight(string[] arr)
   {
      if (arr == null)
         throw new ApplicationException("The parameter 'string[] arr' is null");

      if (arr.Length < 2)
         return;

      string last = arr[arr.Length - 1];
      for (int i = arr.Length - 1; i > 0; i--)
      {
         arr[i] = arr[i - 1];
      }
      arr[0] = last;
   }

   private void PrintResult(string[] arr, int step)
   {
      if (arr == null)
         throw new ApplicationException("The parameter 'string[] arr' is null");

      Debug.Write(String.Format("Step {0}: ", step));

      foreach (var a in arr)
      {
         Debug.Write(a + " ");
      }
      Debug.WriteLine("");
   }
}

Результат на каждый шаг:

Code: Select all

Step 0: 4 0 1 2 3 
Step 1: 3 4 0 1 2 
Step 2: 2 3 4 0 1 
Step 3: 1 2 3 4 0 
Step 4: 0 1 2 3 4 
Step 5: 4 0 1 2 3 
Step 6: 3 4 0 1 2 

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

Ok. Но это опять квадратичное время а не линейное..

[jms]

Че то как то я не уловил логики. Работающуюу программу я написал. Вопроса "о почему о других так плохо думаете или о себе слишком хорошо ?" я если чесно не понял. Я думаю о людях плохо когда они того заслуживают.

Так с логикой похоже тоже не лады. Ну ладно, расшифруем: с чего вы решили, что вы тут "один Д`Артаньян", а "правильное решение (за O(n)) подавляющее большинство местных гуру не напишет на собеседовании" ?

Это моя субьективная оценка обьективной реальности. Кстати я нигде не давал себе оценку как програмисту, это ваша фантазия.

[jms]

Не знаю будет ли это работать, но сложность явно O(nm).

Что там может не работать?

Какая разница.

Ответ, достойный интервьюера!

Вы вырвали фразу из контекста.

[jms]

Кстати о гугле, вот ответ на задачу o циклическом сдвиге (Внимание! кто хочет сам решить - туда не смотреть): http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position

Нарветесь на грамотного индуса - спеца по задачкам, вот он вам напрограммирует.

Кстати мой алгоритм быстрее, у них 2n итерации, а у меня n
Хотя записывается их намного элегантнее.

Update: хотя если подумать у меня операций в итерации намного больше, так что у них полюбому круче.

[GarikToo]

В Америке индустрия (ИТ) уже слишком сильно проедена индусами. Индусов не исправишь, остается только менять профессию. Переквалифицироваться в управдома (лендлорда), например.

Да ладно. Можно подумать белые програмеры все идеальны