脸家店面1+段子

国人小哥, 放水严重上来问做过最屌的prject，楼主一不小心没有刹住车，被打断说你丫废话真多还想不想愉快地撸题了。。。小哥人真的太好了
1 Decode ways
2 判断subarray的和是否有目标值，只返回布尔值。有正有负。


------------------------------------段子分割线
题真的太简单了，然而楼主还是丢人丢大了
第一题略装了一下
第二题看到这么简单，就嘴贱问了一句是不是immutable的。

我：如果是mutable的我们可以用Binary Index Tree做
小哥：影垂思婷，你怎么用BST做
我：不是BST，人

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

是很快搞定了。

问了两个无关痛痒的问题以后结束了。

我觉得我如果挂了，真不能怪别人，就是自己作的。面试题准备了3000多行，结果万没想遇到这样的情况。
求个米吧。



补充内容 (2017-3-29 13:18):
并且楼主后来意识到BIT并不适合做这个题。
简直了。蠢出了一个新高度。

哈哈 我觉得有戏

楼主的段子不错。。祝福你

Q2: Use a hash set to record partial sums and check if it contains (current sum - target):

1. bool hasSubSum(vector<int>& arr, int target) {
   
2.     int sum = 0;
   
3.     unordered_set<int> sums = {0};   
   
4.     for (int a : arr)
   
5.         if (sums.count((sum+=a)-target)) return true;
   
6.             else sums.insert(sum);
   
7.     return false;
   
8. }

复制代码

第二题应该是 01背包问题?

Youknowwho 发表于 2017-3-28 18:13
第二题应该是 01背包问题?

不是   就是最简单的range sum

第二题如果是mutable的，为什么要用BIT做？

windywinter 发表于 2017-3-29 04:19
第二题如果是mutable的，为什么要用BIT做？

update的时候是O(lgn)的时间复杂度

翻滚吧豆子 发表于 2017-3-29 04:26
update的时候是O(lgn)的时间复杂度

那求解是怎么做？

当什么程序员，你可以去当段子手了。

windywinter 发表于 2017-3-29 04:28
那求解是怎么做？

http://www.hawstein.com/posts/binary-indexed-trees.html
这里是详细介绍