Skip to content

Latest commit

 

History

History
executable file
·
112 lines (68 loc) · 7.2 KB

interview-tasks.md

File metadata and controls

executable file
·
112 lines (68 loc) · 7.2 KB
Raw

Задачи с собеседований

Собрано в интернете. Задачи выстроены по увеличению сложности. Помни, что вместо попытки выучить решение задач лучше перечитать мануал по PHP. Если язык не указан, решать можно на любом.

Два наибольших числа

Дан массив чисел, найдите 2 наибольших.

Подвох: в массиве [1, 2, 2, 2, 3, 3] надо вернуть числа 2 и 3. Подвох: массив может содержать 0 или 1 элемент.

Угол между стрелками

Дано время в виде строки, например '12:30'. Найдите угол между часовой и минутной стрелкой на часах, показывающих это время.

  • для '12:00' это будет 0°
  • для '15:20' или '3:20' это будет 20°
  • для '12:30' будет 165°
  • для '10:50' это будет 25°
  • я считал цифры выше почти что в уме так что мог ошибиться.

Сортировка

Дан массив чисел, отсортируйте по возрастанию без использования стандартной функции sort() и подобных.

Помощь: алгоритмы сортировки wiki, анимация алгоритмов сортировки, бенчмарк алгоритмов

Совет: самый простой (хоть и неэффективный) метод — сортировка пузырьком.

Дерево

Дан массив элементов. Каждый элемент имеет следующие параметры:

  • id — уникальный числовой идентификатор
  • parentId — идентификатор родителя, если таковой имеется, иначе null
  • text — текст.

Необходимо вывести элементы в виде дерева (дерево — это структура, где у каждого узла может быть от нуля до бесконечности детей, и есть один корневой узел, из которого дерево «растет», вики ). Вот пример массива:

$templates = array(
    array("id" => 1, "parentId" => null, "text" => "Первая строка"), 
    array("id" => 2, "parentId" => 3,    "text" => "Вторая строка"), 
    array("id" => 3, "parentId" => 1,    "text" => "Третья строка"),
    array("id" => 4, "parentId" => 1,    "text" => "Четвертая строка"),
    // ...
);

Вот как выглядит дерево:

Первая строка    
    Третья строка
        Вторая строка
    Четвертая строка
        ...

Подвох: хотя тут написано «вывести дерево», на деле деревьев может быть несколько, если в массиве есть несколько узлов-корней с parentId равным null.

Баланс весов

Дана последовательность целых чисел. Считая их массами имеющихся в наличии предметов, определить, можно ли все эти предметы положить на весы так, чтобы весы находились в равновесии. Вывести вариант расположения.

Определить, можно ли из них отобрать какое-то количество предметов с суммарным весом 100 (вывести yes или no, в зависимости от результата).

Пример входных данных:

2 3 4 5 6

Пример выходных данных:

2 3 5 - 4 6
no

Минимальное расстояние

Дан набор из N точек на плоскости (для простоты можно считать, что у всех точек целочисленные координаты). Найдите минимальное расстояние между двумя точками из этого набора.

Пример входных данных:

10 10
20 10
20 15

Пример выходных данных:

5

От Ecwid

https://github.com/Ecwid/new-job

Шарики

Есть 2 абсолютно одинаковых (в том числе по прочности) стеклянных шарика и многоэтажный дом. Ты можешь ходить по дому и сбрасывать шарики с любого этажа. Вопрос, как определить высоту, с которой начинают разбиваться шарики, за минимальное число попыток (я кстати не смог найти самое оптимальное решение).

Учти, что тебе могут попасться как 2 одинаково хрупких шарика, которые разобьются на первом же этаже, так и 2 шарика из кобальтового стекла, которые пробивают асфальт на полметра, а сами не бьются. Задача — найти оптимальный порядок бросания шаров.

Решение потребует написания некоторого количества формул.

Знаменитость (яндекс)

В множестве из n человек каждый может знать или не знать другого (если A знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой матрицей n × n. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет.

Сложность по времени — O(n), сложность по памяти — O(1).

Из Яндекса

Вот еще задачки с собеседований, на JS/HTML: http://company.yandex.ru/job/vacancies/devint_kinopoisk.xml

Вот тоже неплохие задачки: http://download.yandex.ru/company/shad/exam.pdf