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

[Boriskin]

Одно интервью за последние 15 лет работы.
Кто меньше?

Ага и два поста на привете Да Вы, батенька, немногословны

Так работать же надо, а жизнь так коротка.

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

[Sergunka]

Одно интервью за последние 15 лет работы.
Кто меньше?

Ага и два поста на привете Да Вы, батенька, немногословны

Так работать же надо, а жизнь так коротка.

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Были такие сроки с "без права переписки" (с)

[tau]

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Дети появятся - сможешь.

[Boriskin]

Были такие сроки с "без права переписки" (с)

Дык то не по своей воле.

[Boriskin]

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Дети появятся - сможешь.

Может проще работу сменить?

[tau]

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Дети появятся - сможешь.

Может проще работу сменить?

Перестанет устраивать - тут же сменю.

[Sergunka]

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Дети появятся - сможешь.

Может проще работу сменить?

Перестанет устраивать - тут же сменю.

Не говори гоп...

[Boriskin]

Перестанет устраивать - тут же сменю.

Ну тогда "бог в помощь..." (с)

[Easbayguy]

Одно интервью за последние 15 лет работы.
Кто меньше?

Ага и два поста на привете Да Вы, батенька, немногословны

Так работать же надо, а жизнь так коротка.

15 лет на работе, где все время надо работать - это сильно! Я бы не смог.

Капитализм! С работы надо уходить с чуством невыполненного долга!

[olg2002]

Решил не открывать новую тему, а воспользоваться существующей - благо название подходящее и место, вроде, людное.
Придумалась алгоритмическая задача, которую можно было бы использовать при собеседовании (не обязательно очном и за час) в диапазоне от студента до PhD. Хочется понять реальные пределы применимости.

Есть 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]

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

Вызов библиотечной функции сортировки - 1 балл + мороженное.
Дополнительная память O(n), время O(n) - 2 балла.
Дополнительная память O(1) - 3 балла.
Дополнительная память O(1), оптимальное количество чтений/записей в массив - 4 балла.
Дополнительная память O(1), оптимальное количество чтений/записей в массив, время O(n) - 5 баллов.

5, наверное, запредельно. 3 - вполне реально. Вопрос, подъемно ли 4?

[sereja123]

Такое решение на сколько тянет?

Code: Select all

public static void main(String[] args) {
        String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"};
        System.out.println(Arrays.toString(a));
        for(int i = 1; i<a.length/2; i++) {
            for(int j=i; j<(a.length-i); j+=2)
                exch(a, j,j+1 );
        }
        System.out.println(Arrays.toString(a));
    }

Я использовал бы Shellsort, объяснил что он идеален для частично сортированного массива. Написал бы Shelllsort и получил мороженное. Интересно как повлияет на производительность Shellsort если подобрать increment sequence отличную от (3*k-1)/2.

[Aleksey Kudinov]

Code: Select all

	String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"}, b = new String[a.length];
	for (int i = 0, idx1 = 0, idx2 = a.length / 2; i < a.length; i++)
		b[i % 2 == 0 ? idx1++ : idx2++] = a[i];
	a = b;

но задачка так себе, ни уму ни сердцу.

[olg2002]

Такое решение на сколько тянет?

Время O(n^2) - 1 балл. Я бы отредактировал свой пост, заменив N на n: n = 2^k, чтобы все оценки сложности были от длины массива.

[olg2002]

Code: Select all

	String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"}, b = new String[a.length];
	for (int i = 0, idx1 = 0, idx2 = a.length / 2; i < a.length; i++)
		b[i % 2 == 0 ? idx1++ : idx2++] = a[i];
	a = b;

но задачка так себе, ни уму ни сердцу.

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

[Aleksey Kudinov]

Code: Select all

	String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"}, b = new String[a.length];
	for (int i = 0, idx1 = 0, idx2 = a.length / 2; i < a.length; i++)
		b[i % 2 == 0 ? idx1++ : idx2++] = a[i];
	a = b;

но задачка так себе, ни уму ни сердцу.

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

Ишь, квалификации ещё понапридумывали... [EDIT] nevermind, похоже на читинг

Code: Select all

		int[] a = {0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15};
		int idx = 0;
		while (idx < a.length / 2) {
			while (a[idx] != idx) 
				exchange(a, idx, a[idx]);
			idx++;
		}

[John Smith]

Code: Select all

	String[] a = {"A0", "A8", "A1", "A9", "A2", "A10", "A3", "A11", "A4", "A12", "A5", "A13", "A6", "A14", "A7", "A15"}, b = new String[a.length];
	for (int i = 0, idx1 = 0, idx2 = a.length / 2; i < a.length; i++)
		b[i % 2 == 0 ? idx1++ : idx2++] = a[i];
	a = b;

но задачка так себе, ни уму ни сердцу.

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

Ишь, квалификации ещё понапридумывали... [EDIT] nevermind, похоже на читинг

Code: Select all

		int[] a = {0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15};
		int idx = 0;
		while (idx < a.length / 2) {
			while (a[idx] != idx) 
				exchange(a, idx, a[idx]);
			idx++;
		}

это неверное решение, рассмотрите пример где a[0] = 1

[Aleksey Kudinov]

Набросились, критиковать-то все мастера... Ну ужас ужасный, конечно, получился, ну что ж теперь тут поделать.

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"};
		System.out.println(Arrays.toString(a));
		int halfSize = a.length / 2;

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

[olg2002]

Мысль движется в правильном направлении, но для n=32 алгоритм не сработает.

[Aleksey Kudinov]

Мысль движется в правильном направлении, но для n=32 алгоритм не сработает.

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

[Pantigalt]

Решил не открывать новую тему, а воспользоваться существующей - благо название подходящее и место, вроде, людное.
Придумалась алгоритмическая задача, которую можно было бы использовать при собеседовании (не обязательно очном и за час) в диапазоне от студента до PhD. Хочется понять реальные пределы применимости.

Есть 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]

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

Вызов библиотечной функции сортировки - 1 балл + мороженное.
Дополнительная память O(n), время O(n) - 2 балла.
Дополнительная память O(1) - 3 балла.
Дополнительная память O(1), оптимальное количество чтений/записей в массив - 4 балла.
Дополнительная память O(1), оптимальное количество чтений/записей в массив, время O(n) - 5 баллов.

5, наверное, запредельно. 3 - вполне реально. Вопрос, подъемно ли 4?

Мое подправленное решение следующее
1. Надо вычислить формулу для нахождения индекса j в Aj имея на входе только номер позиции (начиная с нуля).
Например в позиции 5 лежит число A10, индекс j=10
Общая формула следующая
j = (i%2 == 0) ? i/2 : (N+i)/2
Для четных j = i/2, для нечетных j = N/2 + i/2, где i - номер позиции

2. Для все нечетных позиций от 1 до N/2-1 вычислить последовательность переходов-обменов значениями.
По номеру позиции мы всегда можем узнать индекс j следующего перехода.
На примере это выглядит так для N = 16
A8->A4->A2->A1
A9->A12->A6->A3
A10->A5
A11->A13->A14->A7
Количество итераций равно N/4, максимально число переходов обменов равно 4.
То есть количество обменов не больше чем O(N).

[olg2002]

1. Формула вычисления следующего индекса выглядит коряво, но за ней скрывается очень простая и наглядная идея.
2. Случай N=16 оказывается слишком простым и приводит к неверным обобщениям. Для N=32 один такой цикл это
 A5 -> A18 -> A9 -> A20 -> A10
т.е. если мы просто применим такой цикл ко всем нечетным индексам меньше N/2, то поскольку в этом конкретном цикле
встречаются 5 и 9, он будет применен два раза (это то же самое, что происходит в последнем алгоритме Aleksey Kudinov).
Если бы мы могли избежать повторного применения одного и того же цикла, мы бы получили решение на 4 балла.

[Pantigalt]

1. Формула вычисления следующего индекса выглядит коряво, но за ней скрывается очень простая и наглядная идея.
2. Случай N=16 оказывается слишком простым и приводит к неверным обобщениям. Для N=32 один такой цикл это
 A5 -> A18 -> A9 -> A20 -> A10
т.е. если мы просто применим такой цикл ко всем нечетным индексам меньше N/2, то поскольку в этом конкретном цикле
встречаются 5 и 9, он будет применен два раза (это то же самое, что происходит в последнем алгоритме Aleksey Kudinov).
Если бы мы могли избежать повторного применения одного и того же цикла, мы бы получили решение на 4 балла.

Применим цикл ко всем нечетным индексам меньше N/2, где N=32, рассматриваем цепочки длины k, такое что N = 2^k
a) Запомним наименьшее значение индекса для всех уже рассмотренных цепочек global min
b) Находим наименьшее значение индекса для текущей цепочки local min
c) Если global min >= local min то отбрасываем цепочку
d) Производим обмены значениями

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)

В цепочках нет дубликатов следственно число обменов меньше N.

Отступление 1:
Из этого кстати видно что количество дубликатов будет расти по логарифмическому закону
Число дубликатов = N * (k/4 - 1) = N * (log(N)/4 - 1)
Число дублирующих цепочек = N * (k/4 - 1)/k = N * (log(N)/4 - 1)/log(N)

Отступление 2:
По сути это задача нахождения Эйлерова цикла в графе. Для поиска Эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Ребра графа - это переходы, например A5 -> A18.
Так как есть ограничение по памяти то мы не можем кэшировать уже рассмотренные ребра. Но можем узнать есть ли значение в кэше или нет. Ребро не может находится больше чем в одном простом цикле графа. Сравнивая вершины с минимальными индексами ребер мы можем отсечь те циклы которые являются дубликатами существующих.
Сложность алгоритма линейно зависит от числа ребер (числа переходов) и равна O(N).

[OtherSide]

Из свежего: Есть мешок с шарами, пронумерованными от 1 до 100. Один из шаров вынули и дали мешок Вам. Ваша задача - за один проход узнать какой именно шар был вынут.

5050 - Сумму посчитать

[olg2002]

Применим цикл ко всем нечетным индексам меньше N/2, где N=32, рассматриваем цепочки длины k, такое что N = 2^k
a) Запомним наименьшее значение индекса для всех уже рассмотренных цепочек global min
b) Находим наименьшее значение индекса для текущей цепочки local min
c) Если global min >= local min то отбрасываем цепочку
d) Производим обмены значениями

Почему цепочки получаются длины k? (Это, кстати, неверно в общем случае: при N=16 у нас уже была цепочка длины 2.)
Идея с глобальным минимумом неверна. Собственно, b) - уже практически решение, остается только правильно сформулировать, что делать с этим локальным минимумом.

Отступление 2:
По сути это задача нахождения Эйлерова цикла в графе.

Я не вижу связи. Наш "граф" состоит из большого количества несвязных циклов длины k (делящей k на самом деле). Искать их не надо - все они заданы формулой пересчета индекса.

[Pantigalt]

Применим цикл ко всем нечетным индексам меньше N/2, где N=32, рассматриваем цепочки длины k, такое что N = 2^k
a) Запомним наименьшее значение индекса для всех уже рассмотренных цепочек global min
b) Находим наименьшее значение индекса для текущей цепочки local min
c) Если global min >= local min то отбрасываем цепочку
d) Производим обмены значениями

Почему цепочки получаются длины k? (Это, кстати, неверно в общем случае: при N=16 у нас уже была цепочка длины 2.)
Идея с глобальным минимумом неверна. Собственно, b) - уже практически решение, остается только правильно сформулировать, что делать с этим локальным минимумом.

Отступление 2:
По сути это задача нахождения Эйлерова цикла в графе.

Я не вижу связи. Наш "граф" состоит из большого количества несвязных циклов длины k (делящей k на самом деле). Искать их не надо - все они заданы формулой пересчета индекса.

Почему цепочки получаются длины k? (Это, кстати, неверно в общем случае: при N=16 у нас уже была цепочка длины 2.)

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

Идея с глобальным минимумом неверна.

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

Я не вижу связи. Наш "граф" состоит из большого количества несвязных циклов длины k (делящей k на самом деле). Искать их не надо - все они заданы формулой пересчета индекса.

Мы их не ищем. Мы отсекаем те простые циклы графа которые будут дублирующими существующих.