Статьи

Мои Google Интервью

Ноябрь 19, 2018

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

После еще одного мучительного (но менее запоминающегося) интервью они вежливо показали меня.

Так что на этот раз я немного нервничал. Тем не менее, я рад сообщить, что я никогда не был в недоумении от того, что делать, и все вопросы казались довольно справедливыми и разумными. Большинство вопросов были в основном вариациями в « Взломе кодирования» , поэтому я решил поделиться ими. У меня есть еще несколько творческих вопросов, которые не перечислены ниже (я не хочу испортить чей-то «личный» вопрос), но они не были сложнее или проще, чем другие.

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

Вот что меня спросили:

  • Учитывая эту странную древовидную вещь:

    semitree

    Найти наибольшую сумму на пути от корня к листу (который может касаться только одного узла на уровень — без движения вверх и вниз).

    Я сделал рекурсивное решение длиной около шести строк, а затем она попросила меня придумать способ сделать это итеративно.

  • Рассмотрим степенной ряд:

    a 0 + a 1 x + a 2 x 2 +…

    Предположим, у нас есть интерфейс для получения коэффициентов: a 0 , a 1 , a 2 и т. Д .:

class PowerSeries {
public:
    virtual double next();
};

Вы можете взять произведение двух степенных рядов:

(a 0 + a 1 x + a 2 x 2 +…) * (b 0 + b 1 x + b 2 x 2 +…)

Реализуйте next (), чтобы получить следующий коэффициент в произведении двух степенных рядов:

class PowerProduct : public PowerSeries {
public:
    PowerProduct(PowerSeries* A, PowerSeries* B);
    virtual double next();
};
  • Обратные байты в int.

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

  • Напишите функцию, чтобы найти, является ли множество A подмножеством множества B, B является подмножеством A, два набора равны или ничего из вышеперечисленного (вам разрешено использовать операции над множествами, такие как объединение и пересечение).
  • Часть 2 предыдущего вопроса: предположим, вам дан список наборов. Вы хотите отфильтровать любой набор в списке, который является подмножеством другого набора в списке. Используйте ваше решение сверху, чтобы найти наименьший возможный список результатов максимально эффективно.
  • Реализовать atoi (преобразовать строку в целое число).
  • По заданной строке найдите самую длинную подстроку только из двух разных символов. Например, если указать «aabacccaba», вы бы вернули «accca».
  • Дизайн кеша.
  • Предположим, вы находитесь на декартовой системе координат. Найдите все пути от (0,0) до (m, n), которые проходят через каждую точку только один раз. Например, если бы вам дали m = 2, n = 2, вы бы получили следующее:

    пути

    Это был бы один из возможных путей:

    paths2

    Вернуть количество возможных путей. Затем продолжите для отрицательных координат.

  • Учитывая два целых числа, a и b , найдите наименьшее квадратное целое число в диапазоне (или верните -1, если такого квадрата нет).

34
Share: