Вопросы на собеседовании #6

Попробую сгрести интересные и достаточно простые задачи, некоторые относятся к типу "out of the box", некоторые решаются с помощью простой математики.

1. Про торт

Задача: Как поделить торт на 8 равных частей 3мя разрезами?

Делим на 4 части двумя разрезами перпендикулярно друг другу. А дальше есть как минимум 2 варианта продолжения:

  • Ставим кусочки друг на друга и режем их пополам одним разрезом
  • Разрезаем торт попрек сбоку

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

2. Про мешки

Задача: Как сложить 100 картофелин в 2 мешка так, чтобы в одном было в 2 раза больше чем в другом?

Банальной системой или математикой тут не решишь. Складываем 50 в один мешок и 50 в другой, после чего один мешок засовываем в другой и задача решена.

3. Про возраст

Задача: Встретились 2 ребенка и стали рассуждать о своем возрасте. Один из них сейчас старше другого в 3 раза, но всего через 2 года он будет старше всего лишь в 2 раза. Сколько детям лет?

Конечно задачу можно решить подбором, но попробуем подойти со стороны простой школьной математики 7ого класса(может уже и раньше). У нас однозначно есть 2 неизвестных:

  • X — возраст одного ребенка
  • Y — возраст второго ребенка

И есть 2 соотношения:

Сейчас один ребенок старше другого в 3 раза:

y = 3*x  

Через 2 года, один будет старше другого в 2 раза

y + 2 = 2*(x + 2)  

Получаем систему уравнений:

y = 3*x  
y = 2*x + 2  

Подставляя одно в другое, получим

x = 2  
y = 6  

И действительно, когда детям станет на 2 года больше разница будет всего в 2 раза

x = 4  
y = 8  

4. Про пруд

Задача: Вы владелец пруда. В одном его углу начинают бурно размножаться кувшинки. Каждый день их становится вдвое больше. Через 30 дней вы обнаруживаете, что ими заросла уже половина пруда. Вы достаточно ленивый товарищ, поэтому не хотите дергаться раньше времени, но если с кувшинками не бороться, то они все заполонят. Вы решаете, что хотите вмешаться только в последний день, перед тем как они полностью заполнят ваш пруд. Какой это день?

Задачка очень простая, на самом деле она скорее на внимательность, чем на что либо еще. В условии сказано, что кувшинки размножаются вдвое каждый день, значит если вы видите перед собой пруд наполовину заполненный кувшинками, то завтра он будет заполнен полностью и вам надо что-то придумать уже сегодня.

Кстати если кто-то знает интересные задачи, то с радостью готов их услышать, только не надо тащить их из книжек наподобие "Как сдвинуть гору Фудзи", я думаю её уже все читали.

Прочитать

Вопросы на собеседовании #5

Как поменять местами 2 переменные без использования третьей?

Пусть нам даны 2 переменные a=3 и b=2. Нужно получить a=2 и b=3.

Способ №1

a = a + b  
b = a - b  
a = a - b  

Недостатоки: В случае когда переменные a и b типа int можно выйти за границы этого типа.

Способ №2

С помощью сложения по модулю 2 (XOR).

a = a ^ b # a = 1  
b = a ^ b # b = 3  
a = a ^ b # a = 2  

Матрица состояний:

a b xor
0 0 0
0 1 1
1 0 1
1 1 0

Для простоты запоминания, в случае бинароной операции, если аргументы равны, то значение 0, если различны, то 1, с тернарным случаем все ненамного сложнее, если количество аргументов равных единице нечетное, то функция принимает значение 1, во всех остальных случаях 0.

Прочитать

Вопросы на собеседовании #4

В этот раз, в отличие от предыдущих, не буду указывать к какому языку относятся эти вопросы — они общие для всех. Такие задачки часто любят задавать в «продвинутых» компаниях.

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

1. На часах 3:15, какой угол между минутной и часовой стрелками?

Ну тут еще куда ни шло, можно посмотреть как человек математически посчитает что-нибудь, но вы представьте, что сидите на собеседовании, дергаетесь, переживаете и тут надо решить какую-то неординарную с виду задачу, которую в глаза никогда не видели и вроде бы ничего такого не решали.

Можно посчитать как в градусах так и в π. В градусах это 7.5°, в π это π/8. Весь круг 360°, на каждый час приходится по 30°, часовая прошла четверть часа, потому что это как раз 15 минут =>

30/4 = 7.5°.

Ничего сложного, но если не быть к такому готовым, то вряд ли решишь.

2. Если обмотать веревкой земной шар, а потом взять веревку на 1 метр больше чем до этого и снова обмотать, между веревками останется зазор, пролезет ли в него мышка?

Привет любителям геометрии. Длина круга(и нашей веревки тоже) 2πR1, а длина второй веревки 2πR2.

2πR1 — 2πR2 = 1
R1 — R2 = 1 / 2π

Напоминаю, что все у нас в метрах: 1 ÷ 2π ≈ 0,159 м

В 15 сантиметровый зазор много кто может пролезть. А сначала очень хочется сказать, что не может. Вроде 1 метр это крайне мало по сравнению со всей веревкой и радиусом.

3. Расскажи о проекте, которым ты гордишься.

Вот тут как раз можно посмотреть на уровень человека, потому что обычно тот проект, которым он гордится, сделан лучше всего и разбирается человек в нем отлично. Он будет увлеченно о нем рассказывать и что-то доказывать, что кстати позволит его немного расслабить. Далеко не все психологически стойкие и хорошо переносят такие мероприятия. Если человек ничем не гордится или «не может вспомнить» с очень большой долей вероятности у него нет никакого опыта. Если в резюме так и написано, что нет опыта, то и вопрос не стоит задавать.




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

http://www.braingames.ru/ — сайт с головоломками

Книга "Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию" Г. Лакман Макдауэлл - Coding Interview ISBN 978-5-4461-0038-5Книга "Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию" Г. Лакман Макдауэлл - Coding Interview ISBN 978-5-4461-0038-5
Книга "Как сдвинуть гору Фудзи?" У. Паундстоун - ISBN 978-5-9614-0688-7Книга "Как сдвинуть гору Фудзи?" У. Паундстоун - ISBN 978-5-9614-0688-7

Прочитать

[PHP]: Вопросы на собеседовании #3

Продолжаю цикл статей про вопросы, которые встречались мне на собеседованиях. Поехали:

1. Какова алгоритмическая сложность операции strlen?

Вопрос интересный, чтобы ответить на него надо знать особенности выделения памяти и хранения массивов в PHP. Пытаясь решить задачку в лоб, можно получить ответ O(N), где N — кол-во элементов. Насколько я знаю, strlen возвращает количество байт занятых строкой, поэтому на юникодных кодировках возникают проблемы. Эта цифра хранится в первых четырех байтах памяти выделенной под переменную, поэтому функцию просто берет значение оттуда и возвращает, следовательно вся алгоритмическая сложность сводится к O(1).

2. Приведите пример позднего статического связывания

Если человек знает что это такое, то особо труда сделать не составит. Технология достаточно полезная, но со статикой лучше не борщить. Приведу простенький пример, с использованием слова static:

abstract class DocumentType  
{ 
    public static function create()
    {
        return new static();
    }
}

class Doc extends DocumentType {}

class Ppt extends DocumentType {}

var_dump(Doc::create());  

Выведет:

Doc Object

Показывает, что static в отличие от self относится к тому классу откуда вызывается метод, а не к тому, в котором данный метод содержится.

3. Что такое "магические" методы в PHP?

Вообще в англоязычной литературе эти методы называют interceptors (дословно перехватчики). Всего их 5:

  • __get( $property ) — вызывается при обращение к неопределенному свойству
  • __set( $property, $value ) — вызывается при попытки присвоить значение неопределенному свойству
  • __isset( $property ) — вызывается при попытке проверить существование неопределенного свойства
  • __unset( $property ) — вызывается при попытке освободить память неопределенного свойтсва
  • __call( $method, $args ) — вызывается при попытке вызвать неопределенный метод

Подробнее расписывать не буду, лучше отправлю в мануал. Там указываются еще несколько магических методов: __construct(), __desctruct(), __callStatic(), __sleep(), __wakeup(), __toString(), __clone(), __invoke(). В документации более подробно написано когда тот или иной метод вызывается и используется.

4. Как быстрее всего найти мануал по функции PHP?

С одной стороны ответ или отсутствие такового не позволит узнать силу разработчика. С другой стороны, те, кто используют язык каждый день, когда им надо уточнить какой-то нюанс не будут набирать в google sort или preg_match. Потому что программисты любят использовать всякие крутые плюшки, для ускорения всего, что только можно ускорить. Самый простой и быстрый способ найти документацию по методу это набрать следующее:

http://php.net/<имя_функции>

ex: http://php.net/preg_match

5. Что означает аббревиатура SOLID?

Проще всего информацию о том, что эта аббревиатура значит найти в Wikipedia. Это акроним, собранный из нескольких аббревиатур, которые относятся к объектно-ориентированному дизайну в программировании. Более подробно про каждый из них можно найти на просторах интернета. Достаточно интересный подход, советую всем хотя бы ознакомиться поверхностно.

Прочитать

[PHP]: Вопросы на собеседовании #2

Продолжаю цикл статей (1, 2, 3) , посвященных вопросам на собеседовании. В этот раз постараюсь рассказать про интересные задачки. Итак, поехали:

1. Задача на логику

Ситуация:

Представьте, что есть 3 бочки с шариками: в одной только черные, во второй только белые, в третьей и черные и белые. На каждой из бочек таблички: черные, белые, черно/белые соответственно. Один раз можно достать один шар из любой бочки. Заведомо известно, что все таблички лгут.

Вопрос: Что же надо узнать? :) В какой бочке какие шарики лежат?

Решение: Берем шар из бочки с табличкой "черно/белые", если там черный, то значит в бочке с табличкой "черные" лежат белые, а бочке с табличкой "белые" лежат черно/белые. В противном случае, в бочке оказывается белый шар и значит в бочке с табличкой "белые" лежат черные, а в бочке с табличкой "черные" лежат черно/белые.

2. Какие паттерны проектирования вы знаете

Размер ответа прямо пропорционален опыту работы. Конечно, такое утверждение тоже далеко от правды, но буду полагать, что все работают в компаниях пропагандирующих ООП и хороший стиль кода. Про паттерны проектирования очень хорошо написано в наверное самой известной книге. Стоит обратить внимание на статью в Википедии, гуляя по просторам рунета наткнулся на хороший блог, в котором освещены самые известные паттерны, и что самое приятное — на PHP. Меня в основном спрашивали про фабрику, синглтон и пару раз про observer и decorator.

3. Привести пример интерфейса из реальной жизни

Забавный вопрос, по крайней мере меня, он на несколько секунд поставил в тупик. Примеров таких много, поэтому напишу, что сам ответил на него: педали в автомобиле. Тут стоит объяснить почему — во всех машинах есть либо 2 либо 3 педали, и любой водитель знает, что справа газ, посередине тормоз, а слева сцепление. Давишь на газ машина едет, при нажатии тормоза автомобиль останавливается. Это и есть пример интерфейса, описаны методы взаимодействия, а как уж там они реализованы внутри, не наши проблемы.

4. Задача на логику № 2

Ситуация:

Есть дверь и 3 выключателя рядом с ней. Узнать, что происходит внутри можно только открыв её. За дверь находится лампа дневного света. Можно нажимать на кнопки выключателей неограниченное кол-во раз, можно всего 1 раз открыть дверь, зайти внутрь или посмотреть, в общем сделать все, что в голову взбредет.

Вопрос:

Определить какой из выключателей управляет ламой.

Решение:

Задачи такого рода называются out-of-the-box, для их решения требуется немного выйти за рамки описанной ситуации. Сначала, все пытаются просчитать ситуации с включением выключением и открыванием двери, в итоге приходят к невозможности решения стандартными средствами. Решение же лежит на поверхности и происходит из бытового опыта. Сказано, что можно зайти в дверь и делать все, что в голову взбредет. Мне данная задача ставилась несколько по-другому, поэтому надо было самому дойти до такого решения. Троллить человека, который задал вопрос, на тему "а я поставлю датчик и выкину провода в коридор" не стоит. Надо сделать следующее: щелкнуть 1 выключатель, подождать чуть чуть, выключить его, щелкнуть 2ой и открыть дверь. Если лампа горит, то это 2ой выключатель, если лампа не горит, то подойти и потрогать её, если горячая, то это 1ый, если холодная, то 3ий. Все как обычно легко и просто. Тут надо либо знать, либо уметь решать такие задачки.

5. Подмена сервиса

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

Вопрос:

Есть приложение, приложение обращается к внешнему сервису, в приложении нужно внести какие-то правки, как сделать так, чтобы на девелоперской машине приложение не стучалось во внешний сервис?

Перед описанием решения:

Вопрос был задан именно в такой формулировке, поэтому с собеседником у нас возникли некоторые разночтения в понимании контекста. Человек задавал вопрос в контексте паттернов, ответ был без их учета. Я подошел к ответу с технической точки зрения. Мои ответы:

  • Через рефлексию обратиться к вызывающему классу и подменить его
  • Подменить через мок внешний сервис, подсунув ответ
  • Есть модуль runkit, с помощью него на лету подменить поведение объекта
  • Сделать тестовую апи и переключить девелоперскую машину на неё

Все они были примерно правильные, но на поставленный вопрос все же не ответил.

Решение

Воспользоваться паттерном Service Locator, чтобы сделать дополнительный уровень абстракции при общении с внешними сервисами. Примерно тоже самое, что мок, но с точки зрения паттернов. Лучше самим посмотреть и почитать про него.

P.S. На этом завершим сегодняшнюю top-5 вопросов на собеседовании.

Прочитать