b***e
发帖数: 1419 | 1 There is a street with 9 houses in a row, numbered from 1 to 9:
1 2 3 4 5 6 7 8 9
There is a burglar on the street. He always steals one of the 9 houses
each night. He is disciplined such that if he steals a house one night,
then the next night he will steal a house that is adjacent. In maths, if
he steals house i one night, then the next night he will steal either
house i-1 or house i+1. In particular, if he steals 1(9) one night, then
the next night he can only steal 2(8).
Now, you are the | a*****e
发帖数: 51 | 2 I doubt there is deterministic way if there is only one cop. To be
deterministic, you need at least (10-2)/2=4 cops.
【在 b***e 的大作中提到】
: There is a street with 9 houses in a row, numbered from 1 to 9:
: 1 2 3 4 5 6 7 8 9
: There is a burglar on the street. He always steals one of the 9 houses
: each night. He is disciplined such that if he steals a house one night,
: then the next night he will steal a house that is adjacent. In maths, if
: he steals house i one night, then the next night he will steal either
: house i-1 or house i+1. In particular, if he steals 1(9) one night, then
: the next night he can only steal 2(8).
: Now, you are the
| g*******y
发帖数: 1930 | 3 带boundary的随机行走问题？
感觉是个数学问题呢。。。
算出某个点第一次出现歹徒的期望时间最小，然后就去那个点蹲守?
【在 b***e 的大作中提到】
: There is a street with 9 houses in a row, numbered from 1 to 9:
: 1 2 3 4 5 6 7 8 9
: There is a burglar on the street. He always steals one of the 9 houses
: each night. He is disciplined such that if he steals a house one night,
: then the next night he will steal a house that is adjacent. In maths, if
: he steals house i one night, then the next night he will steal either
: house i-1 or house i+1. In particular, if he steals 1(9) one night, then
: the next night he can only steal 2(8).
: Now, you are the
| l*****k
发帖数: 1059 | 4 t: thief,
o: officer.
1 2 3 4 5 6 7 8 9
1 t o t t t t t t t
2 t o t t t t t t
3 t t o t t t t t
4 t t o t t t t
5 t t t o t t t
6 t t t o t t
7 t t t t o t
8 t t t o
9 t t t o
10 t t o
11 t t o
12 t o
13 t o
14 o | a*****e
发帖数: 51 | 5 well, please notice he mentioned 'deterministic way'...
【在 g*******y 的大作中提到】
: 带boundary的随机行走问题？
: 感觉是个数学问题呢。。。
: 算出某个点第一次出现歹徒的期望时间最小，然后就去那个点蹲守?
| H*M
发帖数: 1268 | 6 he can not stay at one fixed point because if the thief ossilate between two
houses he wont be catched.
【在 g*******y 的大作中提到】
: 带boundary的随机行走问题？
: 感觉是个数学问题呢。。。
: 算出某个点第一次出现歹徒的期望时间最小，然后就去那个点蹲守?
| a*****e
发帖数: 51 | 7 Nice solution...
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| g*******y
发帖数: 1930 | 8 我觉得应该就是在中点蹲着守候
考虑一个任意点i和中点j （i
假设起始位置在1...i 和 i'...n这两段
应该能证明，到达i和j的期望时间是相等的(利用期望的性质--如果x,y是随机变量，E(x+y)=E(x)+E(y))
对于i...j之间的起始位置，有一半的情况favor i，一半的情况favor j，又是平手
对于j...i'之间的位置，必然是先到达j
那么就说明中点优于其他任何点。
【在 b***e 的大作中提到】
: There is a street with 9 houses in a row, numbered from 1 to 9:
: 1 2 3 4 5 6 7 8 9
: There is a burglar on the street. He always steals one of the 9 houses
: each night. He is disciplined such that if he steals a house one night,
: then the next night he will steal a house that is adjacent. In maths, if
: he steals house i one night, then the next night he will steal either
: house i-1 or house i+1. In particular, if he steals 1(9) one night, then
: the next night he can only steal 2(8).
: Now, you are the
| g*******y
发帖数: 1930 | 9 是我没理解对题目？
警察一天只能check一个房间吧？没有说警察还能同时监视两个neighbor吧？
也就是说警察完全靠“撞运气”撞到贼，没法做任何逻辑推理，因为他对于贼的信息始
终不会增加直到他抓住贼
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| H*M
发帖数: 1268 | 10 this is the correct one..
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| | | H*M
发帖数: 1268 | 11 he said deterministic...
【在 g*******y 的大作中提到】
: 我觉得应该就是在中点蹲着守候
: 考虑一个任意点i和中点j （i: 假设起始位置在1...i 和 i'...n这两段
: 应该能证明，到达i和j的期望时间是相等的(利用期望的性质--如果x,y是随机变量，E(x+y)=E(x)+E(y))
: 对于i...j之间的起始位置，有一半的情况favor i，一半的情况favor j，又是平手
: 对于j...i'之间的位置，必然是先到达j
: 那么就说明中点优于其他任何点。
| a*****e
发帖数: 51 | 12 t means the possible houses that the thief can steal in i^th day
【在 g*******y 的大作中提到】
: 是我没理解对题目？
: 警察一天只能check一个房间吧？没有说警察还能同时监视两个neighbor吧？
: 也就是说警察完全靠“撞运气”撞到贼，没法做任何逻辑推理，因为他对于贼的信息始
: 终不会增加直到他抓住贼
| g*******y
发帖数: 1930 | 13 嗯，理解了，很好的方法，鼓掌~
惭愧，我一上来看着随机行走就往随机那里想了。。。
【在 a*****e 的大作中提到】
: t means the possible houses that the thief can steal in i^th day
| c*********n
发帖数: 1057 | 14 如果面试让我做，我肯定找不到这个解法的。。。真厉害
这种算什么题目呢？
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| a****l
发帖数: 245 | 15 很强！
出题的牛，解题的也牛！
签名档也很有意思，谁想出来的
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| l*****k
发帖数: 1059 | 16 解这类题有个技巧：先简化，找除解法，再推广到更general的情况。
比如这道题，如果只有3个房子很trivial， 4个就麻烦点。 能做出5
个房子基本上就能找到9个解法了。
【在 c*********n 的大作中提到】
: 如果面试让我做，我肯定找不到这个解法的。。。真厉害
: 这种算什么题目呢？
| c*********n
发帖数: 1057 | 17 恩，好方法！这类题目在面software development的职位的时候出现的多么？
【在 l*****k 的大作中提到】
: 解这类题有个技巧：先简化，找除解法，再推广到更general的情况。
: 比如这道题，如果只有3个房子很trivial， 4个就麻烦点。 能做出5
: 个房子基本上就能找到9个解法了。
| b***e
发帖数: 1419 | 18 I like your approach. But brute-force.
In fact this one is VERY simple. It's a parity checking problem. If
the burglar is at odd(even) one night, then the next night he's at
even(odd).
So you assume he's at even at the beginning and traverse the street one
pass starting from a even position. If you catch him, then done.
Otherwise, he was at odd in the beginning, and you can traverse the
street once more to catch him. Just like what you show in your diagram.
The invariant is that at each
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| b***e
发帖数: 1419 | 19 Here's the problem: when I enter the room, I decide whether I like the
person. If I do, I ask him/her to write a function that computes x^n
(which is quite non-trivial in fact). If I don't, I ask him/her this
question. If I get a good answer, then he/she deserves my respect and my
recommendation regardless.
【在 c*********n 的大作中提到】
: 恩，好方法！这类题目在面software development的职位的时候出现的多么？
| H*M
发帖数: 1268 | 20 在你不喜欢的人当中,大概有多少人当场做出来的啊(以前没看过的,觉得你应该能感觉到
那个人以前做过没有)?
【在 b***e 的大作中提到】
: Here's the problem: when I enter the room, I decide whether I like the
: person. If I do, I ask him/her to write a function that computes x^n
: (which is quite non-trivial in fact). If I don't, I ask him/her this
: question. If I get a good answer, then he/she deserves my respect and my
: recommendation regardless.
| | | m*****f
发帖数: 1243 | 21 能详细说说 x^n么? x, n都是给的parameter? 主要考边界条件?
【在 b***e 的大作中提到】
: Here's the problem: when I enter the room, I decide whether I like the
: person. If I do, I ask him/her to write a function that computes x^n
: (which is quite non-trivial in fact). If I don't, I ask him/her this
: question. If I get a good answer, then he/she deserves my respect and my
: recommendation regardless.
| c*********n
发帖数: 1057 | 22
~~~~~~~~~~~~~~~~~~~~~how do you decide it? Sounds interesting
【在 b***e 的大作中提到】
: Here's the problem: when I enter the room, I decide whether I like the
: person. If I do, I ask him/her to write a function that computes x^n
: (which is quite non-trivial in fact). If I don't, I ask him/her this
: question. If I get a good answer, then he/she deserves my respect and my
: recommendation regardless.
| H*M
发帖数: 1268 | 23 主要看长得好看不好看
-blaze
【在 c*********n 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~how do you decide it? Sounds interesting
| b***e
发帖数: 1419 | 24 No, nothing tricky or fancy. Just computer x^n without considering border
cases, or overflow. Both x and n are integers. Just that.
【在 m*****f 的大作中提到】
: 能详细说说 x^n么? x, n都是给的parameter? 主要考边界条件?
| H*M
发帖数: 1268 | 25 大概唯一需要点注意的就是分奇偶吧
【在 b***e 的大作中提到】
: No, nothing tricky or fancy. Just computer x^n without considering border
: cases, or overflow. Both x and n are integers. Just that.
| b***e
发帖数: 1419 | 26 Yea, you bet.
Say, I like mudhoof('s avatar) and dislike yours. Man, I like you, but I
cannot appreciate your taste in the choice of avatar.
【在 H*M 的大作中提到】
: 主要看长得好看不好看
: -blaze
| g*******y
发帖数: 1930 | 27 y=1;
while(n){
if(n&1) y*=x;
x*=x;
n/=2;
}
【在 b***e 的大作中提到】
: No, nothing tricky or fancy. Just computer x^n without considering border
: cases, or overflow. Both x and n are integers. Just that.
| H*M
发帖数: 1268 | 28 靠,还让不让人活了
【在 b***e 的大作中提到】
: Yea, you bet.
: Say, I like mudhoof('s avatar) and dislike yours. Man, I like you, but I
: cannot appreciate your taste in the choice of avatar.
| b***e
发帖数: 1419 | 29 See, here's the problem: there's an hours or so. If you spend the first 5
min to give this, then I start to think: what a smart-ass, let's go to the
next (you know what). hahahahaha...
【在 g*******y 的大作中提到】
: y=1;
: while(n){
: if(n&1) y*=x;
: x*=x;
: n/=2;
: }
| g*******y
发帖数: 1930 | 30 面试中题目做的快是不是能加分啊？
做太快了你会不会怀疑我是做过的呢？事实上这个算power的题我确实以前写过的。
【在 b***e 的大作中提到】
: See, here's the problem: there's an hours or so. If you spend the first 5
: min to give this, then I start to think: what a smart-ass, let's go to the
: next (you know what). hahahahaha...
| | | H*M
发帖数: 1268 | 31 我觉得你面试时候说你做过没啥吧,尤其是这么常见的
如果做过,知道怎么做,又要装的没做过,才怪异,别人也能看出来.
【在 g*******y 的大作中提到】
: 面试中题目做的快是不是能加分啊？
: 做太快了你会不会怀疑我是做过的呢？事实上这个算power的题我确实以前写过的。
| m*****f
发帖数: 1243 | 32 hmm...这个程序是不是没写完整？或者有笔误
哦， 是我看错了
【在 g*******y 的大作中提到】
: y=1;
: while(n){
: if(n&1) y*=x;
: x*=x;
: n/=2;
: }
| b***e
发帖数: 1419 | 33 你要是给这个答案, 不管你做的快慢我都认定你以前做过, 而且是抄标准答案. Only
extreme
hardcore c programmer whose exceptionally good in algorithm can give that
answer within reasonably amount of time. In 99.9~% cases, I can tell you
are not by your resume.
【在 g*******y 的大作中提到】
: 面试中题目做的快是不是能加分啊？
: 做太快了你会不会怀疑我是做过的呢？事实上这个算power的题我确实以前写过的。
| b***e
发帖数: 1419 | 34 You are cool. New look.
【在 H*M 的大作中提到】
: 我觉得你面试时候说你做过没啥吧,尤其是这么常见的
: 如果做过,知道怎么做,又要装的没做过,才怪异,别人也能看出来.
| m*****f
发帖数: 1243 | 35 知道怎么做装的没做过, 被看出来那是还要多练....
【在 H*M 的大作中提到】
: 我觉得你面试时候说你做过没啥吧,尤其是这么常见的
: 如果做过,知道怎么做,又要装的没做过,才怪异,别人也能看出来.
| H*M
发帖数: 1268 | 36 不知道了,我觉得我装不来.
所有我做过的题目我都会说做过.我觉得一些比较难的题目,随口说出怎么做,怎么可能,
爱因斯坦能不能做到都不知道.
再说了,像Longest increasing subsequence这种经典题,算法作业都会有,说做过又怎么
了
【在 m*****f 的大作中提到】
: 知道怎么做装的没做过, 被看出来那是还要多练....
| g*******y
发帖数: 1930 | 37 呵呵，一下子直接写出来肯定显然是做过的~
不过如果没做过的话，要做出这个答案来应该也不难
如果我不知道这个答案的话，我会首先给个logN的recursive的解法，在此基础上再改
为non-recursive的(当然，这需要面试官来push我，呵呵)
【在 b***e 的大作中提到】
: 你要是给这个答案, 不管你做的快慢我都认定你以前做过, 而且是抄标准答案. Only
: extreme
: hardcore c programmer whose exceptionally good in algorithm can give that
: answer within reasonably amount of time. In 99.9~% cases, I can tell you
: are not by your resume.
| m*****f
发帖数: 1243 | 38 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
也很容易考到
能,
怎么
【在 H*M 的大作中提到】
: 不知道了,我觉得我装不来.
: 所有我做过的题目我都会说做过.我觉得一些比较难的题目,随口说出怎么做,怎么可能,
: 爱因斯坦能不能做到都不知道.
: 再说了,像Longest increasing subsequence这种经典题,算法作业都会有,说做过又怎么
: 了
| g*******y
发帖数: 1930 | 39 现在面试题都水涨船高到考DP优化技术的地步了啊？
我前阵子学DP优化的时候漫不经心的，总觉得这个东西面试不会涉及到，最多起点锦上
添花impress考官的作用。。。
看样子得回去重新学学了。。。
【在 m*****f 的大作中提到】
: 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
: 也很容易考到
:
: 能,
: 怎么
| H*M
发帖数: 1268 | 40 经典题变化的,当然不算做过的.
【在 m*****f 的大作中提到】
: 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
: 也很容易考到
:
: 能,
: 怎么
| | | f*********r
发帖数: 68 | 41 请教一下LCS怎么做到O(nlogn), 很容易么?
【在 m*****f 的大作中提到】
: 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
: 也很容易考到
:
: 能,
: 怎么
| m*****f
发帖数: 1243 | 42 hint 就是 "比如LIS现在是O(nlogn)了", 把LCS转换成LIS就可以了
【在 f*********r 的大作中提到】
: 请教一下LCS怎么做到O(nlogn), 很容易么?
| g*******y
发帖数: 1930 | 43 要有额外的条件的吧，比如1...n的两个permutation找LCS
【在 f*********r 的大作中提到】
: 请教一下LCS怎么做到O(nlogn), 很容易么?
| f*********r
发帖数: 68 | 44 我不觉的LCS可以很容易的转换成LIS问题.
能说说你是怎么转化的么?
【在 m*****f 的大作中提到】
: hint 就是 "比如LIS现在是O(nlogn)了", 把LCS转换成LIS就可以了
| f*********r
发帖数: 68 | 45 这个也太special了吧, 不过好像也不容易把LCS转换成LIS
【在 g*******y 的大作中提到】
: 要有额外的条件的吧，比如1...n的两个permutation找LCS
| m*****f
发帖数: 1243 | 46 LCS转换成LIS：
假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
为一个数组, 求此序列LIS (O(nlogn))
比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
组成序列{7,3,4,2,1,7,3,6,7,3}
LIS 为 1 3 6 7, 即 b a x a
【在 f*********r 的大作中提到】
: 我不觉的LCS可以很容易的转换成LIS问题.
: 能说说你是怎么转化的么?
| g*******y
发帖数: 1930 | 47 还是不错的，不过:
如果每个字母出现的次数是O(n)呢
那么你的数字序列长度就是O(n^2)级别了，呵呵
【在 m*****f 的大作中提到】
: LCS转换成LIS：
: 假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
: 为一个数组, 求此序列LIS (O(nlogn))
: 比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
: a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
: 组成序列{7,3,4,2,1,7,3,6,7,3}
: LIS 为 1 3 6 7, 即 b a x a
| H*M
发帖数: 1268 | 48 DP优化的材料哪本书上有啊？
谢了。
【在 g*******y 的大作中提到】
: 现在面试题都水涨船高到考DP优化技术的地步了啊？
: 我前阵子学DP优化的时候漫不经心的，总觉得这个东西面试不会涉及到，最多起点锦上
: 添花impress考官的作用。。。
: 看样子得回去重新学学了。。。
| H*M
发帖数: 1268 | 49 CLRS上面DP只有一章，例子也比较常见
【在 H*M 的大作中提到】
: DP优化的材料哪本书上有啊？
: 谢了。
| m*****f
发帖数: 1243 | 50 我只知道topcoder上DP的题目非常多
【在 H*M 的大作中提到】
: CLRS上面DP只有一章，例子也比较常见
| | | m*****f
发帖数: 1243 | 51 你是说A中每个字母在B中出现次数都是O(n)? 那B本身是不是也是O(n^2)级别了？
我想不太清楚， 能举个例子么?
说LCS = O(n^2) 实际上默认了A, B等长， 否则应该是O(n*m), 就假设A,B等长把， 呵呵
【在 g*******y 的大作中提到】
: 还是不错的，不过:
: 如果每个字母出现的次数是O(n)呢
: 那么你的数字序列长度就是O(n^2)级别了，呵呵
| f*********r
发帖数: 68 | 52 这样做在某些情况下复杂度岂不成了O(n^2logn)?
【在 m*****f 的大作中提到】
: LCS转换成LIS：
: 假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
: 为一个数组, 求此序列LIS (O(nlogn))
: 比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
: a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
: 组成序列{7,3,4,2,1,7,3,6,7,3}
: LIS 为 1 3 6 7, 即 b a x a
| m*****f
发帖数: 1243 | 53 哪种情况?
【在 f*********r 的大作中提到】
: 这样做在某些情况下复杂度岂不成了O(n^2logn)?
| g*******y
发帖数: 1930 | 54 abbbaaaababbaba bababbbaaaabab
我乱输的两串，呵呵
【在 m*****f 的大作中提到】
: 哪种情况?
| m*****f
发帖数: 1243 | 55 恩， 看来前提条件是任何字符没有频繁出现到O(n)的程度
【在 g*******y 的大作中提到】
: abbbaaaababbaba bababbbaaaabab
: 我乱输的两串，呵呵
| c*******d
发帖数: 255 | 56 高！
【在 l*****k 的大作中提到】
: t: thief,
: o: officer.
: 1 2 3 4 5 6 7 8 9
: 1 t o t t t t t t t
: 2 t o t t t t t t
: 3 t t o t t t t t
: 4 t t o t t t t
: 5 t t t o t t t
: 6 t t t o t t
: 7 t t t t o t
| k***e
发帖数: 556 | 57 难道准备太充分也是错？
做得快，是背题目不是真实水平的体现
做的慢，编程不熟练，水平差，没的说
真理永远在面试官的手里
what do you want from us?
【在 b***e 的大作中提到】
: 你要是给这个答案, 不管你做的快慢我都认定你以前做过, 而且是抄标准答案. Only
: extreme
: hardcore c programmer whose exceptionally good in algorithm can give that
: answer within reasonably amount of time. In 99.9~% cases, I can tell you
: are not by your resume.
| b***e
发帖数: 1419 | 58 Well, I am not speaking for myself only, but indicating a general case in
the interviewing process: don't answer TOO fact. 欲速则不达.
As a matter of fact, I believe people on this board, at least the several
active IDs are VERY GOOD. If they are sent to me, I will certainly
recommend everyone of them strongly.
【在 k***e 的大作中提到】
: 难道准备太充分也是错？
: 做得快，是背题目不是真实水平的体现
: 做的慢，编程不熟练，水平差，没的说
: 真理永远在面试官的手里
: what do you want from us?
|
|
