|
n****o
发帖数: 399 | 2
如果允许increment和deletion，从左往右也不对啊，比如 4 1 2 3
主要是你那个从右往左的方法好像不容易找到反例，但是也不容易想清楚greedy方法一
定能得到最优的解 |
|
b****e
发帖数: 45 | 3 多谢你的反例！我的解法确实也有问题。
看来不管从左往右还是从右往左都没办法完全考虑到达成全局最优的条件，
Greedy算法可能行不通。 |
|
l*****a
发帖数: 14598 | 4 找个例子试试，不保证没问题 :)
简单说就是有左子树就往左，否则就往右
左右都结束了，就可以打印当前了。
stack里似乎保存的是当前到跟的path |
|
p*g
发帖数: 141 | 5 同疑惑
不过这样空间肯定是 罗格恩
比如一串010101， 表示从入特开始， 往左往右 |
|
d**********x
发帖数: 4083 | 6 恩，我想了一下，主要是靠灵感，要是灵错了请指出。。
直接按照问题定义来，是可以做到时间O(n)空间O(1)的
具体就是使劲往右边走，然后输出，记录当前输出的最后一层层数 -- 当且仅当当前层
数大于记录的层数时输出。
当没有right child的时候，就往parent方向走，找到第一个具有left child的(注意区
分返回时是从right返回还是left返回)，然后继续重复以上算法
这样可以保证遍历的时候每层总是这一层的最右边节点先被访问到
没有parent指针的话可以利用child指针，不碍事。 |
|
p*****2
发帖数: 21240 | 7
发现1往左找，发现0往两边找吧。不是完全的二分。 |
|
S**********r
发帖数: 284 | 8 来自主题: JobHunting版 - G 家面经 问题
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便，改成从左上（0,0） 走到 右下 (m-1, n-1)
分析
三维 DP ，有点烦琐，我也没有验证过，自己感觉是对。这个问题的重点就是，每走一
步都会破原来的状态。 通过分析，可以知道，最优解中，两个人走的线路，不可能有
任何的重合。 证明方法是，只要有重合，总能通过修改一条线路，去掉重合而达到更
优的解。 也就是说，要得到最优解的话，如果某个位置的金币被人拿走了，这个位
置，另一个人就不能再去走。 还可以观察到，在任何一层 i， 这两个人所处的位
置 j 和 k， j < k 总成立.
A 是 m x n 的matrix，假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表... 阅读全帖 |
|
S**********r
发帖数: 284 | 9 来自主题: JobHunting版 - G 家面经 问题
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便，改成从左上（0,0） 走到 右下 (m-1, n-1)
分析
三维 DP ，有点烦琐，我也没有验证过，自己感觉是对。这个问题的重点就是，每走一
步都会破原来的状态。 通过分析，可以知道，最优解中，两个人走的线路，不可能有
任何的重合。 证明方法是，只要有重合，总能通过修改一条线路，去掉重合而达到更
优的解。 也就是说，要得到最优解的话，如果某个位置的金币被人拿走了，这个位
置，另一个人就不能再去走。 还可以观察到，在任何一层 i， 这两个人所处的位
置 j 和 k， j < k 总成立.
A 是 m x n 的matrix，假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表... 阅读全帖 |
|
K********y
发帖数: 47 | 10 我见过的是Manhattan distance。答案的x/y坐标分别是N个点x/y坐标的median。二维
问题可以分离：sum_i(|x-x_i|+|y-y_i|) = sum_i(|x-x_i|) + sum_i(|y-y_i|)。
median的两边各有N/2个人，从median往左（上）走一步，有N/2个人多走一步，N/2个
人少走一步。如果左边人数多于右边，往左挪一步可以减少总步数。当然如果N是偶数
，其实不需要真正的median，可以是最中间两个人之间的任何地方。 |
|
r*******e
发帖数: 7583 | 11 第1题跟那个找数列最长连续子序列一样把
把array所有元素都放进hashset
对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
扫完了计数器加一
分。
)) |
|
x*****0
发帖数: 452 | 12 给定一个n*n的board里面是0或1.算出里面独立0group的数量。比如
0 0 1 1 1
0 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 1 1 1 1
我的两个想法：
第一个当然就是DFS，bfs也行。每次遇到0的时候，进行DFS，得到一个connected
component。在DFS的过程中，把当前这个connected component的label改成count,
count初始化为1。并且DFS之后，count++。伪代码如下：
void dfs(int[][n] board, int row, int col, int count){
...
}
numofcp(board) {
count = 1;
for i = 1 : n
for j = 1 : n
if (board[i][j] == 0) {
dfs(i, j, count);
++count;
}
end
end
return count;
}
因为DFS的过程中，我们得用一个二维visited数组来标示已经访... 阅读全帖 |
|
|
s**x
发帖数: 7506 | 14 如何判断stack是往上还是往下增长
just declare 2 local variables and check the address should be enough.
int a;
int b;
&a < &b |
|
J******u
发帖数: 42 | 15 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 16 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 17 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 18 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
r*******2
发帖数: 104 | 19
好的，我把我的解题过程也说一下。Leetcode原题就不用说了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第... 阅读全帖 |
|
h*****k
发帖数: 8 | 20 你这个也是个很好的往下说的思路，当时面试官跟我说是个general program. 我就没
问功能，workflow，use case之类的了。感觉他不太care我往哪个思路说，更care在一
些细节的处理上，我是否考虑全面了，是否跟上他的思路。 |
|
D*********G
发帖数: 193 | 21 和next permutation无关
有空练一下，还是我之前说的，这题考察 design + dfs.
“按照数字大小的顺序”是按照行从上往下，列从左往右。仔细看我的例子就知道了。 |
|
D*********G
发帖数: 193 | 22 和next permutation无关
有空练一下，还是我之前说的，这题考察 design + dfs.
“按照数字大小的顺序”是按照行从上往下，列从左往右。仔细看我的例子就知道了。 |
|
c****m
发帖数: 179 | 23 其实双向bfs就可以。
再简化一下就是ls说的dp。N^2
先把左边和上边的置为true，然后往右边和下边扫根据高度决定是否当前点为true
然后再从右边和下边往左上扫，遇到true就输出，要注意边界。
这个过程是dp。 |
|
p**p
发帖数: 742 | 24 嗯，这样好像也有问题。还是搞不定下面这种情况：
1 1 1 1 1 1
1 1 1 2 1 1
1 2 1 2 1 1
3 2 2 2 2 2
（2，2）里面的那个1在从下往上，从右往左扫描的时候不会被考虑，因为它比下面和
右面的元素都小。
看来还是老老实实DFS吧。
it
true |
|
y****t
发帖数: 23 | 25 o(n)就行了...
提示：从左往右+从右往左 |
|
l*****n
发帖数: 246 | 26 怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted |
|
y****t
发帖数: 23 | 27 o(n)就行了...
提示：从左往右+从右往左 |
|
l*****n
发帖数: 246 | 28 怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted |
|
n*******y
发帖数: 453 | 29 用stack 扫， 不match 的 ) 全部删掉。
最后如果有剩下的 ( , 从右往左删掉对应的个数就可以了。 因为 ( 如果在右边是
match的，往左移仍然match.
随后好像不是唯一解
比如输入
(()()
可以是
()()
也可以是 (())
我的算法会得出
(())的结果 |
|
f*****6
发帖数: 61 | 30 找到最高的那根柱子，把array分成左右两部分，分别从左往右到最高的那根柱子为止
，然后从右往左到最高的柱子为止，然后计算的结果累加起来。 |
|
Q**F
发帖数: 995 | 31 1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
2。 两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。 |
|
b*****n
发帖数: 618 | 32 " 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。"
这是原来的描述，二维matrix，所以我觉得是m×n
我题都没看懂傻逼了，你牛逼你继续喷吧，你还可以继续用你牛逼的backtracking来解
这个只有两行的matrix |
|
l*****z
发帖数: 3022 | 33 来自主题: JobHunting版 - 来个面试题 给个想法，
扫描一遍找到总重量处以M得到每个包的最佳重量，再按重量排序，然后从最重的报开
始往最轻的移动物品，移动到差不多最佳就下一个包，2个指针往中间移动。 |
|
e********3
发帖数: 229 | 34
问题就是停止branch的条件.不能遇到1或者*就停止吧.比如1左边位置是*,这时候不能
停止,因为*的左边和上边可能都需要染色.比如这样:
0000*00
000*1*0
0000*10
对于第三行的1,你bfs时往左走发现有个*,这时候按照染色算法就停止了.但是实际还是
要继续往左染色. 因为这个不是将包围面积染色,而是一定要染k^2个附近的cell.所以
对于每个cell按照这个算法一定要走遍k^2个cell.这样说对不 |
|
t*******e
发帖数: 274 | 35 up和down具体怎么处理？up node都往head前面放？down node都往tail后面放？ |
|
t******d
发帖数: 1383 | 36 我告诉你吧，巴基斯坦的同龄精英算是恨毒了自己国内那帮搞政治的，印度人往美国人
身上靠，结果劈材都能执掌谷歌，还个巴基斯坦人，不是一样的吹。本来都是没啥区别
的民族。结果自己爹往中国身上靠。你见过百度找巴铁当ceo的没？ |
|
b**w
发帖数: 78 | 37 这个能work吗？edge不一定是一直向外延伸的，可能先往里走然后再往外走。
1 |
|
s******4
发帖数: 24 | 38 Phone（烙印）
1. a lot questions about database sharding/partitioning
2. merge 2 linkedin list(lc 原题 已经问烂了)
onsite(4烙印＋1白人)
1. write producer/consumer for multi-threading environment(discussed
condition variable / synchronized), 建议看Java Condition API
2. find k-th largest element in unsorted array(lc 原题 已经问烂了)
3. 还有一个lc原题不记得了 也是很简单的
4. 在一个迷宫里，假设有一个机器人，怎么保证能走到出口。这个不画图比较难描述
。和一般bfs,dfs的区别就是，机器人只记得自己做过的决定（Left->Left->Straight
类似这样），没有整个图的概念。就想想一下自己在走迷宫好了。答案就是，一直往左
走，走到尽头就往回，没有左就往前走，没有前就往右走。然后会有一些followu... 阅读全帖 |
|
f*******r
发帖数: 976 | 39 祝LZ早日拿到大offer，eBay，PayPal等都是烙印的老巢，不去也罢
Phone（烙印）
1. a lot questions about database sharding/partitioning
2. merge 2 linkedin list(lc 原题 已经问烂了)
onsite(4烙印＋1白人)
1. write producer/consumer for multi-threading environment(discussed
condition variable / synchronized), 建议看Java Condition API
2. find k-th largest element in unsorted array(lc 原题 已经问烂了)
3. 还有一个lc原题不记得了 也是很简单的
4. 在一个迷宫里，假设有一个机器人，怎么保证能走到出口。这个不画图比较难描述
。和一般bfs,dfs的区别就是，机器人只记得自己做过的决定（Left->Left->Straight
类似这样），没有整个图的概念。就想想一下自己在走迷宫好了。答案就是，一直往左... 阅读全帖 |
|
M***6
发帖数: 895 | 40 先扫一遍找到array的max值，然后从左0往右扫到max算有多少雨水，然后再从右边
length －1往左到max，算有多少雨水。。算每个bin上有多少水用stack的思想，但是
不用需要stack。。
比如算左到右：
int pre = -1;
int i = 0;
while(i < maxIndex){
if(height[i] < pre){
sum += (pre - height[i]);
}
else{
pre = height[i];
}
i++;
} |
|
a********5
发帖数: 1631 | 41 fiber也不错啦。也很多人往那边转。
还有好多更烂的组呢，现在往外换组也没什么好选择。 |
|
r*****s
发帖数: 1815 | 42 视你简历 面试的级别和面试官当天心情而定
比如说现在看photo都流行无限往下滚啊 这无线往下滚就要load很多图片 哪些框架有
现成支持 要是自己实现有哪些方法 各有啥利弊。。。这个可能问一半面试官就满意了
也可能你全答完了还有一半没问。。
: 那请问这些点需要说的有多详细呢？还是说只是high level的说一下？会涉及到
用啥框
: 架去实现之类的么？或者让你自己说一下实现原理之类的
: 目
|
|
k**x
发帖数: 2611 | 43 原来是男ID。你那照片太萌了，让我觉得只有亲妈才挂这么萌
的娃照片啊。
如果你一定要在family room放娃的书，那可以做一半是开放的
书架，一半是有门的柜子么。上边是架子，放点好看的东西
下面是柜子，堆娃的书、玩具、乱七八糟的东西。这样好收拾。
弄几个收敛盒子，把娃扔在地上的玩具往盒子里一扔，把盒子往
柜子里一放，门一关，干干净净。 |
|
|
a*******p
发帖数: 1955 | 45 我家小宝好像刚出生就会吃手了，看似在肚子里就会了的。至于抓东西往嘴里放应该要
三个月后吧，不过每个孩子发育情况不同。 |
|
k*****a
发帖数: 7110 | 46 唔，偶就是来混包子的...
话说啊，有的时候超市\药店会有打折的牛奶，便宜到0.99/gal，看看很心动，在保质
期前喝不掉，即使如此也比买别的牛奶都便宜...那么，过期的牛奶怎么办呢？
叮叮叮铛~ 偶的答案是：洗脸~
以前和美国人一起住。室友很标准的美国人（偶印象中的“标准”），每天信誓旦旦要
做饭，不吃外面的垃圾食品，减肥，并且买回一堆菜蛋肉奶；每天到了吃饭的时候还是
拿出一个微波炉热一下就能吃的速冻食品（就是超市冰柜里的那些...）。于是那些菜
蛋肉奶就都过期了...
有一天看到她对着一加仑的牛奶嘀嘀咕咕，过去一聊，她说：牛奶都过期了，还没喝过
呢，好可惜，用来洗牛奶浴吧...
原来小时候格林童话里写的"小公主每天用牛奶洗脸，玫瑰泡澡"是真的啊...
偶的皮肤不好，严重过敏体质，什么铅笔啊，origin啊，通通过敏...泪奔...
但用牛奶洗脸倒不过敏，洗出来效果也不错的说~
过期的牛奶倒到洗脸盆里，倒点水（别倒开水哦，会结块的...毕竟是过期牛奶...），
然后洗啊洗，洗刷刷~
感觉洗完牛奶后，脸部皮肤非常光滑，忍不住摸自己的脸...- -b
牛奶洗脸可能的效果大概来自：
1.... 阅读全帖 |
|
J*C
发帖数: 4579 | 47 http://tw.news.yahoo.com/article/url/d/a/101025/8/2fm8d.html
蘇花公路失蹤的25人，至今持續搜尋，但創意旅行社整團連車帶人，21條寶貴性命，至
今依舊下落不明，根據當地漁民研判，一旦遊覽車不幸落海，車體將可能卡在海溝中，
但由於洋流方向往東北方走，以每小時1.5海浬計算，幾天下來，旅客的搜救範圍，將
必須得擴大到70多海浬以外的頭城外海，甚至更北邊的海域，只是幾天下來，當地漁民
幫忙搜尋，還是沒有著落。
經過幾天幾夜搜尋，儘管國軍精銳部隊出籠，但進度卻沒有想像中順利，失蹤人員下落
不明，包括整團出遊的創意旅行社21人，至今生死未卜。
幾乎是用盡各種方式，研判各種可能，海軍水下作業大隊，兩度在附近的可能海域搜救
，但水裡夾雜泥沙土石，幾乎沒有能見度，也沒有發現任何殘骸，當地漁民研判，前幾
天海象洶湧，遊覽車一旦落海，可能卡在海溝或沉入海底，旅客如果沒卡在車中，搜救
範圍將再擴大。
因為時間正值秋季，一旦遊覽車在蘇花公路112K到116K關鍵點落海，人員將可能被洋流
往東北方向漂流，以每小時1到1.5浬計算，至今超過70小時，恐怕... 阅读全帖 |
|
u**c
发帖数: 17972 | 48 和中国的农产品比起来，walawala的农作物算是天然无污染的。
http://money.163.com/13/0311/18/8PN3972K00252G50.html?from=news
一种新型污染正引起越来越多的关注。它产自养殖业，流到环境中，游离于各国现有污
染物排放清单之外，却给人类带来真实的威胁。
一个中美联合研究团队调查了三个年产肉猪1万头以上的大型养猪场，分别位于北京、福
建莆田和浙江嘉兴郊区。研究结果显示：国内一些养猪场药物滥用情况严重，以致养猪
场成为耐药细菌的选拔场。通过猪的粪便，这些耐药细菌流入外界环境，可能产生对人
类健康造成危害的具有多重耐药性的细菌。
耐药细菌，是那些发生基因突变后，从而进化出耐药性的细菌。大量、长期使用抗生素
，会加速细菌的耐药性。
这个研究团队以三个养猪场的猪粪便、粪便堆肥和养猪场附近使用堆肥的农田土壤为样
本，共检测到149种耐药基因，其中，有63种的浓度比原始森林的土壤检出量高出上百倍
，甚至有的高达近3万倍。这意味着，这些养猪场在抗生素的种类和数量上严重滥用。《
财经》记者的调查也显示，同样的问题在国内其他养殖业也普遍存在。由... 阅读全帖 |
|
e*f
发帖数: 1709 | 49 珍妮巴斯都旁敲侧击地提到大鲨鱼也可以走（为什么抠鼻要赖在这？）。 如果抠鼻还
能吸引门票那湖人还会考虑，可现在抠鼻正在往票房毒药发展，下一季球场无人看的场
面很可怕。 |
|
c*m
发帖数: 836 | 50 不说法律，只说常识，在一个劫匪看到你手里有枪，撒腿往外跑的时候，他是逃跑，还
是去拿枪甚至叫同伙，哪种可能大一些？现实生活中前者的可能远远大于后者吧？除非
他是杀人狂或者别人雇来杀专门杀你的或者跟你有仇，很难想象一个进门偷东西或者打
算实施强奸的劫匪会面对一杆shotgun还硬上。
当然反例是肯定有的，但是你面对陪审团的时候，陪审团考虑的是what a reasonable
person would think。有人说，I'd rather judged by 12 than carried by 6, 这在
歹徒对你攻击的时候，再对也没有了。哪怕最后因此坐牢或者破产，也完全值得，我
100%认同。
但是在歹徒已经转身跑掉的情况下，你不开枪，绝大多数情况下就此结束，你开枪，非
常非常大的可能就是判你二级谋杀或者manslaughter坐几年甚至十几年的牢，外加倾家
荡产的赔偿。而这一切的原因，只不过来自于一个你假象的可能性非常小的攻击。我觉
得不值得。枪的目的是为了最大限度保护自己，而不是为了打死别人。如果因为打死一
个很可能已经准备逃跑的人而坐牢加破产，那买枪只是害了自己而已。
如果... 阅读全帖 |
|
