Tech Dev Guide Flashcards
VIDEO
Interview tips from Google engineers
Interested in tips for software engineering interviews? Google engineers share their advice for software engineering interviews at Google or other companies in this video. (YouTube)
https://youtu.be/mOyo4NoFRI4
READING
How to prepare for coding interviews
Studying for coding interviews can be challenging. Check out this article to learn more about what you can do to make the best use of your study time to ace those interviews! (freeCodeCamp)
https://www.freecodecamp.org/news/how-to-make-progress-while-studying-for-coding-interviews-894c320bfa74/
READING
View more Reading content
Google’s hiring process
Whether you’re applying for an engineering position or another role at Google, check out this page to learn more about our hiring process and what Google looks for in candidates. (Google Careers)
https://careers.google.com/how-we-hire/
VIDEO
View more Video content
How to communicate in technical interviews
Knowing how to communicate your thoughts in an interview is just as important as showcasing your technical ability. Check out this video to learn more about how to communicate in technical interviews. (YouTube)
https://m.youtube.com/watch?v=dEeoT377NJE
VIDEO
View more Video content
How to prepare for interviews
Curious about how to prepare for coding interviews? Check out this video where Google engineers offer advice on what you can do to practice both your technical and communication skills. (YouTube)
https://m.youtube.com/watch?t=0s&v=6ZZX9iIgFoo&feature=youtu.be
VIDEO
View more Video content
Mock Google interview
Are you curious about what an interview at Google looks like? Watch this video of a mock coding interview among two Google engineers, who also share their tips and best practices at the end. (YouTube)
https://m.youtube.com/watch?v=XKu_SEDAykw
READING
View more Reading content
Where to practice coding interview questions
The best way to learn how to solve coding questions is by practicing them! If you’re unsure where to start, check out this article to find interactive websites you can use to find practice problems. (Medium)
https://medium.com/coderbyte/learn-by-doing-the-8-best-interactive-coding-websites-4c902915287c
CODING QUESTION
View more Coding Question content
Former interview question: compression and decompression
Challenge your knowledge of data structures and algorithms with this gentle practice problem that involves compressing and decompressing a string.
The Challenge
In this exercise, you’re going to decompress a compressed string.
Your input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example:
The input
3[abc]4[ab]c
Would be output as
abcabcabcababababc
Other rules
Number can have more than one digit. For example, 10[a] is allowed, and just means aaaaaaaaaa
One repetition can occur inside another. For example, 2[3[a]b] decompresses into aaabaaab
Characters allowed as input include digits, small English letters and brackets [ ].
Digits are only to represent amount of repetitions.
Letters are just letters.
Brackets are only part of syntax of writing repeated substring.
Input is always valid, so no need to check its validity.
Learning objectives
This question gives you the chance to practice with strings, recursion, algorithm, compilers, automata, and loops. It’s also an opportunity to work on coding with better efficiency.
CODING QUESTION
View more Coding Question content
Former interview question: volume of lakes
Interested in solving a coding problem related to geology, specifically terrain and water volume? Check out this coding question and put your algorithmic skills into practice!
The Challenge
Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.
Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.
Example: Given [1,3,2,4,1,3,1,4,5,2,2,1,4,2,2], return 15 (3 bodies of water with volumes of 1,7,7 yields total volume of 15)
An image showing the volume of water
Learning objectives
This question offers practice with algorithms, data structures, Big-O, defining functions, generalization, efficiency, time and space complexity, and anticipating edge cases.
CODING QUESTION
View more Coding Question content
Former interview question: flatten iterators
If you like tongue twisters and a challenge that tests your creativity, sink your teeth into this former Google interview question where you’ll be asked to implement a unique type of iterator.
The Challenge
Given an iterator of iterators, implement an interleaving iterator
Background: Iterator defined
In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container’s elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. This code snippet illustrates:
Copy
int[] arr = [1, 2, 3];
Iterator<Integer> it = arr.iterator();
while(it.hasNext()){
print it.next();
}
// 123
hasNext() // returns whether or not the iterator has additional elements
next() // returns next element in iterator, throws NoSuchElementException otherwise.</Integer>
Your challenge, should you choose to accept it…
Given an iterator of iterators, implement an interleaving iterator that takes in an iterator of iterators, and emits elements from the nested iterators in interleaved order. That is, if we had the iterators i and j iterating over the elements [ia, ib, ic] and [ja, jb] respectively, the order in which your interleaving iterator should emit the elements would be [ia, ja, ib, jb, ic].
Your interleaving iterator should implement the Iterator interface, take in the iterator of iterators in its constructor, and provide the next and hasNext methods. Assume that there are no additional methods offered by the iterator.
Given the following three iterators put into an array of iterators…
Copy
int[] arr1 = [1, 2, 3];
int[] arr2 = [4, 5];
int[] arr3 = [6, 7, 8, 9];
Iterator<Integer> a = arr1.iterator();
Iterator<Integer> b = arr2.iterator();
Iterator<Integer> c = arr3.iterator();
Iterator<Integer>[] iterlist = [a, b, c];</Integer></Integer></Integer></Integer>
… build an “Interleaving Flattener” (IF), which works much like an iterator:
Copy
IF itfl = new IF(iterlist);
while(IF.hasNext()){
print IF.next();
}
// 1 4 6 2 5 7 3 8 9
To assist you, here’s a skeleton for the class:
Copy
class IF{
public IF(Iterator<T>[] iterlist){
}
public T next(){
}</T>
public boolean hasNext(){
}
}
Learning objectives
This question gives you the chance to practice with iterators, iteration, data structures, classes, and nesting. It calls for thoughtful problem-solving and optimizing your solution. If you write it successfully in one language, try it again in a second.
CODING QUESTION
View more Coding Question content
Former interview question: find longest word
Hone your problem-solving skills with this former Google interview question where you’ll need to find the longest word in a dictionary that is a subsequence of a given string.
The Challenge
Given a string S and a set of words D, find the longest word in D that is a subsequence of S.
Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters.
Note: D can appear in any format (list, hash table, prefix tree, etc.
For example, given the input of S = “abppplee” and D = {“able”, “ale”, “apple”, “bale”, “kangaroo”} the correct output would be “apple”
The words “able” and “ale” are both subsequences of S, but they are shorter than “apple”.
The word “bale” is not a subsequence of S because even though S has all the right letters, they are not in the right order.
The word “kangaroo” is the longest word in D, but it isn’t a subsequence of S.
Learning objectives
This question gives you the chance to practice with algorithms and data structures. It’s also a good example of why careful analysis for Big-O performance is often worthwhile, as is careful exploration of common and worst-case input conditions.
CODING QUESTION
View more Coding Question content
Former interview question: word squares
Pit yourself against this problem that asks you to write a program that can identify word sequences defined as word squares, and then return all word square sequences within a given list of words.
The Challenge
A “word square” is an ordered sequence of K different words of length K that, when written one word per line, reads the same horizontally and vertically. For example:
Copy
BALL
AREA
LEAD
LADY
In this exercise you’re going to create a way to find word squares.
First, design a way to return true if a given sequence of words is a word square.
Second, given an arbitrary list of words, return all the possible word squares it contains. Reordering is allowed.
For example, the input list
[AREA, BALL, DEAR, LADY, LEAD, YARD]
should output
[(BALL, AREA, LEAD, LADY), (LADY, AREA, DEAR, YARD)]
Finishing the first task should help you accomplish the second task.
Learning objectives
This problem gives practice with algorithms, recursion, arrays, progressively optimizing from an initial solution, and testing.
CODING QUESTION
View more Coding Question content
Former interview question: minesweeper
Put your problem-solving skills to the test as you create your own version of the Minesweeper game for this former Google interview question.
The Challenge
Implement Minesweeper
Minesweeper is a game where the objective is correctly identify the location of all mines in a given grid. You are given a uniform grid of gray squares in the beginning of the game. Each square contains either a mine (indicated by a value of 9), or an empty square. Empty squares have a number indicating the count of mines in the adjacent squares. Empty squares can have counts from zero (no adjacent mines) up to 8 (all adjacent squares are mines).
If you were to take a complete grid, for example, you can see which squares have mines and which squares are empty:
Copy
0 0 0 0 0
0 0 0 0 0
1 1 1 0 0
1 9 1 0 0
1 2 2 1 0
0 1 9 1 0
0 1 1 1 0
The squares with “2” indicate that there 2 mines adjacent to that particular square.
Gameplay starts with a user un-hiding a square at random. If the square contains a mine, the game ends. If it is a blank, the number of adjacent mines is revealed.
Exposing a zero means that there are no adjacent mines, so exposing all adjacent squares is guaranteed safe. As a convenience to the player, the game continues to expose adjacent squares until a non-zero square is reached.
For example, if you click on the top right corner you get this (‘-‘ means hidden):
CODING QUESTION
View more Coding Question content
Distributing candies
Have a sweet tooth? Try your hand at this coding problem in which you’ll be asked to write an algorithm to determine how to equally distribute candy between siblings. After all, sharing is caring. (LeetCode)
Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.
The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor’s advice.
Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.
Example 1:
Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.
Example 2:
Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.
Example 3:
Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.
Constraints:
n == candyType.length
2 <= n <= 104
n is even.
-105 <= candyType[i] <= 105
CODING QUESTION
View more Coding Question content
Longest increasing subsequence
Interested in getting practice with binary search and dynamic programming? Check out this coding question in which you’ll be asked to find the length of the longest increasing subsequence in an array. (LeetCode)
Given an integer array nums, return the length of the longest strictly increasing
subsequence
.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
