Lecture_Notes/imperfect_notes/Google and Facebook Interviews/1.md

Google and Facebook Interviews

Interview Tips

1. 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
2. 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

3. 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

Question 1 Time Based Key-Value Store

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

• Stores the key and value, along with the given timestamp.

2. 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.

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 be O(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 maximum O(n) pairs. So, the overall time complexity will be O(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	{"()"}