Microsoft SDE2 Interview Experience

Round 1

Questions:

1. You are given a string s = "31415926535 8979323846264338327" and a list of words: ["314", "15926535 89", "79323846264", "338327", "7932", "3846264", "338327"]. Your task is to partition the string s into substrings such that: Each substring is present in the given list of words. The number of partitions (substrings) is minimized.

   I was not able to solve this question.

2. Time-Based Key-Value Store The second question was easy, able to solve it, but the interviewer did not like my approach.

class TimeMap {
public:
    unordered_map<string,vector<pair<string,int>>> umap;
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        if(umap.find(key)!=umap.end()){ //already exist in map
            umap[key].push_back({value,timestamp});
            return;
        }
        umap[key].push_back({value,timestamp});
        return;
    }
    
    string search_val(vector<pair<string,int>> &v, int timestamp){
        int n=v.size();
        int i=0;
        int j=n-1;

        if(timestamp<v[0].second) return "";
        string ans="";
        while(i<=j){
            int mid=i+(j-i)/2;
            if(v[mid].second==timestamp) return v[mid].first;
            else if(v[mid].second<timestamp){
                ans=v[mid].first;
                i=mid+1;
            }
            else{
                j=mid-1;
            }
        }

        return ans;
    }

    string get(string key, int timestamp) {
        if(umap.find(key)==umap.end()) return "";
        return search_val(umap[key],timestamp);
    }
};

/**
 * 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);
 */