面经/LintCode/LeetCode题目想法和代码分享

Battleship & Find the Duplicate Number
地里面经 & LeetCode No.287
详见Google两次面试的经验（phone+onsite)和Google onsite 一道算法和最后一道系统题

先来设计一下Battleship这个游戏。然后再探讨一下LeetCode No.287以及原帖中楼主16年面试第二轮第二道题。
这三道题之所以放在一起讲，是因为它们都有一个共通的小技巧。我会在阐述完我个人对于Battleship的设计思路之后会指明这个小技巧。

Design Battleship:
Battleship是一个很经典的board game。我以前上高中的时候经常在文曲星上玩。估计大家都熟悉这个游戏规则，不过因为规则跟设计有关，我们在这里还是大概的叙述一下。
首先我们有一个game board，这个game board是两面的，我们及对手玩家/AI会在游戏初始阶段，自己的一面，依据自己喜好放上5个长度分别为2, 2, 3, 4, 5的军舰。双方看不到对方军舰的摆放情况。游戏开始后，双方轮流交替的放置一枚炸弹，系统会回馈炸弹是炸空，还是炸到军舰了。如果一艘军舰所有所在的点都被炸了，这艘军舰就沉了。谁先将对方的五艘军舰都炸沉，即赢得比赛。

这里直接给出我个人的设计方案。我们用一个类似union find的结构来存储军舰所在位置。一个军舰的所有child node都存储parent node的index，然后在parent node记录目前这艘军舰还未被炸毁的节点数。再用一个变量记录目前幸存的军舰数量。如果某个parent node所对应的节点数为零，目前幸存的军舰数量 - 1；用到的数据结构如下：

1. 
   
2. vector<vector<int>> board_;
   
3. unordered_map<int, int> ships_; //key: index, value: parent index
   
4. unordered_map<int, int> ship_cnts_; //key: index, value: count
   
5. int alive_cnt_;
   

复制代码

游戏初始阶段，我们需要一个function来根据user input来摆放军舰：

1. 
   
2. void placeBattleships(vector<vector<pair<int, int>>> ships_pos) {
   
3.   //skip validation
   
4.   int n = board_.size();
   
5.   for (const auto& s : ships_pos) {
   
6.     int ship_len = s.size();
   
7.     int index_0 = s[0].first * n + s[0].second;
   
8.     for (int i = 0; i < ship_len; ++i) {
   
9.       int index_i = s[i].first * n + s[i].second;
   
10.       ships_[index_0] = index_i;
    
11.     }
    
12.       ship_cnts_[index_0] = ship_len;
    
13.   }
    
14.   alive_cnt_ = ships_pos.size();
    
15. }
    

复制代码

游戏开始后，我们需要一个function来放置炸弹，并且返回是否炸到了军舰：

1. 
   
2. // true - hit, false - missed
   
3. bool placeBomb(pair<int, int> pos) {
   
4.   int n = board_.size();
   
5.   int index = pos.first * n + pos.second;
   
6.   auto it = ships_.find(index);
   
7.   if (it == ships_.end() || it->second == -1) {
   
8.     return false;
   
9.   }
   
10.   int p_index = index;
    
11.   while (ships_[p_index] != p_index) {
    
12.         p_index = ships_[p_index];
    
13.   }
    
14.   ships[index] = -1; // visited
    
15.   if (--ship_cnts[p_index] == 0) {
    
16.     --alive_cnt_;
    
17.   }
    
18.   return true;
    
19. }
    

复制代码

然后我们还需要一个function显示幸存的军舰数量，以及一个function来判断所有军舰是否被炸沉：

1. 
   
2. int aliveBattleships() const {
   
3.   return alive_cnt_;
   
4. }
   
5. bool won() const {
   
6.   return aliveBattleships() == 0;
   
7. }
   

复制代码

可以看出这个类似union-find的data structure其实是一个很简单的结构。而且对于Battleships这个游戏来说，我们其实根本不用额外的unordered_map来存取军舰的状态。所有信息都存在board_里就好了。
Battleship游戏里只用摆放五个军舰，最长的军舰只有5的长度。一般游戏的棋盘不会很大，都是10X10的。毕竟太大了，双方很难炸完对方的军舰。所以在board_的每一格，我们可以用-1来表示这格已经被炸过。0 ~ n*n - 1来表示parent node的 index。n来表示这个格是空的。n + 2 ~ n + 6来表示这个格是个parent node以及其所对应的军舰还剩余的node的数量。

那么这道题又跟Find the Duplicate Number有什么关系呢？
在table中每个元素存储的是table index，根据其跳转，其实就是把table中的元素作为指针来使用。就像我们在上题中也是在child node中存parent node的index，并做跳转。
我们结合Find the Duplicate Number这道题来看。这道题讨论区most voted的解法即是一个国人大神把它转化为了Linked List Cycle来做。
find linked list cycle是一道大家都很熟悉的题。而国人大神的解法就是把given array中的每一个元素当作指针来用跳转到下一个元素。
我们用A[1, 4, 3, 2, 5, 2, 6]来做例：
当我们扫到A[0]时，A[0] == 1，把它作为指针来使用，我们跳到A[1];
A[1] == 4, 跳到A[4];
A[4] == 5, 跳到A[5];
A[5] == 2, 跳到A[2];
A[2] == 3, 跳到A[3];
A[3] == 2, 开始循环...
这道题之所以可以把元素作为指针来使用当然也是题干出的巧。

这个小技巧也可以用在原帖第二轮第二题上。
原帖中Heliuhun对于这道题给了一个很精妙的解法。我们来分析一下这个解法。
用A[a1, a2, a3, a4, a5], B[1,0,4,2,3]做例:
我们并不在乎A中的每个数到底是什么。我们想知道的是A中的每个数按照B来移动，最少经过多少次可以回到原位。
对于a2来说，它经历一次移动从1来到了0的位置。再经历一次移动从0回到了1的位置。
对于a4来说，它经历一次移动从3来到了2的位置。再经历一次移动从2来到了4的位置。再经历一次移动从4回到了3的位置。
可以看到A中的元素是根据B来跳转的，并且把B中的元素当作指针来使用。B中的元素形成了一个或多个封闭的环状“linked list”。
按照Heliuhun的思路，我们需要找出B中有多少封闭的环状“linked list”，再找出它们的最小公倍数。
为什么是最小公倍数呢？
拿上面的例子来说，当a2经过两次移动后回到原位时，a4还需要一次移动才能回到原位。最少经过6次移动，a2，a4以及a1，a3，a5才能同时回到原位。



补充内容 (2016-6-23 03:11):
placeBattleships第十行应为
ships_[index_i] = index_0;

dg7743 发表于 2016-6-22 12:34
Battleship & Find the Duplicate Number
地里面经 & LeetCode No.287
详见Google两次面试的经验（phone+ ...

恩，具体找到[1,0] 和[4,2,3]的代码要怎么写呢？ input可以有n那么长，可以有k个这样的cycle

yoo 发表于 2016-6-22 12:44
恩，具体找到[1,0] 和[4,2,3]的代码要怎么写呢？ input可以有n那么长，可以有k个这样的cycle

我们只需要知道有多少个cycle，每个cycle的长度是多少就可以了，代码如下

1. 
   
2. vector<int> findCycles(const vector<int>& in) {
   
3.   vector<int> res;
   
4.   int s = in.size();
   
5.   if (s == 0) {
   
6.     return res;
   
7.   }
   
8.   unordered_set<int> visited;
   
9.   for (int i = 0; i < s; ++i) {
   
10.     if (visited.find(i) != visited.end()) {
    
11.       continue;
    
12.     }
    
13.     visited.insert(i);
    
14.     int len = 1;
    
15.     int next = in[i];
    
16.     while (i != next) {
    
17.       visited.insert(next);
    
18.       ++len;
    
19.       next = in[next];
    
20.     }
    
21.     res.push_back(len);
    
22.   }
    
23.   return res;
    
24. }
    

复制代码

在根据user input来摆放军航的代码第10行，楼主是指 “ships_[index_i] = index_0;” 吗？

crimsonfaith91 发表于 2016-6-23 02:59
在根据user input来摆放军航的代码第10行，楼主是指 “ships_ = index_0;” 吗？

对，这里写错了。谢谢你细心的指出。

dg7743 发表于 2016-6-22 14:58
我们只需要知道有多少个cycle，每个cycle的长度是多少就可以了，代码如下

很棒，谢谢分享！

STL <algorithm>

stable_sort

这两天钻进牛角尖了。两个晚上一直在做LeetCode No.315 Count of Smaller Numbers After Self 这道题。
主要是我看到讨论区里most votes的merge sort做法。这个做法中，在merge这个步骤，当lhs <= rhs时，我们会把lhs插入result中，并且把lhs原本index所对应的count加上这步之前已经插入rhs的个数。
说起来很绕，结合代码看一下就懂了。
我就脑洞大开的想，我可不可以不自己写一个merger sort，而是用STL已有的function，通过把这步操作写在comparator里而解决这道题。
因为merge sort是staple sort，而我们经常用的sort是unstable sort，不能用来解这道题。于是乎我发现STL algorithm里有提供stable_sort，并用它搞了半天，写出了一个巨复杂毫无意义的代码。
虽然我浪费了不少时间，但作为抛砖引玉，我发现STL algorithm里提供了很多很有意思的functions，我个人平常在工作中并没有注意及使用到它们。借此机会我来研究一下它们，并看看它们对于做面试题有没有什么帮助。

P.S. 关于sort和stable_sort的implementation，参考这个overflow链接。
http://stackoverflow.com/questio ... implement-quicksort

Binary search (operating on partitioned/sorted ranges):
lower_bound
upper_bound
equal_range
binary_search

STL里提供的binary search应该算是平常比较常见的。当然一般来说我们遇到binary search的面试题肯定不能直接用它们(一般来说也用不了，STL提供的只能搜索固定值，像是Find Minimum in Rotated Sorted Array， 或者Find Peak Element这种题就不行)，比如LeetCode No.35 Search Insert Position这道题，用lower_bound两行就完事：

1. 
   
2. int searchInsert(vector<int>& nums, int target) {
   
3.   auto it = lower_bound(nums.begin(), nums.end(), target);
   
4.   return it - nums.begin();
   
5. }
   

复制代码

再比如given a sorted array and a target number, find the number of occurrences in the array这道题：

1. 
   
2. int findOccurrences(vector<int>& nums, int target) {
   
3.   auto it_b = lower_bound(nums.begin(), nums.end(), target);
   
4.   auto it_e = upper_bound(nums.begin(), nums.end(), target);
   
5.   return it_e - it_b;
   
6. }
   

复制代码

我个人的话会手写完binary search后，跟面试官说By the way，we can simplify our code like this with C++ STL。

Heap
push_heap
pop_heap
make_heap
sort_heap
is_heap
is_heap_until

在讨论Hash Heap这道题时，我们探讨了用multimap或自己实现一个heap的做法。
虽然我后来经过订正后发现，我们用multimap也可以实现O(1)取least frequent node的操作，O(logn)的更新操作。但理论上的run time performance相同，不等同于实际上的相同。
首先heap是用array实现的，是一段contiguous memory。而multimap使用BST实现的，每个node都是分散的，由pointer链接在一起。
因为cache的缘故，contiguous memory的数据结构往往都是更高效的。
其次，比起单纯的heap，BST保证了每个node都是排序的，但这个特性对于LFU这道题来说是多余的。用multimap来当heap显然是用牛刀杀鸡。
看到这一系列heap相关的functions之后，我就想这些能不能用来实现hash heap呢？但是并不能。。。
事实上，priority_queue其实就是一个使用这些functions的adepter class。

nth_element
next_permutation
prev_permutation

这三个function都可以找到LeetCode对应的题。LeetCode No.215 Kth Largest Element in an Array； LeetCode No.31 Next Permutation。

lexicographical_compare
is_permutation

这两个function一个判断两个input的字典顺序，一个判断两个input是否为permutation。一时想不起再哪个LeetCode题里可以用到它们，感觉上挺有用的，mark下。

min_element
max_element

很多题里面我们都会用一个loop来找最大/小值。这两个wrapper function可以经常用到。
还有很多类似的简单的loop wrapper functions，例如for_each，fill等。虽然它们并不是很复杂，很重要的东西，但是了解一下它们，至少可以帮我们节省一些白板时手写代码的时间。

for_each以前是一个很傻的存在，但是C++ 11 lambda functions出现后，它俩很适合在一起使用。
sort，或者priorit_queue之类的需要compare function object的情况，我们也可以用lambda。
例如Rain Path那道题中，我们可以把priority queue写成这样：

1. 
   
2. auto comp = [&matrix](const pair<int, int>& rhs, const pair<int, int>& lhs) {
   
3.   int rhs_val = matrix[rhs.first][rhs.second];
   
4.   int lhs_val = matrix[lhs.first][lhs.second];
   
5.   return rhs_val != lhs_val ? rhs_val > lhs_val : rhs > lhs;
   
6. };
   
7. priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
   
8. 
   

复制代码

lambda看似方便，但其实使用时有许多需要注意的地方。推荐大家如果要使用的话，要先全面的了解它。

Minimax
地里面经
详见Uber onsite5.B

这道题两个player，轮流取字母，谁取走最后一个谁就输了。
首先，根据题干，很容易想到要根据字典建立一个Trie。
其次，遇到这种Game类的问题，我就想到了minimax这个很简单的算法。
关于minimax，这里有篇很不错的博文:http://neverstopbuilding.com/minimax
对于这道题，我们可以用minimax+DFS来遍历我们建立的Trie。
如果返回到Trie root的minimax value < 0说明先手肯定输。比如cat, cool这种情况。
不知道这道题要的winning strategy具体是什么。不过这个思路应该是没问题的。

1. 
   
2. class Solution {
   
3. public:
   
4.   pair<int, string> winSequence(vector<string> &dict) {
   
5.     buildTrie(dict);
   
6.     auto res = calculateMinimax(root_, true);
   
7.     deleteTrie(root_);
   
8.     reverse(res.second.begin(), res.second.end());
   
9.     bool play_fist_win = res.first > 0;
   
10.     return pair<int, string>(play_fist_win, res.second);
    
11.   }
    
12. 
    
13. private:
    
14.   struct TrieNode {
    
15.     bool isWord = false;
    
16.     unordered_map<char, TrieNode*> children;
    
17.   };
    
18. 
    
19.   void buildTrie(vector<string> &dict) {
    
20.     root_ = new TrieNode();
    
21.     for_each(dict.begin(), dict.end(), [&](string& s){insertTrie(s); });
    
22.   }
    
23. 
    
24.   void insertTrie(string word) {
    
25.     TrieNode *cur = root_;
    
26.     for (char & c : word) {
    
27.       if (cur->children.find(c) == cur->children.end()) {
    
28.         cur->children[c] = new TrieNode();
    
29.       }
    
30.       cur = cur->children[c];
    
31.     }
    
32.     cur->isWord = true;
    
33.   }
    
34. 
    
35.   void deleteTrie(TrieNode* root) {
    
36.     for (auto& p : root->children) {
    
37.       deleteTrie(p.second);
    
38.     }
    
39.     delete root;
    
40.   }
    
41. 
    
42.   pair<int, string> calculateMinimax(TrieNode* root, bool fp_turn) {
    
43.     if (root->children.empty()) {
    
44.       return !fp_turn ? pair<int, string>(-10, "") : pair<int, string>(10, "");
    
45.     }
    
46.     int minimax_val = fp_turn ? INT_MIN : INT_MAX;
    
47.     string sequence;
    
48.     for_each(root->children.begin(), root->children.end(),
    
49.       [&](pair<char, TrieNode*> c){
    
50.         auto res = calculateMinimax(c.second, !fp_turn);
    
51.         if (fp_turn) {
    
52.           if (res.first > minimax_val) {
    
53.             minimax_val = res.first;
    
54.             sequence = res.second + c.first;
    
55.           }
    
56.         }
    
57.         else {
    
58.           if (res.first < minimax_val) {
    
59.             minimax_val = res.first;
    
60.             sequence = res.second + c.first;
    
61.           }
    
62.         }                               
    
63.       }
    
64.     );
    
65.     return pair<int, string>(minimax_val, sequence);
    
66.   }
    
67. 
    
68.   TrieNode* root_;
    
69. };
    

复制代码

这道题返回-10或10有点多余，直接true/false就可以了，但这涉及到minimax的进一步优化。这里就不展开了。


补充内容 (2016-7-19 14:10):
LeetCode No.294 Flip GameII
LeetCode No.375 Guess Number Higher or Lower II
也有用到minimax的思路。

Lockers Distances
地里面经
详见Amazon家新鲜OA，HackRanker 90min第三题

这道题求的是，matrix中每个点到最近的locker的距离是什么。在graph这类题中，看到关键字短，近，我的第一反应就是BFS。
那么这道题我们怎么用BFS来解决呢？我们可以从每个locker的位置同时出发，因为是同时出发的，matrix中任意一个点必然会被离它最近的locker出发的指针先遍历到。如果某个点已经被遍历到了，我们就不再把这个点添加到BFS的循环中。
而且题干给了我们一个很关键的信息，即两点之间距离为abs(x1 - x2) + abs(y1 - y2)。例如，(0, 0)到(0, 1),(1, 0)的距离是1，到(1, 1)的距离是2。
本来我还考虑斜着走怎么算，但是根据题目给的条件我们可以看出从每个点移动只能水平，垂直走，这进一步简化了这道题。

1. 
   
2. vector<vector<int>> getLockerDistanceGrid(int length, int width, vector<pair<int, int>>& locker_idx) {
   
3.   const vector<pair<int, int>> directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
   
4.   vector<vector<int>> res(length, vector<int>(width, -1));
   
5.   queue<pair<int, int>> q;
   
6.   int s = locker_idx.size();
   
7.   for (int i = 0; i < s; ++i) {
   
8.     res[locker_idx[i].first][locker_idx[i].second] = 0;
   
9.     q.emplace(locker_idx[i].first, locker_idx[i].second);
   
10.   }
    
11.   while (!q.empty()) {
    
12.     int ls = q.size();
    
13.     for (int i = 0; i < ls; ++i) {
    
14.       auto cur = q.front();
    
15.       q.pop();
    
16.       for (const auto& d : directions) {
    
17.         auto next = pair<int, int>(cur.first + d.first, cur.second + d.second);
    
18.         if (next.first < length && next.first >= 0 && next.second < width && next.second >= 0 && res[next.first][next.second] == -1) {
    
19.           res[next.first][next.second] = res[cur.first][cur.second] + 1;
    
20.           q.push(move(next));
    
21.         }
    
22.       }
    
23.     }
    
24.   }
    
25.   return res;
    
26. }
    

复制代码

这道题很重要的一个技巧就是“同时”从每个locker所在index为起点进行BFS。

稍微修改一下用Minimax那道题的代码。
用shared_ptr构造Trie。

1.        
   
2. struct TrieNode {
   
3.   bool isWord = false;
   
4.   unordered_map<char, shared_ptr<TrieNode>> children;
   
5. };
   
6. 
   
7. void buildTrie(const vector<string> &dict) {
   
8.   root_ = make_shared<TrieNode>();
   
9.   for_each(dict.begin(), dict.end(), [&](const string& s){insertTrie(s); });
   
10. }
    
11. 
    
12. void insertTrie(const string& word) {
    
13.   shared_ptr<TrieNode> cur = root_;
    
14.   for (const char & c : word) {
    
15.     if (cur->children.find(c) == cur->children.end()) {
    
16.       cur->children[c] = make_shared<TrieNode>();
    
17.     }
    
18.     cur = cur->children[c];
    
19.   }
    
20.   cur->isWord = true;
    
21. }
    
22. 
    
23. shared_ptr<TrieNode> root_;
    

复制代码