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

[Сабина]

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

[Boriskin]

Я с завтрашенго дня начну слать резюме по инстанциям

"Що, опять?!" (с) Жил был пес.

[mynameiszb]

Я с завтрашенго дня начну слать резюме по инстанциям

"Що, опять?!" (с) Жил был пес.

У контрактора только один плюс: каждый месяц знакомишься с новым коллективом и новыми людьми. Движуха...

(смайл добавлять под настроение)

[valchkou]

кто бы мог подумать что ничего нового ?

у каждого свои критерии новизны, что нового для вас лично?

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

[Сабина]

http://searchsoa.techtarget.com/feature ... ct-in-2015

[Сабина]

Везде все хотят LRU cache, но сколько людей столько и вариантов.
http://www.careercup.com/question?id=17230678

Если у кого есть любимая имплементация на Джаве не поделитесь?

У нас одни из варинатов был держать две структуры, HashMap для самого кеша и SortedMap чтобы потом оттуда быстро вытащить least recently used. Но что то больше никто так не делает

[valchkou]

Если у кого есть любимая имплементация на Джаве не поделитесь?

https://code.google.com/p/guava-librari ... d#Eviction
src: https://code.google.com/p/guava-librari ... on%2Fcache

[turic]

У нас одни из варинатов был держать две структуры, HashMap для самого кеша и SortedMap чтобы потом оттуда быстро вытащить least recently used. Но что то больше никто так не делает

Элементарный алгоритм. Как ты пишиешь: HashMap и List (queue) для ключей. Ключи с списке чем выше, тем новее - авто сортировка. Если ключ уже есть, то он перемещается в начало, если нет, то добавляем в начало.

Вот тут четко описно как сделать:
http://www.geeksforgeeks.org/implement-lru-cache/

[Сабина]

У нас одни из варинатов был держать две структуры, HashMap для самого кеша и SortedMap чтобы потом оттуда быстро вытащить least recently used. Но что то больше никто так не делает

Элементарный алгоритм. Как ты пишиешь: HashMap и List (queue) для ключей. Ключи с списке чем выше, тем новее - авто сортировка. Если ключ уже есть, то он перемещается в начало, если нет, то добавляем в начало.

Вот тут четко описно как сделать:
http://www.geeksforgeeks.org/implement-lru-cache/

Да, получается это самая быстрая имплементация и на Джаве

[anarchist]

Делюсь как технично завалить практически любого индуса на интервью: спросите "how do you traverse a binary tree?".
Эти клоуны с дипломом computer science понятия не имеют что такое бинарное дерево!

[turic]

Делюсь как технично завалить практически любого индуса на интервью: спросите "how do you traverse a binary tree?".
Эти клоуны с дипломом computer science понятия не имеют что такое бинарное дерево!

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

С другой стороны, какой вывод из того, что кандидат не знает деревья? Ну только, то что он не знает деревья.

[valchkou]

Делюсь как технично завалить практически любого индуса на интервью: спросите "how do you traverse a binary tree?".
Эти клоуны с дипломом computer science понятия не имеют что такое бинарное дерево!

это любимый вопрос нашего штатного индуса.

[assazello]

Имеется следующая игра - задумывается некоторое случайное число из промежутка 1..2000. Игрок пытается его угадать, называя числа из того же промежутка. На каждую попытку он получает результат сравнения названного числа с искомым - "больше", "меньше" или "равно". Игра идет до ответа "равно". Если этот ответ был дан на 1й,3й,5й, нечетной попытке - игрок выиграл, если же на 2й,4й,6й, четной - игрок проиграл. Исключенные предыдущими ответами числа называть нельзя. Т.е., если игрок называет 10 и получает ответ "больше", то исключаются 0,1,2,3,...,10. Найти алгоритм действий игрока, дающий ему максимальную вероятность выигрыша.

[turic]

Имеется следующая игра - .

Я бы такое решение двинул: методом половинного деление сужаем диапазон до 4-х. К примеру, задумал 3, то подходим к 2-6. Теперь продолжая половинное деление ответ будет точно в 2 хода до ответа. Если текущий ход игрока четный, то "пропустить" ход путем вычитания 1 большей границы или прибавления 1 к меньшей. Если текущий ход был нечетный то продолжить половинный поиск. Теперь игрок находи ответ нечетном ходу.

[assazello]

Имеется следующая игра - .

Я бы такое решение двинул: методом половинного деление сужаем диапазон до 4-х. К примеру, задумал 3, то подходим к 2-6. Теперь продолжая половинное деление ответ будет точно в 2 хода до ответа. Если текущий ход игрока четный, то "пропустить" ход путем вычитания 1 большей границы или прибавления 1 к меньшей. Если текущий ход был нечетный то продолжить половинный поиск. Теперь игрок находи ответ нечетном ходу.

Не вижу как оно повышает шансы. Так и остается 50/50.

[Boriskin]

Надо сделать так, чтобы когда при делении пополам остается только одно число для проверки - этв проверка была нечетной по счету. Другими словами, когда загадано число х, то нужно прийти к диапазону (х-1, х+1) на четной итерации. Таким образом в среднем получится увеличить шансы в том случае, когда число угадывается на последней итерации. Как это сделать - надо еще думать, а тут тяпница и лень. Имхо, это единственный способ как то повысить общие шансы, все остальные расклады - 50 на 50.
Попытки чтото менять в плане "срезать снизу по одной, а сверху - по половине" ничего не дают т.к. распределение равномерное и вероятность налететь не на то одинакова.

[assazello]

Мне эта задача интересна тем, что я довольно быстро нашел ответ, дающий (судя по эксперименту) больше 90% шансов, ближе к 95%. Но является ли он лучшим и как вообще теоретически обосновать и доказать - не имею понятия.

[Сабина]

Какую то мне задачу муторную задали сегодня. Скорее всего я чего то недопоняла ибо было не на бумаге и не в колабеэдите каком нибудь а чисто на словах. Задача типа про Джаву, хотя я не уверена уже.
Вот есть два листа. Первый - суперсет второго, в нем перемешаны законченные и незаконченные таски но проперти показывающее какой эелемент закончен, какой нет - не видно. Во втором списке таски делятся на законченные и незаконченные но их так просто не отфильтруешь, доступа нет к этой проперти. Как получить список todo tasks основного листа?

Сначала я подумала что вообще речь идет про банальное removeAll, менеджер все таки. Потом когда оказалось что проперти не видно - получается вообще никак не решить. Короче я что-то поспекулировала про хешкод и сдалась. Он мне говорит что hint в слове bitmasking

Если кто понимает о чем речь - не дайте пропасть, а то мне с ними еще одно проходить

[Сабина]

Мне эта задача интересна тем, что я довольно быстро нашел ответ, дающий (судя по эксперименту) больше 90% шансов, ближе к 95%. Но является ли он лучшим и как вообще теоретически обосновать и доказать - не имею понятия.

заинтриговали

[Ion Tichy]

Имеется следующая игра...

Вероятность угадать число на шаге i есть 1/Ni где Ni - длина промежутка на i-м шаге. Длиной промежутка для следующеи итерации мы можем управлять (есс-но управлять с вероятностями) - просто делите отрезок пополам только на _четных_ итерациях.

Пример - пусть на 7-й итерации остаюся 100-1099. Следующая итерация - 8-я и я не хочу угадать. Я называю 100:
- с вероятностью 1/1000 я угадал - Ура!
- с вероятностью 999/1000 я перехожу не след итерацию где вер-ть угадать минимальная из возможных.
8-я итерация - делю пополам:
- с вер-тью 1/999 угадал
- с вертью 998/999 отбрасываю для след.нечетной итерации половину кандидатов
Как-то так...

Не бейте сильно, пишу из головы чистый экспромт.

[assazello]

Имеется следующая игра...

Вероятность угадать число на шаге i есть 1/Ni где Ni - длина промежутка на i-м шаге. Длиной промежутка для следующеи итерации мы можем управлять (есс-но управлять с вероятностями) - просто делите отрезок пополам только на _четных_ итерациях.

Пример - пусть на 7-й итерации остаюся 100-1099. Следующая итерация - 8-я и я не хочу угадать. Я называю 100:
- с вероятностью 1/1000 я угадал - Ура!
- с вероятностью 999/1000 я перехожу не след итерацию где вер-ть угадать минимальная из возможных.
8-я итерация - делю пополам:
- с вер-тью 1/999 угадал
- с вертью 998/999 отбрасываю для след.нечетной итерации половину кандидатов
Как-то так...

Не бейте сильно, пишу из головы чистый экспромт.

Great minds think alike! Это была моя первая идея.
Но вы попробуйте экспериментально проверить этот алгоритм. Удивитесь.

[assazello]

Вот даже кусок кода, там нужно только подставить собственно выбор.

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main() {
	int nAttempts = 1000;
	int nWin = 0, nLose = 0;
	int nMax = 2000; // 1..nMax
	
	srand(time(NULL));
	
	for(int iAttempt = 1; iAttempt <= nAttempts; ++iAttempt)
	{
		int i = 0;
		
		int prize = rand() % nMax + 1;
		int left = 1, right = nMax;
		int answer = 0;
		
		//cout << "prize: " << prize << endl;
		
		for(i = 1; i <= nMax; ++i)
		{
			answer = ... ; // ПОДСТАВИТЬ НУЖНОЕ ТУТ
			
			//cout << "[" << left << "," << right << "] answer = " << answer << endl;
			
			if(answer == prize)
				break;
			else if(answer < prize)
				left = answer + 1;
			else
				right = answer - 1;
		}
		
		if(answer == prize)
		{
			nWin += i % 2;
			nLose += 1 - i % 2;
		}
	}
	
	cout << "win: " << nWin << " lose: " << nLose << endl;
	
	return 0;
}

Это С++. Можно запустить онлайн на ideone.com.

Ion Tichy, ыаш алгорим будет
answer = (i % 2 == 0 ? left : (left + right) / 2) ;

[helg]

Имеется следующая игра - задумывается некоторое случайное число из промежутка 1..2000. ...

Просчитал полным рекурсивным перебором. Получается, что вероятность выигрыша при увеличении промежутка при наилучшей стратегии имеет асимптоту на 2/3. Для интервала 1..2000 наилучший алгоритм выигрывает для 1333 чисел из 2000.

Табличка, фрагмент которой приведён ниже, даёт для каждого промежутка алгоритм угадывания и количество чисел из промежутка, которые выигрывают. Max num - размер промежутка угадывания, LoosingTurn(#, ctWin) - оптимальный ход и количество задуманных чисел, которые выигрываются, когда угадывание на текущем ходу проигрывает, WinningTurn(#, ctWin) - то же самое, но когда угадывание на текущем ходу выигрывает.

Если, к примеру, задумано число в промежутке длиной 4 (от 1 до 4), то из четвёртой строки таблички вероятность выигрыша 3/4. WinningTurn#(4) = 0, значит первым надо назвать число с номером 0 из промежутка(1,2,3,4), то есть единицу . Если не угадал, задача сводится к LoosingTurn#(3) . Из таблички следует, что LoosingTurn#(3) = 1, и надо назвать число #1 в оставшемся промежутке(1,2,3), если считать от нуля, - то есть двойку. Если задумана двойка, мы проиграли, в остальных трёх случаях выиграли, что и указано в таблице: WinningTrn.ctWin(4) = 3.

Code: Select all

Max  LoosingTrn WinningTrn
num   #,ctWin #,ctWin
   1  0    0  0    1
   2  0    1  0    1
   3  1    2  0    2
   4  0    2  0    3
   5  0    3  0    3
   6  1    4  0    4
   7  0    4  0    5
   8  0    5  0    5
   9  1    6  0    6
  10  0    6  0    7
  11  0    7  0    7
  12  1    8  0    8
  13  0    8  0    9
  14  0    9  0    9
  15  1   10  0   10
  16  0   10  0   11
  17  0   11  0   11
  18  1   12  0   12
[..]
1991  0 1327  0 1327
1992  1 1328  0 1328
1993  0 1328  0 1329
1994  0 1329  0 1329
1995  1 1330  0 1330
1996  0 1330  0 1331
1997  0 1331  0 1331
1998  1 1332  0 1332
1999  0 1332  0 1333
2000  0 1333  0 1333

Глядя на таблицу, можно сформулировать оптимальный алгоритм словами: называть самое первое число из допустимого интервала на нечётном ходу всегда, а на чётном только если размер интервала не кратен трём. Если же на нечётном ходу размер допустимого интервала кратен трём, называть второе число из интервала. Полученный алгоритм - не единственный, дающий максимальный шанс выиграть, более того, он самый длинный по числу попыток угадывания. Зато он просто формулируется и асимптотические 2/3 его вероятности выигрыша очевидны.

Программа, которая обсчитала табличку, - вот:

Code: Select all

#include <stdio.h>

#define MAXNUM 2000
struct Strategy
{
	int bestTurn;
	int winCount;
};

Strategy strategy[MAXNUM+1][2]; // 2nd index = 1 => winningTrn

Strategy calcBestStrategy(int intervalLen, bool isWinningTurn)
{
	if (intervalLen == 1)
	{
		static Strategy strategyWt1 = { 0, 1 };
		static Strategy strategyLt1 = { 0, 0 };
		return isWinningTurn ? strategyWt1 : strategyLt1;
	}
	else
	{
		Strategy s = { -1, -1 };
		for (int i = 0; i < (intervalLen + 1) / 2; i++)
		{
			int iLeft = i ;
			int iRight = intervalLen - i - 1;
			int winCount = isWinningTurn ? 1 :0;
			if (iLeft > 0)
				winCount += strategy[iLeft][!isWinningTurn].winCount;
			if (iRight > 0)
				winCount += strategy[iRight][!isWinningTurn].winCount;
			if (winCount > s.winCount)
			{
				s.winCount = winCount;
				s.bestTurn = i;
			}
		}
		return s;
	}
}

int main(int argc, char* argv[])
{
	printf("Max  LoosingTrn WinningTrn\n");
	printf("num   #,ctWin #,ctWin\n");

	for (int i = 1; i <= MAXNUM; i++)
	{
		strategy[i][0] = calcBestStrategy(i, false);
		strategy[i][1] = calcBestStrategy(i, true);
		printf("%4d %2d %4d %2d %4d\n", i, 
			strategy[i][0].bestTurn, strategy[i][0].winCount, 
			strategy[i][1].bestTurn, strategy[i][1].winCount);
 	}
	return 0;
}

[assazello]

helg,
Попробовал ваш алгоритм на своем коде:
answer = (i % 2 == 0 ? ((right - left) % 3 == 0 ? left : left + 1 ) : left);

Все верно, действительно ваше решение дает 66%!

А вот мое решение: на каждом нечетной попытке называть самое первое число из допустимого интервала, а на каждой четной - случайное число из допустимого интервала.
answer = (i % 2 == 0 ? rand() % right + left : left);

Вы будете смеяться, но оно дает ~95%. Почему - я не знаю, то есть логически понимаю (уменьшаем шансы угадать на четном ходу), доказывать пытался, запутался в вероятностях и бросил.

[helg]

answer = (i % 2 == 0 ? rand() % right + left : left);

Возможно, Вы хотели сказать:

answer = (i % 2 == 0 ? rand() % (right-left+1) + left : left);

По правилам нельзя же называть числа за пределами интервала между left и right.

Если не называть на чётном ходу числа за пределами диапазона, строго доказано, что максимальный шанс выигрыша - 1333/2000.

Попробовал ваш алгоритм на своем коде:
answer = (i % 2 == 0 ? ((right - left) % 3 == 0 ? left : left + 1 ) : left);

Небольшое уточнение. Размер диапазона между left и right включительно: (right - left + 1), а не (right - left). Несмотря на то, что оба варианта: с единчкой и без, асимптотически, на больших интервалах дают вероятность выигрыша 2/3 с единичкой выигрыш выше, он теоретически максимальный. Например, на интервале 4 - он даёт шанс 0.75 против 0.5.