Google Top Interview Questions Flashcards
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Sliding Window
By using HashSet as a sliding window, checking if a character in the current can be done in O(1).
Use HashSet to store the characters in current window [i, j)
Then we slide the index j to the right. If it is not in the HashSet, we slide j further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index i. If we do this for all i, we get our answer.
3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Hashset
Since triplets must sum up to the target value, we can try the hash table approach from the Two Sum solution where the complement of the target is stored in a HashMap.
Time Complexity: O(n^2)
twoSum is O(n), and we call it n times.
For the main function:
- Sort the input array nums.
- Iterate through the array:
- If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
- If the current value is the same as the one before, skip it.
- Otherwise, call twoSum for the current position i.
For twoSum function:
- For each index j > i in A:
- Compute complement value as -nums[i] - nums[j].
- If complement exists in hashset seen:
- We found a triplet - add it to the result res.
- Increment j while the next value is the same as before to avoid duplicates in the result.
- Add nums[j] to hashset seen
Return the result res.
Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Elementary Math
We mimick using long hand multiplication from elementary school.
We take the ones place digit of the second number, then multiply it with all digits of the first number consequently going backward, and write the result. We need to remember about carry as well.
Then we take the tens place digit of the second number and multiply it with all digits of the first number. Since we used the tens place digit, we will multiply this result by 10. Then we write this result below the previous result, signifying that we will add it to the previous result later.
Unique Email Addresses
Every valid email consists of a local name and a domain name, separated by the ‘@’ sign. Besides lowercase letters, the email may contain one or more ‘.’ or ‘+’.
For example, in “alice@leetcode.com”, “alice” is the local name, and “leetcode.com” is the domain name.
If you add periods ‘.’ between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. Note that this rule does not apply to domain names.
For example, “alice.z@leetcode.com” and “alicez@leetcode.com” forward to the same email address.
If you add a plus ‘+’ in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered. Note that this rule does not apply to domain names.
For example, “m.y+name@email.com” will be forwarded to “my@email.com”.
It is possible to use both of these rules at the same time.
Given an array of strings emails where we send one email to each email[i], return the number of different addresses that actually receive mails.
Approach 1: Linear Iteration
Intuition
We can iterate over an email from left to right, and add characters to local name until a ‘+’ occurs, then we can skip all characters until ‘@’ occurs, then we can again start appending the characters till the end of the email string to form the domain name.
Notice that per the rules, we do not need to read any characters between the first ‘+’ and ‘@’. While checking each character from left to right, after finding the first ‘+’ in the local name we can directly find the domain name by switching to a reverse iteration as there is only one ‘@’ and we will skip all characters in between ‘+’ and ‘@’.
Odd Even Jump
You are given an integer array arr. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd-numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.
You may jump forward from index i to index j (with i < j) in the following way:
During odd-numbered jumps (i.e., jumps 1, 3, 5, …), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
During even-numbered jumps (i.e., jumps 2, 4, 6, …), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
It may be the case that for some index i, there are no legal jumps.
A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).
Return the number of good starting indices.
This problem can be broken down into non-overlapping subproblems and solved using Dynamic Programming
First create boolean DP array.
dp[i][0] stands for you can arrive index n - 1 starting from index i at an odd step.
dp[i][1] stands for you can arrive index n - 1 starting from index i at an even step.
To quickly find the next greater or smaller number and its index: traverse the array reversely and store data into a TreeMap using the number as Key and its index as Value.
License Key Formatting
You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.
We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.
Return the reformatted license key.
Scan linearly through the string backwards from left to right.
Add the dashes at the appropriate spots and store the results in a StringBuffer.
At the end reverse the string back.
public String licenseKeyFormatting(String s, int k) {
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--)
if (s.charAt(i) != '-')
sb.append(sb.length() % (k + 1) == k ? '-' : "").append(s.charAt(i));
return sb.reverse().toString().toUpperCase();
}
Fruit Into Baskets
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Solve with sliding window using a left and right pointer.
Maintain a HashMap counter which count the number of element between the two pointers.
public int totalFruit(int[] tree) {
Map count = new HashMap<>();
int i = 0, j;
for (j = 0; j < tree.length; ++j) {
count.put(tree[j], count.getOrDefault(tree[j], 0) + 1);
if (count.size() > 2) {
count.put(tree[i], count.get(tree[i]) - 1);
count.remove(tree[i++], 0);
}
}
return j - i;
}
Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Two Pointer Approach
The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.
We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Further, we maintain a variable, maxArea, to store the maximum area obtained till now. At every step, we find out the area formed between them, update maxArea and move the pointer pointing to the shorter line towards the other end by one step.
Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.
Single Pass Approach
We observe that for any given sequence that is in descending order, no next larger permutation is possible. For example, no next permutation is possible for the following array:
[9, 5, 4, 3, 1]
Scan through the numbers from right to left, when a descending number is found mark it’s index and then start going back to the right until we find the number just larger than it. Swap it in place.
Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Reverse on Diagonal and then Reverse Left to Right
Intuition
The most elegant solution for rotating the matrix is to firstly reverse the matrix around the main diagonal, and then reverse it from left to right. These operations are called transpose and reflect in linear algebra.
Jump Game
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Dynamic Programming Top-down
Top-down Dynamic Programming can be thought of as optimized backtracking. It relies on the observation that once we determine that a certain index is good / bad, this result will never change. This means that we can store the result and not need to recompute it every time.
Therefore, for each position in the array, we remember whether the index is good or bad. Let’s call this array memo and let its values be either one of: GOOD, BAD, UNKNOWN. This technique is called memoization[3].
An example of a memoization table for input array nums = [2, 4, 2, 1, 0, 2, 0] can be seen in the diagram below. We write G for a GOOD position and B for a BAD one. We can see that we cannot start from indices 2, 3 or 4 and eventually reach last index (6), but we can do that from indices 0, 1, 5 and (trivially) 6.
Steps
- Initially, all elements of the memo table are UNKNOWN, except for the last one, which is (trivially) GOOD (it can reach itself)
- Modify the backtracking algorithm such that the recursive step first checks if the index is known (GOOD / BAD)If it is known then return True / FalseOtherwise perform the backtracking steps as before
- Once we determine the value of the current index, we store it in the memo table
Plus One
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.
Increment the large integer by one and return the resulting array of digits.
“Plus One” is a subset of the problem set “Add Number”, which shares the same solution pattern.
All these problems could be solved in linear time, and the question here is how to solve it without using the addition operation or how to solve it in constant space complexity.
The choice of algorithm should be based on the format of input. Here we list a few examples:
Integers
Usually the addition operation is not allowed for such a case. Use Bit Manipulation Approach. Here is an example: Add Binary.
Strings
Use bit by bit computation. Note, sometimes it might not be feasible to come up a solution with the constant space for languages with immutable strings, e.g. for Java and Python. Here is an example: Add Binary.
Linked Lists
Sentinel Head + Schoolbook Addition with Carry. Here is an example: Plus One Linked List.
Arrays (also the current problem)
Schoolbook addition with carry.
Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.
Sliding Window
Intuition
The question asks us to return the minimum window from the string SS which has all the characters of the string TT. Let us call a window desirable if it has all the characters from TT.
We can use a simple sliding window approach to solve this problem.
In any sliding window based problem we have two pointers. One rightright pointer whose job is to expand the current window and then we have the leftleft pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.
The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.
The answer is the smallest desirable window.
For eg. S = “ABAACBAB” T = “ABC”. Then our answer window is “ACB” and shown below is one of the possible desirable windows.
Algorithm
- We start with two pointers, left and right initially pointing to the first element of the string SS.
- We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of TT.
- Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.
- If the window is not desirable any more, we repeat step \; 2step2 onwards.
Read N Characters Given Read4 II - Call multiple times
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.
Method read4:
The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.
The return value is the number of actual characters read.
Note that read4() has its own file pointer, much like FILE *fp in C.
private int buffPtr = 0;
private int buffCnt = 0;
private char[] buff = new char[4];
public int read(char[] buf, int n) {
int ptr = 0;
while (ptr < n) {
if (buffPtr == 0) {
buffCnt = read4(buff);
}
if (buffCnt == 0) break;
while (ptr < n && buffPtr < buffCnt) {
buf[ptr++] = buff[buffPtr++];
}
if (buffPtr >= buffCnt) buffPtr = 0;
}
return ptr;
}
I used buffer pointer (buffPtr) and buffer Counter (buffCnt) to store the data received in previous calls. In the while loop, if buffPtr reaches current buffCnt, it will be set as zero to be ready to read new data.
Longest Substring with At Most Two Distinct Characters
Given a string s, return the length of the longest substring that contains at most two distinct characters.
Sliding Window
Intuition
Sliding window + HashMap
To solve the problem in one pass let’s use here sliding window approach with two set pointers left and right serving as the window boundaries.
The idea is to set both pointers in the position 0 and then move right pointer to the right while the window contains not more than two distinct characters. If at some point we’ve got 3 distinct characters, let’s move left pointer to keep not more than 2 distinct characters in the window.
- Return N if the string length N is smaller than 3.
- Set both set pointers in the beginning of the string left = 0 and right = 0 and init max substring length max_len = 2.
- While right pointer is less than N:
a) If hashmap contains less than 3 distinct characters, add the current character s[right] in the hashmap and move right pointer to the right.
b) If hashmap contains 3 distinct characters, remove the leftmost character from the hashmap and move the left pointer so that sliding window contains again 2 distinct characters only.
c) Update max_len.
Missing Ranges
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
“a->b” if a != b
“a” if a == b
Example 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99 Output: ["2","4->49","51->74","76->99"] Explanation: The ranges are: [2,2] --> "2" [4,49] --> "4->49" [51,74] --> "51->74" [76,99] --> "76->99"
Linear Scan
Intuition and Algorithm
Since the input array, nums, is sorted ascendingly and all the elements in it are within the given [lower, upper] bounds, we can simply check consecutive elements to see if they differ by one or not. If they don’t, then we have found a missing range.
Time complexity : O(N)
Space complexity : O(1)
class Solution {
public List findMissingRanges(int[] nums, int lower, int upper) {
List result = new ArrayList<>();
int prev = lower - 1;
for (int i = 0; i <= nums.length; i++) {
int curr = (i < nums.length) ? nums[i] : upper + 1;
if (prev + 1 <= curr - 1) {
result.add(formatRange(prev + 1, curr - 1));
}
prev = curr;
}
return result;
}
// formats range in the requested format
private String formatRange(int lower, int upper) {
if (lower == upper) {
return String.valueOf(lower);
}
return lower + "->" + upper;
}
}
Next Closest Time
Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.
You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.
Example 1:
Input: time = “19:34”
Output: “19:39”
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.
This approach here is trying to find next digit for each position in “HH:MM” from right to left. If the next digit is greater than current digit, return directly and keep other digits unchanged.
Here is the steps: (e.g. “17:38”)
Retrieve all four digits from given string and sort them in ascending order, “17:38” -> digits[] {‘1’, ‘3’, ‘7’, ‘8’}
Apply findNext() from the right most digit to left most digit, try to find next greater digit from digits[] (if exist) which is suitable for current position, otherwise return the minimum digit (digits[0]):
“HH:M_”: there is no upperLimit for this position (0-9). Just pick the next different digit in the sequence. In the example above, ‘8’ is already the greatest one, so we change it into the smallest one (digits[0] i.e. ‘1’) and move to next step: “17:38” -> “17:31”
“HH:_M”: the upperLimit is ‘5’ (00~59). The next different digit for ‘3’ is ‘7’, which is greater than ‘5’, so we should omit it and try next. Similarly, ‘8’ is beyond the limit, so we should choose next, i.e. ‘1’: “17:38” -> “17:11”
“H_:MM”: the upperLimit depends on result[0]. If result[0] == ‘2’, then it should be no more than ‘3’; else no upperLimit (0-9). Here we have result[0] = ‘1’, so we could choose any digit we want. The next digit for ‘7’ is ‘8’, so we change it and return the result directly. “17:38” -> “18:11”
“_H:MM”: the upperLimit is ‘2’ (00~23). e.g. “03:33” -> “00:00”
Expressive Words
Sometimes people repeat letters to represent extra feeling. For example:
“hello” -> “heeellooo”
“hi” -> “hiiii”
In these strings like “heeellooo”, we have groups of adjacent letters that are all the same: “h”, “eee”, “ll”, “ooo”.
You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.
For example, starting with “hello”, we could do an extension on the group “o” to get “hellooo”, but we cannot get “helloo” since the group “oo” has a size less than three. Also, we could do another extension like “ll” -> “lllll” to get “helllllooo”. If s = “helllllooo”, then the query word “hello” would be stretchy because of these two extension operations: query = “hello” -> “hellooo” -> “helllllooo” = s.
Return the number of query strings that are stretchy.
Example 1:
Input: s = “heeellooo”, words = [“hello”, “hi”, “helo”]
Output: 1
Explanation:
We can extend “e” and “o” in the word “hello” to get “heeellooo”.
We can’t extend “helo” to get “heeellooo” because the group “ll” is not size 3 or more.
Loop through all words. check(string S, string W) checks if W is stretchy to S.
In check function, use two pointer:
If S[i] == W[j], i++, j++
If S[i - 2] == S[i - 1] == S[i] or S[i - 1] == S[i] == S[i + 1], i++
return false
public int expressiveWords(String S, String[] words) {
int res = 0;
for (String W : words) if (check(S, W)) res++;
return res;
}
public boolean check(String S, String W) {
int n = S.length(), m = W.length(), j = 0;
for (int i = 0; i < n; i++)
if (j < m && S.charAt(i) == W.charAt(j)) j++;
else if (i > 1 && S.charAt(i) == S.charAt(i - 1) && S.charAt(i - 1) == S.charAt(i - 2));
else if (0 < i && i < n - 1 && S.charAt(i - 1) == S.charAt(i) && S.charAt(i) == S.charAt(i + 1));
else return false;
return j == m;
}
Find And Replace in String
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.
To complete the ith replacement operation:
Check if the substring sources[i] occurs at index indices[i] in the original string s.
If it does not occur, do nothing.
Otherwise if it does occur, replace that substring with targets[i].
For example, if s = “abcd”, indices[i] = 0, sources[i] = “ab”, and targets[i] = “eee”, then the result of this replacement will be “eeecd”.
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
For example, a testcase with s = “abc”, indices = [0, 1], and sources = [“ab”,”bc”] will not be generated because the “ab” and “bc” replacements overlap.
Return the resulting string after performing all replacement operations on s.
A substring is a contiguous sequence of characters in a string.
Intuition:
Verify equality of string and change it if necessary.
The only thing we need take attention is that the string form sources and targets can be different.
Instead of record the length changement, I sort indexes and do it from right to left.
(Since indexes.length <= 100 is really small)
In this way, the different length won’t bother us anymore.
Explanation:
Descending indexes[] with tracking its index.
Verify equality of subring in S source and source.
Replace S if necessary.
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
List sorted = new ArrayList<>();
for (int i = 0 ; i < indexes.length; i++) sorted.add(new int[]{indexes[i], i});
Collections.sort(sorted, Comparator.comparing(i -> -i[0]));
for (int[] ind: sorted) {
int i = ind[0], j = ind[1];
String s = sources[j], t = targets[j];
if (S.substring(i, i + s.length()).equals(s)) S = S.substring(0, i) + t + S.substring(i + s.length());
}
return S;
}
Maximize Distance to Closest Person
Solution
You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.
Return that maximum distance to the closest person.
Next Array [Accepted]
Intuition
Let left[i] be the distance from seat i to the closest person sitting to the left of i. Similarly, let right[i] be the distance to the closest person sitting to the right of i. This is motivated by the idea that the closest person in seat i sits a distance min(left[i], right[i]) away.
Algorithm
To construct left[i], notice it is either left[i-1] + 1 if the seat is empty, or 0 if it is full. right[i] is constructed in a similar way.
Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Use Stacks
Intuition
Imagine you are writing a small compiler for your college project and one of the tasks (or say sub-tasks) for the compiler would be to detect if the parenthesis are in place or not.
The algorithm we will look at in this article can be then used to process all the parenthesis in the program your compiler is compiling and checking if all the parenthesis are in place. This makes checking if a given string of parenthesis is valid or not, an important programming problem.
The expressions that we will deal with in this problem can consist of three different type of parenthesis:
(),
{} and
[]
Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Compare one by one using a Priority Queue
Algorithm
Compare every k nodes (head of every linked list) and get the node with the smallest value.
Extend the final sorted linked list with the selected nodes.
Use a Priority Queue
Almost the same as the one above but optimize the comparison process by priority queue. You can refer here for more information about it.
Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Dynamic Programming
Intuition
In brute force, we iterate over the left and right parts again and again just to find the highest bar size up to that index. But, this could be stored. Voila, dynamic programming.
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Min Heap (PriorityQueue)
The idea is to init a heap “the smallest element first”, and add all elements from the array into this heap one by one keeping the size of the heap always less or equal to k. That would results in a heap containing k largest elements of the array.
The head of this heap is the answer, i.e. the kth largest element of the array.
The time complexity of adding an element in a heap of size k is O(log k), and we do it N times that means O(N log k) time complexity for the algorithm.
