Главная

Apple: Задачки с интервью

Как пройти собеседование в крупную IT-компанию.

Поделиться:
 

8+

В этой статье мы разберём много задачек, которые могут попасться на интервью при устройстве на работу программистом. Я, в свою очередь, буду давать описание задачи, а затем покажу вам ее решение. Также я разберу основные концепции, которые лежат в основе той или иной задачи.

Решая эти задачи, вы получите опыт и бесценные знания. Использовать мы будем язык программирования JavaScript.
Окей, начинаем.

Задачка № 1

Реализуйте программу, которая в качестве аргумента принимает функцию fи интовое(целочисленное) значение n. Суть программы заключается в том, что она вызывает функцию f каждые n миллисекунд.

Решение

  • Я буду использовать встроенную функцию setTimeout. Если у вас есть более грамотное решение, то можете воспользоваться им.

Задачка № 2

Реализуйте очередь, используя два стека. Напомню, очередь представляет собой структуру данных FIFO (первым зашел, первым вышел, с англ. first in first out) со следующими методами: enqueue, который ставит элемент в очередь, и dequeue, который удаляет элемент из очереди.

Решение

Прежде всего, надо инициализировать пустую очередь с двумя стеками. PS. Массив в Javascript может вести себя так же, как и стек.

Далее необходимо вставить элемент в очередь.

Затем удалить элемент из очереди.

Наконец, давайте попробуем все протестить.

Задачка № 3

Предположим, у вас есть таблица умножения, которая равна N на N. То есть двумерный массив, в котором значение в i-й строке и j-м столбце равно (i + 1) * (j + 1) (если индексы начинаются с 0) или i * j (если индексы начинаются с 1).
Есть два целых числа N и X. Напишите функцию, которая возвращает, сколько раз X появляется как значение в таблице N на N.
Например, если N = 6 и X = 12, функция должна вернуть 4, поскольку таблица умножения выглядит следующим образом:

Число 12 встречаться в таблице 4 раза.

Решение

Задачка № 4

По заданному дереву найдите самое большое дерево / поддерево, которое является BST(Binary Search Tree).
Для данного дерева верните размер самого большого дерева / поддерева, которое является BST.

Решение

Вот решение с временной сложностью O(N) и пространственной сложностью O(d).
mostBB(), возвращает наибольшее дерево/поддерево, которое является BST.

ФункцияsizeOfLargestBST(), возвращает размер самого большого дерева / поддерева, которое является BST.

Функция constructor() для инициализации класса BSTInfo.

И наконец, функция BSTHelper(root), которая возвращает информацию о самом большом дереве / поддереве, которое является BST.

На этом пока закончим. Надеюсь, вам было полезно и очень интересно!

Спасибо!

8+