16 KiB
Google and Facebook Interviews
Interview Tips
- Always give Brute Force for every question.
- Benefits:
- It favours against worse odds. It is better to give a brute force then to be totally blank.
- Predicts Optimal Solution
- Benefits:
- Data Structures/ Algorithms
Time Complexity | Datastructure and Algorithms |
---|---|
O(n\log{n}) |
Sorting |
O(n) |
Two Pointers/ Smart Sorting/ dfs/ bfs |
O(n^2) |
Dynamic Programming |
O(\log{n}) |
Binary Search |
O(1) |
HashMap |
- Writing a working code
- Google/Facebook/Uber/Microsoft
- They need working code
- Take care of Edge cases
- Candidates may get rejected for not taking care of Edge cases
- Spend
10\%
of your time on Edge cases
- Give proper names to characters
- Benefits
- Less Confusion, Error free code
- Good presentation and easier to explain
- Benefits
Question 1 Time Based Key-Value Store
Create a timebased key-value store class TimeMap, that supports two operations.
- set(string key, string value, int timestamp)
- Stores the key and value, along with the given timestamp.
- get(string key, int timestamp)
- Returns a value such that set(key, value, times tamp_prev) was called previously, with timestamp_prev <= timestamp.
- If there are multiple such values, it returns the one with the largest timestamp_prev.
- If there are no values, it returns the empty string ("").
Example 1:
Input:
inputs = ["TimeMap","set","get","get","set","get","get"],
inputs = [[],["foo","bar",1],["foo",1],["foo",3],
["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.get("foo", 1); // output "bar"
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // output "bar2"
kv.get("foo", 5); //output "bar2"
Example 2:
Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]
Note:
- All key/value strings are lowercase.
- All key/value strings have length in the range [1, 100]
- The timestamps for all TimeMap.set operations are strictly increasing.
- 1 <= timestamp <= 10^7
- TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.
Brute Force
- Store key, value and timestamp in an array.
- For every get request run a linear loop to find the largest timestamp in the given bounds with the given key. Return value.
- Time complexity:
- TimeMap.set =
O(1)
. - TimeMap.get =
O(n)
. Because you are iterating over the whole array.
- TimeMap.set =
Hints
- Suppose there were no time stamps. What would be the best data structure for this problem. Hashmap, As it gives
O(1)
look up. - If we store all the timestamps corresponding to a key in an array, and store that array as value in a HashMap. Then for a given key we can run a loop on the corresponding array and find our answer.
- This approach is still
O(n)
as we may have only one key. - It is given that "The timestamps for all TimeMap.set operations are strictly increasing." Can we do a binary search to find our answer?
- The time complexity now will be
O(\log{n})
.
Code
class TimeMap {
public:
/** Initialize your data structure here. */
unordered_map<string, vector<pair<int,string>>> mp;
TimeMap() {
}
void set(string key, string value, int timestamp) {
if(mp.find(key)!= mp.end()){
mp[key].push_back({timestamp,value});
}else{
vector<pair<int,string>> temp;
temp.push_back({timestamp,value});
mp[key] = temp;
}
}
string get(string key, int timestamp) {
if(mp.find(key) == mp.end()){
return NULL;
}
int lo = 0, hi = mp[key].size()-1;
string ans;
while(lo<=hi){
int mid = lo + (hi-lo)/2;
if(mp[key][mid].first <= timestamp){
ans = mp[key][mid].second;
lo = mid+1;
}else{
hi = mid-1;
}
}
return ans;
}
};
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap* obj = new TimeMap();
* obj->set(key,value,timestamp);
* string param_2 = obj->get(key,timestamp);
*/
Time Complexity
- Worst case it will
O(\log{n})
for each get query, where n is the number of set queries. - For set query it will be
O(1)
.
Dry Run
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.set("foo", "bar2", 2);
kv.set("foo", "bar3", 3);
kv.set("foo", "bar4", 4);
kv.get("foo", 3);
lo | hi | mid | key | mp[key] | Answer |
---|---|---|---|---|---|
0 | 3 | 1 | foo | {{1,bar},{2,bar2},{3,bar3},{4,bar4}} | bar2 |
2 | 3 | 2 | foo | {{1,bar},{2,bar2},{3,bar3},{4,bar4}} | bar3 |
3 | 3 | 3 | foo | {{1,bar},{2,bar2},{3,bar3},{4,bar4}} | bar3 |
3 | 2 |
Question 2 Order of People Heights
You are given the following :
A positive number N Heights : A list of heights of N persons standing in a queue Infronts : A list of numbers corresponding to each person (P) that gives the number of persons who are taller than P and standing in front of P You need to return list of actual order of persons’s height
Consider that heights will be unique
Example
Input :
Heights: 5 3 2 6 1 4
InFronts: 0 1 2 0 3 2
Output :
actual order is: 5 3 2 1 6 4
Explaination:
So, you can see that for the person with height 5,
there is no one taller than him who is in front of him,
and hence Infronts has 0 for him.
For person with height 3, there is 1 person
( Height : 5 ) in front of him who is taller than him.
You can do similar inference for other people in the list.
Brute Force
- Go through all the permutations of the heights and for every permutation check if it holds true with Infronts order.
- The time complexity of this approach will be
O(n!* n)
Hints
- If we sort the arrays based on heights, can we do something?
Heights: 1 2 3 4 5 6
Infront: 3 2 1 2 0 0
- We know the largest element will always have
0
infront value. No matter how many elements we put in front of largest element there will be no larger element than the largest element. - Lets put largest element at first place.
Ans: 6
- Now for the next largest element we know the position to insert.
Ans: 5 6
Ans: 5 6 4
Ans: 5 3 6 4
Ans: 5 3 2 6 4
Ans: 5 3 2 1 6 4
- Putting a smaller element in front a given element will not affect it. Thus if we move from the largest to smallest we can insert elements at their respective positions.
- Time complexity:
O(n^2)
. As we are shifting all the elements while inserting a given element. This is similar to insertion sort. - Can we do better than this?
- If we already know which place a given element should go, we would not have to move the elements.
- For this we need to know the number of empty places infront a given position.
- If we fill elements in sorted order of ascending values, at every step we will know what ever is coming next will be greater than the given element.
- We can use segment trees to do the range queries.
Code
void buildST(int s, int e, int index, vector<int> &tree){
if(s == e){
tree[index] = 1;
return;
}
int mid = s + (e-s)/2;
buildST(s, mid, index*2+1, tree);
buildST(mid+1, e, index*2+2, tree);
tree[index] = tree[index*2+1] + tree[index*2+2];
}
int getPos(vector<int>&tree, int s, int e, int index, int pos){
if(s==e){
tree[index]--;
return s;
}
int mid = s+(e-s)/2;
if(pos >= tree[index*2+1]){
tree[index]--;
return getPos(tree, mid+1, e,index*2+2, pos-tree[index*2+1]);
}else{
tree[index]--;
return getPos(tree, s, mid, index*2+1, pos);
}
}
vector<int> Solution::order(vector<int> &A, vector<int> &B) {
int n = A.size();
vector<int> tree(4*n);
vector<pair<int,int>> person;
for(int i = 0; i<n; i++){
person.push_back({A[i],B[i]});
}
sort(person.begin(), person.end());
buildST(0,n-1,0,tree);
vector<int> res(n);
for(auto p: person){
int pos = getPos(tree,0,n-1,0,p.second);
//cout << pos << endl;
res[pos] = p.first;
}
return res;
}
Time Complexity
- For each element we will spend
O(\log{n})
time to find the proper position. Total time will beO(n\log{n})
. - Space Complexity will be
O(n)
as we will be storing the elements in a segment tree.
Dry Run
Heights: 1 2 3 4 5 6
Infront: 3 2 1 2 0 0
Segment Tree | Height | Infront | Answer |
---|---|---|---|
{0,5,6}{0,2,3}{3,5,3}{0,1,2}{2,2,1}{3,4,2}{5,5,1}{0,0,1}{1,1,1}{}{}{3,3,1}{4,4,1}{}{} | 1 | 3 | {, , ,1, , } |
{0,5,5}{0,2,3}{3,5,2}{0,1,2}{2,2,1}{3,4,1}{5,5,1}{0,0,1}{1,1,1}{}{}{3,3,0}{4,4,1}{}{} | 2 | 2 | { , ,2,1, , } |
{0,5,4}{0,2,2}{3,5,2}{0,1,2}{2,2,0}{3,4,1}{5,5,1}{0,0,1}{1,1,1}{}{}{3,3,0}{4,4,1}{}{} | 3 | 1 | {,3,2,1, , } |
{0,5,3}{0,2,1}{3,5,2}{0,1,1}{2,2,0}{3,4,1}{5,5,1}{0,0,1}{1,1,0}{}{}{3,3,0}{4,4,1}{}{} | 4 | 2 | {,3,2,1, ,4} |
{0,5,2}{0,2,1}{3,5,1}{0,1,1}{2,2,0}{3,4,1}{5,5,0}{0,0,1}{1,1,0}{}{}{3,3,0}{4,4,1}{}{} | 5 | 0 | {5,3,2,1, ,4} |
{0,5,1}{0,2,0}{3,5,1}{0,1,0}{2,2,0}{3,4,1}{5,5,0}{0,0,0}{1,1,0}{}{}{3,3,0}{4,4,1}{}{} | 6 | 0 | {5,3,2,1,6,4} |
{0,5,0}{0,2,0}{3,5,0}{0,1,0}{2,2,0}{3,4,0}{5,5,0}{0,0,0}{1,1,0}{}{}{3,3,0}{4,4,0}{}{} |
Question 3 Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals.
For example:
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Make sure the returned intervals are sorted.
Brute Force
- If we iterate over all the intervals and for each interval try to find another interval that is overlapping.
- When we find an overlapping pair we can merge them and again start our iterations.
- Time Complexity: For finding a pair we may take
O(n^2)
time. Every time we merge a pair we reduce the list by one. There can be at maximumO(n)
pairs. So, the overall time complexity will beO(n^3)
.
Hint
- If we sort the intervals based on the starting time, all the overlapping itervals will be adjacent to each other.
- We can then merge the overlapping intervals in linear time.
Code
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool compareIntervals(Interval a, Interval b){
return a.start < b.start;
}
vector<Interval> Solution::merge(vector<Interval> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
sort(A.begin(), A.end(), compareIntervals);
vector<Interval> res;
int cur_start, cur_end;
bool first = true;
for(auto a:A){
if(first){
first = false;
cur_start = a.start;
cur_end = a.end;
continue;
}
if(a.start <= cur_end){
cur_end = max(a.end,cur_end);
}else{
Interval *i = new Interval(cur_start, cur_end);
res.push_back(*i);
cur_start = a.start;
cur_end = a.end;
}
}
Interval* i = new Interval(cur_start, cur_end);
res.push_back(*i);
return res;
}
Time Complexity
O(n)
Dry Run
Array: [1,3],[2,6],[8,10],[15,18]
cur_start | cur_end | cur_interval | Answer |
---|---|---|---|
[1,3] | {} | ||
1 | 3 | [2,6] | {} |
1 | 6 | [8,10] | {{1,6}} |
8 | 10 | [15,18] | {{1,6},{8,10}} |
15 | 18 | {{1,6},{8,10},{15,18}} |
Question 4 Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Example 1:
Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")("
Output: [""]
Brute Force
- If we are given a string of parentheses, we can check if it is valid or not. We can use a stack or a counter to do so. This will be an
O(n)
algorithm. - We can recursively solve this question by keeping track of number of characters removed.
- We will first remove no character and check the string. Then we will remove one character to iteratively using backtracking.
- We will check when ever the number of characters to remove becomes zero.
- When we find a valid string we can add it to the result set. As there can be multiple calls to same string.
- Whenever the result array becomes non-empty we will stop increasing the number of characters to be removed and return.
Hint
- Questions like this do not have good algorithms.
- I am sharing it so that you understand the importance of Brute force.
- However, you can apply some pruning to considerably improve the actual running time.
- I have used several ideas to improve time complexity.
- Count the number of bad parentheses. And you know your minimum.
- I also counted number of bad open parentheses and bad close parentheses saperately.
- I counted number of open and close parentheses so far.
Code
class Solution {
public:
bool isValid(string s){
if(s=="")return true;
int count = 0;
for(auto c: s){
if(c == '('){
count++;
}else if (c== ')'){
if(count <= 0) return false;
count--;
}
}
if(count!=0) return false;
return true;
}
void makevalid(string s, int open_to_remove, int close_to_remove, int open_count, int close_count, int from, unordered_set<string> &res){
if(close_count > open_count) return;
int toDelete = open_to_remove + close_to_remove;
if(toDelete > s.size() - from){
return;
}
if(toDelete == 0 && isValid(s)){
res.insert(s);
}else{
for(int i = from; i<=s.size()-toDelete; i++){
if(s[i] == ')' && close_to_remove>0){
string newS = s.substr(0,i);
newS += (i+1<s.size())? s.substr(i+1, s.size()-i-1):"";
makevalid(newS,open_to_remove, close_to_remove-1, open_count, close_count, i, res);
}
if(s[i] == '(' && open_to_remove>0){
string newS = s.substr(0,i);
newS += (i+1<s.size())? s.substr(i+1, s.size()-i-1):"";
makevalid(newS,open_to_remove-1, close_to_remove , open_count, close_count, i, res);
}
if(s[i] == ')') close_count++;
else if(s[i] == '(') open_count++;
}
}
}
int findMin(string s, int &open_to_remove, int &close_to_remove){
int ans = 0, count =0;
for(auto c:s){
if(c==')'){
count--;
}else if(c=='('){
count++;
}
if(count < 0){
ans++;
count=0;
}
}
open_to_remove = count;
close_to_remove = ans;
return ans+count;
}
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> res;
int open_to_remove, close_to_remove;
findMin(s, open_to_remove, close_to_remove);
makevalid(s,open_to_remove, close_to_remove,0,0,0,res);
vector<string> res2;
for(auto s: res){
res2.push_back(s);
}
return res2;
}
};
Time Complexity
O(2^n)
For every i, every element will either be removed or included.
Dry Run
s = "())"
Main Call | Children Calls | res |
---|---|---|
makevalid("())",1,0) | makevalid("))",0,0), makevalid("()",0,1), makevalid("()",0,2) | |
makevalid("))",0,0) | Invalid | |
makevalid("()",0,1) | Valid | {"()"} |
makevalid("()",0,2) | Valid | {"()"} |