Elements of Programming Interviews 白班编程记录，求挑刺求反馈

LC 489. Robot Room Cleaner

Problem Metrics:
1. Understand problem at 4 min
2. Get core concept
3. Algorithm draft
4. Detailed example derivation
5. Code draft at 66 min
6. AC solution at 68 min

没有仔细计时间，凭感觉一块一块写出来了。这是典型的backtracking，使用模板解决，难点是把它给的API转成我们能有效运用的，属于代码实现的范畴。
C++ 代码如下：
/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* class Robot {
*   public:
*     // Returns true if the cell in front is open and robot moves into the cell.
*     // Returns false if the cell in front is blocked and robot stays in the current cell.
*     bool move();
*
*     // Robot will stay in the same cell after calling turnLeft/turnRight.
*     // Each turn will be 90 degrees.
*     void turnLeft();
*     void turnRight();
*
*     // Clean the current cell.
*     void clean();
* };
*/
class Solution {
public:
    void cleanRoom(Robot& robot) {
        /* I need to start building a map of this room */
        /* Depth First Search in an Undirected graph */
        /* Every node has 1~4 edges */
        
        /*
                    0
                   ^
                    |
           3 < - X - > 1
                    |
                    v
                    2
        
        */
        
        /* First at every node, we are going to explore the four neighbors, see whether we can access it */
        /* label the direction as true or false */
        /* to record a path using a stack, the path should record relative POSITIONS (NSWE), not left or right */
        
        /* robot direction state */
        
        /* pre-order processing: clean() */
        /* post-order processing: move back */
        /* use direction state and turnLeft()/turnRight() to create function turnNorth(), turnSouth(), turnEast(), turnWest() */
        
        state = 0; i = 0; j = 0;
        cleanRoomRecursion(&robot);
    }
   
    void cleanRoomRecursion(Robot * robot){
        if(discovered.find(locationStr(i,j)) != discovered.end()){
            return;
        }
            
        robot->clean();
        discovered.emplace(locationStr(i,j));
        if(canAccess(robot, "NORTH")){
            --i;
            TurnTo("NORTH", robot);
            robot->move();
            cleanRoomRecursion(robot);
            TurnTo("SOUTH", robot);
            robot->move();
            ++i;
        }
        if(canAccess(robot, "EAST")){
            ++j;
            TurnTo("EAST", robot);
            robot->move();
            cleanRoomRecursion(robot);
            TurnTo("WEST", robot);
            robot->move();
            --j;
        }
        if(canAccess(robot, "SOUTH")){
            ++i;
            TurnTo("SOUTH", robot);
            robot->move();
            cleanRoomRecursion(robot);
            TurnTo("NORTH", robot);
            robot->move();
            --i;
        }
        if(canAccess(robot, "WEST")){
            --j;
            TurnTo("WEST", robot);
            robot->move();
            cleanRoomRecursion(robot);
            TurnTo("EAST", robot);
            robot->move();           
            ++j;
        }
        processed.emplace(locationStr(i , j));
    }
   
    bool canAccess(Robot * robot, string direction){
        TurnTo(direction, robot);
        bool accessible = robot->move();
        if(accessible){
            TurnAround(robot);
            robot->move();
        }
        return accessible;
    }
   
    void TurnTo(const string& direction, Robot * robot){
        int target;
        if(direction == "NORTH")target = 0;
        if(direction == "EAST")target = 1;
        if(direction == "SOUTH")target = 2;
        if(direction == "WEST")target = 3;
        
        /* turn, turn, turn! until you make the direction! */
        while(state != target){
            robot->turnRight();
            ++state;
            state %= 4;
        }
    }
   
    /* reverse direction */
    void TurnAround(Robot * robot){
        robot->turnRight();
        robot->turnRight();
        state += 2;
        state %= 4;
    }
   
    string locationStr(int i, int j){
        return to_string(i) + " " + to_string(j);
    }
   
    int state, i, j;
    unordered_set<string> discovered, processed;
};

LC 269. Alien Dictionary

Problem Metrics:
1. Understand problem at 2 min
2. Get key concept at 18 min
3. Algorithm draft at 24 min
4. Detailed example derivation at 40 min
5. Code draft at 63 min
6. Code compile at 67 min
7. AC solution at 95 min (major error occurs in lexGraph building phase and topo sort phase)
    1. for lexGraph building, I forget the forloop tail case
    2. for toposort, I misplaced the stack.pop(). Since I need to do postorder processing, I cannot pop the stack right after I read the top. I should check the top's state and decide whether I need to pop it. (only pop when the top is "processed" or "discovered" )

又是一道综合型leetcode hard，运用知识点如下：
1. BFS
2. Graph construction
3. Two pointer basics
4.  Topological sort

首先，运用BFS和two pointers来把所有的rule揪出来，然后，用这些rule建一个ruleGraph，之后对这个ruleGraph进行topo sort，然后返回结果。我犯了两个错误，一个是two pointer for loop时loop结束后的tail case没有处理，导致ruleGraph建造不全，二是graph traversal算法模板写串了道BFS模板去了，过早的做了pop。正确的pop应该考虑post-order processing，所以应该在合适的时候在pop（node discovered and node processed）

大木虫 发表于 2018-10-11 23:31
LC 269. Alien Dictionary

Problem Metrics:

C++ 代码如下：
class Solution {
public:
    string alienOrder(vector<string>& words) {
        /* graph */
        /* topological sorting */
        
        /* build a graph using word list */
        /* detect cycle to detect invalid ordering */
        /* do topo sort on graph to get letter order */
        /* use a queue to process the rules */
        
        /* should be one node with in-degree-0, one node with out-degree-0 */
      
        /* 0. MISC */
            if(words.size() == 0)return ""; /* we cannot infer any ordering with less than two words */
            if(words.size() == 1)return string(words[0].rbegin(), words[0].rend());
        
        /* 1. prep */
            queue<vector<string> > rules;
            rules.emplace(words);
            unordered_map<char, unordered_set<char> > lexGraph;
            unordered_set<char> allChars;
            
            for(string word : words){
                for(char letter : word){
                    allChars.emplace(letter);
                }
            }
        
        /* 2. key algorithm */
            
            /* rule processing stage (graph building) */
            while(!rules.empty()){
                vector<string> rule = move(rules.front());
                rules.pop();
               
                /* by definition, our rule has a minimum size of 2 */
                char currentPrefix = rule[0][0];
                vector<string> newRule;
                for(string word : rule){
                    
                    if(word[0] == currentPrefix && word.size() > 1){
                        newRule.emplace_back(word.substr(1, word.size()-1));
                    }else if(word[0] != currentPrefix){
                        /* push the newly constructed rule into queue */
                        if(newRule.size() > 1){
                            rules.emplace(newRule);
                        }
                        
                        /* add a new char ordering into lexGraph */
                        if(lexGraph.find(currentPrefix) == lexGraph.end()){
                            lexGraph[currentPrefix] = unordered_set<char>();
                        }
                        lexGraph[currentPrefix].emplace(word[0]);
                        
                        /* construct a new rule */
                        newRule.clear();
                        if(word.size() > 1){
                            newRule.emplace_back(word.substr(1, word.size()-1));
                        }
                        currentPrefix = word[0];                        
                    }
                }
                if(newRule.size() > 1){
                    rules.emplace(newRule);
                }
            }
        
      
            /* topo sort lexGraph */
            lexGraph[' '] = unordered_set<char>();
            for(auto itr = allChars.begin(); itr != allChars.end(); ++itr){
                lexGraph[' '].emplace(*itr);
            }
      
            string answer = topoSort(lexGraph, allChars);           
        
        /* 3. answer */
            return answer;
        
    }
   
    string topoSort(const unordered_map<char, unordered_set<char> > & lexGraph,
                    const unordered_set<char> & allChars){
        string answer = "";
        unordered_set<char> discovered, processed;
        stack<char> path;
        path.emplace(' ');
        
        /* debug print start */
        /* printLexGraph(lexGraph); */
        /* debug print end */
        
        while(!path.empty()){
            char node = path.top();
            
            if(processed.find(node) != processed.end()){
                path.pop();
            }else if(discovered.find(node) != discovered.end()){
                processed.emplace(node);
                answer += node;
                path.pop();
            }else{
                discovered.emplace(node);
                if(lexGraph.find(node) == lexGraph.end()){
                    continue;
                }
                for(auto itr = lexGraph.find(node)->second.begin();
                    itr !=  lexGraph.find(node)->second.end(); ++itr){
                    char child = *itr;
                    if(processed.find(child) != processed.end()){
                        continue;
                    }else if(discovered.find(child) != discovered.end()){
                        return ""; /* find cycle */
                    }else{
                        path.emplace(child);
                    }
                }
            }            
        }      
        
        answer.pop_back(); /* remove the dummy node */
        if(answer.size() < allChars.size()){
            return ""; /* the lexGraph is not connected */  
        }
        return string(answer.rbegin(), answer.rend());
    }
   
    void printLexGraph(const unordered_map<char, unordered_set<char> > & lexGraph){
        for(auto itr = lexGraph.begin(); itr != lexGraph.end(); ++itr){
            char parent = itr->first;
            cout << parent << ":";
            for(auto childItr = lexGraph.find(parent)->second.begin();
                childItr != lexGraph.find(parent)->second.end(); ++childItr){
                cout << *childItr << " ";
            }
            cout << endl;
        }
    }
};

补充内容 (2018-10-11 23:49):
154行，C++代码写太长真是个问题。。。

厉害了！ 手动给楼主点赞

Problem Metrics:
1. Understand Problem at 1 min
2. Get key concept at 1 min
3. Algorithm draft at 1 min
4. Detailed example derivaiton & code draft at 5 min
5. Code compile at 5 min (one typo)
6. AC solution at 5 min

This is Fibonacci

休息一下，用easy换换脑子



补充内容 (2018-10-12 00:30):
70. Climbing Stairs

300. Longest Increasing Subsequence
Problem Metrics:
1. Understand Problem at 1 min
2. Get key concept at 1 min
3. Algorithm draft at 4 min
4. Detailed example derivation at 5 min
5. Code draft at 8 min
6. Code compile at 9 min (placed "return" outside of the function)
6. AC solution at 11 min (runtime error,  wrongly wrote "--" to "++", didn't handle corner case of empty input)

速度！正确率！

198. House Robber
1. Understand problem at 3 min
2. Get key concept at 7 min (1D/2D DP)
3. Algorithm draft at 20 min
4. Detailed example derivation & code draft at 27 min
5. AC solution at 28 min (no compile/runtime error)

一维DP，这题其实对于我来说算是偏难的一个，因为它属于带twist的一维DP

补充内容 (2018-10-12 01:27):
看来，对于“对这个东西选还是不选”类型的题，这种DP模式可以作为一个思考方向

399. Evaluate Division
1. Understand problem at 1 min
2. Get key concept at 7 min
3. Algorithm draft at 8 min
4. Detailed example derivation
5. Code draft at 53 min
6. Code compile at 54 min (only ONE syntax error in 170 lines of code)
7. AC solution at 61 min (found one semantic error)

狗家经典题，知识点如下：
1. 有向图遍历
2. find path between node A and B (BFS/DFS)
3. memoization basics

C++代码量太大了，170行，可读性没问题，但是太长了写不完，这是问题。不过通过最近写几个150行上下的题目，感觉对C++语法愈加熟练，这次170行代码从头到尾只有一个syntax error (typo) 和一个semantic error，而且非常容易debug。

C++ 代码如下：
class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        /* First, build the graph */
        /* This is a directed graph, but each edge exist in both ways (with its value inverted) */
        /* a/b:a->b, b/c: b->c, a/c: a/b * b/c a->b->c */
        /* This is a graph search problem, my target is find if there is a directed path from A to B */
        /* The key clean coding using Given API */
        
        /* Algorithm:
            1. Build a graph using inputs
            2. Write a modular BFS function for node search
            3. Before each search, do a sanity check (a/a, x/x, a/e)
            4. Repeatedly call BFS to fill answer query
        */
        
        /* 1. prep */
        vector<double> answerStore;
        if(equations.size() != values.size()){
            return answerStore;
        }
        
        /* 2. key algorithms */
        
        /* build graph */
        unordered_map<string, unordered_map<string, double> > graph = BuildGraph(equations, values);
        unordered_map<string, double> doneAnswers; /* memorize the result for quick lookup*/
        
        
        /* BFS calls (do sanity check for every query) */
        for(auto query : queries){
            string fromNode = query.first, toNode = query.second;
            
            /* check for existing answers */
            string pathCode = fromNode + " " + toNode;
            if(doneAnswers.find(pathCode) != doneAnswers.end()){
                answerStore.emplace_back(doneAnswers[pathCode]);
                continue;
            }
            
            /* calculate (heavy lifting) */
            double ansVal = findPath(graph, fromNode, toNode);
            
            /* store to answerStore */
            answerStore.emplace_back(ansVal);
            
            /* memorize answer */
            double invertVal = 1 / ansVal;
            string invertCode = toNode + " " + fromNode;
            
            doneAnswers[pathCode] = ansVal;
            doneAnswers[invertCode] = invertVal;            
        }
        
        /* 3. answer */
        return answerStore;
        
    }
   
    /* need to record path */
    double findPath(const unordered_map<string, unordered_map<string, double> > & graph,
                    const string & fromNode, const string & toNode){
        
        /* bfs, record path */
        /* 0. MISC*/
        
        /* sanity check */
        /* doesn't exist */
        if(graph.find(fromNode) == graph.end() || graph.find(toNode) == graph.end()){
            return -1.0;
        }
        /* divide self */
        if(fromNode == toNode){
            return 1.0;
        }
        
        /* 1. prep */
        unordered_map<string, pair<string, double> > trackBack;
        unordered_set<string> visited;
        queue<string> bfsQueue;
        bfsQueue.emplace(fromNode);
        visited.emplace(fromNode);
        
        /* 2. key algorithm */
        /* BFS */
        bool found = false;
        while(!bfsQueue.empty() && !found){
            string node = bfsQueue.front();
            bfsQueue.pop();
            
            unordered_map<string, double> edges = graph.find(node)->second;
            
            for(auto edgeItr = edges.begin(); edgeItr != edges.end(); ++edgeItr){
                string dstName = edgeItr->first;
                double dstValue = edgeItr->second;
                if(visited.find(dstName) != visited.end()){
                    continue;
                }
                visited.emplace(dstName);

                trackBack[dstName] = {node, dstValue}; /* this values are the invert of actual edge values */
                if(dstName == toNode){
                    found = true;
                }
                bfsQueue.push(dstName);
            }
        }
        
        if(!found){
            return -1.0;
        }
        
        /* track back */
        double answer = 1.0;
        string target = fromNode;
        string current = toNode;
        while(current != fromNode){
            answer *= trackBack[current].second;
            current = trackBack[current].first;
        }
        
        /* 3. return answer */
        return answer;
    }
   
    unordered_map<string, unordered_map<string, double> >
    BuildGraph(const vector<pair<string, string>> & equations, const vector<double>& values){
        /* every single equation represents a both-way edge with inverted values */
        /* the finished graph should contain all possible values as keys; this fact can be used for sanity check */
        
        /* 1. prep */
        unordered_map<string, unordered_map<string, double> > graph;
        
        /* 2. key algroithm */
        for(int i = 0; i < equations.size(); ++i){
            string fromNode = equations[i].first, toNode = equations[i].second;
            double forwardValue = values[i], backwardValue = 1/forwardValue;
            if(graph.find(fromNode) == graph.end()){
                graph[fromNode] = unordered_map<string, double>();
            }
            graph[fromNode][toNode] = forwardValue;
            
            if(graph.find(toNode) == graph.end()){
                graph[toNode] = unordered_map<string, double>();
            }
            graph[toNode][fromNode] = backwardValue;
        }
        
        # if 0
        /* debug print start */
        PrintGraph(graph);
        /* debug end */
        #endif
        
        /* 3. answer */
        return graph;
    }
   
    void PrintGraph(const unordered_map<string, unordered_map<string, double> > & graph){
        for(auto itr = graph.begin(); itr != graph.end(); ++itr){
            cout << itr->first << " : ";
            
            unordered_map<string, double> edges = itr->second;
            for(auto toItr = edges.begin(); toItr != edges.end(); ++toItr){
                cout << toItr->first << " " << toItr->second << " | ";
            }            
            cout << endl;
        }
    }   
};

burst balloon 引发的思考：
DP的目的就是用最优的方法走穿一个有向无环图，正着走，反着走，根据题目规则，怎么好走怎么走（寻找高效的最优子结构）

Burst Balloon 引发的思考2 （瞎乱说只言片语，别太认真）
DP：通过多角度思考，根据题目逻辑定义出最为高效的最优的子结构
DP的思维如此
无论几维，其核心都是寻找搞笑最优子结构
高效的定义是减少divide and conquer设计逻辑的branching
这个要根据具体题目逻辑得出
得出的思考方式是尝试多角度定义base case，从多个起点方向接近main problem
都是图，全是图，全都是图！！！
DP是根据题目逻辑抽骨出最简洁的图
然后把这个图遍历求最优，或者遍历推出终点值。
由此看来，算法的一个核心，就是图，
图图图图图图图
高纬度，也不过是图罢了，
图不分维度，都是图
维度只不过是对图狭义的定义而已
啊，顺畅
（我就随便说说而已。。。）

补充内容 (2018-10-13 00:47):
搞笑 -> 高效