Blog #interview

Допустим, что вам нужно найти середину связного списка, как это быстрее всего сделать? Завести 2 указателя, один будет шагать через один элемент, а второй - по каждому элементу. Таким образом когда первый указатель доберется до конца такого списка - второй будет указывать на середину. Так вот первый указатель называют "быстрым".

Недавно встретил такую задачку и хотел бы с вами поделиться:

На вход нашему методу передается некий граф, который содержит ноды вида

Node {
  int value;
  Node next;
}

Нам нужно найти ноду в этом графе, которая начинает бесконечный цикл.

Например:

1 -> 2 -> 3 -> 4 -> 2

Тут нода со значением 2 начинает цикл.

Если же ноды нет, то метод должен вернуть null.

Решение этой задачи довольно простое, если бы не одно условие: нужно найти решение без использования дополнительной памяти.

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

p.s: задача была задана на собесе в компанию Apple.

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

- List<> это такой массив, но с более удобными методами;

- При расширении листа - увеличивается массив x2, а данные копируются;

Но был еще дополнительный вопрос:

Vector3[] arr = ; // 1 элемент или больше
List<Vector3> list = ; // 1 элемент или больше
arr[0].x = 123f;
list[0].x = 123f;

Где сломается такой код?

- Нигде

- arr[0].x

- list[0].x

- В обоих случаях

Этот вопрос был не то чтобы прям "отсеивающим", но в большинстве случаев те, кто не мог ответить на этот вопрос, - никогда не писали своих коллекций и никогда не разбирались как устроены существующие.

Обычно такой вопрос был у нас на собесах N лет назад. И правильный ответ на него должен быть один: он - Барбара.

Я на собеседованиях спрашиваю простой вопрос: Почему нельзя написать transform.position.y = 123f;? Ответы бывают разные от банального "не знаю" и "ну юнити не дает" до единственно верного 🙂 

Вообще довольно забавно, что мало кто из разрабов в принципе вникает в суть происходящего, а она банальна: transform.position - это getter, а get - это метод. А Vector3 - это структура. 

Вот и получается, что при вызове get мы делаем копию структуры и пытаемся ее менять. А это очевидно, что не приведет ни к чему.