Задачи от Интервюта

"Стандартните" интервюта за работа като програмист в големи фирми (като Google, Facebook, Microsoft, etc.) най-често включват няколко специфични типа задачи. Поради алгоритмичния си характер те са интересни и за хора, които няма скоро да се явяват на интервю. Тук ще намерите компилация от такива задачи, заедно с приложени примерни решения. Ако пък търсите по-логически-ориентирани задачи можете да погледнете страницата с логически задачи.

В различни интервюта биха тествали различни неща, например:

Дали можете да пишете код (и дали кодът, който пишете, е хубав);
Дали знаете популярни алгоритми и структури данни;
Как бихте подходили към непознат проблем;
Дали бихте проявили креативност при решаване на нестандартен проблем;
Как бихте design-нали не-твърде-сложна но не и тривиална система;
Други.

Най-често добрите въпроси са комбинация на две или повече от тези неща.

Тук сме се опитали да разделим задачите в категории, макар че често една задача би могла да попадне и в повече от една от тях.

Списък със задачите

Алгоритмични Задачи

При този тип задачи трябва да измислите алгоритъм или структура данни, която да се справя ефективно с даден проблем. Понякога има "врътка", чието откриване води до решение на задачата чрез стандартен алгоритъм. В повечето интервюта след като измислите как да решите задачата, трябва да напишете и имплементация чрез код или псевдокод.

Сливащи се свързани списъци

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

Покажи решението

Очевидно можем да следваме връзките на всеки от списъците докато стигнем последните им елементи. Ако те са един и същ елемент (тоест с един и същ адрес) значи двата списъка се сливат.

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

Трябва да направим наблюдението, че ако тръгнем от подходящ елемент в някой от списъците и от първия елемент на другия списък и мърдаме с по един елемент на всяка стъпка, като проверяваме дали сме се "слели" след всяка стъпка, ще можем да го намерим.

Как да определим от кой-списък и от кой негов елемент да започнем? Просто - разглеждаме дължините на двата списъка (преброяваме елементите им при първата итерация, в която проверяваме дали завършват в един и същ елемент). В по-дългия от двата итерираме толкова на брой елементи, колкото е абсолютната стойност на разликата им. Тоест ако единият е имал 7 елемента, а другият - 5, то трябва да започнем от третия елемент на първия и от първия елемент на втория списък. Оттам нататък итерираме двата списъка едновременно докато намерим първия им общ елемент.

Нагоре-надолу

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

Покажи решението

По-опитните програмисти веднага ще забележат, че задачата може да бъде решена с техниката "Двоично Търсене". Същата задача с по-подробно описание има в темата за него.

На всяка стъпка ще разделяме интервала на две равни части, като в зависимост от отговора "нагоре" или "надолу" ще знаем в коя половина да търсим числото. Така постигаме най-много логаритъм от големината на интервала на брой питания, тоест в случая 10 (тъй като двоичният логаритъм от 1000 е малко по-малко от 10). Нека, например, случайно-избраното число е 42. Питанията към guess() ще са (интервал, питане): ([1, 1000], 500) -> ([1, 499], 250) -> ([1, 249], 125) -> ([1, 124], 62) -> ([1, 61], 31) -> ([32, 61], 46) -> ([32, 45], 38) -> ([39, 45], 42) -> BINGO!
Може да ви накарат да напишете код на алгоритъма си. Той би бил нещо от сорта на:

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

Под-интервал с максимална сума

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

Покажи решението

Едно очевидно решение е да проверим всеки подинтервал на масива и да изведем този с най-голяма сума. Това решение за съжаление е O(N²) по време, което е точно нещото, за което ще следят по време на интервюто. Бързодействието в този тип задачи е жизнено важно, затова ще изградим алгоритъм, който решава задачата за оптималното линейно време (тоест О(N)). Тук трябва да направим наблюдението, че един подинтервал е потенциално оптимален, ако няма негов префикс или суфикс, който да е с отрицателна сума. Exempli gratia, ако имаме подинтервала {1, 2, -5, 6, 3, -1, 4, -2, 3, 3, -2, 3}, то той има префикс с отрицателна сума. Този префикс е именно {1, 2, -5}. Наистина, в случая би било по-оптимално да вземем само подинтервала {6, 3, -1, 4, -2, 3, 3, -2, 3}. Същото важи ако имаме и отрицателен суфикс (просто си представете същия пример, обърнат на обратно). Така нашият алгоритъм ще се стреми алчно да избира така подинтервала, че да няма отрицателен префикс, и да тества всички възможни суфикси, така че дори да има отрицателен такъв, да гарантираме, че сме тествали и подинтервала без него.
Оттук нататък алгоритъмът е както следва: почвайки с празен интервал, на всяка стъпка разширяваме надясно интервала със следващото число в редицата. Проверяваме дали сумата в този интервал е по-добра от най-добрата до сега намерена (ако да, запазваме подинтервала). След като евентуално обновим отговора, проверяваме дали пък сумата не е станала отрицателна (тоест това би било отрицателен префикс, на по-нататък разширения подинтервал). Ако наистина сумата е отрицателна, премахваме всички числа от интервала и започваме отново с празен интервал (разбира се, продължавайки от следващото недобавено число в редицата).

Ето и пример:
Вход: {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}

Инициализация: Интервал {}, сума 0, отговор -безкрайност.
Стъпка 1: Интервал {1}, сума 1, индекс 0, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(обновяваме отговора на 1 с текущия интервал)
Стъпка 2: Интервал {1, 2}, сума 3, индекс 1, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(обновяваме отговора на 3 с текущия интервал)
Стъпка 3: Интервал {1, 2, -5}, сума -3, индекс 2, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(интервалът става с отрицателна сума, следователно го изчистваме)
Стъпка 4: Интервал {6}, сума 6, индекс 3, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(обновяваме отговора на 6 с текущия интервал)
Стъпка 5: Интервал {6, -1}, сума 5, индекс 4, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
Стъпка 6: Интервал {6, -1, 4}, сума 9, индекс 5, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(обновяваме отговора на 9 с текущия интервал)
Стъпка 7: Интервал {6, -1, 4, -2}, сума 7, индекс 6, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
Стъпка 8: Интервал {6, -1, 4, -2, 3}, сума 10, индекс 7, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(обновяваме отговора на 10 с текущия интервал)
Стъпка 9: Интервал {6, -1, 4, -2, 3, -40}, сума -30, индекс 8, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}

Стъпка 10: Интервал {-2}, сума -2, индекс 9, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}
(интервалът става с отрицателна сума, следователно го изчистваме)
Стъпка 11: Интервал {3}, сума 3, индекс 10, {1, 2, -5, 6, -1, 4, -2, 3, -40, -2, 3}

Отговор: 10 с подинтервал {6, -1, 4, -2, 3}.

Има ли цикъл?

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

Покажи решението

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

Местим единия указател с два елемента напред (като следим за край на листа или "задминаване" на другия указател);
Местим другия указател с един елемент напред.

Очевидно сложността по памет е О(1) (пазим единствено два указателя). Можем също така лесно да покажем, че заекът ще измине елементите на листа най-много два пъти (преди да настигне костенурката), а тя, от своя страна ще ги извърви най-много веднъж, тоест общо 3 пъти, което е О(N).

Тройка с нулева сума

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

Покажи решението

Най-простият алгоритъм би бил да въртим три вложени цикъла, като проверим всички тройки. Това е решението със сложност O(N³) и не би зарадвало интервюиращите.
Ако фиксираме две от числата (тоест въртим само два вложени цикъла) които да кажем са A и B, то има ли бърз начин да проверим дали има трето, което е със стойност -(A + B)? Всъщност има, даже повече от един такъв. По-стандартният от тях е да сортираме предварително числата (със сложност O(N∙logN), а дори и O(N∙N) не разваля сложността), след което фиксираме всички двойки числа и с двоично търсене търсим дали масивът съдържа третото. Този метод води до сложност O(N∙log(N) + N∙N∙log(N)), тоест О(N²∙log(N)).

Ако имаме право на O(N) допълнителна памет, можем в хеш таблица (hashmap в случая) да пазим по колко пъти се среща всяко число и търсенето ни за число да става константно, вместо логаритмично по време. Това би довело до решение със сложност O(N²), но O(N) откъм допълнителна памет.

Най-доброто решение ползва отново O(N²) време, но O(1) допълнителна памет. Отново е нужно да сортираме елементите, след което въртим цикъл по един от елементите на тройката. Нека този елемент е с индекс i.
Фиксираме два указателя (в смисъл на нещо, което ни сочи позиция в масива, не на указател към памет) към елементите с индекси i + 1 и N (които ще наричаме, съответно, "ляв" и "десен" указател). Проверяваме каква е сумата на трите елемента.

Ако тя е нула - супер, намерихме решение.
Ако тя е отрицателна, то, очевидно, е в наш интерес да я увеличим. Тъй като сме фиксирали първия елемент и можем да местим само втория и третия указател, то единственото, което можем да направим, за да увеличим сумата, е да преместим левия указател с един елемент надясно.
Ако сумата е положителна, за да я намалим ще преместим десния указател с един елемент наляво.

След всяко такова преместване проверяваме отново каква е сумата на трите елемента (фиксирания и двата, които сочим в момента) и действаме адекватно. Тъй като на всяка стъпка или местим левия надясно, или десния наляво, те рано или късно ще се срещнат. Нещо повече, те ще се срещнат след не повече от N такива премествания. Така ако можем да фиксираме първия елемент по N начина, и за всяко фиксиране правим по не повече от N местения, сложността на този алгоритъм е O(N²).

Защо работи и не пропуска ли той решения? С малко мислене можем да се убедим, че той е еквивалентен на алгоритъма с Binary Search, само че правим търсенето по-умно и спираме по-рано фиксирането на втория елемент.

Не е толкова лесно да се види защо той не изпуска решения. Нека разгледаме едно решение (в сортиран масив). То представлява три числа, които можем да наричаме "ляво", "средно" и "дясно" (тъй като, очевидно, едното ще е най-малко (или равно на (някое от) останалите), другото ще е най-голямо (или равно на (някое от) останалите) и третото ще е между тях (или равно на (някое от) тях)). Фиксираното от нас във външния цикъл число е "лявото" (демек най-малкото). Тъй като в хода на вътрешния цикъл двата индекса се срещат, то със сигурност на някоя стъпка левият индекс е минал през "средното", а десният индекс е минал през "дясното". Ако някой от индексите е преминал през двете числа, а другият през нито едно от тях, то тогава на някоя стъпка от алгоритъма сме преместили неправилния индекс, което е противоречие с алгоритъма или с това, че разглежданата тройка е решение.

Тъй като алгоритъмът не е особено интуитивен и не е лесен за асимилиране, ще дадем и пример:
Дадени са ни числата {7, -5, 2, 3, -4, -4, 2, 0, 1, -6}.
Като първа стъпка от алгоритъма ги сортираме. Получаваме {-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}.
Въртим цикъл за всяко от тях, като казваме, че то ще е най-малкото ("най-лявото") от тройката.

При фиксиране на -6 за такова, ето стъпките, които ще се изпълнят във вътрешния цикъл:
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -4, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -3, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -3, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума +1, следователно местим десния индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -3, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -2, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -1, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -1, следователно местим левия индекс.
Индексите се срещат, следователно няма тройка със сума 0, чието най-малко число е -6.

Продължаваме нататък, като фиксираме следващото число, -5.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -2, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -2, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума +2, следователно местим десния индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -2, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -1, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума 0, намерихме отговор!

Ако усложним задачата, като искаме да преброим колко са всички тройки с нулева сума, трябва леко да модифицираме алгоритъма (но той си остава със сложност O(N²)). Трябва да внимаваме правилно да имплементираме вътрешния цикъл да продължава дори след като сме намерили решение, тъй като може да има повече от една валидна тройка с дадено най-малко число.

Понякога може да имаме повече от един отговор с дадено минимално число дори като не ползваме последователни повтарящи се числа.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -1, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума +3, следователно местим десния индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума -1, следователно местим левия индекс.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума 0, намерихме отговор! 1 ≠ 2 и 2 ≠ 3 (тоест следващото ляво и следващото дясно число са различни от, съответно, текущото ляво и текущото дясно), така че можем да преместим и двата индекса.
{-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}, със сума 0, намерихме отговор!
На следващата стъпка указателите се срещат, така че прекратяваме вътрешния цикъл.

Повтарящ се елемент в масив

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

Покажи решението

Може би най-лесното решение е да сортираме числата и да обходим масива, като проверяваме дали два съседни елемента са равни. Това решение е със сложност O(N∙log(N)) и ползва константа допълнителна памет.
Друго очевидно решение е да заделим един нов масив с N елемента и да обходим дадените ни числа, като броим всяко колко пъти се среща. Този подход е O(N) откъм време, но също така О(N) откъм допълнителна памет.

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

Тоест алгоритъмът е следния:

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

Всеки от елементите на масива променяме на -1 максимум по веднъж. Освен това намирането на най-малкия елемент с -1 обикаля елементите също точно веднъж. Така сложността по време е O(N). Имаме само 2 допълнителни променливи, така че сложността по памет е О(1).

Нека за показно на алгоритъма разгледаме два примера - където няма повтарящ се елемент и където има повтарящ се елемент.

Пример 1: {5, 3, 1, 4, 2, 7, 6}

{5, 3, 1, 4, 2, 7, 6}
{-1, 3, 1, 4, 2, 7, 6}
{-1, 3, 1, 4, -1, 7, 6}
{-1, -1, 1, 4, -1, 7, 6}
{-1, -1, -1, 4, -1, 7, 6}

Достигнахме -1 на позиция 1 при начална позиция 1, следователно обходихме един цикъл. Нямаме противоречие, продължаваме нататък.

{-1, -1, -1, 4, -1, 7, 6}
{-1, -1, -1, -1, -1, 7, 6}

Достигнахме -1 на позиция 4 при начална позиция 4. Нямаме противоречие, продължаваме нататък.

{-1, -1, -1, -1, -1, 7, 6}
{-1, -1, -1, -1, -1, -1, 6}
{-1, -1, -1, -1, -1, -1, -1}

Достигнахме -1 на позиция 6 при начална позиция 6. Нямаме противоречие, продължаваме нататък.

Няма повече необходени елементи в масива, следователно прекратяваме алгоритъма.

Не стигнахме до противоречие, следователно няма повтарящо се число.

Пример 2: {5, 3, 1, 4, 2, 3, 6}

{5, 3, 1, 4, 2, 3, 6}
{-1, 3, 1, 4, 2, 3, 6}
{-1, 3, 1, 4, -1, 3, 6}
{-1, -1, 1, 4, -1, 3, 6}
{-1, -1, -1, 4, -1, 3, 6}

{-1, -1, -1, 4, -1, 3, 6}
{-1, -1, -1, -1, -1, 3, 6}

Достигнахме -1 на позиция 4 при начална позиция 4. Нямаме противоречие, продължаваме нататък.

{-1, -1, -1, -1, -1, 3, 6}
{-1, -1, -1, -1, -1, -1, 6}

Достигнахме -1 на позиция 3, при начална позиция 6. Това е противоречие, следователно прекратяваме алгоритъма и твърдим, че има повтарящо се число. При това числото е текущият индекс (тоест 3).

Неповтарящ се елемент в масив

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

Покажи решението

Най-тъпото решение е да направите два цикъла и да проверите всяко число дали се повтаря или не. Това дори не си правете труда да го пишете на интервюта. Сложността му е О(N²).
Малко по-добро решение е да сортираме масива и да търсим кое не се повтаря линейно в сортирания масив. Сложността на това решение е O(N∙log(N)).
Използвайки хешове, задачата може да се реши с O(N) както откъм време, така и откъм допълнителна памет. Това е едно (що-годе) приемливо решение
Най-доброто решение е O(N) откъм време и О(1) откъм допълнителна памет. Първо трябва да се запознаете с операцията xor. Тя е имплементирана във всички процесори и я има в (почти) всички програмни езици. По дискретна математика трябва да сте я учили като "изключващо или". Ако вземем две числа в двоична бройна система и направим техния xor, на всяка позиция (в двоичния си запис), на която числата се различават, записваме 1, а на всяка позиция, на които не се различават пишем 0. Така получаваме ново двоично число. Примери:

101010 xor 011001 == 110011
111111 xor 000000 == 111111
101010 xor 101010 == 000000

Идеята на решението се базира на това, че бинарната операция xor на две числа дава нула, ако числата са равни, или число различно от нула, ако не са. Така:

A xor A == 0
A xor B ≠ 0 (при А ≠ B)
A xor A xor B xor B == 0
A xor B xor A xor B == 0
A xor B xor B xor A == 0
C xor 0 == C

От горните свойства на операцията xor можем да изведем, че ако всяко число се повтаря по два пъти (или по четен брой пъти) с изключение на едно, то xor-ът на всички числа ще бъде равен точно на уникалното число.

Неповтарящ се елемент в масив 2.0

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

Покажи решението

Както виждаме, задачата е модификация на предходната. Следователно е логично и решението да е модификация на предходното. Какво става обаче ако вземем xor-а на всички числа в масива? Получаваме xor-а на двете уникални числа. Тъй като те са различни, този xor е ненулев. Тъй като е ненулев, в него можем да намерим поне една позиция (в двоичния му запис) която е 1. Това означава, че едното от двете числа има 1 на тази позиция, а другото има 0. Нека отново обходим масива, като го разбием на две групи - в едната са числата, които имат 1 на тази позиция, а в другата - тези, които имат 0. Вижда се, че тези две множества от числа са непресичащи се, и в същото време съдържат всички числа от първоначалния масив. Какво забелязваме? Едното множество съдържа едното от уникалните числа, а другото съдържа второто. Нещо повече, във всяко от множествата всички елементи се срещат по два пъти, с изключение на по едно уникално число. Това е точно предходната задача! Правим xor-овете на числата във всяко от подмножествата и намираме двете уникални числа.

Забележете, че не ни трябва реално да копираме числата, когато ги разделяме на две групи. Можем просто да пазим в 2 променливи: едната ще бъде xor-ът на числата, които имат 0 на тази позиция, а другата - на тези, които имат 1 на тази позиция. Така решението отново е O(N) откъм време и O(1) откъм допълнителна памет.

Точно едно повтарящо се число

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

Покажи решението

Решението на тази задача е относително просто поради условието, че точно едно число се повтаря. Така можем да сумираме дадените ни N числа и от тях да извадим очакваната сума ако нямаше повтарящо се. Тоест повтарящото се число е SUM - N * (N - 1) / 2.

Точно едно липсващо число

Дадени са ви N числа между 1 и N+1, включително. Всички числа са различни, като едно липсва. Намерете кое е то.

Покажи решението

Решението като идея е абсолютно същото като на предходната задача: намираме сумата на дадените ни числа, намираме сумата, която бихме имали ако нямаше липсващо и изваждаме от нея намерената сума на дадените ни числа. Тоест липсващото число е (N + 1) * (N + 2) / 2 - SUM.

Произволно разбъркване

Напишете алгоритъм, който разбърква по произволен начин елементите на дадено множество с 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
)]);
}

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

Нека покажем, че всяка пермутация е равно-вероятна. С един елемент очевидно няма какво да правим. С два елемента бихме разменили 1-вия и 2-рия с шанс 1/2, което е и точно вероятността за всяка от двете пермутации на 2 елемента. Нека разгледаме как работи алгоритъма с 3 елемента. На първа стъпка разменяме 3-тия елемент с 1-вия със шанс 1/3, с 2-рия с шанс 1/3 и го оставяме на същото място също с шанс 1/3. Следващата итерация на цикъла решава същата задача, но с по-малко елементи (разглежда само първия и втория), за което вече показахме, че работи правилно.

По-формално можем да ползваме индукция за доказателство. Приемаме случаите с 1 и 2 елемента за база и допускаме, че алгоритъмът работи за K елемента -- тоест шансът на всеки елемент да се озове на дадена позиция е 1/K.
За K+1 елемента по време на първата итерация шансът на всеки елемент да застане на последна позиция е 1/(K+1). След като сме го преместили остават K елемента за K позиции. Всеки от K+1-те елементите има шанс 1 - 1/(K+1) да не е преместен и 1/K (по индукция) шанс да застане на всяка от K-те оставащи позиции. Тоест шансът на всеки от непреместените елементи да се озове на някоя от тези K позиции е (1 - 1/(K+1)) * (1 / K), което е точно 1/(K+1).

Игра на 21

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

Покажи решението

Тази игра е една от най-базовите в Game Theory (което се различава от "Теория на Игрите", която се преподава във ФМИ). За да решим поставената задача ще тръгнем отзад напред. Първо, ако са останали 0 монети, то играчът, който е на ход, не може да направи нищо и губи (тоест обявяваме 0 за губеща позиция). Ако има 1, 2, или 3 монети, то текущият играч може да ги вземе и да остави на другия играч 0 (което, както вече казахме, е губеща позиция). Тоест 1, 2, и 3 са печеливши позиции за първия играч. Нека разгледаме случая, в който в купчината има 4 монети. Независимо дали играчът, който е на ход, вземе 1, 2, или 3 монети, винаги в купчината остават, съответно, 3, 2, или 1 монета. Тоест след този ход другият играч може да спечели. Така намерихме, че 4 е губеща позиция.
Като цяло в такива игри правим следните стъпки:

Разглеждаме играта отзад напред (тоест от по-малки купчини към по-големи);
Разделяме позициите на печеливши и губещи, спрямо това дали от една позиция можем да спечелим при оптимална игра.
Ако от дадена позиция можем да вкараме другия играч във вече доказано губеща позиция, то текущата позиция е печеливша.
Ако всички възможни ходове водят до печеливши позиции, то текущата позиция е губеща.

Така намираме, че 22-те позиции (от 0 до 21, включително) са: Г, П, П, П, Г, П, П, П, Г, П, П, П, Г, П, П, П, Г, П, П, П, Г, П. Тоест 21 е печеливша позиция, като от нея трябва да вземем 1 монета (за да вкараме противника в губеща). Като цяло, в така зададената игра всяка позиция, която се дели на 4 е губеща.

Забележете, че този начин на определяне на позициите работи не само за тази игра. Например ако имахме право да взимаме 1, 3 или 4 монети (вместо 1, 2 или 3) позициите биха били: Г, П, Г, П, П, П, П, Г, П, Г, П, П, П, П, Г, П, Г, П, П, П, П, Г. В тази игра първоначалната позиция е губеща -- тоест ако противникът играе оптимално, ние не можем да спечелим независимо от стратегията ни.

Първо липсващо число

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

Покажи решението

Най-очевидното решение е за всяко естествено число линейно да проверим дали то присъства или не. Тъй като отговорът ще е най-много N+1 като стойност, получаваме сложност О(N²).

Възможна оптимизация е да сортираме масива и после линейно да проверим кое е първото, което липсва. Сложността на това решение е O(N∙log(N)), което е по-приемливо, но все пак бавно.

Друго, още по-бързо решение е да вкарате всички числа в хеш-таблица, в която после да проверите кое е първото липсващо. Така ще имате O(N) сложност по време и O(N) сложност откъм допълнителна памет. Това на интервю е що-годе приемливо решение, макар и не оптимално.

Оттук до края на решението на задачата ще считаме, че индексацията в масивите е от 1, а не от 0.Получената сложност O(N∙log(N)) в по-предното решение дойде от сортирането, но можем да я оптимизираме, като забележим, че можем спокойно да игнорираме всички числа, които са по-големи от N. Наистина, ако има число в масива, което е по-голямо от N, то със сигурност отговорът ще е по-малък от него. Така потенциални кандидати за отговор са числата между 1 и N+1, включително. Можем да заделим втори масив, като в него направим Counting Sort на всички числа в масива, които попадат в този интервал. Това е почти еквивалентно на хеш-таблицата, само където доста по-лесно за имплементиране, а също така елиминира константата, идваща от хеш-таблицата.
"Преброяваме" числата по-малки или равни на N в новия масив, като, ако сме срещнали числото X, увеличаваме с 1-ца X-тата му позиция. Реално даже не ни интересува колко точно пъти се среща дадено число, а само дали се среща или не. Можем да инициализираме втория масив с 0 и да записваме 1 на X-та позиция, всеки път, когато срещнем число X. След като обходим входния масив и запишем кои числа се срещат, обхождаме втория масив и търсим първата позиция, на която имаме 0. Ако има такава позиция, то тя е отговорът на задачата. Ако пък няма, то отговорът е N+1 (тъй като явно всички числа от 1 до N се срещат). Това решение е линейно както по време така и по допълнителна памет.

Оптималното решение е вместо да ползваме втори масив, да ползваме първия. За съжаление не можем да затриваме числата, но пък тъй като ни е необходим само един допълнителен бит информация на число, можем да ги правим отрицателни. Тоест отрицателно число на X-та позиция би означавало, че във входния масив сме срещнали число X. Тук трябва да внимаваме да вземаме от входния масив вече не самите му елементи, а техните абсолютни стойности (тъй като е възможно да сме ги променили). Също така, когато искаме да направим отрицателна X-та позиция трябва да внимаваме дали тя вече не е отрицателна. Така постигнахме O(N) по време и O(1) откъм допълнителна памет.

Липсващо число в сортиран масив

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

Покажи решението

Тази задача почти крещи "binary search, binary search". Винаги, когато имате нещо сортирано, погледнете защо ви го дават сортирано. Една от възможностите е да приложите двоично търсене (както е и в случая). На всяка стъпка от двоичното търсене проверявате дали на M-та позиция (където M е средата на текущо-разглеждания интервал) стои числото M. Ако не, то липсващото число е или на тази позиция, или наляво. Ако ли пък е, то значи липсващото число е на индекс, по-голям от M.

Премахване на дубликати

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

Покажи решението

Можем да ползваме хеш-таблица. За всяко число от входното мултимножество първо проверяваме в нея дали вече е срещано. Ако сме го срещали, директно продължаваме нататък. Ако не сме го добавяме в множеството, което ще върнем, както и в хеш-таблицата (с цел да не го добавяме повече от веднъж). Сложността на това решение е линейна по броя елементи в началното множество.
Случая, в който началното множество вече е сортирано също се решава с O(N), но за него не ни е нужна хеш-таблица. Примерна реализация би била:

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
;
}

Най-големи числа, срещащи се поне два пъти

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

Покажи решението

Това е поредният пример за задача от интервюта, която може да се реши с хешове. В случая можем да ползваме hashmap и за O(N) да намерим колко пъти се среща всяко от числата, където N е броят числа в началната редица. При добавянето на всеки елемент проверяваме дали неговите срещания са станали 2 и ако това е така, update-ваме отговора (ако се налага). Това решение всъщност работи за задачата "Кои са 2-та най-големи елемента, които се срещат поне K пъти". Като (малка) оптимизация можем да ползваме hashset вместо hashmap за задачата с 2 срещания, като просто пазим кои елементи сме срещали до сега, и при попадане на елемент, който вече присъства в hashset-а да update-ваме отговора (ако се налага). Тъй като щом текущият елемент е вече в сет-а, то значи това е поне второто му срещане.

Структура данни за медиана

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

Покажи решението

Най-тривиалното решение би било да пазим досега вкараните елементи сортирани и питането ни за медианата да става константно. Така, обаче, вкарването на нов елемент ще е с линейна сложност, което не можем да дефинираме като "бързо".

Разбира се, ако пазим числата в двоично наредено дърво (binary search tree) бихме постигнали логаритмична сложност (ако дървото е балансирано) както за вкарване на нов елемент, така и за питане за медианата. За съжаление за да можем да намираме медианата трябва за всеки връх да пазим и колко наследници има той. Повечето вградени в езика или стандартните библиотеки имплементации не поддържат това нещо (питане за K-ти по големина елемент), така че трябва ние сами да напишем балансираните дървета. Това е сравнително сложно, особено ако трябва да се имплементира на интервю.

Вместо това ще покажем друг подход, който не само е значително по-лесен за имплементиране, ами предоставя и по-добра сложност при питане за медианата. Нека имаме две приоритетни опашки (пирамиди, heaps, priority_queue) - едната пазеща числата в прав ред (най-голямото е най-отгоре), а другата - в обратен ред (пазеща най-малкото най-отгоре). Първата от тях ще наричаме "лява", а втората - "дясна". Ще ги държим с равен брой елементи (а когато има нечетен брой елементи едната ще съдържа 1 повече от другата).

Нека разгледаме как добавяме елемент. Нека елементът е със стойност X. Проверяваме дали X е по-малък от най-големия елемент на лявата пирамида. Ако да, го вкарваме в нея, иначе го вкарваме в дясната. В този момент е възможно една от пирамидите да има с 2 елемента повече от другата (ако е имала 1 елемент повече и сме добавили новия елемент в нея). Ако това е така, местим най-големия елемент от лявата пирамида в дясната (ако лявата е с повече елементи), или най-малкия елемент на дясната в лявата (ако дясната пирамида е с повече елементи). Така след всяко добавяне запазваме разликата в броят елементи най-много 1.

Питането за медианата също е тривиално. Ако едната пирамида има повече елементи, то медианата е най-големият елемент от лявата пирамида (ако тя е с повече елементи) или най-малкият елемент на дясната в противен случай. Ако пък двете пирамиди са с равен брой елементи, то медианата е средното аритметично на най-големия елемент на лявата и най-малкия елемент на дясната.

Каква сложност постигнахме в така имплементираната структура данни? Добавянето на нов елемент в най-лошия случай се изразява в едно добавяне, едно изваждане и още едно добавяне на елемент в пирамида. Всяка от тези операции е O(log(N)), така че добавянето ни е със сложност O(log(N)). Питането за max от дясната пирамида и за min от лявата става константно, така че сложността за питане е O(1).

Съществува и трето (малко по-бавно) решение, ползващо структурата данни Tiered Vector, при която добавянето е със сложност O(sqrt(N)), докато питането за медианата е O(1).

Произведения на останалите числа

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

Покажи решението

Едно интуитивно решение би било да намерим произведението на всички числа от първоначалния масив (нека то бъде productAll), и после с второ обхождане да запълним масива, който връщаме като result[i] = productAll / input[i].

Ако нямаме деление, обаче, задачата не е толкова лесна. Съществуват няколко подхода, като най-хубавият както откъм ефективност така и откъм леснота за писане е следният. Създаваме два помощни масива fromLeft[N] и fromRight[N]. Първия от тях запълваме, като на i-та позиция пазим произведението на всички числа до i-тото (невключително) от входния масив. Тоест fromLeft[i] = input[0] * input[1] * ... * input[i-1]. Забележете, че запълването на масива може да стане линейно:

fromLeft[0] = 1;
fromLeft[i] = fromLeft[i - 1] * input[i - 1], за i > 0

Аналогично, масива fromRight[] запълваме по такъв начин, че на i-та позиция пазим произведението на всички числа от входния масив с индекси от i+1 до N-1. Тоест:

fromRight[N-1] = 1;
fromRight[i] = fromRight[i + 1] * input[i + 1], за i по-малко от N-1

Така можем константно да намерим резултата за всяка позиция: result[i] = fromLeft[i] * fromRight[i]. Тоест, след като сме създали тези два помощни масива ни трябва само едно обхождане за да намерим крайните резултати.

Както създаването на масивите, така и намирането на отговора става линейно (по показания начин), затова и цялото решение е със сложност O(N) както по време, така и по памет.

Можем да се справим дори малко по-добре откъм памет, като забележим, че не ни трябват два допълнителни масива - всъщност не ни трябва нито един! Можем да изчислим fromLeft[] в result, и после с второ обхождане (отдясно наляво) директно да намерим отговорите. За целта ни трябва една допълнителна променлива prod, в която да пазим досегашното произведение на срещнатите числа. Така при второто обхождане отдясно наляво правим result[i] = result[i] * prod.

Ъгъл между стрелки на часовник

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

Покажи решението

Можем да определим ъгъла на малката и голямата стрелка спрямо някаква отправна точка (например 12:00), като след това намирането на ъгъла между двете стрелки става лесно.

Нека даденият ни час е hh:mm и ако hh е 12 да го считаме като hh = 0. Тъй като цялото завъртане е 360 градуса, то малката стрелка се завърта 360 / 12 = 30 градуса за всеки час. Но тъй като и минутите влияят на нейното завъртане, то към ъгъла, който определихме от часовете, трябва да прибавим още малко отместване за минутите. Това допълнително отместване което е mm / 60 * 30 или mm / 2. Така цялото отместване на малката стрелка е hh * 30 + mm / 2 градуса.

Отместването на голямата стрелка е доста по-просто - то е само mm / 60 * 360 или mm * 6.

Нека сме намерили angleHour = hh * 30 + mm / 2 и angleMinute = mm * 6. Тогава по-малкият ъгъл между двете стрелки е min(abs(angleMinute - angleHour), 360 - abs(angleMinute - angleHour)).

Триминота

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

Покажи решението

Това е една интересна задача, която се решава чрез техниката "Разделяй и Владей". Ако дъската е 1 на 1 очевидно има решение (без нито едно тримино). Ако дъската е 2 на 2 то също очевидно има решение. Нека разгледаме случая, в който дъската е 4 на 4.

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

Намерихме решение на три от възможните начални разположения. След известно наблюдение се забелязва, че всяка дъска с размер 4 на 4 има решение чрез ротация и/или симетрия на някоя от горните три дъски. Бихме могли да предположим, че всяка дъска със страна 2^N има решение. Сега да намерим стратегия и как да намираме самите решения.

Нека разделим началната дъска на 4 равни части (два разреза: един през средата по X и един през средата по Y). В една от тези 4 е първоначалното черно квадратче, a останалите 3 са изцяло бели. Но ако сложим едно тримино в центъра (там, където двата разреза се пресичат) така, че липсващата му плочка да застъпва частта, която съдържа началната черна плочка, то вече всяка от четирите части е с размер 2^N-1 и има по една черна плочка. Но това е същата задача с по-малък размер! Следователно можем да решим рекурсивно със същия алгоритъм всяка от 4-те подзадачи и да "съединим" решенията, получавайки решение и за големия квадрат. Дъното на рекурсията може да бъде дъска с размер 1. Нека видим как би изглеждало първото разрязване на дъска с размер 8 на 8:

........    ........    .... ....    .... ....    .. ..  .. ..    66 77  88 99
.#......    .#......    .#.. ....    .#2. .33.    .# 2.  .3 3.    6# 27  83 39
........    ........    .... ....    .22. ..3.                               
........    ....1...    .... 1...    .... 1...    .2 2.  .. 3.    A2 2B  CC 3D
........ => ...11... =>           =>           => .. ..  1. .. => AA BB  1C DD
........    ........    ...1 1...    ...1 1...                               
........    ........    .... ....    .4.. ..5.                               
........    ........    .... ....    .44. .55.    .. .1  1. ..    EE F1  1G HH
                        .... ....    .... ....    .4 ..  .. 5.    E4 FF  GG 5H

                                                  .4 4.  .5 5.    I4 4J  K5 5L
                                                  .. ..  .. ..    II JJ  KK LL

Крайният резултат изглежда по следния начин:

66778899
6#278339
A22BCC3D
AABB1CDD
EEF11GHH
E4FFGG5H
I44JK55L
IIJJKKLL

Разделяне на твърд диск

Купили сте си нов твърд диск с размер 1 ≤ N ≤ 4,000 гигабайта. Сега искате да го разделите на различни партишъни (C:, D:, ...), като имате изискването всеки от тях да е поне M гигабайта. По колко различни начина може да стане това?

Считаме, че N и M са цели положителни числа. Също така считаме, че редът на размерите има значение - например разделянията (3, 4) и (4, 3) са различни, тъй като в единия случай C:\ би бил 3 гигабайта, а в другия - 4.

Покажи решението

Тук трябва да питате дали ни интересуват само практични решения - например едва ли бихте желали 4000 партишъна, всеки с по един гигабайт? За целите на задачата, обаче, ще приемем, че (стига M да е достатъчно малко) такива разпределения са възможни.

Решението е базирано на просто динамично оптимиране. Стейтът се базира единствено на това колко неразпределено пространство имаме все още (в началото то е N).

typedef
 int
 Type;
const
 int
 MAX =
 4096
;

int
 N,
 M;
bool
 vis[MAX];
Type dyn[MAX];

Type partition(int rem) {
    if
 (rem =
=
 0)
        return
 1
;
    if
 (rem < M)
        return
 0
;
    if (vis[rem])
        return
 dyn[rem];

    Type ans =
 0
;
    for
 (int
 use =
 M;
 use <
=
 rem;
 use+
+)
        ans +
=
 partition(rem -
 use);

    vis[rem] =
 true
;
    return
 dyn[rem] =
 ans;
}

Това решение е със сложност O(N²), ако приемем, че събиранията и прехвърлянията на числа с тип Type са O(1). Наистина, за всеки от възможните N стейта правим по (най-много) N операции. Най-лошият случай се получава когато M е 1.

Също така трябва да отбележим, че отговорът нараства много бързо - затова трябва да ползваме тип, който може да съдържа такива числа. Предвиждането на такива неща прави добро впечатление на интервюиращите.

Как можем да се сетим за това? Като аналогия можем да дадем числата на Фибоначи*. Тъй като стотното от тях вече не се побира в 64-битов int лесно бихме заключили, че 4000-то ще е много далеч от който и да е от вградените типове. При това, отговорите в дадената задача нарастват много по-бързо, поради факта, че можем да ползваме целия интервал [M, N], а не само 1 и 2.

*Числата на Фибоначи, впрочем, имат доста общо с тази задача. С известно мислене можем да съобразим, че намирането на N-тото от тях е еквивалентно на това да разделите твърд диск с размер N гигабайта на партишъни от по 1 и 2 гигабайта.

Засичащи се мероприятия

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

Покажи решението

Това е известна задача в програмирането, която се решава чрез алчна стратегия (Greedy). Нека разгледаме следния пример с event-и { [0, 13], [2, 5], [4, 6], [5, 9], [8, 14], [11, 12], [15, 20] }.

Ако просто ги взимаме в хронологичен ред (от тези, които започват по-рано към тези, които започват по-късно) не бихме постигнали оптимален резултат. Например за даденото множество бихме намерили резултат 2: {[0, 13], [15, 20]}, което очевидно не е оптимално.

Ако взимаме с приоритет по-къси мероприятия, бихме получили {[4, 6], [11, 12], [15, 20]}. Този път намерихме отговор 3, но и той не е оптимален.

Правилната алчна стратегия е да сортираме събитията по техния край и ги взимаме в този ред (като гледаме всеки следващ да не се застъпва с последния взет). Така получаваме подмножеството {[2, 5], [5, 9], [11, 12], [15, 20]}.

Това решение работи със сложност O(N∙logN), където N e броят събития, между които имаме избор. Логаритъмът идва от сортирането по края на събитията -- ако те вече са ни сортирани в този ред, останалата част от алгоритъма е O(N).

Стъпала

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

Покажи решението

Тази задача може да бъде решена по много начини, като може би най-простият е да разгледаме отговорите за малки N:

Едно стъпало може да бъде изкачено само по един начин;
Ако имаме две стъпала можем или да ги качим двете наведнъж или едно по едно (два начина);
Ако имаме три стъпала можем или да ги качим поединично, или да качим две на веднъж и после 1, или първо едно и после две (три начина);
С четири стъпала вариантите са {(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)} (пет начина);
С пет стъпала вариантите са {(1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1)} (осем начина).

Вече трябва да сте видели, че това е редицата на Фибоначи. Наистина, има логика да е тя, тъй като на K-тото стъпало или сме се изкачили от K-1-вото или от K-2-рото, което е точно рекурентната зависимост на числата на Фибоначи.

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

По-интересното е, че дори логаритмичният начин има няколко варианта. Единият е с формула, а другият с по-generic метод за решаване на рекурентни зависимости. Тоест можем просто да вдигнем матрица 2 на 2 на N-та степен за да намерим N-тото число на Фибоначи:

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

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

Текст и стрингове

Имате (потенциално много дълъг) текст и три стринга S₁, S₂, и S₃. Намерете най-късия откъс от текста, съдържащ и трите стринга. Редът на стринговете няма значение.

Покажи решението

Първото, което ни трябва, е алгоритъм, с който бързо да можем да намерим къде се среща някакъв стринг в текст. Такива алгоритми са сравнително популярни поради практическата им приложимост и почти задължително се изучават в университета. Двата най-популярни (и сравнително лесни за за имплементация) са алгоритъмът на Кнут-Морис-Прат (повече инфо тук и тук), разчитащ на стейт машина с фейлбек линкове и алгоритъмът на Рабин-Карп, разчитащ на хеширане (повече инфо тук и тук). Вторият е моят personal фаворит, тъй като е сравнително лесен за запомняне и имплементиране.

Внимавайте! Тъй като съществуват много популярни алгоритми за тази подзадача, тръгвайки със стандартно търсене с два цикъла (даващ сложност O(N∙|S|), където N е броят символи в текста, а |S| е броят символи в стринга) прави лошо впечатление на интервюиращите. Първо покажете, че знаете по-добри алгоритми, и тогава най-вероятно самите те ще ви кажат в случая да ползвате тривиалния алгоритъм (ако изобщо искат да го имплементирате).

За простота на изчисленията по-нататък можем в допълнителни масиви да си запишем позициите в текста, където "влизаме" или "излизаме" от S₁, S₂ и S₃.

?	Като бонус можете да отбележете, че това може да стане в `byte[]` масив с размер `N`, където пазите битова маска с 6 бита - три за влизания и три за излизания.

Тъй като и двата от дадените по-горе алгоритъма работят за O(N+|S|), и трябва да приложим за трите стринга, то сложността по време за тази подзадача е O(N + |S1| + |S2| + |S3|). Но тъй като ако |Si| > N очевидно задачата няма решение, то можем да кажем, че сложността по време също е O(N).

Сега вече можем да допуснем, че знаем кога влизаме и излизаме от всеки от стринговете. Остана да свършим същинската работа - да намерим най-късия откъс от текста, който съдържа и трите стринга. За тази задача ще приложим техниката на плъзгащия се прозорец. Тя, накратко, е да пазим ляв и десен край на някаква част от текста, които са валиден отговор, и да движим ("плъзгаме") този откъс ("прозорец") надясно, докато стигнем края на текста.

Ще са ни нужни три брояча, които указват колко пъти се среща всеки от трите стринга в текущия прозорец. Очевидно, ако и трите брояча са по-големи от нула, то текущият прозорец е валиден отговор, а в противен случай не е. Така лесно можем да намерим най-късия откъс (демек прозорец), който е отговорът на задачата.

Алгоритъмът накратко: Обхождаме целия текст, символ по символ. Със всеки символ разширяваме текущия прозорец (демек мърдаме десния му край), след което проверяваме дали всички броячи са по-големи от нула. Ако това е така, започваме да мърдаме левия край на прозореца докато това е изпълнено. Преди всяко мърдане на левия край проверяваме дали текущият прозорец е по-къс от най-доброто намерено до сега решение и евентуално ъпдейтваме отговора.

Следва примерна имплементация, в която считаме, че вече сме изчислили два масива bool isBeginningOf[3][N] и bool isEndOf[3][N]. Стойността на isBeginningOf[k][i] е true, ако i-тият символ от текста е начало на срещане на k-тия стринг. Аналогично, isEndOf[k][i] e true ако i-тият символ от текста е край на k-тия стринг.

bool
 isBeginningOf[3
][N],
 isEndOf[3
][N];

int
 shortestTextPart(int textLength) {
    // We assume we've already calculated isBeginningOf[][] and isEndOf[][].
    // Note that we no longer need neither the text, nor the strings.
    int
 ans =
 textLength +
 1
;
    int
 cnt[3
] =
 {0
,
 0
,
 0
};
    for
 (int
 left =
 0
,
 right =
 0
;
 right <
 textLength;
 right+
+) {
        // Update the counters after moving the right window border.
        for
 (int
 k =
 0
;
 k <
 3
;
 k+
+)
            if
 (isEndOf[k][right]) cnt[k]+
+
;
        while
 (left <
=
 right &
&
 cnt[0
] >
 0
 &
&
 cnt[1
] >
 0
 &
&
 cnt[2
] >
 0) {
            // Update the answer, if the current window is better.
            ans =
 min(ans,
 right -
 left +
 1
);
            // Update the counters and move the left window border.
            for
 (int
 k =
 0
;
 k <
 3
;
 k+
+)
                if
 (isBeginningOf[k][left]) cnt[k]-
-
;
            left+
+
;
        }
    }
    // We return the length of the shortest text part, that contains the three
    // strings, or textLength + 1, if the entire text does not contain them.
    return
 ans;
}

Не е толкова очевидно, че сложността на тази функция също е линейна по дължината на текста. Наистина, макар и да мърдаме два итератора (left за лявата граница на прозореца и right за дясната), като и двата се движат между 1 и N, на практика фактът, че left <= right ни гарантира, че не правим повече от 2 * N стъпки.

Забележете, че горната имплементация може сравнително лесно да се модифицира да работи за K стринга (не задължително 3). За да запазим сложността O(N∙K) ще ни е нужен един допълнителен брояч колко от K-те брояча са нула.

Двойки числа в масив

Даден ви е масив A[] с N елемента и число T. Намерете колко на брой различни индекса (i, j) съществуват, така че A_i+A_j ≤ T. Можете ли да се справите по-добре, ако ви питаха колко такива двойки индекси има, за които A_i+A_j == T? За простота можете да считате, че (i, j) е насочена двойка, тоест ако (2, 4) е отговор, то трябва да преброите и (4, 2).

Покажи решението

Тази задача е доста подобна на тройка с нулева сума, с тази разлика, че не можем да ползваме hashset/hashmap за постигане на линейно решение, тъй като от нас се иска да намерим бройката, а не дали просто такава двойка индекси съществува.

Как да се справим с A_i+A_j ≤ T? Първо, както и при много други задачи от интервюта, ще сортираме числата. Ще итерираме с левия индекс надясно и ще местим десния индекс наляво, когато сумата стане > T. Ако знаем, че A[i] + A[j] <= T (за i < j), то очевидно A[i] + A[j-1] <= T, A[i] + A[j-2] <= T .. и т.н., за всеки индекс k, намиращ се между i и j. Съответно, след като сме фиксирали i и сме намерили най-голямото j, с което сумата е <= Т, то можем директно да прибавим към отговора 2 * (j-i) и да продължим със следващото i. Така сложността на решението ни се доминира от сортирането и е O(N∙logN).

В случая с A_i+A_j == T, можем да считаме, че -T ни е първото число от решението на тройката с нулева сума, а A_i и A_j са второто и третото, съответно. Наистина, ако просто прехвърлим T от другата страна на равенството (с обратен знак, разбира се), се получава точно тройка с нулева сума. Тук можем да ползваме hashmap за да пазим на колко различни индекса се среща дадено число. След това, итерирайки всеки индекс, имаме A[i] + X == T. Интересува ни колко на брой числа X има във входния масив -- което е точно нещото, което записахме в hashmap-а! Малък детайл е случаят, в който A[i] е равно на X (примерно входните числа са {2, 3, 2} и T е 4): трябва да внимаваме да не преброим (i, i) към отговора (в дадения пример да отговорим, че съществуват 4 двойки, вместо 2).
Сложността на това решение е O(N), тъй като имаме само две обхождания на входните числа и за lookup ползваме hashmap, чиито операции са константни.

Мажорант

Даден ви е масив с числа. Едно от тях се среща над половината пъти (тоест > 50%). Напишете програма, която намира това число.

Покажи решението

Това е друга известна информатическа задача (задача за намиране на мажорант) с просто, но неочевидно решение. Мажорант наричаме числото, което се среща >50%, ако има такова.

Решението е да ползваме стек. Обхождаме числата от входния масив и за всяко от тях:

Ако стекът е празен, го пушваме на върха;
Ако стекът не е празен:

Ако числото на върха на стека е същото като текущото, пушваме текущото също в стека;
Ако числото е различно, вадим това от върха на стека.

След прилагането на този алгоритъм върху всички числа, ако стекът е празен със сигурност няма мажорант. Ако стекът съдържа поне едно число, то то е потенциален мажорант. Правим ново обхождане на входния масив и проверяваме колко пъти се среща. Ако е > 50%, значи намерихме отговор. Ако е ≤ 50%, значи няма мажорант.

Забележете, че стекът, по всяко време, съдържа нула, една, или повече инстанции на едно и също число. Съответно стек изобщо не ни е нужен -- можем просто да имаме две променливи - едната, означаваща числото в стека, а другата - колко пъти се среща там. Така сложността по време е O(N), а тази по (допълнителна) памет е O(1).

Чупливи Крушки

Имате 20 електрически крушки, които се чупят ако паднат от над определена височина. Също така имате 100 етажна сграда. Как ще намерите от кой етаж се чупят крушките с минимален брой опити?

Покажи решението

Тъй като искаме да минимизираме броя опити, а не броя счупени крушки, оптималната стратегия е да приложим двоично търсене по етажа. Така ще са ни нужни log(100) ~= 7 опита.

Подстринг, съставен от два символа

Даден ви е стринг с дължина N. Намерете най-дългия негов подстринг, съдържащ най-много два различни символа.

Например в стринга "aababbaacacaacacccaabad", един възможен подстринг, съдържащ най-много два различни символа е "aababbaa", започващ от началото на входния стринг. Най-дългият такъв подстринг, обаче, е "aacacaacacccaa", започващ от позиция 6 (индексирано от 0).

Покажи решението

Първия въпрос, който трябва да зададем (и би направил добро впечатление колкото по-рано го зададем) е върху каква азбука ще се работи - ASCII, Unicode, нещо друго? От това зависи много по-нататъшната ни имплементация, затова е хубаво да го знаем още от самото начало. Обикновено интервюиращият би ни попитал защо ни интересува, и как бихме се справили в единия случай и в другия случай.

Първо ще кажем, че ASCII е удобно за задачата, тъй като можем да ползваме всеки символ за индексиране в обикновен масив с 256 елемента. Така, например, ще можем да пазим неща като бройката или последната позиция, на която сме срещали всеки от символите, в даден интервал.

Unicode става малко по-сложно (поради огромния размер на азбуката), но пък за него можем да ползваме хештаблица (или хешмап), постигайки O(1) за lookup и O(N) по памет, тъй като (макар потенциално да има милиони различни символи), входният стринг е с N символа, следователно ще ни се наложи да индексираме най-много N различни символа. That being said, най-често интервюиращият ще ни каже да ползваме ASCII, тъй като опростява много имплементацията, а хендълването на Unicode няма много общо с алгоритъма, който искат от нас - това са просто детайли.

Сега да се захващаме със същинската задача. Тривиалното решение би било за всяка позиция да конструираме подстринг (започващ от нея) с възможно най-голяма дължина. Това решение работи, но е със сложност O(N²).

Вместо това имаме няколко избора как да подходим и да постигнем значителни подобрения. Първият разчита на стандартната техника "метод на плъзгащия се прозорец", която ползвахме и в други задачи (например в задачата Текст и стрингове). В тази задача за прозореца трябва да пазим кои две букви са в него и по колко пъти се срещат. Както обикновено, ползването на плъзгащ се прозорец води до O(N) сложност по време. Примерна имплементация би била:

// Връща началото на подстринга с максимална дължина.
int
 longest2CharSubstring(const
 char
*
 str,
 int n) {
    int
 best =
 0
,
 startAt =
 0
;

    int
 cnt[256
] =
 {0
},
 in =
 0
;
    for
 (int
 left =
 0
,
 right =
 0
;
 right <
 n;
 right+
+) {
        // Вкарваме символа в прозореца и увеличаваме броя различни символи ако е нов.
        if
 (cnt[str[right]]+
+
 =
=
 0)
            in+
+
;

        // Ако имаме 3 (или повече) различни символа в прозореца трябва
        // да го скъсим отляво докато останат само 2.
        while
 (in >
 2) {
            if
 (-
-
cnt[str[left+
+
]] =
=
 0)
                in-
-
;
        }
 
        // Ако текущият прозорец е по-дълъг от най-добрия до сега, ъпдейтваме отговора.
        if
 (best <
 right -
 left +
 1)
            best =
 right -
 left +
 1
,
 startAt =
 left;
    }
    return
 startAt;
}

Забележете, че са нужни минимални промени в горната имплементация за да се справя с по-сложния вариант на задачата "най-дълъг подстринг, съдържащ най-много K различни символа" - единственото, което трябва да променим, е да заменим '2' с 'K'!

Друго решение, което е донякъде по-интуитивно за имплементация, разчита на следното не-толкова-тривиално наблюдение. От входния пример видяхме, че част от стринга може да участва в повече от един потенциален кандидат (това бяха символите "aa", които участваха както в подстринга "aababbaa", така и в "aacacaacacccaa"). В колко най-много потенциални кандидати може да участва даден подстринг (ако считаме, че потенциален кандидат е подстринг, който не можем да увеличим повече нито наляво нито надясно)? Оказва се, че само два. Наистина, тъй като "отляво" има някаква друга буква (в дадените примери 'b'), а отдясно има трета буква ('c'), то няма как да го включим в трети потенциален отговор, тъй като той ще съдържа поне три различни символа.

Така, можем да направим решение, което "уж" е O(N²), но поради даденото свойство се оказва, че разглеждаме всяка буква най-много по два пъти - следователно решението е O(N).

// Връща началото на подстринга.
int
 longest2CharSubstring(const
 char
*
 str,
 int n) {
    int
 best =
 0
,
 startAt =
 0
;

    for
 (int
 i =
 0
;
 i <
 n;) {
        // Казваме, че текущият подстринг ще съдържа символа на позиция i.
        int
 start =
 i,
 end =
 i;
        char
 ch1 =
 str[i],
 ch2 =
 -
1
;

        // Увеличаваме подстринга наляво.
        for
 (;
 start >
 0
;
 start-
-) {
            if
 (str[start -
 1
] =
=
 ch1 |
|
 str[start -
 1
] =
= ch2)
                continue
;
            if
 (ch2 =
=
 -
1)
                ch2 =
 str[start -
 1
];
            else
 break
;
        }

        // Увеличаваме подстринга надясно.
        for
 (;
 end +
 1
 <
 n;
 end+
+) {
            if
 (str[end +
 1
] =
=
 ch1 |
|
 str[end +
 1
] =
= ch2)
                continue
;
            if
 (ch2 =
=
 -
1)
                ch2 =
 str[end +
 1
];
            else
 break
;
        }

        // Ъпдейтваме отговора.
        if
 (best <
 end -
 start +
 1)
            best =
 end -
 start +
 1
,
 startAt =
 start;

        // Следващият потенциален кандидат ще съдържа новия символ str[end + 1].
        i =
 end +
 1
;
    }
    return
 startAt;
}

Допълнително трябва да внимаваме да хендълваме частните случаи като хората - например ако отговорът е целият текст ("ABBA"), и частните случаи на този частен случай - ако текстът е празен стринг, и ако текстът съдържа един единствен различен символ ("eeeeeeeeee").

Винени бутилки

Ели е наследила от баба си (Нора) винарска изба. В нея има N бутилки вино, наредени в редица. За простота ще ги номерираме с числата от 0 до N-1, включително. Техните начални цени са неотрицателни цели числа, които са ни дадени в масива P[]. Цената на i-тата бутилка е дадена в P_i. Колкото повече отлежават бутилките, толкова по-скъпи стават те. Ако бутилка k е отлежала Х години, нейната цена ще бъде X*P_k.

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

Например ако имаме 4 бутилки с цени {P₀ = 1, P₁ = 4, P₂ = 2, P₃ = 3}, оптималното решение би било да продаде бутилките в реда {0, 3, 2, 1} за печалба 1*1 + 2*3 + 3*2 + 4*4 = 29.

Покажи решението

Относително интуитивно, лесно, и грешно решение е винаги да взимаме по-евтината бутилка, като така оставяме по-скъпата да се умножава по по-големи числа. Както се оказва, обаче, това не винаги е оптимална стратегия. Например нека вземем {P₀ = 2, P₁ = 3, P₂ = 5, P₃ = 1, P₄ = 4}. Нашата стратегия би взела бутилките в ред {0, 1, 4, 3, 2} за печалба 1*2 + 2*3 + 3*4 + 4*1 + 5*5 = 49. Оптималният отговор, обаче, се постига при реда {0, 4, 3, 1, 2} и има печалба 1*2 + 2*4 + 3*1 + 4*3 + 5*5 = 50. Този контра-пример ни убеждава, че (дори на пръв поглед добро) алчно решение в случая не е приложимо.

Истинското решение се базира на техниката динамично оптимиране.
Въпросът, който ще формулираме, е "Колко максимално може да спечели Ели, ако най-лявата непродадена бутилка е с индекс left, а най-дясната непродадена бутилка е с индекс right?". И left и right са числа между 0 и N-1, включително, следователно динамичната таблица ще е с размер O(N²). Ето и решението:

const
 int
 MAX =
 256
;
 // Трябва да питаме интервюиращия колко най-много може да е N.

int
 price[MAX],
 n;
int
 dyn[MAX][MAX];

int
 recurse(int
 left,
 int
 right,
 int year) {
    // Вече сме продали всичко.
    if
 (left >
 right) return
 0
;
    // Вече сме запаметили отговора в динамичната таблица.
    if
 (dyn[left][right] !
=
 -
1)
        return
 dyn[left][right];

    // Пробваме да продадем лявата бутилка.
    int
 winLeft =
 recurse(left +
 1
,
 right,
 year +
 1
) +
 year *
 price[left];
    // Пробваме да продадем дясната бутилка.
    int
 winRight =
 recurse(left,
 right -
 1
,
 year +
 1
) +
 year *
 price[right];

    // Запаметяваме отговора и го връщаме.
    return
 dyn[left][right] =
 max(winLeft,
 winRight);
}

Тъй като цените на бутилките са неотрицателни, то очевидно не можем да имаме отговор -1. Затова можем да инициализираме динамичната таблица с memset(dyn, -1, sizeof(dyn); и после да извикаме рекурсията с int ans = recurse(0, N - 1);. В ans получаваме оптималният отговор за всички бутилки.

Скачащи пешки

В някои от клетките на правоъгълна дъска с N реда и M колони са разположени пешки. Във всяка клетка има най-много по една пешка. Пешките могат да бъдат движени по следните правила:

С една клетка надолу или една клетка надясно. Този ход е възможен, ако:
- така пешката не излиза от дъската;
- клетката, където отива, е празна.
"Прескачайки" две пешки надолу или две пешки надясно. Този ход е възможен, ако:
- така пешката не излиза от дъската;
- клетката, където отива, е празна;
- биват прескочени точно две клетки;
- и двете прескочени клетки съдържат пешки.

В момента, в който пешка попадне в долния десен ъгъл (клетката на последния ред и последна колона), тя изчезва. Гарантирано е, че в началото там няма пешка.

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

Покажи решението

Решението на тази задача е хитро и не толкова очевидно, но много лесно за имплементация.

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

Ако има една пешка, момичетата ще я движат надолу и надясно, докато стигнат крайната клетка. Независимо коя движи пешката накъде, броят валидни ходове е винаги един и същ. Така ако броят ходове до крайната клетка се дели на 2, побеждава Крис, в противен случай побеждава Ели.

Ако има две пешки, то те все още не могат да се прескачат, затова развоят на играта е подобен. Лесно виждаме, че независимо коя пешка местят и независимо в коя посока, победителят е предопределен от сумата на броя клетки до крайната позиция на двете пешки по модул 2. Отново, ако сумата се дели на 2, побеждава Крис, в противен случай побеждава Ели.

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

Сега, да видим какво става ако има три (или повече) пешки, и са възможни прескачания. По-специално, да видим какво се случва при прескачане: някоя от пешките се придвижва 3 (вместо 1) позиции надясно или наляво, намалявайки общия брой оставащи ходове до "крайната" празна дъска с 3. При това, рано или късно броят пешки ще стане две или по-малко, или няма да са възможни повече прескачания, в който случай сме в някой от предните варианти.

Нека въведем понятието четност на състоянието. Това дефинираме като сбора на оставащите ходове (без прескачания) на всички оставащи пешки до крайната позиция, по модул две. Така в случая с 0, 1 или 2 пешки, победителят се определя именно от четността на състоянието: Ели ако тази четност е 1 или Крис, ако четността е 0.

Какво прави местенето на пешка с една позиция надолу или надясно? Ами - сменя четността на състоянието! Наистина, тъй като сумата е с точно 1 по-малко, то е логично и четността по модул две да е различна.

А какво, тогава, прави скокът? Хм, отново сменя четността! Наистина, сумата е с 3 по-малко, но три по модул две е 1, което е еквивалентно на това да сме направили единично преместване!

Изненадващото е, че от гледна точка на крайния победител, не само, че посоката (дали мърдаме надясно или надолу) няма значение, ами и това дали мърдаме с 1 позиция, или прескачаме 2 пешки (мърдаме с 3 позиции) също! Победителят е еднозначно определен независимо от ходовете и на двамата играчи.

Проста имплементация:

// board[i][j] съдържа 'X' ако на ред i, колона j има пешка, и '.' в противен случай.
string
 getWinner(char
 board[MAX_ROWS][MAX_COLS],
 int
 numRows,
 int numCols) {
    int
 sum =
 0
;
    for
 (int
 row =
 0
;
 row <
 numRows;
 row+
+) {
        for
 (int
 col =
 0
;
 col <
 numCols;
 col+
+) {
            if
 (board[row][col] =
=
 'X')
                sum +
=
 numRows -
 row +
 numCols -
 col;
        }
    }
    return
 sum %
 2
 =
=
 0
 ?
 "Kriss"
 :
 "Elly"
;
}

Произволен Елемент от Генератор

Даден ви е безкраен генератор на числа. При всяко негово викане той връща произволно число в интервала [-2⁶³, 2⁶³ - 1]. Казано ви е, че известно време ще бъдат теглени числа от генератора, а по някое време ще спре генерирането и вие трябва да върнете случаен елемент от вече изтеглените. Иска се изтегленият елемент да е перфектно случаен, тоест ако са изтеглени N елемента и елемент със стойност X се е паднал K пъти, той да бъде върнат с шанс точно X/N. Можете ли да измислите как да направите това, ползвайки само константна допълнителна памет?

Можете да си представите генератора като списък с неизвестен брой елементи, които не можете да индексирате. Когато генерирането на елементи (слагането им в списъка) спре, трябва да върнете стойността на равно-вероятно избран елемент от списъка.

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

Покажи решението

Основните проблеми в тази задача са следните:

генераторът е безкраен, тоест може потенциално да бъдат генерирани огромно количество числа и въпроси;
можем да генерираме елементите само веднъж;
не можем да запазим елементите (искаме константна допълнителна памет).

Следователно трябва да измислим нещо по-хитро.

Реално решението не е много по-хитро, просто е малко по-сложно да се види защо е вярно.
В началото инициализираме брояч на досега генерираните елементи counter = 0; и заделяме памет за върнатия елемент ret. Очевидно това е О(1) откъм памет. След всеки изтеглен елемент:

Увеличаваме брояча;
С шанс 1/counter присвояваме на ret стойността на току-що изтегления елемент.

Ако в генератора има само един елемент, то той е в ret с шанс 1/1. Ако в генератора е имало два елемента, то всеки от тях е в ret с шанс 1/2 (тъй като на първата стъпка сме взели първия, а на втората с шанс 1/2 сме го сменили с втория елемент). По индукция можем да докажем, че ако сме генерирали N елемента преди да ни зададат въпрос, при ползването на този алгоритъм всеки от тях е в ret с шанс 1/N. Наистина, нека допуснем, че алгоритъмът работи вярно за K елемента (можем да вземем база примерите с 1 и 2 елемента). Тогава, при добавяне на K+1-ви елемент шансът да вземем него е 1/(K+1) (колкото трябва), а шансът да вземем всеки от предходните е шансът да не вземем текущия K/(K+1) умножено по шансът му до сега 1/K, което е точно K/(K+1) * 1/K = 1/(K+1).

Този алгоритъм (и задача) са достатъчно известни да си имат собствена страница в Wikipedia.

Рандом Генератор чрез Монета

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

Покажи решението

Задачата има две решения, като де факто (въпреки че не е много очевидно) едното е еквивалентно на другото.

Първо решение:

Правим „двоично търсене" в интервала. На всяка стъпка разделяме останалия интервал на две равни части. В зависимост от това дали се падне ези или тура, запазваме само лявата или само дясната част от него. Така след определен брой хвърляния останалият интервал ще е толкова малък, че можем да го счетем за едно единствено число (например взимайки средата му).
Нека, например, при ези взимаме лявата страна, а при тура взимаме дясната. Нека също така са се паднали в този ред: ези, тура, ези, ези, тура, ези, тура, тура, тура, ези, тура. Така нашият алгоритъм би стеснявал интервала по следния начин: [0, 1] -> [0, 0.5] -> [0.25, 0.5] -> [0.25, 0.375] -> [0.25, 0.3125] -> [0.28125, 0.3125] -> [0.296875, 0.3125] -> [0.3046875, 0.3125] -> [0.3046875, 0.30859375] -> [0.306640625, 0.30859375]. В крайна сметка можем да вземем просто средата на останалия интервал, в случая 0.3076171875 и да кажем, че това е нашето рандом число. Разбира се, прилагайки повече итерации бихме постигнали значително по-голяма точност.

Друг начин да си представим този метод е по следния начин. В началото образуваме редицата (0.5, 0.25, 0.125, 0.0625, 0.03125, ...), или A_i = 2^-i. За всеки член от тази редица хвърляме монетата и ако се падне тура, го добавяме в сумата (която първоначално е била нула). Ако тази редица е безкрайна резултатното число би било напълно случайно, равномерно разпределено в интервала [0, 1].

Второ решение:

Образуваме двоично число с N бита (при N хвърляния на монетата). Тъй като максималното число, което би могло да се получи при такова генериране е 2^{N - 1}, ако полученото число е било X, то връщайки X / 2^{N - 1} получаваме именно число между 0 и 1, включително. От компютърна гледна точка това е същото като горния метод, с тази разлика, че ако ползваме double за горния модел ще стигнем до ограничение на типа, докато дълги числа във втория вариант биха ни позволили произволна точност.

Имплементационни Задачи

Тези задачи обикновено имат минимално мислене и по-скоро се изисква добро познание от програмните езици и писането на код като цяло. Изисква се писане на код, като почти цялата оценка за задачата зависи от него.

Точна степен на две

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

Покажи решението

Едно от възможните решения тук е:

if
 (X &
&
 !
(X &
 (X -
 1
)))

Ако числото е било точна степен на две, то то има точно един сетнат бит в двоичния си запис. Изваждането на 1 би направило този бит нула, а всички по-младши битове 1-ци. Но побитовия and би ги елиминирал (както и сетнатата единица). Така X & (X - 1) става нула, ако X е точна степен на две. Ако пък числото не е точна степен на 2, то ще има поне още една сетната единица, която ще се запази след операцията and.
Ако не считаме 0 за естествено число можем да премахнем "X &&" от if-а, но горното решение е вярно и за двете разбирания.

Най-нисък бит

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

Покажи решението

Подобно на предходната задача, ще ползваме X & (X - 1) за да премахнем най-ниския бит. Така X - (X & (X - 1)) би ни дало разликата между числото с и без въпросния lowest bit, тоест неговата стойност. Това е и нещото, което искахме да намерим.

Нула или едно

?	Побитови оператори са `{~, \|, &, ^, !, <<, >>}`.

Дадено ви е цяло число X. Съставете израз, съдържащ само X, побитови оператори, и скоби, който се евалюира до true, ако X е нула или едно, и до false в противен случай.

Покажи решението

Едно възможно решение е !(X ^ !!X). Това е еквивалентно на X == !!X, но тъй като нямаме право да ползваме равно, вместо това ползваме факта, че xor на еднакви числа дава нула. Двойно отрицание, от друга страна, дава 0 ако началното число е 0, и 1 ако началното число е което и да е друго.

Умножение по седем

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

Покажи решението

Да умножим числото по 7 е еквивалентно на това да го умножим по 8 и да го извадим веднъж. Тъй като имаме лесен начин за умножение по степени на две (<<, също познато като shift left), бихме могли да представим 7 * X като (X << 3) - X.

Размяна на числа

Как можете да размените две цели числа (например от тип int или long long) без никаква допълнителна памет?

Покажи решението

Това е що-годе стандартен трик с побитови операции. За целта трябва да ползваме, че операцията XOR е обратима чрез себе си - ако имаме XOR-ът две числа X и Y, както и едно от двете, можем да намерим другото като XOR-нем XOR-ът им с това от двете, което имаме.

Така следната функция разменя стойностите на двете числа без да ползва допълнителна променлива (съответно и допълнителна памет):

void
 swap(int
&
 x,
 int
& y) {
    x ^
=
 y ^
=
 x ^
=
 y;
}

Битови под-маски

? За да записваме подмножества на някакво множество със сравнително малък брой елементи (до 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);
    fprintf(stdout
,
 "0\n"
);
}

Рекурсивно решение:

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

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

Всички пермутации

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

Покажи решението

Решение 1 (cheat):

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

Решение 2:

void
 printAllPerms(char
*
 str,
 int n) {
    sort(str,
 str +
 n);
    while
 (true) {
        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 the 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.
        swap(str[swp],
 str[idx -
 1
]);
        sort(str +
 idx,
 str +
 n);
    }
}

Вторият алгоритъм би могъл да бъде оптимизиран на няколко места. Например търсенето на най-малката буква, която е по-голяма от тази на индекса с инверсията може да стане с двоично търсене, тъй като буквите надясно са сортирани (макар и в обратен ред). Също така при внимателно имплементиране на swap-овете не се налага да сортираме буквите надясно всеки път - както казахме, те са сортирани, но в обратен ред. Можем просто да ги reverse-ваме, което става със сложност O(N) вместо O(N∙logN).

Ще има ли препълване?

Имате две unsigned числа A и B. Как бихте проверили дали ще се получи ли препълване (overflow) ако ги съберем?

Покажи решението

if
 (A +
 B < A)
    fprintf(stderr
,
 "There is an overflow!\n"
);

Ползваме това, че сборът на естествени (unsigned) числа винаги е по-голям или равен на всяко от двете числа. Също така тъй като максималният размер на числата е същия като максималния размер на резултата (32 бита, на повечето сегашни компилатори), то при овърфлоу със сигурност резултатът ще е по-малък от всяко от двете числа.

Дълбочина на дърво

Напишете функция, която намира дълбочината на дърво.

Покажи решението

Трябва да отбележим, че щом става дума за "дълбочина", то дървото е кореново (демек насочено). В противен случай то не би имало "дълбочина" ами "диаметър", който се намира с друг алгоритъм (взимаме произволен връх A, намираме най-далечния на него връх B, и накрая намираме най-далечния на него връх C: пътят от B до C е диаметър на дървото).

struct Node {
    vector
 <
Node*
>
 children;
};

int
 depthOfTree(Node* node) {
    int
 ans =
 1
;
    for
 (int
 i =
 0
;
 i <
 (int
)node-
>
children.size();
 i+
+)
        ans =
 max(ans,
 depthOfTree(node-
>
children[i]) +
 1
);
    return
 ans;
}

Сложността на това решение е O(N), където N е броят върхове в дървото. Можем да отбележим, че потенциален проблем на това решение е много дълбоко дърво, в който случай може да получим препълване на стека (тъй като рекурсията ще има твърде много нива).

Масив в спирала

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

Покажи решението

void
 printInSpiral(int
 array[MAX][MAX],
 int
 numRows,
 int numCols) {
    int
 dir[4
][2
] =
 { {0
,
 1
},
 {1
,
 0
},
 {0
,
 -
1
},
 {-
1
,
 0
} };
    int
 row =
 0
,
 col =
 -
1
,
 idx =
 0
;
    while
 (numRows >
 0
 &
&
 numCols >
 0) {
        int
 numCells =
 (idx %
 2
) ?
 numRows :
 numCols;
        for
 (int
 i =
 0
;
 i <
 numCells;
 i+
+) {
            row +
=
 dir[idx][0
],
 col +
=
 dir[idx][1
];
            fprintf(stdout
,
 "%d\n"
,
 array[row][col]);
        }
        if
 (idx %
 2
) numCols-
-
;
 else
 numRows-
-
;
        idx =
 (idx +
 1
) %
 4
;
    }
}

Бързо степенуване

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

Покажи решението

?	Задачи, в които се налага да ползваме логаритмичното (бързо) вдигане на степен, най-често искат отговора по модул (тоест остатък при деление на друго число).

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

Линейно решение:

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

Логаритмично решение:

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

Палиндром 1.0

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

Покажи решението

bool
 isPalindrome(char
*
 str,
 int len) {
    for
 (int
 i =
 0
;
 i <
 len /
 2
;
 i+
+) {
        if
 (str[i] !
=
 str[len -
 1
 - i]) {
            return
 false
;
        }
    }
    return
 true
;
}

Палиндром 2.0

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

Покажи решението

void
 palindromize(char
*
 str,
 int len) {
    for
 (int
 i =
 0
;
 i <
 len /
 2
;
 i+
+) {
        str[i] =
 str[len -
 1
 -
 i] =
 min(str[i],
 str[len -
 1
 -
 i]);
    }
}

Общи елементи на множества

Дадени са ви два сортирани масива. Напишете функция, която отпечатва по веднъж всички елементи, които се срещат и в двата масива. Как бихте решили задачата, ако масивите не бяха сортирани?

Покажи решението

В тази задача има две основни уловки. Първо, трябва да внимавате да не ползвате O(lenA∙lenB) алгоритъм, тъй като съществува далеч по-ефективен O(lenA + lenB) такъв. Второ, трябва да се справяте по подходящ начин с повтарящи се елементи. Много честа грешка е да се напише решение, което е почти вярно, но печата някои от числата по повече от веднъж.

void
 printCommonElements(int
*
 A,
 int
 lenA,
 int
*
 B,
 int lenB) {
    int
 idxA =
 0
,
 idxB =
 0
;
    while
 (idxA <
 lenA &
&
 idxB < lenB) {
        if
 (A[idxA] =
= B[idxB]) {
            fprintf(stdout
,
 "%d\n"
,
 B[idxB+
+
]);
            // Не забравяйте да се справите правилно с повтарящи се елементи!
            while
 (idxB <
 lenB &
&
 A[idxA] =
= B[idxB])
                idxB+
+
;
            idxA+
+
;
        }
        else
 if
 (A[idxA] < B[idxB]) {
            idxA+
+
;
        }
        else {
            idxB+
+
;
        }
    }
}

В несортирания вариант бихме запазили елементите на единия от масивите в hashset, след което бихме минали през елементите на другия и бихме отпечатали тези от тях, които са в hashset-a. Тук е много важно при отпечатване на елемент да го премахнем от hashset-а, за да не го отпечатаме повторно!
Сложността по време отново е O(lenA + lenB), като този път ни трябва и O(min(lenA + lenB)) по памет.

Дигитален корен

Имате число X₀. Ако числото е по-голямо или равно на 10, съберете цифрите му да получите ново число X₁. Ако X₁ е по-голямо или равно на 10 съберете цифрите му получавайки ново число X₂. Продължете тази процедура докато получите едноцифрено число. Това число се нарича "дигитален корен" (digital root) на X₀. Напишете функция int digitalRoot(int X), която намира дигиталния корен на дадено число X.
Бонус: Можете ли да намерите по-бърз начин, по който да го изчислявате?

Покажи решението

int
 digitalRoot(int X) {
    while
 (X >
=
 10) {
        int
 nX =
 0
;
        while (X)
            nX +
=
 X %
 10
,
 X /
=
 10
;
        X =
 nX;
    }
    return
 X;
}

От статията в Wikipedia можем да видим, че digitalRoot(int X) == X - 9 * ((X - 1) / 9). Тъй като е бонус, няма проблем ако не можете намерите този начин - за неговото откриване ви трябва по-скоро математика, отколкото информатика. Зависи за каква позиция кандидатствате все пак би могло да бъде релевантно.

Избор на град според населението му

Напишете функция, която по дадено множество от градове и тяхната популация, избира някой от тях, като шансът даден град да бъде избран е пропорционален на броя жители в него. Например ако градовете са София (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."
;
}

Rock-Paper-Scissors-Lizard-Spock

Rock-Paper-Scissors-Lizard-Spock е интересна модификация на играта "Камък-Ножица-Хартия", в която са добавени гущер и Спок.

Гущерът отравя Спок и изяжда хартията, но бива смачкан от камъка и обезглавен от ножицата. Спок счупва ножицата и прави на пара камъка с бластера си, но бива отровен от гущера и опроверган от хартията.

Представете си, че имплементирате програма, която симулира горната игра. Как бихте направили проверката кой побеждава в дадена битка с най-малко код?

Покажи решението

Ще "пренаредим" възможните форми като "rock", "spock", "paper", "lizard", "scissors", като ще им дадем номера от 0 до 4 (в този ред). Разгледана като цикъл, тази наредба има предимството, че всеки елемент побеждава "левите" два и пада срещу "десните" два.

Нека двете показани фигури са A и B. Ще считаме, че функцията, която искаме да напишем, връща -1 ако A губи, 0 ако са равни, и +1 ако A печели. Ползвайки модулна аритметика и наредбата, която дефинирахме, можем да стигнем до следния код:

int
 getWinner(int
 A,
 int B) {
    return
 A =
=
 B ?
 0
 :
 (A -
 B +
 5
) %
 5
 <
=
 2
 ?
 1
 :
 -
1
;
}

Езикови познания

Това са по-скоро въпроси, които могат да ви зададат по време на интервю. В тях рядко се изисква писане, но трябва добре да познавате езика за програмиране и като цяло различни програмни термини и идиоми.

Каст

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

Покажи решението

"Cast" се използва когато искаме да превърнем някаква променлива в тип, различен от оригиналния й. Например ако искаме да ползваме нецелочислено, вместо целочислено деление на две цели числа, трябва да cast-нем едното към нецелочислен тип. Например int A = 42, B = 5;. A / B би дало 8, но (double)A / B би дало 8.4. Тук "cast"-ваме integer-а A към double.
Най-често се налага да каст-ваме в следните случаи:

Когато при някакви сметки има шанс да се получи overflow, и за да избегнем това, предварително превръщаме променливите в по-голям тип. Обикновено кастваме int към long long, но са възможни и всякакви други.
В обектно-ориентираното програмиране, когато искаме да интерпретираме наследен клас като базов или обратно.
Когато не знаем какъв тип данни получаваме, можем да ползваме аргумент void*, който в последствие cast-ваме към правилния тип.
Имплицитно, когато подаваме аргумент на функция не от типа, който тя очаква, но съществува конверсия (cast), който да превръща аргумента в такъв, какъвто трябва.

Стейтмънт и Блок

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

Покажи решението

Statement обикновено изразява единична операция, например присвояване на стойност, логически оператор (if() без тялото му), цикъл без тялото му (тоест само for() или while() без следващия ги код, който всъщност се изпълнява). От друга страна за block се счита група от statement-и, най-често оградена по някакъв начин (с къдрави скоби в C/C++ и Java; чрез индентация в Python).

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

В горния пример ред 2 (сам по себе си) е statement, както е и ред 6. Ред 2 и ред 3 поотделно също са statement-и, но заедно образува block (тялото на while цикъла). Редове от 2 до 6 също образуват block (тялото на функцията).

Метод и Функция

Каква е разликата между "method" и "function"?

Покажи решението

Функция е парче код, което се извиква чрез неговото име (име на функцията). Възможно е да му се подадат данни, върху които то да работи (наричани аргументи или параметри на функцията), и също така то да върне някакви данни. Всичките данни, които се подават на функцията се подават експлицитно.
Метод, от друга страна, е парче код, което се извиква чрез своето име и е асоциирано с някакъв обект (клас). В повечето аспекти методът е идентичен на функцията, с изключение на две важни разлики:

Имплицитно му се подава обекта, на който принадлежи даденият метод (указателя this);
Има достъп до private данните на класа.

Логически и Бинарни Оператори

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

Покажи решението

Операторите & и | са бинарни оператори (изпълняват операции върху двоични числа), докато && и || са логически оператори (изпълняват операции върху обекти, които се евалюират до true или false).
Пример, в който не са взаимно-заменяеми:

За AND: if(1 & 2) и if(1 && 2): докато първият if не би се изпълнил, то вторият би;
За OR: int A = (5 | 3); би дало стойност на A равна на 7, докато int A = (5 || 3); би дала стойност на а равна на 1.

Препълване

Какво e "overflow"? Дайте пример. Как можем да го избегнем? Как да проверим дали ще се получи препълване при събиране? А при умножение?

Покажи решението

Има два основни вида препълване (overflow) в програмирането: препълване на тип и препълване на някакъв вид памет (най-често стека).
Първият тип се получава, когато се извършва дадена операция между (да кажем) две числа и резултатът от тях е твърде голям да се запази в същия тип. Много прост пример за това е следният код:

int
 A =
 2121212121
;
int
 B =
 2121212121
;
fprintf(stdout
,
 "%d\n"
,
 A +
 B);

Макар и A и B да съдържат числа, които се събират в 32-битов int, тяхната сума вече надхвърля лимита от 2³¹-1 и отпечатаното число няма да бъде очакваното 4242424242. Нещо повече, резултатът от събирането на две положителни числа би бил отрицателно такова!

Можем да го избегнем ако знаем предварително (а много често ще знаем) в какви граници могат да бъдат съответните числа - в такъв случай можем да ползваме по-голям тип или поне да извършваме изчисленията, каствайки някое от числата към по-голям тип. В случая, например, fprintf(stdout, "%lld\n", (long long)A + B); би работело.

Възможни проверки дали ще се получи овърфлоу при събиране и умножение:

bool
 testSumOverflow(int
 A,
 int B) {
    if
 (A <
=
 0
 &
&
 B <
=
 0
 &
&
 A +
 B >
 0)
        return
 true
;
    if
 (A >
=
 0
 &
&
 B >
=
 0
 &
&
 A +
 B <
 0)
        return
 true
;
    return
 false
;
}

// Works, more or less.
bool
 testMulOverflow(int
 A,
 int B) {
    return
 (A !
=
 0
) &
&
 (2147483647
 /
 abs(A) <
 abs(B));
}

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

Другият тип овърфлоу (stack overflow) коментираме в следващата задача.

Програмен Стек

Какво е "program stack"? Кои данни попадат там? Дайте пример за проблем, свързан с програмния стек, който често възниква в практиката.

Покажи решението

В C++ поне програмният стек е паметта, която е заделена за временни данни: локални променливи, аргументи на функция (които са пак един вид локални променливи), памет, нужна за менажирането на функции и други. Програмният стек обикновено е реализиран като парче памет (обикновено 1 мегабайт под Windows и 4 мегабайта под Linux), и указател (stack pointer) кой е следващият свободен байт "на върха на стека". Така паметта от стека е винаги изцяло заета (не се получават дупки) в началото и изцяло празна в края.

Проблем се получава ако имаме повече локални (нестатични) данни, отколкото е размерът на стека - например имаме обявен голям масив в тялото на функция, или имаме рекурсия, която дълбае много нива навътре. Тогава stack pointer-ът почва да сочи памет извън определената за стека и програмата ни се опитва да достъпи данни, които не задължително са наши -- което или води до терминиране на програмата ни от страна на операционната система, или намазва други от данните ни, което води до много трудни за дебъгване проблеми.

Повече информация за програмния стек има в темата за рекурсия и търсене с връщане.

Рекурсия

Какво е "recursion"? Дайте пример. За какво се ползва? Какъв проблем се среща при рекурсия с много нива? Можете ли да обясните и дадете пример какво е "опашкова рекурсия" (tail call optimization)?

Покажи решението

Най-доброто обяснение на рекурсия ще видите като цъкнете тук.

(сега сериозно, за проблемите при рекурсията и за опашковата рекурсия вижте тази тема)

Числа с Плаваща Запетая

Какво са "floats" или "floating point numbers" (числа с плаваща запетая)? Колко големи числа могат да съхраняват те? Какви чести проблеми възникват при тях и защо?

Бонус точки: как се представят вътрешно и как точно работят те?

Покажи решението

Числа с плаваща запетая са специални променливи (които се обработват в специална част на процесора и имат собствени регистри), предвидени за работа с нецели числа. В C++ стандартните типове floating point числа са 32-битов (float), 64-битов (double) и (неофициално) 80-битов (long double).

Помните ли от училище Числото на Авогадро (количество частици в 1 мол)? Не? Окей, това е константата 6,023×10²³. Накъде бия с това? Забелязвате ли означението (+/-)XXX*YYY^ZZZ? Е, числата с плаваща запетая работят по същия начин: имат 1 бит за знак, няколко бита за XXX и няколко бита за ZZZ - като YYY е константата 2 (все пак компютрите са двоични, а не десетични), а XXX и ZZZ са цели числа.

Реално разликата между float, double, и long double е само в това по колко бита са заделени за всяко от тези две числа (наричани мантиса и експонента).

Числата с плаваща запетая "уж" могат да поддържат много голям интервал от числа, но реално има стойности близки до нулата, които не могат да бъдат представени точно. Наистина, най-голямата double стойност е в порядъка на 10³⁰⁸), но реално поддържа само (около) 2⁶⁴ различни стойности -- нещо сметките не излизат, нали?

Можем да си представяме стойностите, които double поддържа като (около) 2⁶⁴ различни числа, концентрирани около нулата и ставащи все по-нарядко, колкото повече се отдалечаваме от нея.

Чести проблеми с floating point е това, че в зависимост в какъв ред извършваме дадени операции, може да получим различни (макар и с много малко) отговори в следствие на неточността (липсващите числа) при тях.
Прост пример е:

double
 A =
 42.0
 /
 15.0
 *
 693.0
;
double
 B =
 42.0
 *
 693.0
 /
 15.0
;
fprintf(stdout
,
 "%s\n"
,
 A =
=
 B ?
 "Yey!"
 :
 "Nah ;("
);

Очаквате да отпечата "Yey!"? Уви, печата се "Nah ;(", като точните стойности са:

A =
 1940.399999999999900
B =
 1940.400000000000100

Static (C++)

За какво служи запазената дума "static" в езика C++? Дайте пример за какво бихте я ползвали.

Покажи решението

Инфо тук, но е малко outdated и зле написано.

Inline (C++)

За какво служи запазената дума "inline" в езика C++? Дайте пример за какво бихте я ползвали.

Покажи решението

Инфо тук, но е малко outdated и зле написано.

Абстрактен клас (C++)

Какво е Абстрактен Клас в C++ и как можем да дефинираме такъв?

Покажи решението

Абстрактен клас е клас, от който искаме да не можем да създаваме инстанции - той служи само като "шаблон" за имплементация от подкласове - много сходно с интерфейсите в Java.
Можем да дефинираме абстрактен клас като направим поне един от методите му да е "равен на нула": void func() = 0;.

Изтрита Функция (C++)

Какво прави func() = delete; в C++?

Покажи решението

За разлика от func() = 0;, което разгледахме горе, func() = delete; в C++ указва на компилатора да не създава дефолтна имплементация. Например, можем да ползваме за да укажем компилаторът да не създава дефолтен конструктор или да лимитираме копирането на базов клас (като изтрием operator=, например), но все пак да оставим възможността да създаваме инстанции от него.

Друга употреба е да забраним извикването на функция с неправилен тип (премахване на автоматични overload-и) - например ако искаме дадена функция да се вика само с double аргумент, но не и такъв с по-малка точност, например float можем да направим:

void
 func(double num) {
    // Do something
}
void
 func(float
 num) =
 delete
;

Пробвайки да извикаме функцията с аргумент променлива от тип float получаваме грешка при компилация.

Hoisting

Какво е "Hoisting"?

Покажи решението

Hoisting е вид scoping механизъм (главно за Javascript, но понякога се ползва и в други езици) при който локални променливи могат да бъдат достъпвани още преди декларацията си, стига да го правим в същия scope (примерно, тяло на функция), в който биват декларирани. Нещо много подобно имаме и прилокалните (не-global) променливи в Python.

Масиви

Какво е "array" (масив)? Как е реализиран той в езика, който ползвате? Как работи индексацията на определена клетка от масив? А от многомерен масив?

Покажи решението

Инфо тук.

Върнати Стойности

Посочете различни начини, по които бихте могли да върнете две или повече променливи от функция/метод.

Покажи решението

Някои от начините са, примерно:

STL pair(s)
пакетирани в структура;
заделени преди викането на функцията и подадени указатели/референции към тях;

Баба Цеца

Обяснете ползите от BABA CECA (или в английския вариант - DEAD BEEF (мъртво говеждо)) в програмирането.

Покажи решението

0xBABACECA и 0xDEADBEEF са валидни 16-тични числа и биват ползвани като константи в кода - обикновено за обозначаване на невалидно/специално състояние.

Обратно Повикване

Какво е "callback" (обратно повикване)? За какво се ползва?

Покажи решението

Колбек е функция, която се изпълнява след настъпване на желано събитие или състояние. Обикновено "вързваме" callback функцията към някакъв асинхронен хендлър (примерно нещо, което чака информация от сървър). След като чаканото събитие се случи (информацията пристигне) се вика callback функцията.

Понякога има специални callback функции (наричани errback), които се викат ако желаното събитие не настъпи за определен период от време или възникне грешка преди тяхното случване.

Копиране при Писане

Какво е "copy on write" (копиране при писане)? За какво помага то? Как бихте го имплементирали?

Покажи решението

Copy-on-write е техника за менажиране на ресурсите (паметта, променливите), при която при присвояване на един елемент на друг (разбирайте A = B) копирането не се извършва директно, а се отлага до извършване на промяна на данните. До тогава A е само псевдоним на B, като така се спестява паметта, която би заела копието, а също така и времето за извършване на копиране. Реално копиране се извършва чак ако се наложи промяна на стойността на A или B - до тогава те сочат една и съща памет.

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

Странен бъг

?	Ако този код случайно не крашва при вас, увеличете броя генерирани числа в началото на `main()` функцията.

Следният относително простичък код имплементира строене на двоично дърво за търсене (и печатането му в ред ляво-корен-дясно).
Имплементацията е вярна... ако изключим това, че crash-ва. Още по-фрапантното е, че ако разкоментираме tree.reserve(values.size()); кодът магически спира да има проблем. Можете ли да откриете какъв е проблемът?

Покажи решението

Задачата е misleading, в смисъл такъв, че най-вероятно повечето (всички?) от вас, както и ние с Румен, са тръгнали да търсят бъга в логиката или синтаксиса на кода (въпреки че изрично е казано, че имплементацията е вярна). Реално проблемът не е в самия код, ами в начина, по който работи C++ и неговата стандартна библиотека. По-специфично, как работи operator= и STL-ския vector.

Нека погледнем следните два реда, в които се вика рекурсията:

tree[curNodeIdx].left =
 buildTree(L,
 idx -
 1
);
tree[curNodeIdx].right =
 buildTree(idx +
 1
,
 R);

Какво се случва в тях? На елемента от вектора tree с индекс curNodeIdx слагаме лявото и дясното дете да са съответно индексите на върховете, в които продължава дървото (или -1, ако няма такива). По-интересното е обаче, че за да намерим тези индекси, викаме рекурсивно buildTree(), където дървото се разраства още (добавят се нови върхове към него, стигайки до листата). При разрастването на vector-а, обаче, се заделя ново, двойно по-голямо парче памет, съществуващите елементи се преместват там и старата памет се освобождава. Когато това стане, обаче, референцията към int-a tree[curNodeIdx].left вече ще е невалидна - тази променлива ще е преместена в друга памет (поради вече споменатото разширение на вектора). Така ние ще се опитаме да променим паметта, където е била тази променлива преди да извикаме рекурсията, но вече сме освободили (или по-скоро vector-ът е освободил). Това води и до Runtime Error-а, с който крашва програмата ни.

От друга страна, ако още в самото начало си резервираме паметта, която ще ни е нужна, няма да се налагат resize()-и на вектора и съответно този проблем няма да се случва. Затова и ако разкоментирате

//tree.reserve(values.size());

кодът магически тръгва.

Дизайн Въпроси

Този тип задачи тества колко добър дизайн бихте предложили в разработката на средно-голям проект. Допълнително, интервюиращите виждат дали сте били достатъчно любопитни да се запитате как работят някои от нещата, които ползвате всеки ден. Не се изисква писането на код, но може да се рисува/чертае модел на интеракция между различни части от проекта. Няма да даваме примерни решения, тъй като тук има много поле за изява (а и самите решения се очаква да са в рамките на 30-40 минутна дискусия с интервюиращия), но все пак ето няколко примерни въпроса.

Автоматично Допълване

Как бихте направили система, която предлага автоматично допълване на това, което потребителят въвежда?

Организатор на Игри

Как бихте направили система, която приема заявки за игра на тенис на маса от работници в голяма фирма и сформира четворки за игра? Хората могат да се записват и отказват по всяко време през работния ден. Какви потенциални проблеми могат да възникнат?

Торент Клиент

Как бихте направили Торент Клиент?

Текстов Редактор

Как бихте направили текстов редактор? Какви неща биха били полезни в него? Какви проблеми може да има?

Тестване на Калкулатор

Как бихте тествали калкулатор?

Съкращаване на URL-та

Как бихте направили сайт за съкращаване на URL-та (URL-shortener)? Пример за такъв туул е goo.gl.

Нестандартни задачи

Това са малко по-различни логически задачи, които тестват как разсъждавате и колко добре бихте апроксимирали нещо, за което нямате много информация, само изхождайки от логика и частични факти. От няколко години вече не се задават по повечето интервюта, тъй като са твърде нестандартни и често пропускат добри кандидати.

Задачата с Голф Топките

Колко топки за голф могат да се съберат в автобус?

Покажи решението

Както и при други подобни задачи, тук се иска да ползвате логика в изчисленията си, като се очаква отговорът ви да е в рамките на няколко пъти от истината.
Първият много важен въпрос е: "Какъв автобус?". Това е нещо, което интервюиращият трябва да ви каже. За целите на задачата приемаме, че това е автобус 94 (или 280) - дълъг двоен автобус, движейки се между студентски град и част от университетите в София.
Аз лично бих игнорирал разстоянието, което остава между топките, тъй като то би било по-малко от запълненото разстояние - тоест игнорирайки го ще получим отговор, който е не повече от два пъти по-голям (реално доста по-малко от това).
Така, обаче, много опростяваме останалите сметки - ако намерим колко е вместимостта (като обем) на автобуса, и колко обем заема всяка топка, то броят топки ще можем да намерим с просто деление.
Дължината на автобуса е някъде между 15 и 20 метра, ширината е между 2 и 3, а височината (вътре в автобуса) около 2. Така обемът е между 60 и 120 кубични метра. Забележете, че така имаме максимална неточност от още 2 пъти.
За нашите изчисления ще вземем средната стойност на границите, които си дадохме (17.5 метра дължина, 2.5 метра ширина и 2 метра височина) получавайки обем 87.5 кубични метра, или за по-голямото удобство можем да работим в сантиметри: 1750см * 250см * 200см = 87,500,000 кубични сантиметра.
Голфът не е особено популярна игра в България. На око ще допуснем, че диаметърът на топката е 5 см. Така изчислявайки обема по формулата V = 4/3 * pi * r^3 получаваме около 65.5 кубични сантиметра на топка.
Извършвайки делението, получаваме краен резултат 1,335,877 топки.
Разбира се, вътре в автобуса има седалки, които заемат част от пространството, но, отново, разликата в отговора заради тях ще е значително по-малка от грешката, която получаваме заради апроксимацията на размерите на автобуса и особено на топките. На интервю би било хубаво да се обосновете защо игнорирате нещата, които игнорирате - иначе интервюиращите ще счетат, че просто не сте се сетили за тях, макар и да са неща, които не променят отговора особено.

Задачата с Бензиностанциите

Колко бензиностанции има в България?

Покажи решението

Както и при други подобни задачи, тук се иска да ползвате логика в изчисленията си, като се очаква отговорът ви да е в рамките на няколко пъти от истината.
Моето решение би се базирало на това, че броят бензиностанции е що-годе пропорционален на населението (или дължината на пътищата, но тя е по-сложна за смятане).
За целта, взимаме някое населено място, за което знаем броя жители и по-важното - знаем броя бензиностанции почти точно. Тук трябва да направим компромис - колкото по-голямо е населеното място, толкова по-трудно е да знаем колко бензиностанции има. Добри примери са някой от що-годе големите (но не най-големите) градове в България (50-150 хиляди души) или квартал на София (те имат що-годе същия брой жители).

Да кажем в Благоевград има 10-тина бензиностанции и 70,000 души. Дианабад (където живея) има 4 бензиностанции и около 30,000 души. Едното дава 70,000 / 10 = 7000, а другото 30,000 / 4 = 7500 души на бензиностанция. Що-годе близки показания.
Смятайки за цяла България, 7,000,000 / 7,000 = 1,000 бензиностанции (в населени места). Разбира се, трябва да включим и някаква допълнителна бройка за бензиностанциите извън населените места - магистрали и главни пътни артерии, които са по-трудни за изчисление, но почти със сигурност ще са над 100 и почти със сигурност ще са под 500 - тоест добавяйки средно-аритметичното 300 ще сме с най-много около 20% off.
Така отговорът ми излезе 1300, но за съжаление не можах да намеря официална информация за това. Някой ако знае да ми пише :)

Update: Някой ми писа! Благодаря страшно много за линка: http://fuelo.net/gasstations. Оказва се, че съм бил относииително близо (под 30% офф, в момента са 1656 според данните на този сайт).

Задачата с Блендера

Смалени сте до размерите на монета от 20 стотинки. Попаднали сте в блендер, който след 60 секунди ще започне да се върти. Как ще се спасите?

Покажи решението

Ще скочите. Ако смаляването запазва плътността ви, би трябвало теглото ви да намалява по-бързо отколкото силата на мускулите ви. С други думи, ако сте смалени 100 пъти, силата на мускулите ви ще е 1/10000 от нормалната, но теглото ви ще е 1/1000000 от сегашното, така че реално ще сте 100 пъти по-силни, или поне ще можете да скачате 100 пъти по-високо!

Задачата с Шахтите

Защо капаците на уличните шахти са кръгли?

Покажи решението

Защото шахтите са кръгли. А причини те да са кръгли има няколко.
Една от тях е, че кръгът е единствената фигура, която не може да влезе сама в себе си след завъртане. Така капакът на шахтата не може да падне в самата шахта. От друга страна, например квадрат, правоъгълник или елипса могат.

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

Въпрос за Живота, Вселената и Всичко Останало

Какъв е отговорът на въпроса за живота, вселената и всичко останало?

Покажи решението

Референции

Careercup - сайт за подготовка за интервюта
InterviewStreet - сайт за подготовка за интервюта
Glassdoor - сайт за подготовка за интервюта
How We Hire (Google) - насоки
Get that job at Google - още насоки

Страницата е посетена 115564 пъти.

Задачи от Интервюта

Списък със задачите

Алгоритмични задачи

Имплементационни задачи

Езикови познания

Дизайн въпроси

Нестандартни задачи

Алгоритмични Задачи

Имплементационни Задачи

Езикови познания

Дизайн Въпроси

Нестандартни задачи

Референции

Предложете корекция