一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 7710|回复: 51
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
dg7743 发表于 2016-6-14 13:22:57 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
开个贴子,记录并分享一些地里面经,LintCode和LeetCode题目的个人思路与代码。
地里的面经题目,我会给出原链接,完整的思路和代码。LintCode和LeetCode相关的代码大家都能找到,我就不贴自己的了。主要是分享一些我个人觉得难以注意到的题目相关的知识点。
解题语言为C++,可能经常会涉及到一些C++独有的特性。
开贴的目的主要是分享并且督促懒惰的自己。争取每天至少分享两道题。
post的代码争取做到bug free,但我离大神差的很远,如果代码有bug或者针对某道题大家有更好的解法,欢迎指出,我定虚心接受。

评分

5

查看全部评分

 楼主| dg7743 发表于 2016-7-7 12:40:28 | 显示全部楼层
本帖最后由 dg7743 于 2016-7-7 13:06 编辑
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. struct node {
  2.   int id;
  3.   int score;
  4.   int nodes;
  5.   node* left;
  6.   node* right;
  7. }
  8. int findByRank(node* root, int rank) {
  9.   if (!root || rank <= 0) {
  10.     return -1;
  11.   }
  12.   int left_nodes = root->left ? root->left->nodes : 0;
  13.   if (left_nodes >= rank) {
  14.     return findByRank(root->left, rank);
  15.   }
  16.   rank -=left_nodes;
  17.   if (rank == 1) {
  18.     return root->id;
  19.   }
  20.   return findByRank(root->right, --rank)
  21. }
复制代码
如果相同score相同rank也好办,每个node里可以有一个unordered_set来存同样score的id。findByRank代码是差不多一样的,只不过返回一系列score相同的一系列id。

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

  1. unorderd_map<int, node*> hash_;
  2. node* root_;

  3. //return pointer to newly inserted node
  4. node* insertNode(node* root, int score);

  5. void deleteNode(node* root, node* target);

  6. //return rank
  7. int findRank(node* root, node* target);

  8. //return id
  9. int findByRank(node* root, int rank);

  10. int addUser(int id, int score) {
  11.   auto it = hash_.find(id);
  12.   if (it != hash_.end()) {
  13.     deleteNode(root_, it->second);
  14.   }
  15.   hash_[id] = insertNode(root_, score);
  16.   return findRank(root_, hash_[id]);
  17. }
复制代码
如果相同的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。
大概就是这样,如果还有哪儿没明白的话再告诉我。



回复 支持 1 反对 0

使用道具 举报

 楼主| dg7743 发表于 2016-6-22 14:58:12 | 显示全部楼层
yoo 发表于 2016-6-22 12:44
恩,具体找到[1,0] 和[4,2,3]的代码要怎么写呢? input可以有n那么长,可以有k个这样的cycle

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

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

使用道具 举报

 楼主| dg7743 发表于 2016-6-14 13:23:37 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-14 14:31 编辑

Bomberman
地里面经
详见G家面经,已跪第四轮题目

我们先假设input为一个n x m的matirx,每个element的值可以为-1/0/1。
-1 代表wall,0代表空位,可放炸弹,1代表敌人。
这道题最容易想到的肯定是暴力解法。思路为:
我们扫描整个matrix,当遇到一个可以放炸弹的空位时,我们水平往左扫,每遇到一个敌人,我们这个空位放置炸弹可以炸死的敌人数量就加一,直到我们遇到墙或者到头。同理,再水平向右,垂直上下扫。
扫描完整个matrix之后,我们便可以得到在某个位置放置炸弹能炸死最多敌人的数量。

我们很容易就可以发现暴力解法的话,我们会有很多重复的扫描,用下面的matirx做例
0 0 1 1 -1
1 1 -1 0 0
0 -1 0 0 1
1 1 1 1 1
我们放置炸弹在matrix[0][0]时,可炸死2(水平) + 2(垂直)个敌人。当我们扫描到matrix[0][1]时,我们这个时候并不知道垂直线上我们可以炸死多少人,但水平线上的结果是已知的。因matrix[0][0]和matrix[0][1]水平线上的结果是一样的。
当遇到重复计算的问题的时候,我们很容易就可以想到要用DP。
下面的代码是我个人使用DP的一种解法:

  1. class Solution {
  2. public:
  3.         //0 empty
  4.         //1 enemy
  5.         //-1 wall
  6.         int mostKills(const vector<vector<int>>& board) {
  7.                 int res = 0;
  8.                 int m = board.size();
  9.                 if (m == 0) {
  10.                         return res;
  11.                 }
  12.                 int n = board[0].size();
  13.                 if (n == 0) {
  14.                         return res;
  15.                 }
  16.                 vector <vector<pair<int, int>>> f(m + 1, vector<pair<int, int>>(n + 1, pair<int, int>(-1, -1)));
  17.                 for (int i = 1; i <= m; ++i) {
  18.                         for (int j = 1; j <= n; ++j) {
  19.                                 if (board[i - 1][j - 1] == -1) {
  20.                                         continue;
  21.                                 }
  22.                                 if (f[i][j - 1].second == -1) {
  23.                                         f[i][j].second = 0;
  24.                                         int k = j;
  25.                                         while (k <= n && board[i - 1][k - 1] != -1) {
  26.                                                 f[i][j].second += board[i - 1][k - 1];
  27.                                                 ++k;
  28.                                         }
  29.                                 }
  30.                                 else {
  31.                                         f[i][j].second = f[i][j - 1].second;
  32.                                 }
  33.                                 if (f[i - 1][j].first == -1) {
  34.                                         f[i][j].first = 0;
  35.                                         int k = i;
  36.                                         while (k <= m && board[k - 1][j - 1] != -1) {
  37.                                                 f[i][j].first += board[k - 1][j - 1];
  38.                                                 ++k;
  39.                                         }
  40.                                 }
  41.                                 else {
  42.                                         f[i][j].first = f[i - 1][j].first;
  43.                                 }
  44.                                 if (board[i - 1][j - 1] == 0) {
  45.                                         res = max(res, f[i][j].first + f[i][j].second);
  46.                                 }
  47.                         }               
  48.                 }
  49.                 return res;
  50.         }
  51. }
复制代码
上面代码的一些值得注意的地方:
建立f时,我使用了n + 1和m + 1作为size,方便处理边界情况,这是大家都知道的DP题很常见的一个小技巧。
我存储的状态为pair<int, int>,其中first代表垂直能炸死敌人的数量,second代表水平能炸死敌人的数量。
当我们遇到空位时,我们会保存此时能炸死敌人的数量;当我们遇到敌人位时,我们还是会计算f,但不保存结果。
感觉上,f可用滚动数组进行空间上的优化。

补充内容 (2016-6-21 10:10):
19楼有这道题的另一个版本。
这道题LeetCode上已经有了No.361 Bomb Enemy
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-14 13:41:59 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-14 14:24 编辑

RainPath
地里面经
详见热乎的G家onsite面经第三轮题目

先假设这个问题是一维的,那么从src能够淹没到dst的日期取决于他俩之间最高的bar的高度。
转换为一个matrix的话,我们其实就是要找一条从src到dst的路径,这条路径上最高bar的高度越小越好。然后最短日期其实就是这条路径上最高bar的高度+1。
我们可以用BFS,然后把一般BFS其中的queue换成priority queue,在priority queue顶端的是当前未走过的高度最小的bar的index。

  1. class Solution {
  2. public:        
  3.         int leastDays(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
  4.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  5.                 int n = matrix.size();
  6.                 if (n == 0) {
  7.                         return 0;
  8.                 }
  9.                 int m = matrix.size();
  10.                 if (m == 0) {
  11.                         return 0;
  12.                 }
  13.                 int highest = matrix[src.first][src.second];
  14.                 unordered_set<pair<int, int>, MyHash> visited;
  15.                 priority_queue<pair<int, int>, vector<pair<int, int>>, MyComp> pq(MyComp{matrix});
  16.         
  17.                 visited.insert(src);
  18.                 pq.push(src);
  19.                 while (!pq.empty()) {
  20.                         auto p = pq.top();
  21.                         pq.pop();
  22.                         int value = matrix[p.first][p.second];
  23.                         highest = max(highest, value);        
  24.                         for (const auto& d : directions) {
  25.                                 pair<int, int> next(p.first + d.first, p.second + d.second);
  26.                                 if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < m && visited.find(next) == visited.end()) {
  27.                                         if (next == dst) {
  28.                                                 highest = max(highest, matrix[dst.first][dst.second]);
  29.                                                 return highest + 1;
  30.                                         }
  31.                                         int next_value = matrix[next.first][next.second];
  32.                                         pq.push(next);
  33.                                         visited.insert(next);
  34.                                 }
  35.                         }
  36.                 }
  37.                 return highest + 1;
  38.         }

  39. private:
  40.         struct MyHash {
  41.                 inline std::size_t operator()(const std::pair<int, int>& p) const {
  42.                         return (hash<int>()(p.first) + hash<int>()(p.second));
  43.                 }
  44.         };

  45.         class MyComp {
  46.                 const vector<vector<int>>* matrix;
  47.         public:
  48.                 MyComp(const vector<vector<int>>& m) {
  49.                         matrix = &m;
  50.                 }
  51.                 bool operator() (const pair<int, int>& rhs, const pair<int, int>& lhs) const {
  52.                         int rhs_val = (*matrix)[rhs.first][rhs.second];
  53.                         int lhs_val = (*matrix)[lhs.first][lhs.second];
  54.                         return rhs_val != lhs_val ? rhs_val > lhs_val : rhs > lhs;
  55.                 }
  56.                
  57.         };
  58. };
复制代码
上面代码的一些值得注意的地方:
stl并未提供pair<int, int>的default hash function,需要自己建立一个。
MyComp是我自己建立的,用为给priority_queue使用的custom comparator。
我把matrix作为一个const reference传到了MyComp里,这样我只需要matrix元素的index就可以进行两个元素的比较,尽量节省了空间。
请注意这里:
priority_queue<pair<int, int>, vector<pair<int, int>>, MyComp> pq(MyComp{matrix});
我使用了{}来construct MyComp,如果直接写pq(MyComp(matrix))的话,不能compile。
因为MyComp overload了overprator (),compiler会认为MyComp(matirx)是一个function call。

补充内容 (2016-6-21 10:11):
19楼有这道题的补充。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-14 14:16:51 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-14 14:22 编辑

Longest Consecutive Sequence
LeetCode No.128

这道题我在讨论区里看到一个十分简短精妙的C++代码。代码如下:

  1. int longestConsecutive(vector<int> &num) {
  2.     unordered_map<int, int> m;
  3.     int r = 0;
  4.     for (int i : num) {
  5.         if (m[i]) continue;
  6.         r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
  7.     }
  8.     return r;
  9. }
复制代码
我们先来分析一下代码:
用[100, 4, 200, 1, 3, 2]做例
当我们扫到4时,4此时并不在map里。
跳过if (m) continue;
此时m[i + 1] 和 m[i - 1]即m[5]和m[3]都不存在,m[i + 1] + m[i - 1] + 1 = 1
m[i - m[i - 1]] 即m[4 - m[3]] => m[4 - 0] => m[4] = 1
同理我们跳过m[i + m[i + 1]]
最后,m[4] == 1。
当我们扫到3时,
3虽然在map里,但m[3] == 0,还是跳过if (m) continue;
这时m[i + 1] + m[i - 1] + 1 => m[4] + m[2] + 1 = 1 + 0 + 1 = 2
m[i - m[i - 1]] => m[3 - m[2]] => m[3]
m[i + m[i + 1]] => m[3 + m[4]] => m[3 + 1] => m[4] = 2
最后, m[3] == 2, m [4] == 2
当我们扫到2时,
2虽然在map里,但m[2] == 0,还是跳过if (m) continue;
这时m[i + 1] + m[i - 1] + 1 => m[3] + m[1] + 1 = 2 + 1 + 1 = 4
m[i - m[i - 1]] => m[2 - m[1]] => m[1]
m[i + m[i + 1]] => m[2 + m[3]] => m[2 + 2] => m[4]
最后, m[1] == m[2] == m [4] == 4, m[3] == 2

这段代码虽然很精妙,但是我觉得要是在面试中这么写出来多半是给自己挖坑。
原因就在于,当 k 不在unorered_map里时,m[k]被假设值为0。
在c++ 官网上对于unorered_map的[] operator注解到
If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

而对于int的default constructor返回的值是什么呢?0 or undefined?
这段代码确实在LeetCode和很多c++ compiler上运行的结果都是正确的。
但是我感觉如果面试官看到这种写法,肯定是要跟你扣C++的细节的。如果不是C++大神的话,这种坑还是不要给自己挖。

回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-6-14 17:12:42 | 显示全部楼层
dg7743 发表于 2016-6-14 13:23
Bomberman
地里面经
详见G家面经,已跪第四轮题目

感觉写的好复杂,没有仔细看,为什么这里while (k <= n && board[i - 1][k - 1] != -1)还有个循环。直接从左上到右下遍历一次,从右下到左上遍历一次就可以了
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-6-14 17:15:30 | 显示全部楼层
dg7743 发表于 2016-6-14 13:41
RainPath
地里面经
详见热乎的G家onsite面经第三轮题目

这里你把x轴和y轴分开考虑写起来比你用pair会好,而且不用自定义hash,因为你是在一个matrix里面,所以直接可以把x和y映射到一维空间内(一一对应)。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-15 03:30:36 | 显示全部楼层
ryancooper 发表于 2016-6-14 17:12
感觉写的好复杂,没有仔细看,为什么这里while (k

我也觉得我的写法不够简练。你可不可以再详细解释一下的你想法呢?
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-15 03:45:29 | 显示全部楼层
ryancooper 发表于 2016-6-14 17:15
这里你把x轴和y轴分开考虑写起来比你用pair会好,而且不用自定义hash,因为你是在一个matrix里面,所以直 ...

不太明白你说的“把x轴和y轴分开考虑写起来”的意思。我明白对于matrix问题,我们都可以做一个二维到一维的映射,即index = x * n + y。这里使用了pair也是平常没有注意到pair没有default hash的问题,做这道题时发现还有这么个情况就保留了这个写法。谢谢你的建议。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-15 10:51:08 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-15 10:52 编辑

Flatten Nested List Iterator
LeetCode 341

这道题思路不难,但我觉得很考验面试者的C++水平
LeetCode已经提供了NestedInteger这个class,并且给出如下的API,让我们填写。

  1. class NestedIterator {
  2. public:
  3.     NestedIterator(vector<NestedInteger> &nestedList) {
  4.         
  5.     }

  6.     int next() {
  7.         
  8.     }

  9.     bool hasNext() {
  10.         
  11.     }
  12. };
复制代码
这个API有一个很大的问题,就是Java或者Python的iterator class确实是这样的,但C++ STL中的iterator可不是这样的API。
我在面试时遇到了这道题,当时还没有在LeetCode上刷到这道题。面试官是Java背景的,并且出题时并没有给我这么多细节,一切让我自己Design。
这道题很明显的体现了用C++面试,有时会自行提高难度。
首先我们来设计一下NestedInteger,我当时给出的答案大概是这样的:

  1. class NestedInteger {
  2.         class NestedInteger_node {
  3.                 int val;
  4.                 list<NestedInteger_node> *ptr;
  5.         };

  6.         list<NestedInteger_node> l_;

  7. };
复制代码
list中每一个node要不然就是存有一个数字,要不然它其中的ptr不为nullptr,指向另一个list。
然后NestedIterator又该长怎么样呢?我们当然可以用LeetCode提供的API,但你如果面的是一个很看重C++水平的公司,如Bloomberg,多半会给面试官不熟悉STL的感觉。
所以我们来仿照STL设计API(给我出这道题的公司并不是用C++)。
首先我们在使用STL容器的iterator时,一般都是类似这么使的:
map<int, int> m;
......
for (map<int, int>::iterator it = m.begin(); it  != m.end(); ++it) {
*it
......
可以看出iterator是嵌套在容器里的。我们需要begin(),和end()来获得iterator的首尾。我们需要overload operator++和operator*。
所以我们的NestedIterator大概应该长这样:

  1. class NestedInteger {
  2. public:        
  3.         class iterator {
  4.         public:
  5.         
  6.                 friend class NestedInteger ;
  7.                
  8.                 iterator() {
  9.                 }
  10.                
  11.                 //pre
  12.                 iterator& operator++() {
  13.                 }

  14.                 //post
  15.                 iterator operator++(int) {
  16.                 }

  17.                 int& operator*() {
  18.                 }
  19.         };
  20.         
  21.         iterator begin() {
  22.         }

  23.         iterator end() {
  24.         }
  25.         
  26. private:
  27.         class NestedInteger_node {
  28.                 int val;
  29.                 list<NestedInteger_node> *ptr;
  30.         };

  31.         list<NestedInteger_node> l_;
  32. };
复制代码
我面试的时候写完了operator++和operator*,这两个相当于next()和hasNext()。但是我们可以看出如果这道题如果要精益求精的,其难度要比LeetCode所给的API要高出不少。
有很多细节需要注意,比如overload operator时pre++和post++对应的function是什么? end() 返回的iterator结尾应该如何设计?因为我们要比较 it != end(),我们是不是还需要overload operator!= ?
这些细节在我们在LeetCode上实现时是不用考虑的,但你如果面试的是一家看重C++的公司,被问了这道题,并且你也表明C++是你的主语言的话。这些还是很重要的,至少会是加分的(当然如果对某些地方不熟悉,不要自行挖坑)。
当我们dereferrence iterator时,返回的是容器中某个元素的referrence,我们可以修改这个元素的值。这道题虽然无所谓,但是有些类似的设计iterator的题,我们只是想按某种规定的顺序读取容器,并不想对其进行修改的话,我们应该实现的是const_iterator。这也是一个值得注意的细节。
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-6-15 13:16:55 | 显示全部楼层
dg7743 发表于 2016-6-15 10:51
Flatten Nested List Iterator
LeetCode 341

如果真是考察你的C++的话,你写的Iterator其实准确来说要继承自std::iterator,同时你得指定你的iterator所属的category。按照你现在的写法,是不能和符合STL container定义的容器一起用的。所以面试的时候按照Java那种接口的设计其实就挺好的了。
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-6-15 13:25:31 | 显示全部楼层
本帖最后由 ryancooper 于 2016-6-15 15:14 编辑
dg7743 发表于 2016-6-15 03:30
我也觉得我的写法不够简练。你可不可以再详细解释一下的你想法呢?

直接从左上到右下遍历的时候,比如定义left[j]表示从位置(i, j)往左看同一行最多能炸多少,up[j]表示从位置(i, j)往上看同一列最多能炸多少。
很明显left[j] = left[j-1] + 1 if matrix[j] == 1 else 0
up[j] = up[i-1][j] + 1 if matrix[j] == 1 else 0
同理从右下到左上遍历算出往右和往下看的,并且对空地的时候累计四个方向值求最大就好了
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-15 14:58:20 | 显示全部楼层
ryancooper 发表于 2016-6-15 13:25
直接从左上到右下遍历的时候,比如定义left[j]表示从位置(i, j)往左看同一行最多能炸多少,up[j]表示从位 ...

明白了,谢谢!
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-16 13:25:02 | 显示全部楼层
Hash Heap
LintCode LFU
LintCode Building Outline

这两道题都会用到Hash Heap这种data structure。(Building Outline基本等同于LeetCode N0.218 The Skyline Problem,不过要求返回的结果不同)
我们用LFU做例,并先来看一下不用Hash Heap怎么做。
首先要实现LFU,我们需要一个hash table来提供O(1)的Key-Value look up,还需要一个heap(min heap)来记录每个Key被访问的Frequency,当user update 了某个Key时,我们需要在hash table里修改其对应的Value,还需要在heap中更新这个Key的Frequency,当cache满了时,我们需要把heap顶所对应的Key从hash table里删除。
hash table很容易就想到可以用unordered_map,但是heap可以用priority_queue吗?
这里用priority_queue是不合适的,因为我们只能访问并删除其顶端的元素。
替代方案就是用multimap来实现这个heap。(因为Frequency可以是重复的,所以我们不能用map)
代码如下:

  1. unordered_map<int, pair<int, multimap<int, int>::iterator>> hash_; //<key, pair<value, position_of_key_in_heap>>
  2. multimap<int, int, less<int>()> heap_; //frequency, key
复制代码
需要额外指出的是,当我们存储iterator用于在未来查找元素在某容器中位置的时候,要注意iterator validity的问题。
当我们需要查找least frequent key时,可以调用heap_.begin()。因为multimap的实现用的是BST,这个操作为O(logn)。
到我们要更新某个key的frequency时,因为multimap中的key是"immutable"的,所以我们需要先删除其frequency,然后frequency + 1,再添加回multimap。因为我们已经保存了iterator,定位key在heap的位置为O(1),而“更新”需要两次O(logn)。
这样的话,我们大概满足了LFU的需求。如果想要保留别的操作的运行时间,并且提供O(1)的查找least frequent key的话,我们就需要实现hash heap了。
可以看到九章官网上Building Outline的java解法中实现了hash heap (C++版用了multiset)。
这个博客里给了很清新明了的java版hash heap LFU解法。
其中heap是使用array实现的。如果我们需要找到某个Key在heap中的位置,只需要存储其frequency在array中的index就好了。
hash heap的实现方法不仅提供了O(1)的查找least frequent key,而且当我们更新某个key的frequency时可以直接shift up/down,而不是删除再添加了。
当然在面试时自己实现hash heap可能会时间不足,九章算法的老师就多次提到,可以用已有的容器解决问题后,再提出有hash heap这个优化。

(这篇敲第一遍时草稿丢失,又手动敲了一遍,心塞)



补充内容 (2016-6-21 10:12):
20楼有对multimap runtime的订正。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-16 13:51:58 | 显示全部楼层
Strobogrammatic Number
LeetCode No.246

这道题不难,但我觉得很有意思的一点是如果LeetCode给的API是
bool isStrobogrammatic(int num)
而不是
bool isStrobogrammatic(string num)
的话,我可能会纠结很半天在bit manipulation的问题上。arguement是string的话,我们可以很方便的进行首尾操作。
如果面试的时候,没有给明我明确的条件,我又假设arguement是int的话,我应该不会直接想到先把int转为string会大大的简化代码。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-16 13:52:22 | 显示全部楼层
Hash Heap
LintCode LFU
LintCode Building Outline

这两道题都会用到Hash Heap这种data structure。(Building Outline基本等同于LeetCode N0.218 The Skyline Problem,不过要求返回的结果不同)
我们用LFU做例,并先来看一下不用Hash Heap怎么做。
首先要实现LFU,我们需要一个hash table来提供O(1)的Key-Value look up,还需要一个heap(min heap)来记录每个Key被访问的Frequency,当user update 了某个Key时,我们需要在hash table里修改其对应的Value,还需要在heap中更新这个Key的Frequency,当cache满了时,我们需要把heap顶所对应的Key从hash table里删除。
hash table很容易就想到可以用unordered_map,但是heap可以用priority_queue吗?
这里用priority_queue是不合适的,因为我们只能访问并删除其顶端的元素。
替代方案就是用multimap来实现这个heap。(因为Frequency可以是重复的,所以我们不能用map)
代码如下:

  1. unordered_map<int, pair<int, multimap<int, int>::iterator>> hash_; //<key, pair<value, position_of_key_in_heap>>
  2. multimap<int, int, less<int>()> heap_; //frequency, key
复制代码

需要额外指出的是,当我们存储iterator用于在未来查找元素在某容器中位置的时候,要注意iterator validity的问题。
当我们需要查找least frequent key时,可以调用heap_.begin()。因为multimap的实现用的是BST,这个操作为O(logn)。
到我们要更新某个key的frequency时,因为multimap中的key是"immutable"的,所以我们需要先删除其frequency,然后frequency + 1,再添加回multimap。因为我们已经保存了iterator,定位key在heap的位置为O(1),而“更新”需要两次O(logn)。
这样的话,我们大概满足了LFU的需求。如果想要保留别的操作的运行时间,并且提供O(1)的查找least frequent key的话,我们就需要实现hash heap了。
可以看到九章官网上Building Outline的java解法中实现了hash heap (C++版用了multiset)。
这个博客里给了很清新明了的java版hash heap LFU解法。
其中heap是使用array实现的。如果我们需要找到某个Key在heap中的位置,只需要存储其frequency在array中的index就好了。
hash heap的实现方法不仅提供了O(1)的查找least frequent key,而且当我们更新某个key的frequency时可以直接shift up/down,而不是删除再添加了。
当然在面试时自己实现hash heap可能会时间不足,九章算法的老师就多次提到,可以用已有的容器解决问题后,再提出有hash heap这个优化。

(这篇敲第一遍时草稿丢失,又手动敲了一遍,心塞)

补充内容 (2016-6-18 16:06):
重复发了一遍,论坛好像没有删除功能。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-16 13:54:33 | 显示全部楼层
有一个回复我一发表就告诉我需要审核,不知道是不是因为我使用了外部链接的缘故。
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-18 09:58:49 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-18 16:07 编辑

Max Value Formula
地里面经
详见[面试经验] snapchat跪经+面经合辑第四轮题目及follow up

先把题目和follow up解法的源代码贴上来,再说一下我的思路:

  1. class Solution {
  2. public:
  3.         double maxValue(const vector<double>& nums) {
  4.                 int s = nums.size();
  5.                 if (s == 0) {
  6.                         return 0;
  7.                 }
  8.                 dp_ = vector<vector<double>>(s, vector<double>(s, -numeric_limits<double>::max()));

  9.                 for (int i = 0; i < s; ++i) {
  10.                         dp_[i][i] = nums[i];
  11.                 }

  12.                 for (int i = 1; i < s; ++i) {
  13.                         for (int j = i - 1; j >= 0; --j) {
  14.                                 for (int k = j; k < i; ++k) {
  15.                                         dp_[j][i] = max(dp_[j][i], max(dp_[j][k] + dp_[k + 1][i], dp_[j][k] * dp_[k + 1][i]));
  16.                                 }
  17.                         }
  18.                 }

  19.                 return dp_[0][s - 1];
  20.         }

  21.         string maxValueFormula(const vector<double>& nums) {
  22.                 string res = "";
  23.                 int s = nums.size();
  24.                 if (s == 0) {
  25.                         return res;
  26.                 }
  27.                 maxValue(nums);
  28.                 list<string> res_list;
  29.                
  30.                 maxValueFormulaHelper(nums, 0, s - 1, res_list, res_list.begin(), res_list.begin(), "+");
  31.                 for (auto it = res_list.begin(); it != res_list.end(); ++it) {
  32.                         res.append(*it);
  33.                 }
  34.                 return res;
  35.         }
  36. private:
  37.         void maxValueFormulaHelper(const vector<double>& nums, int start_i, int end_i, list<string>& res_list, list<string>::iterator list_b, list<string>::iterator list_e, string last_op) {
  38.                 if (start_i == end_i) {
  39.                         res_list.insert(list_b, to_string(nums[start_i]));
  40.                         return;
  41.                 }
  42.                 auto next_b = list_b;
  43.                 auto next_e = list_e;
  44.                 for (int k = start_i; k < end_i; ++k) {
  45.                         if ((dp_[start_i][k] + dp_[k + 1][end_i]) == dp_[start_i][end_i]) {
  46.                                 next_b = res_list.insert(list_b, "+");
  47.                                 if (last_op != "+") {
  48.                                         res_list.insert(next_b, "(");
  49.                                         next_e = res_list.insert(list_e, ")");
  50.                                 }
  51.                                 maxValueFormulaHelper(nums, start_i, k, res_list, next_b, next_b, "+");
  52.                                 maxValueFormulaHelper(nums, k + 1, end_i, res_list, next_e, next_e, "+");
  53.                                 break;
  54.                         }
  55.                         else if ((dp_[start_i][k] * dp_[k + 1][end_i]) == dp_[start_i][end_i]) {
  56.                                 next_b = res_list.insert(list_b, "*");
  57.                                 maxValueFormulaHelper(nums, start_i, k, res_list, next_b, next_b, "*");
  58.                                 maxValueFormulaHelper(nums, k + 1, end_i, res_list, next_e, next_e, "*");
  59.                                 break;
  60.                         }
  61.                 }
  62.         }

  63.         vector<vector<double>> dp_;
  64. };
复制代码
maxValue()是原题目的DP解法。可以看到状态转移方程很简单明了。
原题中包含()作为运算符,我一开始纠结了半天怎么在状态中表示并处理()。
不过其实仔细观察,我们可发现我们并不用处理():
假设我们有三个数a1, a2, a3,这三个数可以有下面这些组合:
1. a1 + a2 + a3        =>        (a1 + a2) + a3
2. a1 + a2 * a3                =>        a1 + (a2 * a3)
3. (a1 + a2) * a3
4. a1 * a2 * a3                =>        (a1 * a2) * a3
5. a1 * (a2 + a3)
6. a1 * a2 + a3                =>        (a1 * a2) + a3
我们给上述运算都强制加上()后可看到,
max(dp[0][1] + dp[2][2], dp[0][1] * dp[2][2]) 处理了1,3,4,6
max(dp[0][0] + dp[1][2], dp[0][0] * dp[1][2]) 处理了2,5
当我们在代码中运行k loop时,dp[j][k]相当于括号内aj到ak的结果,dp[k + 1]相当于括号内ak+1到ai的结果。

maxValueFormula()是follow up的解法。
一看到follow up,大体上我们可以想到是recursion + backtracking的题目。可是我很难想出如何写出一段简洁的一边计算最大值,一边保存当前最大值的公式的代码。
然后我想到既然我们已经在maxValue()中得到了表示最大值的状态转移数列,可不可在follow up中直接backtracking这个数列?
已知dp[0][n - 1],并且我们知道dp[0][n - 1]等于dp[0][k] + or * dp[k + 1][n - 1],我们可以得到(dp[0][k]) + or * (dp[k + 1][n - 1])这个公式。然后我们可以再分治dp[0][k]和dp[k + 1][n - 1],直到我们得到完整的公式。
我运用了STL list来构建这个公式,因为我们可以在list的任意位置添加元素。运用了list::iterator来记录子公式应该被添加到的位置。最后返回结果的时候,再把list转换为string。
通过last_op我们可以知道子公式是否需要被()包围。

我们用{ 0, -1, 4, -9, 0.5 }做例:
max_value = 5.5
dp[0][4] = dp[0][0] + dp[1][4]
list: +
dp[0][0] = 0
list: 0 +
dp[1][4] = dp[1][3] + dp[4][4]
list: 0 + +
dp[1][3] = dp[1][1] * dp[2][3]
list: 0 + * +
dp[1][1] = -1
list: 0 + -1 * +
dp[2][3] = dp[2][2] + dp[3][3]
list: 0 + -1 * ( + ) +
dp[2][2] = 4
list: 0 + -1 * (4 + ) +
dp[3][3] = -9
list: 0 + -1 * (4 + -9) +
dp[4][4] = 0.5
list: 0 + -1 * (4 + -9) + 0.5
we got the result!

昨晚家里网络不好,登不上地里。



补充内容 (2016-7-6 10:55):
-numeric_limits<double>::max()可以替换为numeric_limits<double>::lowest()
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-18 15:48:02 | 显示全部楼层
本帖最后由 dg7743 于 2016-6-18 15:51 编辑

Helicopter Path
地里面经
详见snapchat跪经+面经合辑第三轮题目

这道题跟之前做过的Rain Path很相似,区别在于:
Rain Path是求从src到dst最高高度最小的路径。
Helicopter Path是求从src到dst高度之和最小的路径。其中路径上下一个点的高度必需不小于前一个点。

我的思路还是heap+bfs:
从src开始我们做bfs。heap顶端的点是目前高度之和最小的点,我们把它作为一次循环的起点,如果下一个点我们还没有走过,且它的高度>=现在点的高度,我们就把下一个点的高度与现在已经积累的高度之和相加,并把它添加到heap中。
如果下一个点我们已经走过,但是它的高度之和>我们从一条新的路径到达这个点的高度之和的话,我们就用较小的高度之和的取代原本的。如果这个点已经在heap中了,我们需要先把它从heap中删除,在把其新的高度之和插入heap中。这步操作有没有很眼熟?没错就是前几天LFU那道题中我提到过的hash heap。这道题很巧合的跟Rain Path和LFU都有思路上的重合。
下面的代码我“偷懒”了,还是用的multimap模拟的hash heap。

  1. class Solution {
  2. public:
  3.         int minimumHeightsSum(const pair<int, int>& src, const pair<int, int>& dst, const vector<vector<int>>& matrix) const {
  4.                 const vector<pair<int, int>> directions{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  5.                 int sum = 0;
  6.                 int n = matrix.size();
  7.                 if (n == 0) {
  8.                         return 0;
  9.                 }
  10.                 int m = matrix.size();
  11.                 if (m == 0) {
  12.                         return 0;
  13.                 }

  14.                 unordered_map<int, int> visited;                                //key: index, value: cumulated sum
  15.                 //below two data structue simulate hash heap
  16.                 unordered_map<int, MyHeap::iterator> hash;                //key: index, value: position of index in heap
  17.                 MyHeap heap;                                                                //key: cumulated sum, value: index

  18.                 int src_index = src.first * n + src.second;
  19.                 int dst_index = dst.first * n + dst.second;
  20.                 visited[src_index] = matrix[src.first][src.second];
  21.                 auto res_it = heap.emplace(visited[src_index], src_index);
  22.                 hash[src_index] = res_it;
  23.                 while (!heap.empty()) {
  24.                         auto cur_it = heap.begin();
  25.                         int cur_sum = cur_it->first;
  26.                         int cur_x = cur_it->second / n;
  27.                         int cur_y = cur_it->second % n;
  28.                         for (const auto& d : directions) {
  29.                                 int next_x = cur_x + d.first;
  30.                                 int next_y = cur_y + d.second;
  31.                                 int next_index = next_x * n + next_y;
  32.                                 if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && matrix[next_x][next_y] >= matrix[cur_x][cur_y]) {                        
  33.                                         auto v_it = visited.find(next_index);
  34.                                         if (v_it == visited.end()) {
  35.                                                 //if next point has not been visited
  36.                                                 int next_sum = cur_sum + matrix[next_x][next_y];
  37.                                                 visited[next_index] = next_sum;
  38.                                                 auto res_it = heap.emplace(visited[next_index], next_index);
  39.                                                 hash[next_index] = res_it;
  40.                                         }
  41.                                         else {
  42.                                                 int next_sum = v_it->second;
  43.                                                 if (next_sum > cur_sum + matrix[next_x][next_y]) {
  44.                                                         //if current next_sum > new next_sum
  45.                                                         auto h_it = hash.find(next_index);
  46.                                                         if (h_it != hash.end()) {
  47.                                                                 //if next point is already in heap
  48.                                                                 heap.erase(h_it->second);
  49.                                                         }
  50.                                                         visited[next_index] = cur_sum + matrix[next_x][next_y];
  51.                                                         auto res_it = heap.emplace(visited[next_index], next_index);
  52.                                                         hash[next_index] = res_it;
  53.                                                 }
  54.                                         }
  55.                                         if (next_index == dst_index) {
  56.                                                 return visited[dst_index];
  57.                                         }
  58.                                 }
  59.                         }
  60.                         hash.erase(cur_it->second);
  61.                         heap.erase(cur_it);
  62.                 }
  63.                 return -1;
  64.         }

  65. private:
  66.         using MyHeap = multimap<int, int, less<int>>;
  67. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-19 16:48:55 | 显示全部楼层
Bomberman V2 & Rain Path note

根据@ryancooper的意见写了更简洁版本Bomberman的DP代码:
  1.        
  2. int mostKillsV2(const vector<vector<int>>& board) {
  3.   int res = 0;
  4.   int n = board.size();
  5.   if (n == 0) {
  6.     return res;
  7.   }
  8.   int m = board[0].size();
  9.   if (m == 0) {
  10.     return res;
  11.   }
  12.   vector<vector<int>> ver(n + 2, vector<int>(m + 2, 0));
  13.   vector<vector<int>> hori(n + 2, vector<int>(m + 2, 0));

  14.   for (int i = 1; i <= n; ++i) {
  15.     for (int j = 1; j <= m; ++j) {
  16.       if (board[i - 1][j - 1] == -1) {
  17.         continue;
  18.       }
  19.       ver[i][j] = ver[i - 1][j] + board[i - 1][j - 1];
  20.       hori[i][j] = hori[i][j - 1] + board[i - 1][j - 1];
  21.     }
  22.   }

  23.   for (int i = n; i > 0; --i) {
  24.     for (int j = m; j > 0; --j) {
  25.       if (board[i - 1][j - 1] == -1) {
  26.         continue;
  27.       }
  28.       int up = ver[i][j];
  29.       int left = hori[i][j];
  30.       ver[i][j] = hori[i][j] = 0;
  31.       ver[i][j] = ver[i + 1][j] + board[i - 1][j - 1];
  32.       hori[i][j] = hori[i][j + 1] + board[i - 1][j - 1];
  33.       if (board[i - 1][j - 1] == 0) {
  34.         res = max(res, up + left + ver[i][j] + hori[i][j]);
  35.       }
  36.     }
  37.   }

  38.   return res;
  39. }
复制代码
Rain Path这道题里我把matrix的reference传入了MyComp class。
MyComp里我用了ptr来指向matrix的reference。
const vector<vector<int>>* matrix;
更好的做法是直接使用reference:
const vector<vector<int>>& matrix;
但是C++中 Reference variables must be initialized to the thing they reference。
我在网上搜了搜,发现
There are two places where variables can be initialized:
  • when they're declared
  • in a constructor's initialization clauses

所以,如果我们想使用reference作为class member variable的话,代码可以写成下面这样:

  1. class MyComp {
  2.   const vector<vector<int>>& matrix;
  3. public:
  4.   MyComp(const vector<vector<int>>& m) : matrix(m){}
  5. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-6-21 05:18:16 | 显示全部楼层
Treap
地里面经
详见google 电面 挂经

在我们讨论这道题之前,我先在这里改正一个LFU那道题我犯得一个错误。
我写了multimap.begin()的时间效率为O(logn),这是错误的信息。
STL中所有容器的begin()和end()效率都为O(1)。
我大概浏览了一下一个版本的C++ STL map的源代码,在建立red-black tree时,leftmost和rightmost都是会被记录和更新的。
当begin()被调用时,直接返回的为leftmost所对应的iterator。
每个red-black tree node都有一个parent指针。所以我们进行iterator++的操作时,其时间效率为O(1)。
用iterator遍历map的操作时间效率即为O(n)。

原帖里很多大神都提到了Treap这个数据结构来解这道题,关于Treap,这篇博文里有完美的解读。
我之前也完全没有听说过Treap这个结构,我遇到这道题肯定还是会先想能不能用STL里已有的容器来实现。
如果用STL的话,这道题跟LFU的思路近乎是一模一样的。findByRank也很好实现:

  1. unordered_map<int, pair<int, multimap<int, int>::iterator>> hash;        //key: id, value: pair<score, position_in_bst>
  2. multimap<int, int> bst;                                                                        //key: score, value: id

  3. int findByRank(int rank) {
  4.   if (rank <= 0) {
  5.     return -1;
  6.   }
  7.   int r = 1;
  8.   auto it = bst.begin();
  9.   for (int i = r; i < rank && it != bst.end(); ++i) {
  10.     ++it;
  11.   }
  12.   if (it == bst.end()) {
  13.     return -1;
  14.   }
  15.   return it->second;
  16. }
复制代码
这样的话,findByRank的时间效率为O(n)。如果我们要进一步优化这个操作的话,我们需要自己实现一个BST。
自己实现一个BST的好处在于,我们在每个tree node都可以存一个额外的值。这个值为subtree所含nodes的数量。
这样的话寻找某个id的Rank,或者根据Rank寻找某个id的时效都可以优化为O(logn)。
有关BST Rank的问题可以参考这个stackoverflow的链接:Computing rank of a node in a binary search tree
在面试的时间里实现一个AVL Tree或者Red-Black Tree显然是非大神做不到的。但是实现一个最基本的BST是可行的。

对于这道题来说,我们有三种做法:
1. 大神的做法:知道Treap,并直接实现它。
2. 自己实现一个BST,每个Tree node包含subtree nodes的数量。(当然真大神可以直接写出一个Red-Black Tree)
3. 用自己熟悉的语言带有的容器解题,实现后清晰明了的指出各步操作的效率,并提出可以怎么进一步优化。

如果能做到1,那显然你是一个很优秀的candidate。但是这道题里出现的Treap,包括LFU里出现的hash heap,对于我这种普通的程序员来说是一般不会接触到的。
牢记所有的小众数据结构,并且能够把它与面试题立马联系起来,那显然是已经跨入大神领域的程序员才能做的。
作为一个普通的程序员,熟悉主流的数据结构,通过把它们排列组合来实现2或3应该也足以应对面试了吧???


补充内容 (2016-7-7 12:51):
38楼有更详细的补充。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表