Facebook Top Interview Questions Flashcards
Next Permutation (Medium)
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.
public void nextPermutation(int[] A) {
if(A == null || A.length <= 1) return;
int i = A.length - 2;
while(i >= 0 && A[i] >= A[i + 1]) i–; // Find 1st id i that breaks descending order
if(i >= 0) { // If not entirely descending
int j = A.length - 1; // Start from the end
while(A[j] <= A[i]) j–; // Find rightmost first larger id j
swap(A, i, j); // Switch i and j
}
reverse(A, i + 1, A.length - 1); // Reverse the descending sequence
}
public void swap(int[] A, int i, int j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
public void reverse(int[] A, int i, int j) {
while(i < j) swap(A, i++, j–);
}
Trapping Rain Water (Hard)
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.
Let’s think about the absolute simplest case: we’ve got a [2,1,3] array, telling us that we can trap 1 block of rainwater.
How we arrive to this, is pretty simple, we know that because we’ve got a two at the beginning, we can only fill up to two blocks of water per point, and we know that we can only do that at a point after two, and we know that we can do it at all because 3, at the end of the array, would be able to contain the water, so we can add water until we get to 3, and can only add 2 - the height of the point.
So, if we had something a little more complex, like [2, 1, 3, 1, 4], we could fill up to the 3 optimally, and then repear the same algorithm from the 3 onward. However, if we had, instead, [2, 1, 3, 1, 2] we would fill up to the 3, and then see that we cannot fill over to the 2 because we would overflow, so we instead mirror the algorithm and bring from the 2 backward.
Pow(x, n) (Medium)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Fast Power Algorithm Recursive
Intuition
Assuming we have got the result of x ^ n, how can we get x ^ {2 * n}
Obviously we do not need to multiply x for another n times. Using the formula (x ^ n) ^ 2 = x ^ {2 * n}, we can get x ^ {2 * n} at the cost of only one computation. Using this optimization, we can reduce the time complexity of our algorithm.
Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Sorting
Intuition
If we sort the intervals by their start value, then each set of intervals that can be merged will appear as a contiguous “run” in the sorted list.
Algorithm
First, we sort the list as described. Then, we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.
Valid Number
A valid number can be split up into these components (in order):
A decimal number or an integer.
(Optional) An ‘e’ or ‘E’, followed by an integer.
A decimal number can be split up into these components (in order):
(Optional) A sign character (either ‘+’ or ‘-‘).
One of the following formats:
One or more digits, followed by a dot ‘.’.
One or more digits, followed by a dot ‘.’, followed by one or more digits.
A dot ‘.’, followed by one or more digits.
An integer can be split up into these components (in order):
(Optional) A sign character (either ‘+’ or ‘-‘).
One or more digits.
Given a string s, return true if s is a valid number.
Follow The Rules!
Intuition
The problem statement outlines a very specific set of rules. Let’s put all possible characters into groups, and then create a set of rules for each group. Then, we can iterate through the input and evaluate if the characters are following the rules or not.
Simplify Path
Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
The path starts with a single slash ‘/’.
Any two directories are separated by a single slash ‘/’.
The path does not end with a trailing ‘/’.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.
Using Stacks
Intuition
This is a direct implementation of one of the most common commands used (in one form of the other) on all the famous operating systems. For e.g. this directly translates to a part of the implementation of the cd command functionality in the Unix OS. It basically helps us to change directory. Obviously, there’s much more to it than simply figuring out the smallest path of the final directory where the user wants to go. There is kernel level implementation involved that actually uses the underlying file system to change the directory you are in to the one where you want to go.
Algorithm
Initialize a stack, S that we will be using for our implementation.
Split the input string using / as the delimiter. This step is really important because no matter what, the given input is a valid path and we simply have to shorten it. So, that means that whatever we have between two / characters is either a directory name or a special character and we have to process them accordingly.
Once we are done splitting the input path, we will process one component at a time.
If the current component is a . or an empty string, we will do nothing and simply continue. Well if you think about it, the split string array for the string /a//b would be [a,,b]. yes, that’s an empty string in between a and b. Again, from the perspective of the overall path, it doesn’t mean anything.
If we encounter a double-dot .., we have to do some processing. This simply means go one level up in the current directory path. So, we will pop an entry from our stack if it’s not empty.
Finally, if the component we are processing right now is not one of the special characters, then we will simply add it to our stack because it’s a legitimate directory name.
Once we are done processing all the components, we simply have to connect all the directory names in our stack together using / as the delimiter and we will have our shortest path that leads us to the same directory as the one provided as an input.
Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Compare with Reverse
Intuition
A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. e.g. madam
A palindrome, and its reverse, are identical to each other.
Algorithm
We’ll reverse the given string and compare it with the original. If those are equivalent, it’s a palindrome.
Since only alphanumeric characters are considered, we’ll filter out all other types of characters before we apply our algorithm.
Additionally, because we’re treating letters as case-insensitive, we’ll convert the remaining letters to lower case. The digits will be left the same.
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.
Word Break II
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Top-Down Dynamic Programming
Overview
The solutions for this problem go by many names, such as Dynamic Programming, recursion with memoization, DFS, and backtracking etc. They all capture certain traits of the solutions.
In essence, all these solutions can all be categorized as variants of Dynamic Programming (DP), as we will discuss in this article.
LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
1) LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
2) int get(int key) Return the value of the key if the key exists, otherwise return -1.
3) void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Ordered dictionary: LinkedHashMap
Intuition
We’re asked to implement the structure which provides the following operations in O(1) time :
Get the key / Check if the key exists
Put the key
Delete the first added key
The first two operations in O(1) time are provided by the standard hashmap, and the last one - by linked list.
There is a structure called ordered dictionary, it combines behind both hashmap and linked list. In Python this structure is called OrderedDict and in Java LinkedHashMap.
Find Peak Element (Medium)
A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
You must write an algorithm that runs in O(log n) time.
Recursive Binary Search
Algorithm
We can view any given sequence in numsnums array as alternating ascending and descending sequences. By making use of this, and the fact that we can return any peak as the result, we can make use of Binary Search to find the required peak element.
In case of simple Binary Search, we work on a sorted sequence of numbers and try to find out the required number by reducing the search space at every step. In this case, we use a modification of this simple Binary Search to our advantage. We start off by finding the middle element, midmid from the given numsnums array. If this element happens to be lying in a descending sequence of numbers. or a local falling slope(found by comparing nums[i]nums[i] to its right neighbour), it means that the peak will always lie towards the left of this element. Thus, we reduce the search space to the left of midmid(including itself) and perform the same process on left subarray.
If the middle element, midmid lies in an ascending sequence of numbers, or a rising slope(found by comparing nums[i]nums[i] to its right neighbour), it obviously implies that the peak lies towards the right of this element. Thus, we reduce the search space to the right of midmid and perform the same process on the right subarray.
In this way, we keep on reducing the search space till we eventually reach a state where only one element is remaining in the search space. This single element is the peak element.
To see how it works, let’s consider the three cases discussed above again.
Case 1. In this case, we firstly find 33 as the middle element. Since it lies on a falling slope, we reduce the search space to [1, 2, 3]. For this subarray, 22 happens to be the middle element, which again lies on a falling slope, reducing the search space to [1, 2]. Now, 11 acts as the middle element and it lies on a falling slope, reducing the search space to [1] only. Thus, 11 is returned as the peak correctly.
