Вопросы на собеседовании по кодированию в Google: объяснение 18 основных вопросов

Серия интервью по кодированию в Google

• Полное руководство по подготовке к процессу собеседования

• Объяснение основных вопросов по кодированию в Google

• Взломайте собеседования по кодированию, создав эти 5 реальных функций

Получить работу в Google нелегко подвиг. Как и в случае с другими крупными технологическими гигантами, собеседование в Google по разработке программного обеспечения комплексное и сложное, требующее нескольких недель подготовки и практики. Итак, как вы можете подготовиться к собеседованию по кодированию? К каким вопросам собеседования следует подготовиться?

Сегодня мы вернемся к серии собеседований по Google Coding и разберем 18 распространенных вопросов на собеседовании, которые задают рекрутеры Google.

Сегодня мы рассмотрим следующее:

• Итоги собеседования по кодированию в Google
• 18 самых популярных вопросов на собеседовании по кодированию в Google с пояснениями
• Больше практики и подготовки
• Подведение итогов и ресурсы

Наша команда экспертов собрала наиболее часто задаваемые вопросы на собеседовании в ведущих технологических компаниях и включила их в тщательно разработанный набор сценариев, на которых вы можете учиться. Доступно на Python, Java, C ++ и JavaScript.

Декодирование собеседования по кодированию на C ++: примеры из реальной жизни

Кодирование Google Итоги собеседования

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

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

Собеседования на месте: если вы пройдете предварительный экран, вы будете приглашены на выездное собеседование, на котором вас будут опрашивать 4-6 сотрудников по 45 минут каждый. Эти собеседования будут более тщательно проверять ваши знания структур данных и алгоритмов. Как правило, вы будете писать код в Google Doc или на белой доске.

Решение: в зависимости от вашей работы вы будете оценены по шкале от 1 до 4. , где минимальный порог для найма — 3.

В целом, Google хочет проверить ваше техническое и логическое применение информатики. Вот несколько популярных тем, которые стоит рассмотреть перед собеседованием:

• Алгоритмы
• Сортировка
• Структура данных
• Графы
• Рекурсия
• Объектно-ориентированное программирование
• Нотация Big-O

18 распространенных вопросов на собеседовании по кодированию в Google

1. Найти k-й по величине элемент в числовом потоке

Разработайте класс для эффективного поиска K-го самого большого элемента в числовом потоке. Класс должен иметь следующие две вещи:

• Конструктор класса должен принимать целочисленный массив, содержащий начальные числа из потока и целое число K .

• Класс должен предоставлять функцию add (int num), которая сохранит данное число и вернет K-е наибольшее число.

Пример:

 Ввод: [4, 1, 3, 12, 7,  14], K = 31. Вызов add (6) должен вернуть «7». 2.  Вызов add (13) должен вернуть '12'. 2.  Вызов add (4) по-прежнему должен возвращать '12'. 

Попробуйте решить эту проблему самостоятельно:

 class KthLargestNumberInStream: def __init __ (self, nums, k): # TODO: напишите здесь свой код self.k = k def add (self, num): # TODO: напишите здесь свой код return -1def main (): kthLargestNumber  = KthLargestNumberInStream ([3, 1, 5, 12, 2, 11], 4) print ("4-е наибольшее число:" + str (kthLargestNumber.add (6))) print ("4-е наибольшее число:" + str  (kthLargestNumber.add (13))) print ("4-е по величине число:" + str (kthLargestNumber.add (4))) main () 

Решение

 из heapq  import * class KthLargestNumberInStream: minHeap = [] def __init __ (self, nums, k): self.k = k # добавить числа в минимальную кучу для num in nums: self.add (num) def add (self, num)  : # добавить новый номер в минимальную кучу heappush (self. minHeap, num) # если в куче больше 'k' чисел, удалите одно число if len (self.minHeap)> self.k: heappop (self.minHeap) # верните 'K-е наибольшее число return self.minHeap [0]  def main (): kthLargestNumber = KthLargestNumberInStream ([3, 1, 5, 12, 2, 11], 4) print («4-е по величине число:» + str (kthLargestNumber.add (6))) print («4-е по величине  число: "+ str (kthLargestNumber.add (13))) print (" 4-е наибольшее число: "+ str (kthLargestNumber.add (4))) main () 

Сложность выполнения: O ( l o g ( K ) ) O (log (K)) O (log (K))

Сложность пространства: O ( K ) O (K) O (K)

Чтобы решить эту проблему , мы будем следовать общему шаблону Top ‘K’ Elements. Итак, мы хотим использовать min-heap вместо max-heap, который будет использоваться для K-го наименьшего числа. Как мы знаем, корень — это наименьший элемент в минимальной куче. Итак, мы можем сравнивать каждое число с корнем, когда мы перебираем каждое число. Если число больше корня, мы поменяем их местами. Мы будем повторять этот процесс, пока не переберем все число.

2. Найдите k ближайших чисел

Учитывая отсортированный числовой массив и два целых числа K и X, найдите K ближайших чисел к X в множество. Вернуть числа в отсортированном порядке. «X» не обязательно присутствует в массиве.

 Вход: arr = [1,2,3,4,5], k = 4, x = 3 Выход: [1,2,3,  4] Вход: [2, 4, 5, 6, 9], k = 3, x = 6 Выход: [4, 5, 6] 

Попробуйте решить эту проблему самостоятельно:

 def find_closest_element (arr, K, X): result = [] # TODO: напишите здесь свой код return result 

Решение

Используйте виджет кода выше, чтобы увидеть решение кода вопрос.

Сложность выполнения: O ( K ) O (K) O (K)

Сложность пространства: O ( l o g ( n — k ) ) O (log (nk)) O (log (n − k))

Один раз опять же, эта проблема следует шаблону Top ‘K’ Numbers. Вот наш подход к проблеме:

• Поскольку массив уже отсортирован, мы можем сначала найти число, наиболее близкое к X , с помощью двоичного поиска. . Допустим, это число Y .
• Число K , ближайшее к K рядом с в Y в массиве. Мы можем искать по обе стороны от Y , чтобы найти самые близкие числа.
• Затем мы можем использовать кучу для эффективного поиска ближайших чисел. Мы можем взять числа K в обоих направлениях от Y и поместить их в минимальную кучу, отсортированную по их отличию от X.
• Наконец, мы извлекаем верхние числа K из минимальной кучи, чтобы найти требуемые числа.

3. Сумма двух значений

Учитывая массив целых чисел и значение, определите, есть ли в массиве какие-либо два целых числа, сумма которых равна заданному значению. Вернуть true, если сумма существует, и false, если нет.

Пример

 Дано nums = [2, 7, 11, 15], target = 9, потому что nums [0] + nums [1]  = 2 + 7 = 9, вернуть [0, 1]. 

Попробуйте сами

 def find_sum_of_two (A, val): #TODO: Write - Your - Code return 

Решение

Время выполнения сложность: O ( N ) O (N) O (N)

Сложность пространства: O ( N ) O(N) O (N)

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

• Просканируйте весь массив один раз и сохраните посещенные элементы в хеш-наборе. Во время сканирования для каждого элемента e в массиве мы проверяем, присутствует ли val - e в хеш-наборе, т.е. val - e уже посещен.
• Если val - e найден в хеш-наборе, это означает, что существует пара ( e , val — e ) в массиве, сумма которого равна заданному val .
• Если мы исчерпали все элементы в массиве и не нашли ни одной такой пары, функция вернет false.

4. Удалить узел с заданным ключом

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

Пример

 Input: head = [4,5,1,9], key = 5Output: [4,1,9] Explanation: Вам дается  второй узел со значением 5, связанный список должен стать 4 -> 1 -> 9 после вызова вашей функции. 

Попробуйте сами

 def delete_node (head, key): #TODO: Write - Your - Code return 

Решение

Время выполнения сложность: O ( n ) O (n) O (n)

Сложность пространства: O ( 1 ) O(1) O (1)

Сначала мы должны найти ключ в связанном списке . Мы сохраним два указателя, текущий и предыдущий, при итерации связанного списка.

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

Это можно сделать при линейном сканировании, и мы можем просто обновить текущий и предыдущий указатели при итерации по связанному списку.

5. Копировать связанный список с произвольным указателем

Вам предоставляется связанный список, в котором узел имеет два указателя. Первый — это обычный указатель next . Второй указатель называется произвольный_поинтер , и он может указывать на любой узел в связанном списке. Ваша задача — написать код для создания полной копии данного связанного списка. Здесь глубокая копия означает, что любые операции с исходным списком (вставка, изменение и удаление) не должны влиять на скопированный список..

Пример

 Вход: head = [[7, null], [13,0], [11,4], [10,2], [1,0]] Выход: [[7,  null], [13,0], [11,4], [10,2], [1,0]] 

Попробуйте сами

 def deep_copy_arbitrary_pointer (head): #TODO: Write - Your - Code return None 

Решение

Сложность выполнения: O ( N ) O (N) O (N)

Сложность пространства: O ( N ) O (N) O (N)

Вот как работает алгоритм решения, чтобы найти плату, которая в сумме соответствует цели.

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

• На первом проходе мы создаем копию исходного связанного списка. При создании новой копии используйте те же значения для данных и произвольного_поинтера в скопированном списке. Кроме того, важно постоянно обновлять карту записями, в которых ключом является адрес старого узла, а значением — адрес нового узла.

• После создания копии мы снова передадим скопированный связанный список и обновим произвольные указатели на новый адрес, созданный при первом проходе.

6. Зеркальное отражение узлов двоичного дерева

Учитывая корневой узел двоичного дерева, поменяйте местами «левые» и «правые» дочерние элементы для каждого узла. В приведенном ниже примере показано, как должно выглядеть зеркальное двоичное дерево..

Пример

Попробуйте сами

 def mirror_tree (root): #TODO  : Write - Your - Code return root 

Решение

Сложность выполнения: O ( N)O(N) O (N)

Космический комплекс y: O ( N ) O (N) O (N)

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

7. Проверьте, идентичны ли два двоичных дерева

Учитывая корни двух двоичных деревьев, определите, идентичны ли эти деревья или нет. Идентичные деревья имеют одинаковый макет и данные на каждом узле.

Пример

 Ввод: 1 1// 2 3 2 3 [1,2,3], [1,2,3] Выход:  trueInput: 1 1// 2 1 1 2 [1,2,1], [1,1,2] Вывод: false 

Попробуйте сами

 def are_identical (root1, root2): если root1 == None и root2 == None: вернуть True, если root1! = None и root2! = None: return (root1.data == root2.data  и are_identical (root1.left, root2.left) и are_identical (root1.right, root2. right)) return Falsearr1 = [100,50,200,25,125,350] arr2 = [1,2,10,50,180,199] root1 = create_BST (arr1) display_level_order (root1) root2 = create_BST (arr2) display_level_order (root2) if (are_identical (root1,  root2)): print («Деревья идентичны») else: print («Деревья не идентичны») 

Решение

Сложность выполнения: O ( N ) O (N) O (N)

Сложность пространства: O ( N ) O(N) O (N)

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

Два сравниваемых дерева идентичны, если:

• данные в их корнях совпадают.
• левое поддерево ‘A’ идентифицируется с левым поддеревом ‘B’
• правое поддерево ‘A’ идентично правому поддереву ‘B’

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

8. Сегментация строк

Вам предоставляется словарь слов и большая строка ввода. Вы должны выяснить, можно ли полностью сегментировать входную строку на слова данного словаря. Следующие два примера более подробно рассматривают проблему.

Пример

 Ввод: s = "applepenapple", wordDict = ["apple", "pen"] Вывод: trueExplanation: Вернуть true, потому что "applepenapple" может быть  сегментировано как «яблоко, перо, яблоко».  Обратите внимание, что вам разрешено повторно использовать слово из словаря. 

Попробуйте сами

 def can_segment_string (s, dictionary): #TODO: Write - Your - Code return False 

Решение

Сложность выполнения: O ( 2 N ) O (2 ^ N) O (2 N) (без мемоизации)

Сложность пространства: O ( N 2 ) O (N ^ 2) O ( N 2)

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

 n = длина входной строки для i = от 0 до n - 1 first_word = substring (входная строка из индекса [0, i]) second_word = substring (входная строка из индекса [i + 1, n - 1  ]) если в словаре есть первое_слово, если второе_слово находится в словаре ИЛИ второе_слово имеет нулевую длину, то возвратите true, рекурсивно вызовите этот метод с вторым_словом в качестве входных данных и верните истину, если его можно сегментировать 

9. Найти все подстроки палиндромов

По заданной строке найти все не однобуквенные подстроки, которые являются палиндромами. Например:

Пример

 Ввод: "abc" Вывод: 3 Объяснение: Три палиндромные строки: "a", "b", "c". 

Попробуйте сами

 def find_all_palindrome_substrings (input): # TODO: Write - Your - Code return -1 

Решение

Время выполнения сложность: O ( N 2 ) O (N ^ 2) O (N 2) (без мемоизации)

Сложность пространства: O ( 1 ) O (1) O (1)

Мы будем перебирать каждую букву во входной строке . Для каждой буквы мы можем найти палиндромы, развернув влево и вправо, чтобы проверить наличие палиндромов четной и нечетной длины. Если палиндромов нет, перейдите к следующей букве.

Мы находим палиндромы, проверяя, равны ли левый и правый символы. Если они есть, мы распечатываем подстроку палиндрома.

Решение

Сложность выполнения: O ( N ) O (N) O (N)

Сложность пространства: O ( N ) O (N) O (N)

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

• Дан список входных интервалов, и мы сохраним объединенные интервалы в выходном списке.

Для каждого интервала

• Если входной интервал перекрывается с последним интервалом в выходном списке, мы объединим два интервала и обновим последний интервал выходного списка с объединенным интервалом.

• В противном случае мы добавим входной интервал в выходной список.

17. Найдите недостающее число

Нам дан массив, содержащий «n» различных чисел, взятых из диапазона от 0 до «n». Поскольку в массиве только n чисел из общего числа n + 1, найдите недостающее число. См. Пример ниже.

 Пример  1: Вход: [4, 0, 3, 1] Выход: 2 Пример 2: Вход: [8, 3, 5, 2, 4, 6, 0, 1] Выход: 7 

Попробуйте сами

 def find_missing (ввод): #TODO: Write - Your - Code return 

Решение

Сложность выполнения: O ( N ) O (N) аннотация> O (N)

Сложность пространства: O(1) O (1) O (1) Давайте решим эту проблему с помощью линейного O ( N ) O (N) O (N), решение с использованием формулы суммы арифметических рядов.

Вот алгоритм:

1. Найдите сумму «sum_of_elements» всех чисел в массиве. Для этого потребуется линейное сканирование, O (n).

2. Затем найдите сумму «ожидаемая_сумма» первых «n» чисел, используя формулу суммы арифметического ряда, т.е. (n * (n + 1))/2.

3. Разница между этими, например, «ожидаемая_ сумма — сумма_элементов», заключается в отсутствующем числе в массиве.

18. Переворачивает связанный список

Переворачивает односвязный список. См. Пример ниже.

 Ввод  : 1-> 2-> 3-> 4-> 5-> NULL Выход: 5-> 4-> 3-> 2-> 1-> NULL 

Попробуйте сами

 def reverse (head): reversed_list = head #TODO: Write - Your - Code return reversed_list 

Решение

Сложность выполнения: O ( N ) O (N) O (N)

Сложность пространства: O (1) O (1) O (1)

Давайте посмотрим на итерационный подход.

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

• reversed_list : указатель на уже перевернутый связанный список.

• list_to_do : указатель на оставшийся список.

Затем мы устанавливаем для reversed_list-> next значение NULL . Это становится последним узлом обратного связанного списка.

Для каждой итерации указатель list_to_do перемещается вперед. Текущий узел становится новым заголовком обратносвязанного списка. Цикл завершается, когда мы нажимаем NULL .

Больше практики и подготовки

Поздравляем с решением этих задач! Чтобы пройти собеседование по программированию, важно продолжить практику. Чтобы подготовиться к собеседованию по кодированию в Google, вы должны освежить в памяти динамическое программирование, возврат с возвратом, рекурсию, жадные алгоритмы и разделяй и властвуй. Вот еще несколько распространенных вопросов на собеседовании по кодированию для практики.

Подведение итогов и ресурсы

Чтобы пройти собеседование по кодированию в Google, нужно просто повторить и попрактиковаться. После прочтения этой статьи важно, чтобы вы продолжали практиковать больше вопросов на собеседовании.

Чтобы помочь вам подготовиться к собеседованию в Google, Educative разработал уникальный курс Decode the Coding Interview: Real-World Примеры . Этот курс, доступный на нескольких языках, поможет вам ответить на более 100 вопросов из реальной жизни, подобных этим. После каждого проекта вы лучше поймете, какие методы вы только что применили.

Это подготовка к собеседованию, переосмысленная с учетом ваших потребностей.

Удачного обучения!

Продолжить чтение о подготовке к собеседованию по кодированию

• Взломать интервью по кодированию в Google: подробное руководство по подготовке

• Получите 15 лучших вопросов по Java-алгоритмам для собеседований по кодированию

• 5 проверенных временем методов подготовки к собеседованию по кодированию