Coding Problems and Solutions-9
[1] Flatten a Multilevel Doubly Linked List — You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.
Example:
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:The multilevel linked list in the input is as follows:
After flattening the multilevel linked list it becomes:
(https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/)
Approach — Use recursion.
[2] Remove Zero Sum Consecutive Nodes from Linked List — Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.
After doing so, return the head of the final linked list. You may return any such answer.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.(https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/)
Approach — Use 2 pointer approach. For each node, run a pointer from its next node and every-time the sum is 0 delete all the nodes in between.
[3] Maximum Minimum in Array — Given an array A of N integers. You are also given two integers S and M. Each time you can pick a subarray of size S and increment the values in the subarray by 1. Repeat this at-most M times.
Find the maximum value of minimum value in array A.
Example
Input:
arr = [1,2,3,4,5,6], M=5, S=2Output:
4
Explaination:
1st opertaion subarray index range (0,1) 2 3 3 4 5 6
2nd opertaion subarray index range (0,1) 3 4 3 4 5 6
3rd opertaion subarray index range (0,1) 4 5 3 4 5 6
4th opertaion subarray index range (2,3) 4 5 4 5 5 6
5th opertaion subarray index range (0,1) 5 6 4 5 5 6
(https://leetcode.com/discuss/interview-question/805468/Google-or-OA-or-SDE-(2020)or-India)
Approach — Use binary search.
Binary search on min(arr) to min(arr)+M. For each value K get the minimum number of operations required to obtain minimum value of K. If the number of operations is less than M, then increment K else decrement K.
To obtain minimum number of operations for K, use sliding window.
If the current number is less than K, then increment it to K and add the number of operations to a double ended queue. The current number is added to the current queue sum and then checked if < K.
Keep the queue updated by removing all updates which are older than distance S from current number. Also update queue sum.
[4] Find the Quarter Majority — Given a sorted array of size n, find the majority element. The majority element is the element that appears more than n/4 times. You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7]
Output: 3Example 2:
Input: [1, 1, 2, 2, 3, 3, 4, 5, 7, 7, 7]
Output: 7Example 3:
Input: [1, 1, 2, 3]
Output: 1Approach — Partition the array into N/4 parts. In each part use the first number to do binary search and find index of the first occurrence of that number. Then check if the N/4+1-th number from this index is also same.
If a number occurs more than N/4 times then the number should be starting number in one of the parts.
[5] Validate Stack Sequences — Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
Example:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1(https://leetcode.com/problems/validate-stack-sequences/)
Approach — Use stack.
If the current number in ‘popped’ array is same as the current number in ‘pushed’ stack then pop the ‘pushed’ stack and increment popped index. Else push the number into ‘pushed’ stack.
Return true if the ‘pushed’ stack is empty at the end, else return false.
[6] Pick a random Number — Given a list of intervals e.g. [[4,9], [12,14]], randomaly select one number from any of the intervals.
Each number from all the intervals should have equal probality of getting selected. In the above example, output could be any number from — (4,5,6,7,8,9,12,13,14)
Approach — This is same as random sampling of discrete probability distribution.
Compute the cumulative sums of the distribution for each index. Then pick a uniform random number between 0 and 1. Do binary search to find the index at which cumulative sum ≤ uniform random number.
[7] Merge Intervals With Labels — Given a set of inputs which represents [from, to, comment] in google docs.
Transform the input with overlapping offsets & unique comments to non overlapping offsets and duplicate comments.
Example:
Input:
(0, 3): A
(2, 4): B
(5, 6): COutput:
(0, 2): [A]
(2, 3): [A, B]
(3, 4): [B]
(5, 6): [C]
(https://leetcode.com/discuss/interview-question/634115/)
Approach — Sort the intervals by end time.
For each interval, check which already non-overlapping intervals it intersects with.
If it intersects, the current interval will either create a new interval (if the interval starts before end of the other interval) or will append to an existing interval (if an existing interval is completely within the current interval).
[8] Card Game — Two players are playing a card game where the deck of cards are layed out in a straight line and each card value is visible to both the players.
The value of each card can range from a reasonable [-ve to +ve] number and the length of deck in n.
The rules of the game are such:
- Player 1 starts the game
- Each player has 3 option:
(Option 1: Pick 1st card)
(Option 2: Pick 1st two cards)
(Option 3: Pick 1st three cards) - You’re only allowed to pick cards from the left side of the deck
- Both players have to play optimally.
Return the maximum sum of cards Player 1 can obtain by playing optimally.
(https://leetcode.com/discuss/interview-question/537699/)
Approach — Use recursion with memoization.
In each turn player 1 has 3 options — take 1, 2 or 3 cards from the left (if it is possible) and recursively call the function with the remaining cards.
The function returns the tuple (maximum points for player 1, maximum points for player 2) in each round. Since role of player 1 and player 2 interchanges in each round we need to add the current sum of player 1 to maximum sum of player 2 from next round.
[9] Increment Subsequence — Given an array of +ve numbers and another array of same size with zeros.
Here are the operations you’re allowed to perform on the second array.
- You’re allowerd to increment only a subarray of values. [Subarray has to be a contiguous block]
- You’re allowerd to increment the values of the subarray by a value of 1.
How many increment operations does it require to transform second array of zeros to the first array?
Input:
[3, 4, 2, 5, 7]
Output: 9
(https://leetcode.com/discuss/interview-question/633162/Google-Virtual-Onsite-April-2020-Bangalore)
Approach — Use greedy with divide and conquer strategy.
Find the index of the smallest element in the current sub-array of input and increment the current sub-array by an amount equal to the difference of the input value and the current value of the element in the sub-array.
Recursively do this for the left and right sub-arrays of the min-index. Return the number of steps required to completely transform each sub-arrays. Then take their sums.
[10] Faulty Keyboard — Given a string which is the sentence typed using that keyboard and a dictionary of valid words, return all possible correct formation of the sentence.
Example:
Input: s = "I lik to xplor univ rs ", dictionary = {"I", "like", "explore", "toe", "universe", "rse", "to", "xplore", "univ"}Output:
['I like to explore univ rse',
'I like to explore universe',
'I like toe xplore univ rse',
'I like toe xplore universe']
There are two spaces after “lik”, “to” and before “univ” in the sentence indicating one is actual space and another one is resulted by hitting key ‘e’.
(https://leetcode.com/discuss/interview-question/643158/Google-or-Phone-or-Faulty-Keyboard)
Approach — Use Trie
Store the words in a prefix trie.
In the sentence, find all possible words starting at index i that can be found in the trie. Return the possible words and the end positions in the sentence. Recursively call the trie starting with each end position from the current formations.
[11] Common substrings between two strings — Given two large articles, search and return for all the sub-sentences which existing in both articles. The sub-sentence is required at least more than three words.
Example:
Input: a = "today is sunny and okay I feel yes so happy", b = "tomorrow is sunny and that makes today is sunny and okay me feel yes so happy too"
Output: ["is sunny and", "feel yes so happy", "today is sunny and okay"]
Approach — Use Trie
Store the word level suffixes of input ‘b’ in the trie. For each sub-string (of length ≥ 3) in input ‘a’, check if it can be found in the trie.
