g*******y
发帖数: 1930 | 1 Dec 05
最近又看到了几道很好的题：
1. 我们知道，从一个数组里找一段(连续的)子数组求最大和，是一道经典的面试题，
方法很简单，只要O(n)的时间。把这个问题变一下，假设是一个循环数组呢？找一个
size<=n的子数组with最大和。
分析，很容易想到第一步，找个地方把循环数组切断，回到了原来的问题，然后在考虑
一下额外的情况。额外的情况就是：有可能最大和的子数组是跨越了切断点的？这种情
况的最大和怎么求呢？一个naive的方法能做到O(n)，但是需要O(n)的空间。巧妙的解
法就是，注意到所有数的和是固定的，考虑切断后的非循环数组，找一段从首开始+一
段从尾开始的两个子数组with最大和，等价于找一段子数组with min sum.
总结，要擅长利用等价性转换问题，从而将新的问题转变为一个已知有好solution的旧
问题。利用已知的经典问题来解决新问题，可以说是面试题目中相当重要的一个技巧
2. largest rectangular problem：问题是这样的，一个N×M的棋盘，上面的数字要么
是1，要么是0，那么要：a）最大的一个正方形全是1填充，b）最大的全是1的矩 |
a*u
发帖数: 2334 | 2 你拿到GOOG的OFFER了没有? 恭喜先
【在 g*******y 的大作中提到】
: Dec 05
: 最近又看到了几道很好的题：
: 1. 我们知道，从一个数组里找一段(连续的)子数组求最大和，是一道经典的面试题，
: 方法很简单，只要O(n)的时间。把这个问题变一下，假设是一个循环数组呢？找一个
: size<=n的子数组with最大和。
: 分析，很容易想到第一步，找个地方把循环数组切断，回到了原来的问题，然后在考虑
: 一下额外的情况。额外的情况就是：有可能最大和的子数组是跨越了切断点的？这种情
: 况的最大和怎么求呢？一个naive的方法能做到O(n)，但是需要O(n)的空间。巧妙的解
: 法就是，注意到所有数的和是固定的，考虑切断后的非循环数组，找一段从首开始+一
: 段从尾开始的两个子数组with最大和，等价于找一段子数组with min sum.
|
g*****u
发帖数: 298 | 3 直方图那个题我一直没弄明白，这求最大矩形到底是什么意思？如果要求不相交，那就
画一个矩形把所有的bar圈进去就好了啊。谁能解释一下？
wild card 匹配那个题怎么解？ |
w******1
发帖数: 520 | 4 有n个房间，小偷每天
偷一间，偷的规律简单说就是随机行走，如果今天偷了第i间屋子，明天有一半的几率
偷i-1，一半的几率偷i+1，注意如果刚好偷到了边界上，那么第二天只有唯一的选择。
如果你是警察，你只能每天选择一个房间蹲守，并且贼的手段相当高明，偷了一个房间
后，没有任何人能发觉该房间是否曾经被偷过。
这个题目有意思， 怎么解决的呢？
并且贼的手段相当高明，偷了一个房间
后，没有任何人能发觉该房间是否曾经被偷过。
这个警察就没法确定去哪里了。
但是，可以知道， 如果今天偷的是奇数，明天就是偶数个。 |
s*********t
发帖数: 1663 | 5 奇偶性有啥用？
又不能知道哪个房间被偷了
我只能想到在两边蹲着。。。
【在 w******1 的大作中提到】
: 有n个房间，小偷每天
: 偷一间，偷的规律简单说就是随机行走，如果今天偷了第i间屋子，明天有一半的几率
: 偷i-1，一半的几率偷i+1，注意如果刚好偷到了边界上，那么第二天只有唯一的选择。
: 如果你是警察，你只能每天选择一个房间蹲守，并且贼的手段相当高明，偷了一个房间
: 后，没有任何人能发觉该房间是否曾经被偷过。
: 这个题目有意思， 怎么解决的呢？
: 并且贼的手段相当高明，偷了一个房间
: 后，没有任何人能发觉该房间是否曾经被偷过。
: 这个警察就没法确定去哪里了。
: 但是，可以知道， 如果今天偷的是奇数，明天就是偶数个。
|
w******1
发帖数: 520 | 6 如果N 是很大的数， 那警察叔叔还不等得白了头？？
【在 s*********t 的大作中提到】
: 奇偶性有啥用？
: 又不能知道哪个房间被偷了
: 我只能想到在两边蹲着。。。
|
s*********t
发帖数: 1663 | 7 那应该咋办？
【在 w******1 的大作中提到】
: 如果N 是很大的数， 那警察叔叔还不等得白了头？？
|
c*********s
发帖数: 92 | |
p********7
发帖数: 549 | 9 我觉得小偷那个问题，最好是在最靠边的2个点的旁边点蹲着。比如有9个房间
1，2，3，4，5，6，7，8，9
小偷从任意个房间开始的概率是一样的1／9，那么如果是在2蹲着，有1／9的概率小偷
是从1开始，那么第二天就等到了；如果是从2开始，那第一天就等到了；如果是从三开
始，第二天等到的概率也有1／2；如果是从.... 后面的概率就小了。那么前2天等到的
概率是1／9＋1／9＋1／18＝5／18。
如果是在第3个房间等，那么前2天等到的概率是1／9＋1／18+1/18 = 4/18。
所以在倒数第2个和正数第二个是概率最大的。 |
p********7
发帖数: 549 | 10 从4间房开始推算。
D2检查(2)，如果没有发现小偷，可知小偷在(1)(3)/(4)；
D3检查(3)，如果没有发现小偷，可知小偷在(2)/(4)；
D4检查(3)，如果没有发现小偷，可知小偷在(1)；
D5检查(2)，发现小偷。
足迹是2 3 3 2
如果是5间房
D1检查(2)，如果没有发现小偷，可知小偷在(1)/(3)/(4)/(5)
D2检查(3)，如果没有发现小偷，可知小偷在(2)/(4)/(5)
D3检查(4)，如果没有发现小偷，可知小偷在(1)/(3)/(5)
D4检查(4)，如果没有发现小偷，可知小偷在(2)/
D5检查(3)，如果没有发现小偷，可知小偷在(1)/
D6检查(2)，发现小偷。
足迹是2 3 4 4 3 2 |
|
|
A***e
发帖数: 130 | 11 Generally speaking, you start from (1) on day 1, and go toward (n). If the
thief was also on an odd room on day 1, then you won't miss him and
eventually catch him before you reach (n).
Otherwise, if he was in an even room on day 1, then after you have reached (
n) (at this moment you know for sure he started on an even room, if you have
not caught him), then you adjust your tempo, i.e., stay at (n) for one more
day and check (n) on day n+1 as well. Then you go backward toward (1) and
this time
【在 p********7 的大作中提到】
: 从4间房开始推算。
: D2检查(2)，如果没有发现小偷，可知小偷在(1)(3)/(4)；
: D3检查(3)，如果没有发现小偷，可知小偷在(2)/(4)；
: D4检查(3)，如果没有发现小偷，可知小偷在(1)；
: D5检查(2)，发现小偷。
: 足迹是2 3 3 2
: 如果是5间房
: D1检查(2)，如果没有发现小偷，可知小偷在(1)/(3)/(4)/(5)
: D2检查(3)，如果没有发现小偷，可知小偷在(2)/(4)/(5)
: D3检查(4)，如果没有发现小偷，可知小偷在(1)/(3)/(5)
|
i*******g
发帖数: 100 | 12 会重复偷？
5个房间要守6天，更大的可能是小偷已经偷完了走了 |
l*********0
发帖数: 44 | 13 请哪位大侠解释清楚第一题，如何formulate？ 万分感谢先，想半天没明白。
【在 g*******y 的大作中提到】
: Dec 05
: 最近又看到了几道很好的题：
: 1. 我们知道，从一个数组里找一段(连续的)子数组求最大和，是一道经典的面试题，
: 方法很简单，只要O(n)的时间。把这个问题变一下，假设是一个循环数组呢？找一个
: size<=n的子数组with最大和。
: 分析，很容易想到第一步，找个地方把循环数组切断，回到了原来的问题，然后在考虑
: 一下额外的情况。额外的情况就是：有可能最大和的子数组是跨越了切断点的？这种情
: 况的最大和怎么求呢？一个naive的方法能做到O(n)，但是需要O(n)的空间。巧妙的解
: 法就是，注意到所有数的和是固定的，考虑切断后的非循环数组，找一段从首开始+一
: 段从尾开始的两个子数组with最大和，等价于找一段子数组with min sum.
|
b***6
发帖数: 6011 | 14 请问 第三题 是什么意思 没看懂题目 能不能麻烦讲清楚点 谢谢 |
F**********r
发帖数: 237 | |
i**c
发帖数: 26 | 16 就是对每个row做max rectangle in histogram
O(N^2) |
z*******y
发帖数: 578 | 17 大侠 你blog的地址是什么？ 我要过去瞻仰一下 呵呵
你这次说的这几个题目都是我准备面试的时候头疼略过去的，呵呵
面试时候运气好 没有被问到这些
现在学习补上去 哈哈 |
z*******y
发帖数: 578 | 18 大侠 你blog的地址是什么？ 我要过去瞻仰一下 呵呵
你这次说的这几个题目都是我准备面试的时候头疼略过去的，呵呵
面试时候运气好 没有被问到这些
现在学习补上去 哈哈 |
l********y
发帖数: 1327 | |
s*******d
发帖数: 4135 | 20 谁能给个第4题的思路？想了几个办法，都不是很efficient |
