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.
Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Priority Queues
We can’t really process the given meetings in any random order. The most basic way of processing the meetings is in increasing order of their start times and this is the order we will follow. After all, it makes sense to allocate a room to the meeting that is scheduled for 9 a.m. in the morning before you worry about the 5 p.m. meeting, right?
Algorithm
- Sort the given meetings by their start time.
- Initialize a new min-heap and add the first meeting’s ending time to the heap. We simply need to keep track of the ending times as that tells us when a meeting room will get free.
- For every meeting room check if the minimum element of the heap i.e. the room at the top of the heap is free or not.
- If the room is free, then we extract the topmost element and add it back with the ending time of the current meeting we are processing.
- If not, then we allocate a new room and add it to the heap.
- After processing all the meetings, the size of the heap will tell us the number of rooms allocated. This will be the minimum number of rooms needed to accommodate all the meetings.
Backspace String Compare
(Editor’s Choice: Frequently asked in a Google phone interview)
Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Build String using a Stack
Intuition
Let’s individually build the result of each string (build(S) and build(T)), then compare if they are equal.
Algorithm
To build the result of a string build(S), we’ll use a stack based approach, simulating the result of each keystroke.
Minimum Cost to Hire K Workers
There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.
We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:
- Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
- Every worker in the paid group must be paid at least their minimum wage expectation.
Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10 ^(-5) of the actual answer will be accepted.
Heap
Intuition
At least one worker is paid their minimum wage expectation.
Additionally, every worker has some minimum ratio of dollars to quality that they demand. For example, if wage[0] = 100 and quality[0] = 20, then the ratio for worker 0 is 5.0.
The key insight is to iterate over the ratio. Let’s say we hire workers with a ratio R or lower. Then, we would want to know the K workers with the lowest quality, and the sum of that quality. We can use a heap to maintain these variables.
Algorithm
Maintain a max heap of quality. (We’re using a minheap, with negative values.) We’ll also maintain sumq, the sum of this heap.
For each worker in order of ratio, we know all currently considered workers have lower ratio. (This worker will be the ‘captain’, as described in Approach #1.) We calculate the candidate answer as this ratio times the sum of the smallest K workers in quality.
K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)^2 + (y1 - y2)^2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
This is a very classical problem, so-called K-th problem.
Here I will share some summaries and some classical solutions to this kind of problem.
The very naive and simple solution is sorting the all points by their distance to the origin point directly, then get the top k closest points. We can use the sort function and the code is very short.
Theoretically, the time complexity is O(NlogN), practically, the real time it takes on leetcode is 104ms.
The advantages of this solution are short, intuitive and easy to implement.
The disadvatages of this solution are not very efficient and have to know all of the points previously, and it is unable to deal with real-time(online) case, it is an off-line solution.
The short code shows as follows:
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]);
return Arrays.copyOfRange(points, 0, K);
}
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Elementary Math
Intuition
Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.
Algorithm
Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of l1 and l2. Since each digit is in the range of 0…9, summing two digits may “overflow”. For example 5+7=12. In this case, we set the current digit to 22 and bring over the carry=1 to the next iteration. carry must be either 0 or 1 because the largest possible sum of two digits (including the carry) is 9 + 9 + 1 = 19
The pseudocode is as following:
1) Initialize current node to dummy head of the returning list.
2) Initialize carry to 0.
3) Initialize p and q to head of l1 and l2 respectively.
4) Loop through lists l1 and l2 until you reach both ends.
a) Set x to node p’s value. If p has reached the end of l1, set to 0.
b) Set y to node q’s value. If q has reached the end of l2, set to 0.
c) Set sum = x + y + carry.
d) Update carry = sum / 10.
e) Create a new node with the digit value of (sum mod 10) and set it to current node’s next, then advance
current node to next.
f) Advance both p and q.
5) Check if carry=1, if so append a new node with digit 11 to the returning list.
6) Return dummy head’s next node.
Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Two pass algorithm
Intuition
We notice that the problem could be simply reduced to another one : Remove the (L−n+1) th node from the beginning in the list , where L is the list length. This problem is easy to solve once we found list length L.
Algorithm
First we will add an auxiliary “dummy” node, which points to the list head. The “dummy” node is used to simplify some corner cases such as a list with only one node, or removing the head of the list. On the first pass, we find the list length L. Then we set a pointer to the dummy node and start to move it through the list till it comes to the (L−n) th node. We relink next pointer of the(L−n) th node to the (L−n+2) th node and we are done.
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Iteration
Intuition
We can achieve the same idea via iteration by assuming that l1 is entirely less than l2 and processing the elements one-by-one, inserting elements of l2 in the necessary places in l1.
Algorithm
First, we set up a false “prehead” node that allows us to easily return the head of the merged list later. We also maintain a prev pointer, which points to the current node for which we are considering adjusting its next pointer. Then, we do the following until at least one of l1 and l2 points to null: if the value at l1 is less than or equal to the value at l2, then we connect l1 to the previous node and increment l1. Otherwise, we do the same, but for l2. Then, regardless of which list we connected, we increment prev to keep it one step behind one of our list heads.
After the loop terminates, at most one of l1 and l2 is non-null. Therefore (because the input lists were in sorted order), if either list is non-null, it contains only elements greater than all of the previously-merged elements. This means that we can simply connect the non-null list to the merged list and return it.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// At least one of l1 and l2 can still have nodes at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;
return prehead.next; } }
Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Recursive
Intuition
The basic idea behind the recursive solution is to consider the linked list like a graph. Every node of the Linked List has 2 pointers (edges in a graph). Since, random pointers add the randomness to the structure we might visit the same node again leading to cycles.
All we do in this approach is to just traverse the graph and clone it. Cloning essentially means creating a new node for every unseen node you encounter. The traversal part will happen recursively in a depth first manner. Note that we have to keep track of nodes already processed because, as pointed out earlier, we can have cycles because of the random pointers.
Algorithm
- Start traversing the graph from head node.
- If we already have a cloned copy of the current node in the visited dictionary, we use the cloned node reference.
- If we don’t have a cloned copy in the visited dictionary, we create a new node and add it to the visited dictionary. visited_dictionary[current_node] = cloned_node_for_current_node.
- We then make two recursive calls, one using the random pointer and the other using next pointer. The diagram from step 1, shows random and next pointers in red and blue color respectively. Essentially we are making recursive calls for the children of the current node. In this implementation, the children are the nodes pointed by the random and the next pointers.
Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Recursion
Intuition
First of all, let’s simplify the problem and implement a function max_gain(node) which takes a node as an argument and computes a maximum contribution that this node and one/zero of its subtrees could add.
That means one needs to modify the above function and to check at each step what is better : to continue the current path or to start a new path with the current node as a highest node in this new path.
Algorithm
Now everything is ready to write down an algorithm.
1) Initiate max_sum as the smallest possible integer and call max_gain(node = root).
2) Implement max_gain(node) with a check to continue the old path/to start a new path:
a) Base case : if node is null, the max gain is 0.
b) Call max_gain recursively for the node children to compute max gain from the left and right subtrees : left_gain = max(max_gain(node.left), 0) and
right_gain = max(max_gain(node.right), 0).
c) Now check to continue the old path or to start a new path. To start a new path would cost price_newpath = node.val + left_gain + right_gain. Update max_sum if it’s better to start a new path.
d) For the recursion return the max gain the node and one/zero of its subtrees could add to the current path : node.val + max(left_gain, right_gain).
class Solution {
int max_sum = Integer.MIN_VALUE;
public int max_gain(TreeNode node) {
if (node == null) return 0;
// max sum on the left and right sub-trees of node
int left_gain = Math.max(max_gain(node.left), 0);
int right_gain = Math.max(max_gain(node.right), 0);
// the price to start a new path where `node` is a highest node
int price_newpath = node.val + left_gain + right_gain;
// update max_sum if it's better to start a new path
max_sum = Math.max(max_sum, price_newpath);
// for recursion :
// return the max gain if continue the same path
return node.val + Math.max(left_gain, right_gain);
}
public int maxPathSum(TreeNode root) {
max_gain(root);
return max_sum;
}
}
