Задачи для IT интервью

[olg2002]

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

Эта идея и неверна, как ни назови. Циклы независимы: что было в одном, никак не влияет на другие.

[Pantigalt]

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

Эта идея и неверна, как ни назови. Циклы независимы: что было в одном, никак не влияет на другие.

Я вижу что есть взаимосвязь.
Индекс последнего числа в цикле растет при каждой итерации на 2

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

N=16
8->A4->A2->A1
A9->A12->A6->A3
A10->A5
A11->A13->A14->A7

N=32
A16 -> A8 -> A4 -> A2 -> A1 (local min = A1)
A17 -> A24 -> A12 -> A6 -> A3 (local min = A3)
A18 -> A9 -> A20 -> A10 -> A5 (local min = A5)
A19 -> A25 -> A28 -> A14 -> A7 (local min = A7)
A20 -> A10 -> A5 -> A18 -> A9 (local min = A5)
A21 -> A26 -> A13 -> A22 -> A11 (local min = A11)
A22 -> A11 -> A21 -> A26 -> A13 (local min = A11)
A23 -> A27 -> A29 -> A30 -> A15 (local min = A15)

[helg]

Код, написанный на основе решения, предложенного Pantigalt, - ниже. Памяти O(1), количество записей и чтений - не два меньше, чем размер массива. На мой взгляд, его решение - это пятёрка по предложенной шкале.

Code: Select all

import java.util.Arrays;

public class XSort
{
  static class OddArray
  {
    private int numReads=0;
    private int numWrites=0;
    private String[] s;
    
    OddArray(int power2Len)
    {
      s = new String[1<<power2Len]; 
      for(int i=0; i<s.length/2; i++)
      {
        s[2*i] = "A" + i;  
        s[2*i+1] = "A" + (i+ s.length/2); 
      }
    }
    
    String get(int i)
    {
      numReads++;
      return s[i];
    }
    
    void put(int i, String ps)
    {
      numWrites++;
      s[i] = ps;
    }
    
    boolean isSorted()
    {
      for(int i=0;i<s.length;i++)
      {
        if(!("A" + i).equals(s[i]))
          return false;
      }
      return true;
    }

    void printStat()
    {
      boolean bSorted = isSorted();
      if(bSorted)
        System.out.println("SORTED" +  " numReads=" + numReads + " numWrites=" + numWrites);
      else
        System.out.println(Arrays.toString(s));
    }
    
  }
  
  static int rightPlace(int n, int len)
  {
    if( n%2 ==0 )
      return n/2;
    else
      return (len + n)/2;
  }
  
  static int getMinIndexInLoop(int nStart, int len)
  {
    int nMin = nStart;
    int nCur = nStart;
    do
    {
       nCur=rightPlace(nCur, len);
       if(nMin > nCur)
         nMin = nCur;
    }
    while(nCur!=nStart);
        
    return nMin;
    
  }

  static int pow2Len = 8;
  static int len = 1 << pow2Len;
  static OddArray a = new OddArray(pow2Len);

  static void makeOddArray(int ppow2Len)
  {
    pow2Len = ppow2Len;
    len = 1 << pow2Len;
    a = new OddArray(pow2Len);
    a.printStat();
  }
  
  static void sortOddArray()
  {
    int minDone = 0;
    for(int iStart=1; iStart<len/2; iStart+=2)
    {
      int nMinThisLoop = getMinIndexInLoop(iStart, len);
      if(nMinThisLoop <= minDone)
        continue;
      minDone = nMinThisLoop;
        
      int i=iStart;
      String s=a.get(iStart);
      int iRightPlace=-1;
      
      while(iStart!=iRightPlace)
      {
        iRightPlace = rightPlace(i, len);
        String sTemp=null;
        if(iStart!=iRightPlace)
          sTemp= a.get(iRightPlace);
        a.put(iRightPlace,s);
        if(iStart!=iRightPlace)
        {
          s = sTemp;
          i=iRightPlace;
        }
      }
    }
    a.printStat();
  }
  
  public static void main(String[] args)
  {
    makeOddArray(6);
    sortOddArray();
    makeOddArray(7);
    sortOddArray();
    makeOddArray(10);
    sortOddArray();
  }
}

[A0, A32, A1, A33, ...
SORTED numReads=62 numWrites=62
[A0, A64, A1, A65, ...
SORTED numReads=126 numWrites=126
[A0, A512, A1, A513,
SORTED numReads=1022 numWrites=1022

[olg2002]

Я вижу что есть взаимосвязь.

Я кажется понял. Мы берем индекс 1, проходим по всей цепочке, определяем минимальный индекс (1), называем его "максимальным локальным минимумом" и переходим дальше. Берем индекс 3, локальный минимум - 3, он же теперь "максимальный локальный минимум". То же для 5 и 7. Наконец берем 9 и определяем, что новый локальный минимум 5 меньше текущего "максимального локального минимума" 7 - цепочку отбрасываем, "максимальный локальный минимум" не обновляем. Действительно возникает впечатление, что обработка нового цикла зависит от предыдущих. Но оно ложное. На самом деле все проще: мы идем по нечетным индексам и определяем являются ли они минимальными в своих цепочках; если да - делаем подстановку, если нет - пропускаем, поскольку эта цепочка уже была обработана раньше. Ваш "максимальный локальный минимум" практически эквивалентен текущему нечетному индесу, с которого мы начинаем каждый новый цикл, хотя может и отставать от него. Согласен, что ваш алгоритм будет работать.

Это оптимальное по количеству чтений/записей в массив решение с временной сложностью O(N log N) - то, что я имел ввиду на 4 балла.
Убыстрить до O(N) - это на мой взгляд уже уровень PhD.

[olg2002]

Код, написанный на основе решения, предложенного Pantigalt, - ниже. Памяти O(1), количество записей и чтений - не два меньше, чем размер массива. На мой взгляд, его решение - это пятёрка по предложенной шкале.

Нет, это O(N log N): внешний цикл в sortOddArray - O(N), внутренний цикл в getMinIndexInLoop - O(log N). Для пятерки нужно O(N).

[blanko27]

Есть N=2^n чисел, A0 < A1 < A2 < A3 < …< AN-1, которые расположены в массиве через один, например для 2^4=16:

[A0 A8 A1 A9 A2 A10 A3 A11 A4 A12 A5 A13 A6 A14 A7 A15]

Нужно восстановить естественный порядок (отсортировать).

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

Code: Select all

char a[8][2][5] = {{"A0", "A8"},{"A1", "A9"}, {"A2", "A10"}, {"A3", "A11"}, {"A4", "A12"}, {"A5", "A13"}, {"A6", "A14"}, {"A7", "A15"}};
for (int j = 0; j < 2; ++j)
    for (int i = 0; i < 8; ++i)
      cout << a[i][j] << endl;

[olg2002]

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

На входе массив, в котором элементы расположены в указанном порядке: [A0 A8 A1 A9 A2 A10 A3 A11 A4 A12 A5 A13 A6 A14 A7 A15]
Нужно их упорядочить в том же массиве (in-place): [A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15], без дополнительного массива за минимальное количество обращений к массиву и за линейное время (общее количество операций).
Вроде, вся предыдущая дискуссия, включая примеры, показывает, что общее понимание проблемы достигнуто.

[Aleksey Kudinov]

Минимальное изменение к последнему приведённому коду делает его работоспособным для 32 и 64, дальше просто было лень проверять.

Code: Select all

	@Test
	public void testArray2() {
		//
		// String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"};
		// int[] a = {0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23, 8, 24, 9, 25, 10, 26, 11, 27, 12, 28, 13, 29, 14, 30, 15, 31};
		int[] a={0,	32,	1,	33,	2,	34,	3,	35,	4,	36,	5,	37,	6,	38,	7,	39,	8,	40,	9,	41,	10,	42,	11,	43,	12,	44,	13,	45,	14,	46,	15,	47,	16,	48,	17,	49,	18,	50,	19,	51,	20,	52,	21,	53,	22,	54,	23,	55,	24,	56,	25,	57,	26,	58,	27,	59,	28,	60,	29,	61,	30,	62,	31,	63};
		System.out.println(Arrays.toString(a));
		int halfSize = a.length / 2;

		for (int i1 = 1; i1 < halfSize; i1 ++) {
			int i = i1;
			int tempValue = -1;
			if (a[i] < a[i - 1] || a[i] > a[i + 1])
				do {
					int idx = i + (i % 2 == 0 ? -i / 2 : halfSize - i / 2 - 1);
					if (tempValue == -1) {
						tempValue = a[idx];
						a[idx] = a[i];
					} else {
						int s = tempValue;
						tempValue = a[idx];
						a[idx] = s;
					}
					i = idx;
				} while (i != i1);
		}
		System.out.println(Arrays.toString(a));
	}

[helg]

Code: Select all

 if (a[i] < a[i - 1] || a[i] > a[i + 1])

Это лишние обращения к массиву.

[Aleksey Kudinov]

Code: Select all

 if (a&#91;i&#93; < a&#91;i - 1&#93; || a&#91;i&#93; > a&#91;i + 1&#93;)

Это лишние обращения к массиву.

И? Ну в худшем случае o(n*2), чтение до половины массива, можно ещё наверное проверку на больше предыдущего элемента убрать. Для 5 будете платить PhD вэлыкы гроши.

[helg]

Code: Select all

  if (a[i] < a[i - 1] || a[i] > a[i + 1])

Это лишние обращения к массиву.

И? Ну в худшем случае o(n*2), чтение до половины массива, можно ещё наверное проверку на больше предыдущего элемента убрать.

Code: Select all

 if (a[i] != i)

достаточно.

[Aleksey Kudinov]

Code: Select all

  if (a&#91;i&#93; < a&#91;i - 1&#93; || a&#91;i&#93; > a&#91;i + 1&#93;)

Это лишние обращения к массиву.

И? Ну в худшем случае o(n*2), чтение до половины массива, можно ещё наверное проверку на больше предыдущего элемента убрать.

Code: Select all

 if (a[i] != i)

достаточно.

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

[Pantigalt]

Код на С++ текущего решения на 4 балла.

Code: Select all

// Cycles.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

struct Counter
{
	int read_counter;
	int write_counter;
	int iteration_counter;
} counter;
int next_(int n, int i)
{
	return i%2 == 0 ? i/2 : n/2 + i/2;
}

int read_value(vector<int>& a, int index)
{
	counter.read_counter++;
	return a[index];
}

void store_value(vector<int>& a, int index, int value)
{
	counter.write_counter++;
	a[index] = value;
}

void iteration_increment()
{
	counter.iteration_counter++;
}

void swap_cycle_(vector<int>& a, int i)
{
	int n = a.size();
	int oldj;
	int newj = i;	

	// check
	int min = i;
	do
	{
		iteration_increment();
		oldj = newj;
		newj = next_(n, oldj);
		min = min > newj ? newj : min;
	} while (newj != i);

	if (min <= i - 2)
		return;

	// swap
	newj = i;
	int newv = read_value(a, newj);
	int oldv = newv;
	do
	{
		iteration_increment();
		oldj = newj;
		newj = next_(n, oldj);

		cout << setw(2) << setfill(' ') << oldj;
		if (newj != i)
		{
			cout << " -> ";
			newv = read_value(a, newj);
			store_value(a, newj, oldv);
			oldv = newv;
		}
		else
		{
			store_value(a, newj, oldv);
		}

	} while (newj != i);
	cout << "\n";
}

void assign_values(vector<int>& a)
{
	int n = a.size();
	for (int i = 0; i < n; ++i)
	{
		a[i] = next_(n, i);
	}
}

void print_indexes(int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << setw(2) << setfill(' ') << i << " ";
	}
	cout << "\n";
}

void print_values(vector<int>& a)
{
	int n = a.size();
	for (int i = 0; i < n; ++i)
	{
		cout << setw(2) << setfill(' ') << a[i] << " ";
	}
	cout << "\n";
}

int _tmain(int argc, _TCHAR* argv[])
{
	int k;
	cout << "Enter k, N = 2^k\n";
	cin >> k;
	int n = 1 << k;
	vector<int> a(n);

	cout << "N = " << n << ", k = " << k << "\n";
	cout << "ASSIGNED\n";
	print_indexes(n);
	assign_values(a);
	print_values(a);

	cout << "CYCLES\n";
	// swap
	for (int i = 1; i < n/2; i+=2)
	{
		swap_cycle_(a, i);
	}

	// print ordered
	cout << "ORDERED\n";
	print_indexes(n);
	print_values(a);
	cout << "Counter: reads = " << counter.read_counter << " writes = " << counter.write_counter << " iterations = " << counter.iteration_counter << "\n";

	return 0;
}

[blanko27]

Нужно их упорядочить в том же массиве (in-place)

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

[Pantigalt]

Убыстрить до O(N) - это на мой взгляд уже уровень PhD.

Решение на 5 баллов существует? Хотелось бы знать заранее стоит ли его искать.

Я вот заметил что циклы можно построить циклическим сдвигом битового представления начального нечетного числа.
Например для N = 64
000101 - A5
001010 - A10
010100 - A20
101000 - A40
010001 - A17
100010 - A34

[Aleksey Kudinov]

Code: Select all

 if (a&#91;i&#93; < a&#91;i - 1&#93; || a&#91;i&#93; > a&#91;i + 1&#93;)

Это лишние обращения к массиву.

И? Ну в худшем случае o(n*2), чтение до половины массива, можно ещё наверное проверку на больше предыдущего элемента убрать. Для 5 будете платить PhD вэлыкы гроши.

Кстати нет, тупо просчитав операции - код ниже, получается, что read ratio ~1.6, при записях ~1 (выкидывая крайние числа, которые уже на своих местах). Что имеет смысл - перезаписываем весь массив при этом его читая - следуя по цепочкам + читаем половину массива в цикле + опять же читаем i+1 элемент.

Финальная версия немного почищена

Отвечая на вопрос ТС - давать на интервью можно чисто с целью посмотреть куда ветер подует, сомневаюсь, что рядовой боец начнёт формулу перестановки из умма доставать. Для домашнего задания, опять же, вряд ли кто будет тратить достачное время, чтобы вычистить всё это до блеска. От солидной 3-ки дома можно попробовать прощупать путь дальше у whiteboard, но это уже насколько вам хочется на это тратить своё рабочее сремя. Опять же, для меня и моих задач достаточно, что человек напишет не-нудлевый код с использованием второго массива.

Code: Select all

	@Test
	public void testArray3() {
		// setting up
		final int SIZE = 512;
		final int HALF_SIZE = SIZE / 2;
		int[] a = initArray(SIZE);
		System.out.println(Arrays.toString(a));
		// read first half of the array
		for (int i1 = 1, i = 1; i1 < HALF_SIZE; i1++, i = i1) {
			int tempValue = a[i];
			if (tempValue > a[i + 1]) { // if next element is less than current, follow the chain 
				do {
					int idx = i + (i % 2 == 0 ? -i / 2 : HALF_SIZE - i / 2 - 1); // calc next position
					// swap current / new elements
					int s = tempValue;
					tempValue = a[idx];
					a[idx] = s;
					i = idx;
				} while (i != i1);
			}
		}
		System.out.println(Arrays.toString(a));
		System.out.println("Array check " + (checkArray(a) ? " SUCCESSFUL, sorted " : " FAILED, not sorted"));
	}

[olg2002]

Убыстрить до O(N) - это на мой взгляд уже уровень PhD.

Решение на 5 баллов существует? Хотелось бы знать заранее стоит ли его искать.

Да. Стоит, наверное, лучше определить ожидания. Говоря про уровень PhD, я имел ввиду не столько крутость в решении алгоритмических проблем, сколько способность распознать уже решенную задачу и указать это решение. Хотя, кто его знает, на что способна приветовская публика.

Я вот заметил что циклы можно построить циклическим сдвигом битового представления начального нечетного числа.
Например для N = 64
000101 - A5
001010 - A10
010100 - A20
101000 - A40
010001 - A17
100010 - A34

Без этого наблюдения дальнейший прогресс маловероятен, по моему мнению.

[olg2002]

Финальная версия немного почищена

Должен признать, такое решение для меня оказалось неожиданным. В оригинальном контексте нет никакого отношения порядка - просто нужно осуществить перестановку. Я его добавил, чтобы максимально упростить постановку задачи и дать возможность ряда простых ответов вокруг сортировки. Одним соображением было посмотреть, способен ли кандидат оторваться от привычного описания реальности (сортировка) и увидеть суть предлагаемой задачи (перестановка). Теперь это соображение потеряло вес. Вы реализовали принцип: любая дополнительная информация может быть использована для оптимизации решения. Я как-то этим пренебрег. Ваше решение - O(1) по памяти и O(N) по времени. По формальным признакам - это 3 балла, поскольку оптимальность по операциям доступа к массиву недостижима. За оригинальность, на реальном собеседовании я бы, конечно, добавил балл.

Отвечая на вопрос ТС - давать на интервью можно чисто с целью посмотреть куда ветер подует, сомневаюсь, что рядовой боец начнёт формулу перестановки из умма доставать. Для домашнего задания, опять же, вряд ли кто будет тратить достачное время, чтобы вычистить всё это до блеска. От солидной 3-ки дома можно попробовать прощупать путь дальше у whiteboard, но это уже насколько вам хочется на это тратить своё рабочее сремя. Опять же, для меня и моих задач достаточно, что человек напишет не-нудлевый код с использованием второго массива.

Спасибо за соображения. Думаю, вы недооцениваете выпускников американских университетов, не обязательно даже элиту. Я теперь уверен, что сформулированное 4-балльное решение вполне можно ожидать даже на живом интервью.

[Kirpidonych]

нашел что то мож кому поможет

phpBB [video]

[XpoH]

детям в садике если только

[Kirpidonych]

детям в садике если только

ой - ну что нашел
больше не буду конечно

[XpoH]

без обид, ок? ))

[Kirpidonych]

без обид, ок? ))

нет - все - вы теперь записаны в список на разбор полетов в случае падения цивилизации и войны всех со всеми

[ctin]

Про образовательные ролики: лучшее, что я видел это видеокурсы от центра Специалист при МГТУ им. Баумана.

[Aleksey Kudinov]

Вам тут высокие материи всё, а я сегодня из МБА претендующего на роль бизнес аналитика не смог вытянуть что есть internal rate of return. Кто знает, тот поймёт. А present value of $30 2 years from now at a 10% discount rate у него получилось $24... Рукалицо.