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

Automata
地里面经
详见Google详细onsite面经。败在 self-estimation 上了？第一题
这道题用到了不太常见的automata。state machine的状态图还是不难画的。
这道题的图如下：

制图软件所限，1，2还应各有指回0的箭头，4，5有指回3的箭头。
L代表late，A代表absence。
这道题求的是bad students combination的数量。不过我还在地里另外一个google面经的帖子也看到了这道题的变种，要求的是good students combination的数量。
下面的源代码是good students combination的版本。

1. 
   
2. // please refer to the attached picture for the automata states
   
3. int findGoodComb(int n) {
   
4.   vector<vector<int>> f(n + 1, vector<int>(6, 0));
   
5.    
   
6.   f[0][0] = 1;
   
7.   for (int i = 1; i <= n; ++i) {
   
8.     f[i][0] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2];
   
9.     f[i][1] = f[i - 1][0];
   
10.     f[i][2] = f[i - 1][1];
    
11.     f[i][3] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2] + f[i - 1][4] + f[i - 1][5];
    
12.     f[i][4] = f[i - 1][3];
    
13.     f[i][5] = f[i - 1][4];
    
14.   }
    
15.    
    
16.   int res = 0;
    
17.   for (int i = 0; i < 6; ++i) {
    
18.     res += f[n][i];
    
19.   }
    
20.         
    
21.   return res;
    
22. }

复制代码

一般DP题的难点就是考虑状态转移方程。
这道题把图画出来之后，状态转移方程很容易就能得出来。

LeetCode No.309 Best Time to Buy and Sell Stock with Cooldown 这道题讨论区里，也有一个用到state machine的DP解法。（Share my DP solution (By State Machine Thinking)）
我个人觉得这是一个更为直观，好思考的想法。

dg7743 发表于 2016-6-30 11:39
Automata
地里面经
详见Google详细onsite面经。败在 self-estimation 上了？第一题

赞楼主！ 请问楼主能贴一下那个good student的面经link么？

lizy.wang11 发表于 2016-7-1 06:03
赞楼主！ 请问楼主能贴一下那个good student的面经link么？

不好意思，我大概两个月前看到的，我在地里找了找，但是实在找不到那个帖子了。

Max Holidays
地里面经
详见一道G家onsite 求最长假期问题

这道题原帖里楼主也不知道具体的题目是什么。这里，我自己擅做一些假设：
每个城市都存有12月每个月假期的天数，以及可以飞往的城市。
每个城市的node可以长这样：

1. 
   
2. struct city {
   
3.   int id;
   
4.   string name;
   
5.   vector<int> dst_cities;
   
6.   vector<int> holidays;
   
7.   city(int i, const string& n) : id(i), name(n) {
   
8.     holidays.resize(12);
   
9.   }
   
10. };
    

复制代码

我们先假设可以从任意城市开始我们的旅程，城市之间的航线是双向的，题目给了完整的graph，求在一年内可以获得最多的假期的天数。
input假设是vector<city> cities, output假设是int。
如果只是求天数的话，DP可解：

1. 
   
2. int maxHolidays(const vector<city>& cities) {
   
3.   int n = cities.size();
   
4.   int res = 0;
   
5.   if (n == 0) {
   
6.     return res;
   
7.   }
   
8.   unordered_map<int, int> lookup;
   
9.   vector<vector<int>> dp(13, vector<int>(n, 0));
   
10.   for (int i = 0; i < n; ++i) {
    
11.     lookup.emplace(cities[i].id, i);
    
12.   }
    
13.   for (int i = 1; i <= 12; ++i) {
    
14.     for (int j = 0; j < n; ++j) {
    
15.       dp[i][j] = max(dp[i][j], dp[i - 1][j]);
    
16.       for (const auto& id : cities[j].dst_cities) {
    
17.         dp[i][j] = max(dp[i][j], dp[i - 1][lookup[id]]);
    
18.       }
    
19.       dp[i][j] += cities[j].holidays[i - 1];
    
20.     }
    
21.   }
    
22.   for (int num : dp[12]) {
    
23.     res = max(res, num);
    
24.   }
    
25.   return res;
    
26. }
    

复制代码

因为城市的id不等于其在input vector中的index。所以我们先建立一个lookup table。

然后我们来加大这道题的难度。
如果input不是完整的graph，只给了一个city，让我们以这个city作为起点，并且航线是单向的话，怎么办？
思路是差不多的，我们可以DFS+backtracking+memorialization:

1. 
   
2. struct cityV2 {
   
3.   int id;
   
4.   string name;
   
5.   vector<cityV2*> dst_cities;
   
6.   vector<int> holidays;
   
7. };
   
8. 
   
9. struct myHash {
   
10.   inline size_t operator()(const std::pair<int, int>& p) const {
    
11.     return (hash<int>()(p.first) + hash<int>()(p.second) * 53);
    
12.   }
    
13. };
    
14. 
    
15. using t_hash = unordered_map<pair<int, int>, int, myHash>;
    
16. 
    
17. int maxHolidaysV2Helper(cityV2* city, int& month, t_hash& lookup) {
    
18.   auto p = make_pair(month, city->id);
    
19.   auto it = lookup.find(p);
    
20.   if (it != lookup.end()) {
    
21.     return it->second;
    
22.   }
    
23.   int max_holidays = 0;
    
24.   ++month;
    
25.   for (auto& dst : city->dst_cities) {
    
26.     max_holidays = max(max_holidays, maxHolidaysV2Helper(dst, month, lookup));
    
27.   }
    
28.   max_holidays += city->holidays[--month];
    
29.   lookup[p] = max_holidays;
    
30.   return max_holidays;
    
31. }
    
32. 
    
33. int maxHolidaysV2(cityV2* start_c) {
    
34.   t_hash lookup; //key: <month, city_id>, value: max holidays
    
35.   int month = 1;
    
36.   return maxHolidaysV2Helper(start_c, month, lookup);
    
37. }
    

复制代码

如果要求的是具体的走法，其实也是差不多的做法。

如果知道具体的题目的话，可能会有更巧妙地做法。以上只是我在瞎开脑洞。

Line Breaking
地里面经
详见Google电面。。好难估计跪了第二题

假设：
1. input string肯定valid，每个单词由一个space分开。
2. input中最长的单词<=k。

先看一下brutal force的解法：

1. 
   
2. int minimumRaggedness(const string& in, int k) {
   
3.   if (in.empty()) {
   
4.     return 0;
   
5.   }
   
6.   return minSquaredSumDFS(in, k, 0);
   
7. }
   
8. 
   
9. int minimumRaggednessDFS(const string& in, int k, size_t start_pos) {
   
10.   int space_left = k;
    
11.   int res = INT_MAX;
    
12.   while (space_left > 0) {
    
13.     auto space_pos = in.find(' ', start_pos);
    
14.     space_pos = space_pos == string::npos ? in.size() : space_pos;
    
15.     space_left = space_left - (space_pos - start_pos);
    
16.     if (space_left < 0) {
    
17.       break;
    
18.     }
    
19.     if (space_pos == in.size()) {
    
20.       res = min(res, static_cast<int>(pow(space_left, 2)));
    
21.       break;
    
22.     }
    
23.     int child_res = minimumRaggednessDFS(in, k, ++space_pos);
    
24.     res = min(res, static_cast<int>(pow(space_left, 2)) + child_res);
    
25.     start_pos = space_pos;
    
26.     --space_left;
    
27.   }       
    
28.   return res;
    
29. }
    

复制代码

还可以用strok或者istringstream来分词，这里使用find是因为可以直接得到单词长度。
这里可以看到用DFS的话，会有很多重复计算。所以很容易想到记录已经计算过的结果。

1. 
   
2. int minimumRaggedness(const string& in, int k) {
   
3.   if (in.empty()) {
   
4.     return 0;
   
5.   }
   
6.   //return minSquaredSumDFS(in, k, 0);
   
7.   unordered_map<size_t, int> record;
   
8.   return minSquaredSumDFSWithMem(in, k, 0, record);
   
9. }
   
10. 
    
11. int minimumRaggednessDFSWithMem(const string& in, int k, size_t start_pos, unordered_map<size_t, int>& record) {
    
12.   auto it = record.find(start_pos);
    
13.   if (it != record.end()) {
    
14.     return it->second;
    
15.   }
    
16.   auto pos = start_pos;
    
17.   int space_left = k;
    
18.   int res = INT_MAX;
    
19.   while (space_left > 0) {
    
20.     auto space_pos = in.find(' ', pos);
    
21.     space_pos = space_pos == string::npos ? in.size() : space_pos;
    
22.     space_left = space_left - (space_pos - pos);
    
23.     if (space_left < 0) {
    
24.       break;
    
25.     }
    
26.     if (space_pos == in.size()) {
    
27.       res = min(res, static_cast<int>(pow(space_left, 2)));
    
28.       break;
    
29.     }
    
30.     int child_res = minimumRaggednessDFSWithMem(in, k, ++space_pos, record);
    
31.     res = min(res, static_cast<int>(pow(space_left, 2)) + child_res);
    
32.     pos = space_pos;
    
33.     --space_left;
    
34.   }
    
35.   record[start_pos] = res;
    
36.   return res;
    
37. }
    

复制代码

可以看到record相当于记录了以某个pos开始的word作为某行开头，余下的substring的minimum sum of squared space left over。
写到这里，DP的解法已经呼之欲出。
DP的解法：

1. 
   
2. int minimumRaggedness(const string& in, int k) {
   
3.   if (in.empty()) {
   
4.     return 0;
   
5.   }
   
6.   //return minSquaredSumDFS(in, k, 0);
   
7.   //unordered_map<size_t, int> record;
   
8.   //return minSquaredSumDFSWithMem(in, k, 0, record);
   
9.   return minimumRaggednessDP(in, k);
   
10. }
    
11. 
    
12. int minimumRaggednessDP(const string& in, int k) {
    
13.   unordered_map<int, size_t> words;
    
14.   int i = 0;
    
15.   for (size_t start = 0; start < in.size(); ++i) {
    
16.     size_t space = in.find(' ', start);
    
17.     space = space == string::npos ? in.size() : space;
    
18.     words[i] = space - start;
    
19.     start = ++space;
    
20.   }
    
21.   int n = words.size();
    
22.   vector<int> DP(n + 1, INT_MAX);
    
23.   DP[0] = 0;
    
24.   for (int i = 1; i <= n; ++i) {
    
25.     int space_left = k - words[i - 1];
    
26.     DP[i] = min(DP[i], DP[i - 1] + static_cast<int>(pow(space_left, 2)));
    
27.     --space_left;
    
28.     for (int j = i - 1; j > 0; --j) {
    
29.       space_left -= words[j - 1];
    
30.       if (space_left < 0) {
    
31.         break;
    
32.       }
    
33.       DP[i] = min(DP[i], DP[j - 1] + static_cast<int>(pow(space_left, 2)));
    
34.       --space_left;
    
35.     }
    
36.   }
    
37.   return DP[n - 1];
    
38. }
    

复制代码

这里我们预处理了一下input string。用一个unordered_map(其实直接使用vector就可以)来记录每个单词的长度。
因为计算顺序跟DFS相反，这里的状态转移方程等于以某个word作为某行结尾，其之前的substring的minimum sum of squared space left over。
可以看到虽然用了double loop，但是第二个loop是跟k的大小有关的，所以runtime performance更近似于O(n * k)。

我觉得这道题作为一道电面题目确实挺难的，因为在考虑怎么写DP的时候，还要考虑对input string的处理。
不知道给出recusive DFS+memorialization的解法，并口头指出可以将其转化为iterative DP的话可不可以过。

这道题其实DP并不是最优解，有兴趣的可以看一个这个链接：http://xxyxyz.org/line-breaking/
里面给出了O(n*logn)及O(n)的解法。

Min Time Diff
地里面经
详见Palantir Technologies OA挂经（附当时提交的代码）

我觉得楼主的思路挺不错的。附一个nlog(n)的代码。
如果Input是排序的话，每个time只用跟其前后的比较就好了，遍历整个input的同时记录一个全局最小值。
Input给的是乱序的，我直接利用了multiset是BST的特性来排序，每次BST插入一个新的元素时只会比较log(n)个已经插入的元素。 我直接在comparator里记录并更新全局最小值。

1. 
   
2. class Solution {
   
3. public:
   
4.   int minTimeDiff(const vector<string>& times) {
   
5.     if (times.empty()) {
   
6.       return 0;
   
7.     }
   
8.     int min_diff = numeric_limits<int>::max();
   
9.     multiset<myTime, myComp> s(myComp{ min_diff });
   
10.     for (const auto& time : times) {
    
11.       s.emplace(stoi(time), stoi(time.substr(min_pos)));
    
12.       if (min_diff == 0) {
    
13.         return min_diff;
    
14.       }
    
15.     }
    
16.     return min_diff;
    
17.   }
    
18. 
    
19. private:
    
20.   const int min_pos = 3;        
    
21.   using myTime = pair<int, int>;
    
22. 
    
23.   struct myComp {
    
24.     const int mph = 60;
    
25.     int& min_diff;
    
26. 
    
27.     myComp(int& diff) : min_diff(diff) {}
    
28. 
    
29.     bool operator() (const myTime& lhs, const myTime& rhs) const
    
30.     {
    
31.       int diff = (lhs.first - rhs.first) * mph + (lhs.second - rhs.second);
    
32.       min_diff = min(min_diff, abs(diff));
    
33.       return diff > 0;
    
34.     }
    
35.   };
    
36. };
    

复制代码

这里使用了multiset是因为：
set里每个元素都是unique的，要保证这个特性，每次插入一个新的元素，并把其与一个已经存在的元素进行比较时，它俩会被颠倒顺序，进行两次比较。
如果两次的boolean值相同，证明插入的元素已经存在于set中。
而multiset节约了一次比较的运算。

额外吐槽一下，不知道什么时候LeetCode讨论区改版了。新版真心不如以前好使。

dg7743 发表于 2016-6-21 05:18
Treap
地里面经
详见google 电面 挂经

您好！看过这个题原贴中的回复，好像是说用TreeMap做（太复杂，我放弃了~）。这里楼主说用Treap做，我就想问一下，如果用Treap，每个节点包括score，id，以及LinkedList存储那些score相同的id，左邻居和有邻居，然后 key应该是score，对吗？楼主可以解释一下，如何在log（n）内实现findByRank吗？非常感谢！

littlebearull 发表于 2016-7-7 07:48
您好！看过这个题原贴中的回复，好像是说用TreeMap做（太复杂，我放弃了~）。这里楼主说用Treap ...

可能我原文没有解释清楚。其实Treap就是一种自平衡的BST。这道题用Treap或者普通的BST其实做法都是一样的，都是每个节点存一个额外的值，这个值为所有子结点加自身的数量，这个改造后的结构又称为Rank Tree。至于为什么会提到Treap，是因为Treap是自平衡搜索树中比较好实现的一种，在面试中有可能写出来。如果不用Treap，只实现普通的BST的话，findByRank的worst run time是O(n)。而Treap的自平衡性质保证了这个操作为O(logn)。不管Rank Tree是用Treap，BST还是Black-Red Tree来实现的，我们都还需要一个额外的hash table，key为id，value为pointer to tree node，来更新某个id所对应的score。
如果相同的score可以是不同的rank的，那key为score，但是相同的score我们不放在linked list里，而是应该容许node with duplicate key，就像STL里的multimap/multiset一样。

举例说明：
括号外的数为score，括号里的数为所有子节点加自己的数量(nodes)。
       3(6)
      /        \
    2(4)    4(1)
   /      \
  2(2)   2(1)
/
1(1)
我们首先想找rank为5的node。从root出发，我们知道整个树一共有6个nodes。root的左子树一共有4个nodes，root的右子树一共有1个nodes。所以我们可知root即是rank为5的root。
我们想找rank为4的node。从root出发，我们知道左子树一共有4个nodes，而且全部小于root，所以排名第四的肯定在root的左子树中。
然后我们以2(4)为root，知道以其为root的树一共有4个nodes，而其左子树有两个，所以rank为4的node肯定在右子树中。
而右子树只有一个点，我们可知2(1)即是rank为4的node。代码如下：

1. 
   
2. struct node {
   
3.   int id;
   
4.   int score;
   
5.   int nodes;
   
6.   node* left;
   
7.   node* right;
   
8. }
   
9. int findByRank(node* root, int rank) {
   
10.   if (!root || rank <= 0) {
    
11.     return -1;
    
12.   }
    
13.   int left_nodes = root->left ? root->left->nodes : 0;
    
14.   if (left_nodes >= rank) {
    
15.     return findByRank(root->left, rank);
    
16.   }
    
17.   rank -=left_nodes;
    
18.   if (rank == 1) {
    
19.     return root->id;
    
20.   }
    
21.   return findByRank(root->right, --rank)
    
22. }
    

复制代码

如果相同score相同rank也好办，每个node里可以有一个unordered_set来存同样score的id。findByRank代码是差不多一样的，只不过返回一系列score相同的一系列id。

当我们要删除某个score时，还是从root出发，每个经过的点的nodes--，这个操作跟正常从一个BST里删除node是基本一样的，runtime也为log(n)。更新score的话，我们可以先删除，再插入。
insertNode, deleteNode, findRank的代码就不写了。addUser的代码如下：

1. 
   
2. unorderd_map<int, node*> hash_;
   
3. node* root_;
   
4. 
   
5. //return pointer to newly inserted node
   
6. node* insertNode(node* root, int score);
   
7. 
   
8. void deleteNode(node* root, node* target);
   
9. 
   
10. //return rank
    
11. int findRank(node* root, node* target);
    
12. 
    
13. //return id
    
14. int findByRank(node* root, int rank);
    
15. 
    
16. int addUser(int id, int score) {
    
17.   auto it = hash_.find(id);
    
18.   if (it != hash_.end()) {
    
19.     deleteNode(root_, it->second);
    
20.   }
    
21.   hash_[id] = insertNode(root_, score);
    
22.   return findRank(root_, hash_[id]);
    
23. }

复制代码

如果相同的score是不同的rank且我们有很多duplicate key，我们其实可以用pair(score, id)作为Tree的key，主要用score来排序，如果score相同用id来排序，这样findRank这个操作还是O(logn)。我们还可以每个node有一个额外的timestamp，我们用pair(score, timestamp)作为Tree的key，这样相同的score，后插入的id会有lower/higher rank。
大概就是这样，如果还有哪儿没明白的话再告诉我。

dg7743 发表于 2016-7-7 12:40
可能我原文没有解释清楚。其实Treap就是一种自平衡的BST。这道题用Treap或者普通的BST其实做法都是一样的 ...

楼主讲得非常明白，非常感谢您的详细回答~花了好久，终于把这道题弄懂了。希望以后能有机会继续跟楼主请教问题。

lz 代码解释的非常详尽啊，手动点赞，mark 一记等我复习完常规LC题开始写面经的时候来一起讨论~