Дадени са ни указатели към първите елементи на два ациклични едносвързани списъка. Можете ли с константна памет и линейно време да определите дали в някой елемент единият списък не се "слива" във втория (тоест двата да завършват в един и същ елемент). Ако да, можете ли да намерите кой е първият им общ елемент? Опишете алгоритъма си.

Имайки на разположение генератор на случайни булеви величини (true, false), напишете функция, която генерира случайни числа в интервала [0, 1].
Докажете, че генерираните от нея числа са равномерно разпределени.

По случаен начин е избрано цяло число num между 1 и 1000. Имате функция guess(x), която връща 0, ако num == x, -1 ако x < num, и +1 ако x > num. Изградете алгоритъм, който, познава числото num с минимален брой викания на функцията guess(x). Определете броя извиквания при най-лошия избор на num за вашия алгоритъм.

int left = 1, right = 1000;
while (left <= right) {
	int mid = (left + right) / 2;
	int res = guess(mid); // -1 if less, 0 if correct, 1 if greater
	if (res == 0) return mid;
	if (res < 0) right = mid - 1;
	else left = mid + 1;
}

Даден е бял правоъгълник, във вътрешността на който е нарисуван друг, черен правоъгълник, чиито страни може да не са успоредни на тези на белия. Може ли с една единствена права линия да се раздели остатъка от белия правоъгълник на части с равна площ?

Даден е масив с N числа. Изградете алгоритъм, който намира негов подинтервал с максимална сума. Подинтервал е поредица от последователни негови елементи.

Даден е указател към първия елемент на (потенциално много много дълъг) едносвързан списък, чиито брой елементи не знаем. Възможно е той да се зацикля (тоест връзката на някой от елементите му да сочи към предходен такъв). Можете ли да измислите начин за проверка с константна памет и линейно време дали списъкът се зацикля или не? Нямаме право да променяме елементите на списъка по какъвто и да било начин.

Ели се намира в стая, която има 2 врати: едната води към нейните най-големи кошмари (място, където ноктите й се чупят по-често, косата й не е толкова блестяща, не всички я харесват, и всеки ден има изпити по анализ), а другата - към нейния рай (всъщност не сме много сигурни какво е това, но бихме могли да предположим, че Станчо се намира там). Всяка от вратите се охранява от пазач, единият от които винаги казва истината, а другият - винаги казва лъжата. Ели има право на един единствен въпрос и след това трябва да избере врата, през която да мине. Какъв би могъл да бъде този въпрос?

Даден ви е масив с N цели числа (всяко от тях положително, отрицателно или нула). Изградете алгоритъм, който намира дали съществува тройка негови числа със сума нула. Разгледайте решения със сложности O(N**3), O(N**2 * logN), O(N**2). Можете ли да модифицирате алгоритъма си така, че да брои колко различни такива тройки има?

Даден е масив с N цели числа, като всяко от тях е между 1 и N, включително. Измислите алгоритъм, който проверява дали има повтарящо се число. Имате право да променяте елементите на масива. Каква най-добра сложност по време и по памет можете да направите?

Даден е масив с N (нечетен брой) цели числа. Всяко число се среща по два пъти с изключение на едно, което е уникално. Намерете това число.

Даден е масив с N (четен брой) цели числа. Всяко число се среща по два пъти с изключение на две, които са уникални и различни помежду си. Намерете тези числа.

В триъгълен съд има три мравки - всяка в един от ъглите на триъгълника. Едновременно всяка от тях тръгва към някой от другите ъгли. Какъв е шансът след като стигнат до ъгъла, към който са тръгнали, отново във всеки ъгъл да има точно по една мравка?

Имате 10 буркана, пълни с хапчета. Казано ви е, че във всички буркани хапчетата тежат по 10 грама, с изключение на един, където хапчетата са по 9 грама. Разполагате с електронна везна, която прецизно измерва теглото на сложените върху нея обекти. Можете ли с едно единствено измерване на везната да определите в кой от бурканите хапчетата са по-леки?

Дадени са ви 12 идентични монети, една от която е фалшива (тоест е направена от различен материал и съответно е по-лека или по-тежка). Дадена ви е и обикновена везна (на която от двете страни можете да сложите някакви обекти и тя ще ви покаже дали теглото им е равно, дали левите са по-леки или по-тежки). Можете ли с три измервания да определите коя е фалшивата монета и дали тя е по-лека или по-тежка?

Дадено ви е, че A = 1, B = 2**A, C = 3**B, ..., Z = 26**Y, където операцията ** е вдигане на степен. Намерете (X - A) * (X - B) * (X - C) * ... * (X - Z) = ?.

Дадено ви е число N и от вас се иска да напишете възможно най-прост if() (с възможно най-малко операции в него), с който да проверите дали числото е точна степен на 2 или не. Не са разрешени цикли или по-сложни конструкции.
Примерна реализация би била if (!(N ^ 1) || !(N ^ 2) || !(N ^ 4) || !(N ^ 8) || ...), но тя е много по-дълга от оптималната, а също така зависи колко битов е типа на N.

Дадено ви е положително цяло число N. Намерете неговия най-нисък ненулев бит (lowest bit) или по-точно числото, което представя той (ако индексът е 3, то върнете 2**3 = 8).
Примери: за числото 42 (101010) трябва да върнете 2, докато за 88 (1011000) трябва да върнете 8. Най-ниските битове са най-надясно в двоичния запис на числото.

По дадено цяло число x съставете израз само от побитови операции и х и скоби, който се евалюира до true, ако числото е нула или едно, и до false ако е което и да е друго. Побитови операции са +, -, ~, |, &, ^, !, <<, >> приложени върху аргумента или константи.

Покажете начин за целочислено умножение по 7 използвайки само побитови операции. Побитови операции са +, -, ~, |, &, ^, !, << (shift left), >> (shift right).

Напишете алгоритъм, който разбърква по произволен начин елементите на дадено множество с N елемента. Покажете, че всяко разбъркване е възможно да се случи и докажете защо всеки от възможните изходи е с равен шанс (ако допуснете, че функцията rand() връща произволна стойност). Нямате право да ползвате вградената функция random_shuffle().

void randomShuffle(int* a, int n) {
	for (int i = n - 1; i > 0; i--)
		swap(a[i], a[rand() % (i + 1)]);
}

Колко е очакваният брой разбърквания на стандартно тесте с карти (с 52 карти), които трябва да направите, преди да постигнете уникално подреждане (което никога до сега не се е срещало преди в историята на човечеството). Допускаме, че при разбъркване на картите получаваме с еднаква вероятност всяка възможна тяхна подредба.
Допълнителна информация: 100 милиарда хора, живяли някога на планетата.

Дадени са ви:

• 42 -> 1
• 1337 -> 0
• 669 -> 3
• 1882 -> 4
• 688 -> 5
• 12345 -> 1
• 67890 -> 5
• 123 -> 0
• 456 -> 2
• 789 -> 3

Дадена ви е редицата 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211. Намерете следващия й член.

Инфо:
За да записваме подмножества на някакво множество със сравнително малък брой елементи (до 32 или до 64) понякога е по-удобно (по-бързо и по-икономично откъм памет) вместо да записваме елементите в масив, да ги запазваме в едно единствено 32 (или 64) битово число. Ако i-тият елемент присъства в подмножеството, то числото ще има 1-ца на i-та позиция в двоичния си запис и обратно - ако не присъства ще има 0 на съответната позиция. Този метод се нарича ползване на битови маски (тъй като маската от битовете на числото определя кои елементи присъстват и кои не). Ето и пример за това. Да кажем в един учебен клас има 25 ученика. Учителят може да записва отсъстващите ученици в даден ден в един единствен int. Например 1050784, чието двоично записване е 100000000100010100000, би означавало, че 6, 8, 12 и 21-ви номер са отсъствали в дадения ден.
Понякога се налага да изброим (итерираме) всички подмножества на дадено множество. Подмножество на дадено множество е множеството от някои (потенциално всички или нито един) от елементите на първоначалното множеството.
Задача:
Напишете функция, която генерира всички непразни подмножества на дадено множество, зададено чрез битова маска. Тоест генерирайте всички негови ненулеви битови подмаски.

void iterative(unsigned mask) {
	for (unsigned cmask = mask; cmask > 0; cmask = ((cmask - 1) & mask))
		fprintf(stdout, "%u\n", cmask);
}

void recurse(int idx, unsigned cmask, unsigned mask) {
	if ((1LL << idx) > mask) {
		if (cmask != 0)
			fprintf(stdout, "%u\n", cmask);
		return;
	}
	recurse(idx + 1, cmask, mask);
	if (mask & (1u << idx))
		recurse(idx + 1, cmask | (1u << idx), mask);
}

void recursive(int mask) {
	recurse(0, 0, mask);
}

Напишете функция, която вдига число a на степен p. Има ли по-бързо от линейно решение?

int slowPow(double a, int p) {
	double ret = 1;
	for (; p > 0; p--)
		ret *= a;
	return ret;
}

int fastPow(double a, int p) {
	double ret = 1;
	for (; p > 0; p >>= 1) {
		if (p & 1) ret *= a;
		a *= a;
	}
	return ret;
}

Дадени са ви N числа между 1 и N-1, включително. Точно едно от тях се повтаря. Намерете кое е то.

Дадени са ви N-1 числа между 1 и N, включително, като точно едно от тях липсва (и няма повтарящи се). Намерете кое е то.

В редица са наредени N абсолютно еднакво-изглеждащи предмета, като един от тях е истински, а останалите са негови холограми. На всеки ход можем да пробваме да докоснем точно един от тях. Ако той е бил истинският, холограмите изчезват и ние печелим. Ако не е бил, то истинският разменя мястото си с холограмата от лявата му страна (ако има такава, тоест ако не е в най-лявата позиция) или с холограмата от дясната му страна (отново ако има такава). Измислете стратегия, с която със сигурност да уловите истинския предмет, независимо от това как той се е движил и къде се е намирал в началото.

Играта 21 е известна игра, която се играе от двама души. В началото пред тях има купчинка с 21 монети. Играчите се редуват, започвайки от единия. Играчът, който е на ход, има право да махне 1, 2 или 3 монети от купчината (ако има толкова останали в нея). Играчът, който не може да направи ход (тоест не са останали монети) губи. Има ли стратегия, при която първият може да спечели, независимо от ходовете на втория? Опишете я.

Даден ви е масив с N естествени числа, които (потенциално) могат да бъдат много големи. Пита се кое е първото естествено число, което не фигурира в масива. За тази задача приемете, че естествените числа са целите, положителни числа.

Даден ви е сортиран масив с N числа между 0 и N, включително, без повтарящи се числа, сортирани в нарастващ ред. Как бихте намерили лиспващото число?

За какво се използва термина "cast"? Защо се използва?

Каква е разликата между statement и block?

1.	int gcd(int a, int b) {
2.		if (b > a)
3.			swap(a, b);
4.		while (b) {
5.			a %= b;
6.			swap(a, b);
7.		}
8.		return a;
9.	}

Каква е разликата между метод и функция?

Каква е разликата между & и &&, както и между | и ||? Дайте пример, в който те не са взаимно-заменяеми.

Дадено ви е мултимножество от числа. Върнете множеството от същите числа, но без повторения. Разгледайте случая, в който началното множество е сортирано.

/** 
  * Removes duplicate elements from a sorted array.
  * @return Тhe number of unique elements.
  */
int unique(int* a, int n) {
	int idx = 0;
	for (int i = 1; i < n; i++) {
		if (a[i] != a[idx])
			a[++idx] = a[i];
	}
	return idx + 1;
}

Намирате се в изолирана стая с три ключа за осветление - контролиращи три крушки в съседна стая, която не можете да видите. Как бихте могли да разберете кой ключ коя крушка контролира, ако веднъж отишли в стаята с крушките не можете да се върнете в стаята с ключовете?

Готвачът на краля приготви 1000 гозби за неговата сватба! Но кралските шпиони му съобщиха, че някой е сипал отрова в точно една от гозбите му. Отровата започва да се забелязва 2 часа след поемане на храната, а до сватбения пир остават... малко повече от два часа - тоест има време точно за една проба. За щастие, готвачът има на разположение много прасета, върху които може да експериментира - да им забърка смесица (от една или повече от гозбите) и да им я даде да я изядат. Така ако до два часа прасето умре, то в някоя от гозбите, които е изяло, е имало отрова. Колко най-малко прасета е нужно да са на разположение на готвача, за да може да определи в коя гозба е отровата в рамките на тези 2 часа? Примерно решение е да даде на 1000 прасета по точно една от гозбите, но има решение с много по-малко на брой. Тоест той гледа да минимизира не броя умрели прасета, а броя ползвани такива.

Дадена ви е редица от числа. Намерете двете най-големи от тях, които се срещат поне 2 пъти.

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

Имате масив с N числа и искате да върнете нов масив, в който на i-та позиция има произведението на всички числа с изключение на i-тото от първоначалния масив. Как бихте решили задачата, ако нямахте деление?

Намерете отговора на Живота, Вселената и Всичко Останало.

Дадена ви е кръгла торта. Как можете да я разделите на 8 еднакви парчета с 3 прави разреза?

По даден час и минути определете какъв е (по-малкият) ъгъл между стрелките на аналогов часовник.

Напишете функция, която печата всички пермутации на зададен string.

void printAllPerms(char* str, int n)
{
	sort(str, str + n);
	do {
		cout << str << endl;
	} while (next_permutation(str, str + n));
}

void printAllPerms(char* str, int n)
{
	sort(str, str + n);
	while (1)
	{
		cout << str << endl;

		// Find rightmost index that has inversion
		int idx = n - 1;
		while (idx > 0 && str[idx] <= str[idx - 1]) idx--;
		// If there is no such index we have printed all permutations
		if (idx == 0) break;
		
		// Find minimal letter to the right of that index, 
		// that is greater than it
		int swp = idx;
		for (int i = idx; i < n; i++)
			if (str[i] > str[idx - 1] && str[i] < str[swp]) swp = i;
			
		// Swap it with the one at that index and sort all letters
		// to the right of it
		swap(str[swp], str[idx - 1]);
		sort(str + idx, str + n);
	}
}

Дадена е кръгла маса с радиус 10 сантиметра. Двама играчи се редуват и слагат по една монета с радиус 1 сантиметър на масата така, че да не застъпва никоя от досега сложените монети и да не пада от масата. Играчът, който не може да сложи момента губи. Има ли стратегия за първия играч, при която той винаги печели? Каква е тя?

Даден е квадрат със страна 2**N, разделен на малки квадратчета със страна 1. Едно от тях е оцветено в черно, всички останали в бяло. На всеки ход ние можем да поставим trimino, успоредно на страните на квадрата, ако то е разположено само върху бели плочки. Trimino е плочка от три квадратчета под формата на Г (тоест квадрат 2 на 2, на който липсва една от плочките). След поставянето му, трите бели плочки, върху които лежи стават черни. Възможно ли е да се оцвети целият квадрат в черно с поставяне на trimino-та? Как?

.... => 1122 или .... => 5544 или #... => #122
.#.. => 1#32     .... => 5334     .... => 1132
.... => 4335     .... => 2311     .... => 4335
.... => 4455     ..#. => 22#1     .... => 4455

........    ........
.#......    .#......
........    ........    ....   ....   ...1   1...
........    ....1...    .#..   ....   ....   ....
........ => ...11... => .... , .... , .... , ....
........    ........    ....   1...   ....   ....
........    ........
........    ........

Напишете функция, която по дадено множество от градове и тяхната популация, избира някой от тях, като шансът даден град да бъде избран е пропорционален на броя жители в него. Например ако градовете са София (1,263,328 жители), Стара Загора (150,081 жители), Варна (350,064 жители) би избрала София с шанс 71.638%, Стара Загора с шанс 8.511% и Варна с шанс 19.851%.

string chooseCity(string* names, int* population, int n)
{
	long long sum = 0;
	for (int i = 0; i < n; i++)
		sum += population[i];
	// Make sure random() returns large enough numbers
	long long num = random() % sum;
	for (int i = 0; i < n; i++)
	{
		num -= population[i];
		if (num < 0) return names[i];
	}
	return "Something went terribly wrong.";
}

Зададено е множество от събития, зададени чрез тяхното начално време и крайно време. Изберете максимално (по брой) тяхно подмножество, така че никои две събития да не се застъпват (но може да се "докосват", тоест единото да почва точно когато свършва предходното).

Даден ви е (краен) генератор на числа (списък с неизвестен брой елементи, които НЕ можем да индексираме, единствено можем да искаме следващия елемент докато изчерпим всички). Измислете как с константна допълнителна памет и линейно (по броя генерирани елементи) време да изберете случаен елемент от него. Например ако генерираните елементи са били {3, 1, 5, 1, 5, 2, 7, 5}, То 2, 3 и 7 трябва да бъдат избрани с шанс 1/8, 1 да бъде избрано с шанс 1/4 и 5 да бъде избрано с шанс 3/8.

Човек изкачва стълбище с N стъпала. На всяка стъпка той или се качва на следващото стъпало, или изкачва две наведнъж (прескача едно). По колко различни начина може да изкачи стълбището? А ако броят на стъпалата е много голям (1,000,000,000)?

|1 1| ** N == |F(N+1) F(N)|
|1 0|         |F(N) F(N-1)|

От стандартно тесте карти с 52 карти биват изтеглени 5 произволни карти. Искаме да дадем 4 от тях на друг човек, така че по тях той да може да познае 5-тата. Каквъв "протокол" (стратегия) на комуникация биха могли да имат двамата човека за да определят еднозначно 5-тата карта по дадените 4? Картите се дават наредени (тоест ordered set), но не може да се подсказва по друг начин (като например някоя карта да е обърната или завъртяна).