モックインタビューのサービスGainloのブログの問題を1日1問

gainloというサービスを紹介しているブログを発見。

Software Engineer向けのMocked Interview - 外資系マネージャーの独り言

このモックインタビューのサービスは有料らしいが、ブログも中々読み応えがある。毎日一問ずつ解いてみたのでその記録を。

blog.gainlo.co まずは愚直に解く。この"Sub"というのがポイント。つまり複数のウィンドウに切って処理するので「どこまで切るか」「どこから切るか」で何回もforループを書く必要があるが、そこをウィンドウをスライドするイメージで計算量を減らす工夫をするテクニックを解説している。

vector<vector<int>> getSubArray(vector<int> num, int sum){
    vector<vector<int>> ret;
    int i = 0;
    int j = 0;
    int s = num[0];
    while( i < num.size() && j < num.size()) {
        if( i!=j ){
            s+=num[j];
        }
        if ( s > sum ){
            s -= num[i];
            i++;
        }
        if( s == sum ){
            ret.push_back(getRange(num,i,j));
            s -= num[i];
            i++;
        }
        j++;
    }
    return ret;
}

もしくは動的計画法でメモ化を使ったやり方。

void getSubArrayDP( vector<vector<int>>& result, vector<int> sub, vector<int> num, int sum, int remaining, int i ){

    if( remaining == 0 ) {
        auto it = find(result.begin(),result.end(),sub);
        if(it == result.end())
            result.push_back(sub);
        return;
    }

    if( i == num.size() || remaining < 0 ) return;

    sub.push_back(num[i]);
    getSubArrayDP(result, sub, num, sum, remaining - num[i], i+1);

    getSubArrayDP(result, vector<int>(), num, sum, sum, i+1);

    return;
}

続いてアナグラム。Wikipediaによると

アナグラム - Wikipedia

blog.gainlo.co

なんだ、一旦並べ替えて数えるだけか。

vector<vector<string>>  getAnagramGroup( vector<string> input ){
    vector<vector<string>> ret;
    unordered_map<string,vector<string>> anagramMap;

    for( string s : input ){
        string key = s;
        sort(key.begin(),key.end());
        auto it = anagramMap.find(key);
        if( it != anagramMap.end()){
            it->second.push_back(s);
        } else {
            anagramMap.insert(make_pair(key,vector<string>{s}));
        }
    }

    for( auto it = anagramMap.begin(); it != anagramMap.end(); ++it) {
        if(it->second.size() > 1)
            ret.push_back(it->second);
    }
    return ret;
}

blog.gainlo.co

いわゆる最小の編集距離を求める問題。と聞くと難しそうだが前回紹介した動的計画法がそのまま使える。積み上げていく感じをイメージするとわかりやすい。

int Solution::minDistance(string word1, string word2) {
    vector<vector<int>> distance(word1.length() + 1, vector<int>(word2.length() + 1, 0));
    for (int i = 0; i < distance.size(); i++) {
        for (int j = 0; j < distance[0].size(); j++) {
            if (i == 0)
                distance[i][j] = j;
            else if (j == 0)
                distance[i][j] = i;
        }
    }

    for (int i = 1; i < distance.size(); i++) {
        for (int j = 1; j < distance[0].size(); j++) {
            if (word1[i - 1] == word2[j - 1])
                distance[i][j] = distance[i - 1][j - 1];
            else
                distance[i][j] = 1 + min(distance[i - 1][j - 1], min(distance[i - 1][j], distance[i][j - 1]));
        }
    }
    return distance[word1.length()][word2.length()];    
}

blog.gainlo.co 続いて木の問題。ブログでも書かれているStackを使ったDFSの走査を試しに書いてみる。

struct TreeNode2 {
    TreeNode2* left;
    TreeNode2* right;
    string value;
    bool visited;
    TreeNode2() : left(NULL),right(NULL),value(""),visited(false){}
};

void printDFS(TreeNode2 *root){
    if(root == NULL) return;

    stack<pair<TreeNode2*,string>> s;
    s.push(make_pair(root,""));

    while(!s.empty()){
        TreeNode2 *n = s.top().first;
        string     p = s.top().second;
        p += n->value;
        s.pop();
        n->visited = true;
        if(n->right && !n->right->visited){

            s.push(make_pair(n->right,p+"->"));
        }
        if(n->left && !n->left->visited){
            s.push(make_pair(n->left,p+"->"));
        }
        if(n->left == NULL && n->right ==NULL ){
            cout << p << endl;
        }
    }
}

blog.gainlo.co 今度はリストの並び替え。

struct LinkedList {
    LinkedList *next;
    LinkedList *down;
    int        value;
    LinkedList(int v) : next(NULL),down(NULL),value(v){}
};

void flattenList(vector<vector<LinkedList*>>& result, LinkedList *root, int level){
    if(root==NULL) return;
    queue<pair<LinkedList*,int>> q;
    q.push(make_pair(root,0));

    while(!q.empty()){
        LinkedList* n = q.front().first;
        int level = q.front().second;
        q.pop();
        result[level].push_back(n);
        if(n->next) q.push(make_pair(n->next,level));
        if(n->down) q.push(make_pair(n->down,level+1));
    }
}

blog.gainlo.co これも最初に紹介したスライドウィンドウに似てる。

string findLongestK2( int K, string input ){
    string maxStr = "";
    int    maxLen = 0;
    int    left   = 0;
    int    right  = 0;
    unordered_set<char> h;
    while(left < input.size() && right < input.size()){
        h.insert(input[right]);
        if( h.size() == K ) {
            int len = right-left+1;
            if(  len > maxLen ){
                maxLen = len;
                maxStr = input.substr(left, len);
            }
        }
        else if( h.size() > K ){
            char c = input[left];
            while(input[left]==c){
                left++;
            }
            h.erase(c);
        }
        right++;
    }
    return maxStr;
}

blog.gainlo.co グラフの二つのノードから共通の親を返すものを見つけるもの。

bool findNode(TreeNode *root, TreeNode *target){
    if( root == NULL) return false;
    if( root->val == target->val) return true;
    return findNode(root->left, target) || findNode(root->right, target);
}

TreeNode* getCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){
    if( root == NULL || root == p || root == q ){
        return root;
    };
    bool pIsLeft = findNode(root->left, p);
    bool qIsLeft = findNode(root->left, q);
    if(pIsLeft != qIsLeft){
        return root;
    }
    TreeNode *child = pIsLeft ? root->left : root->right;
    return getCommonAncestor(child, p, q);
}


int getLCA(TreeNode *root, TreeNode *p, TreeNode *q){
    if( !findNode(root,p) || !findNode(root,q) ){
        return -1;
    }
    TreeNode* node = getCommonAncestor(root, p, q);
    return  (node) ? node->val : -1;
}

blog.gainlo.co これも有名な問題のようだ。

int countMaximumMeetingRoom(vector<pair<int,int>> interval){
    struct Event{
        int  time;
        bool in;
        Event(): time(-1),in(false){}
        bool operator< ( const Event& right) const {
            return time < right.time;
        }
    };
    vector<Event> ev(interval.size()*2);
    for( int i = 0; i < interval.size(); i++ ){
        ev[2*i].time   = interval[i].first;
        ev[2*i].in     = true;
        ev[2*i+1].time = interval[i].second;
        ev[2*i+1].in = false;

    }
    sort(ev.begin(),ev.end());
    int count = 0;
    int maxCount = 0;
    for( int i = 0; i < ev.size(); i++ ){
        count += ev[i].in ? 1 : -1;
        maxCount = max(count, maxCount);
    }
    return maxCount;
}

blog.gainlo.co

string getLongestSubStr2(string s){
    string maxStr = "";
    unordered_set<char> dup;
    int start = 0;
    int end = 0;
    while(start < s.size() && end < s.size()){
        if(dup.find(s[end])==dup.end()){
            dup.insert(s[end]);
            string sub = s.substr(start,(end-start)+1);
            if(sub.size()>maxStr.size()){
                maxStr = sub;
            }
            end++;
        } else {
            while(start<end){
                dup.erase(dup.find(s[start]));
                if(s[start]==s[end]){
                    start++;
                    break;
                }
                start++;
            }
        }
    }
    return maxStr;
}

野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

モックインタビューのサービスGainloのブログの問題を1日1問