Статьи с тэгом: Ultimate

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

Графики и деревья

Примечание. Этот раздел будет в значительной степени зависеть от этого плейлиста YouTube Binary Tree . Полная реализация кода двоичного дерева, который мы рассмотрим в этом разделе, может быть найдена в на Github здесь .

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

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

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

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

Каждый узел имеет несколько атрибутов, а именно конкретное поле данных, которое состоит из содержимого, хранящегося в этом узле, в дополнение к левому и правому указателям, которые ссылаются на соответствующий левый и правый дочерний элемент, если таковой имеется, узел. Используя Python, мы можем определить класс Node следующим образом:

Мы также можем собрать класс BinaryTree который будет построен из объектов Node

Когда у нас есть эта базовая структура, мы можем теперь создать простой объект BinaryTree :

Это двоичное дерево, в котором корень содержит значение 1 левый дочерний элемент содержит значение 2 а правый дочерний элемент корня содержит значение 3 .

Вот хорошее обновление для бинарных деревьев.

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

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

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

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

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

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

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

Массивы и строки

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

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

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

Давайте рассмотрим проблему из нашего бесплатного 50 Руководства по вопросам интервью . В частности, давайте посмотрим на проблему 4, которая «найти дубликаты». Вопрос:

Учитывая массив целых чисел, где каждое значение 1 <= x <= len (array) напишите функцию, которая находит все дубликаты в массиве.

Например:

Вы можете найти больше информации по этой проблеме здесь.

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

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

Например, что-то подобное даст правильный ответ при таком подходе:

What is the runtime of this code? Well, we have the outer loop going through the array and the inner loop going through the remaining elements as we progress through the array. This will yield an O(n²) algorithm.

Okay, so not great, but it’s a starting point. We can improve on this solution a bit by taking advantage of the built-in set() function that Python offers. Other languages will have a similar style of algorithm.

The gist of how this improved algorithm will work is that we can create a set object and iterate through out input list. If the element that we are iterating through is not in the set, add it to the set. Otherwise, continue processing the list.

This code for how to implement this is given as:

So we have taken our O(n2) algorithm and improved it to an O(n) algorithm. It also now takes O(n) space for storing the elements into our set. Can we improve this solution?

Well, we can improve on the space and reduce the space to constant.

If we sort our input array, we can then iterate through the array and check if the element we are processing differs from the next element in the array. If it does not, we have a duplicate and we can process that accordingly. If instead it is increasing, we continue processing the array.

The code for this would be something like:

So we have improved our space to O(1)but incurred more of a hit on time, as sorting is going to dominate the time complexity with O(n log n).

Okay, so we have a few approaches here and they all have varying trade-offs with respect to time and space. One thing that we should perhaps do is look again at the question to see if there are any specific attributes of the question we can leverage to our advantage.

Looking again, we indeed see that we have a guaranteed precondition that guarantees that each value 1 <= x <= len(array). The idea or “trick” here is to think about how we can go about encoding that we have already seen a certain number without using any additional data structures and keeping our space complexity constant.

Using the fact that all of the numbers in the array range from 1 to the length of the array, we can encode those in the existing array data structure. So we will be making use of the space that has already been allocated to us from the input that we are given.

Let us take a look at a specific input example to see how our new and improved approach will work. Take the input to be the list [2, 1, 2, 1]. Just to reiterate, we know that every value in the array we are given is between 1 and the total length of the array we are provided.

One thing that will make this easier for us is to subtract one from the values of the list so that our condition becomes that each value in the array ranges from 0 <= x <= len(array) - 1 instead of 1 <= x <= len(array).

Another key observation is that given the guaranteed precondition, we know that every value in the array will be a positive integer.

As we traverse through this array then, we can encode whether or not we have seen a particular number by flipping the sign of the index that the value corresponds to from positive to negative. If we stumble on a value with a negative sign, we know that we’ve previously encountered this value before and will add that value to our duplicate set.

To solidify this concept, let us again turn to our example input of [2, 1, 2, 1]. Iterating through each of the elements of this list, we see that the first value we encounter is 2. We now want to encode the fact that we have encountered a 2 in our array. So we need to calculate the index by subtracting one from the value, giving:

index = 2 - 1 = 1

Then, we flip the index corresponding to index 1 to a negative, giving us a list that now looks like this:

[2, -1, 2, 1]

Moving along in our list, we happen upon a -1which we take the absolute value of to get the original value and calculate the index as we did before

index = 1 - 1 = 0

Now, we go to the index 0 in the array and flip the sign of that value from positive to negative giving us

[-2, -1, 2, 1]

So this list tells us that we have seen a 1 since we flipped the value of index 0 and that we have seen a 2 since we negated the value of index 1. Let’s carry on with the algorithm, we hit a second 2 giving us the index calculate of

index = 2 - 1 = 1

We check the value held at index 1 in the array, but this value is negative, indicating that we have already seen this value in our array. In this case then, we add this duplicate value to our result set.

Analyzing the above approach, we have an algorithm that takes O(n) time and uses O(1) space. The final code listing for this solution is provided below:

Check out this post for more info on common string and array patterns.

Recursion and dynamic programming

Recursion and dynamic programming go hand-in-hand. In order to solve a given problem with the strategy of dynamic programming, this typically involves first finding a recursive solution to the problem, and then finding a way in which to store and consult previous computations to prevent future unnecessary calculations.

Mastering both of these topics surely then requires a solid understanding of recursion. Furthermore, just understanding the idea of recursion is not sufficient, but the ability to quickly apply recursive thinking to a problem in a swift manner is key.

It goes without saying that the previous mentioned categories of popular problems, namely the tree/graph and array/string processing problems often require the use of recursion as well.

For instance, being problems such as finding the upper cases letter in a stringcalculating the length of a stringor counting the number of consonants in a string are all problems that could be categorized as “string problems”, but also have very concise recursive solutions.

The key to solving a problem that requires recursion is develop a strategy for how to recognize, analyze, and solve recursive problems. For this, we have a targeted course for precisely this purpose.

We’ve also talked a lot about how to tackle  dynamic programming problems using the FAST Method.

Additional Resources

There are resource materials involved in preparing for the Google interview that are beyond the scope of what can be contained in a blog post.

As a major chunk of what determines your success for the Google interview is centered on coding proficiency, we will mention a few of my favorite book and video resources.

Note: This section contains some affiliate links. We earn a small commission if you buy through our link.

Books:

Cracking the Coding Interview

For practice material, Cracking the Coding Interview (CTCI) by Gayle Laakmann McDowell is one of the more popular resources. In addition to providing a good array of practice problems, the introduction of the book provides specific information on how Google hires.

It’s a brief few pages, but as Gayle previously has worked for and went through the Google interview process, her advice here is an important piece of information. For a deeper dive on how to extract the most out of CTCI for your interview, check out this video.

Elements of Programming Interviews

If you wish to supplement your book preparation material, this video mentions his top 5 books for preparing for the technical interview, with CTCI being among them.

Extracting content from that video specifically geared towards the Google interview, the book that is my overall favorite for technical interview preparation is Elements of Programming Interviews in Python (EPI) by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

One of the authors, Tsung-Hsien, is a current employee of Google, and it’s probably no coincidence that many of the problems found in this book had a high overlap with the problems that showed up in the Glassdoor data. CTCI is an excellent source of practice problems, but it is so excellent that the problems have declined in popularity for interviewers to ask due to their ubiquity.

For EPI, the solutions are incredibly concise, well-written, and guide your thought process gradually. As you read through one solution, you may be able to stop midway and solve it yourself without reading the entire thing.

This is great and simulates obtaining a hint from the interviewer if you're really stuck on a problem. While it's best to solve the problem without any explicit hints, it's good that the book has that option.

The solution code is also exceptionally Pythonic. I've found that when working through the problems in this text that even if I have the correct idea, looking at the concise way the authors solved the problem was a real inspiration to well-formed Python code.

If you decide that Python is not your strongest language to interview in, they also offer a Java and C++ versions of the book that may be better suited for you. The writing style and theme of these books is just as good.

Byte-by-Byte 50 Coding Interview Problems

We have compiled a large list of  problems that serve as a great companion to the above two resources.You can download the free guide here.

If you are going through a particular problem and need some further guidance, this supplemental material can be incredibly helpful in understanding and solving the problem.

Video Resources:

Depending on your timeline and learning stye, working through video content may be a preferable way in which to spend your time preparing for your Google interview. Assuming your gaps in knowledge are larger, there are no shortage of MOOCs offered through sites like Coursera and Udacity that focus on the fundamentals of computer science, data structures, algorithms, etc.

Assuming you have a solid foundation in data structures and algorithms, finding good video content on the specific type of problems you may encounter in a Google interview will most likely serve you better.

It’s also worth checking out our Youtube channel. We’ve compiled playlists of videos for certain problems in categories including dynamic programminggraphsrecursionand arrays for starters. All of these videos can be found in our Coding Interview Question playlist.