Търсите работа като програмист в Яндекс? Първо преминете онлайн Яндекс тест! Ето шест задачи, които ми се паднаха. Представям и моите решения. Може да бъдат полезни на някого 🙂
Съдържание
скрия
Броят на прости числа, по-малки от n.
Опишете с думи алгоритъма за решаване на задачата.
Вход: естествено число n
Изход: брой на прости числа, по-малки от n.
Решението трябва да бъде изчислително ефективно.
Решение:
Сред алгоритмите за намиране на прости числа, по-малки от дадено естествено число n, алгоритъмът „Решето на Ератостен“ е изчислително ефективен. Основната идея на алгоритъма е, че дадено число k е просто, ако не се дели на нито едно просто число, по-малко от k.
Създаваме поредица от естествени числа, подредени във възходящ ред, от 2 до n-1 включително. Поредицата започва с 2, тъй като 1 не е просто число. Числото n не е включено в поредицата поради условието на задачата.
Обхождаме последователно всички елементи на поредицата. Ако елементът от поредицата е различен от нула, нулираме всички елементи на поредицата, кратни на този елемент.
Отговорът на задачата е броят на останалите ненулеви елементи в поредицата.
Сортиране на масив от ASCII символи по азбучен ред за линейно време.
Даден е неподреден масив от печатни ASCII символи.
Опишете с думите си (без код и псевдокод) алгоритъм за сортиране, който позволява да се подреди този масив по азбучен ред за линеен времеви период.
Необходимо е да се опишат действията на всеки етап от алгоритъма.
Да, възможен е стабилен вариант на такъв алгоритъм за сортиране.
Решение:
В ASCII таблицата печатаемите символи вече са сортирани по азбучен ред. В зададения ненареден масив символите могат да се повтарят.
Създаваме масив от нули с големина, равна на броя символи в ASCII таблицата. Индексацията на масива започва от нула.
Обхождаме зададения ненареден масив. Увеличаваме стойността на елемента на създадения масив с 1, чиято индекс е равен на кода на символа от ненаредения масив. С други думи, в създадения масив ще се съхранява броят на намерените символи от зададения ненареден масив.
Отговорът на задачата ще бъде изведен като масивът, който сме създали, като кодът на изведения ASCII символ е равен на индекса на елемента на масива, а броят (колко на брой) на изведения ASCII символ е равен на стойността на елемента на масива.
Максимум в сортиран и циклично изместен масив
Даден е масив от неповтарящи се числа, който е сортиран и след това циклично изместен с неизвестен брой позиции.
Опишете алгоритъм за намиране на максимума в този масив без използване на код или псевдокод.
Оценете сложността на предложения алгоритъм.
Ще се промени ли сложността, ако масивът съдържа повтарящи се числа?
Решение:
В условието на задачата не е посочено дали началният масив е сортиран във възходящ ред или в низходящ ред. Посоката на сортиране се определя чрез сравнение на първите елементи на масива. Сложността е О(1).
Предполагаме, че масивът е сортиран във възходящ ред. Ако лявата граница на масива е по-малка от дясната граница, тогава изместването е нула и максимумът е дясната граница.
В противен случай прилагаме двоично търсене. Рекурсивно. Т.е. ще разделим масива на две половини. Ако в двете половини на масива лявата граница е по-малка от дясната, тогава максимумът е по-голямата от двете дясни граници.
В противен случай продължаваме да работим с половината на масива, при която лявата граница е ПО-ГОЛЯМА от дясната граница. Ще продължим да разделяме масива на две половини, докато и двете половини не станат с по два елемента. Там, където лявият елемент е по-голям от десния, левият е максимумът.
Сложността на двоичното търсене е логаритмична, т.е. О(log n).
Ако числата в зададения масив се повтарят, двоичното търсене все още е подходящо, т.е. сложността на алгоритъма няма да се промени.
На първата стъпка ще се добави проверка за равенство на лявата и дясната граница на масива. А в тялото на рекурсията ще се добави условие: ако една половина на масива има лява граница, която е по-малка от дясната, а другата половина на масива има лява граница, която е равна на дясната – това е максимумът.
Яндекс тестване. Напишете регулярен израз.
Напишете регулярен израз, който позволява да се извлекат всички редове, отговарящи на условията:
Състоят само от букви
Едната и само една от буквите е главна.
Примерни низове, които могат да бъдат маркирани с израза:
„Майка“,
„кола“,
„гъба“,
‘Ябълка’, ‘ябълка’, ‘ябълка’, ‘ябълко’, ‘ябълко’, ‘ябълко’
Примерни низове, които не трябва да бъдат маркирани с израз:
„агент007“ – съдържа цифри
„стриж“ – само малки букви
„ГТО“, – повече от една главна буква
„Три богатыря“ – съдържа интервал, допустими са само букви“
Решение:
^[a-zа-яё]*[A-ZА-ЯЁ]{1}[a-zа-яё]*$Дали дървото е двоично дърво за търсене?
Даден е указател към корена на двоично дърво. Опишете с думи алгоритъм, който ще върне True, ако дървото е двоично дърво за търсене, и False, ако не е.
Върхът на дървото съдържа целочислена стойност (value) и два указателя към поддървета (left и right).
Като C езикова структура, това може да бъде записано по следния начин:
struct node {
int value;
node* left;
node* right;
}Решение:
Трябва да се реализира рекурсивна функция, която получава за текущия възел минималната и максималната стойност от неговия ляв наследник (ако има такъв), проверява дали стойността на текущия възел е по-голяма от максималната стойност на лявото му дете, т.е. лявото поддърво е отляво. Получава за текущия възел минималната и максималната стойност от неговия десен наследник (ако има такъв), проверява дали стойността на текущия възел е по-малка от минималната стойност на дясното му дете, т.е. дясното поддърво е отдясно.
Ако някое условие не е изпълнено, функцията връща False, т.е. дървото не е двоично дърво за търсене.
Функцията връща минималната и максималната стойност, ако няма наследници, които са равни на стойността на текущия възел. В противен случай, минималната връщана стойност е минималната стойност на лявото дете, а максималната връщана стойност е максималната стойност на дясното дете.
Ако текущият възел е корен и всички условия са изпълнени, функцията връща True, т.е. дървото е двоично дърво за търсене.
Тестване на Яндекс. Напишете SQL заявка.
В релационната база данни има таблиците:
Градове – списък на градове.
id – първичен ключ
name – име
population – население
founded – година на основаване
country_id – идентификатор на страната
Държави – списък на страни.
идентификатор – първичен ключ
име – название
население – численост на населението
БВП – брутен вътрешен продукт в долари
Компании – компании
идентификатор – основен ключ
име – наименование
град_ид – град, в който се намира централата
годишен_приход – годишен приход в долари
трудови_ресурси – брой служители
Постройте таблицу, която да изчисли броя на компаниите, отговарящи на условията, за всяка държава:
1) Седалището на компанията се намира в тази страна. 2) Броят на служителите на компанията е поне 1000 души.
Решение:
SELECT Countries.*, COUNT(CASE WHEN Companies.labors>=1000 THEN 1 ELSE NULL END) AS NumOfCompanies FROM Countries LEFT JOIN Cities ON Countries.id=Cities.country_id LEFT JOIN Companies ON Cities.id=Companies.city_id GROUP BY 1Изводи
Ето е онлайн тестване на Яндекс, което се предлага преди интервюто за позицията на Разработчик-оценител в Яндекс. Моля, оставете критики и въпроси за решенията в коментарите. Успех на всички!
Коментари