5O点pampers code - 未名空间MITBBS历史存档

B*n2010-10-01 07:10

1 楼

悲剧了，贴出来攒点人品
顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
一跳。
1. switch的工作原理流程。
2. 估计挂在这里了。
1）. 生死棋盘游戏。
我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
法吗？
2）. 生成迷宫，基本上不怎么会。
我先说随机生成0/1。但可能会出现迷宫不可解的情况，然后我就差不多挂了。
求更好方法。
3. 从文件中读入记录，然后生成树，计算pathsum，
文件记录格式，node, parent, weight.
然后讨论一些特殊的情况。
4. LRU实现，我其中用的了map，顺便写一个hash table实现map。
我其中有一行出现了bug，删除的时候忘记更新map了。
5. 实现memcpy，这个比较没头绪，不知道要考啥，先写一个最简单的
大概是 *dst = *src，之类的，然后问怎么优化让他更快点，
因为刚开始用的是 char 的指针，我说把指针变成 uint_32t 会更快点，当然也可以
uint_64t了，
有什么别的建议吗？

l*a2010-10-01 07:10

2 楼

不知道贴过没有，刚收到的
JOINNOW4REWARDS

e*22010-10-01 07:10

3 楼

都是非常规题啊，觉得你答得不错，可能是长的不怎么样的缘故。

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

M*o2010-10-01 07:10

4 楼

cong! pai! ngs!

s*k2010-10-01 07:10

5 楼

生成迷宫不常见吧

【在 e********2 的大作中提到】

: 都是非常规题啊，觉得你答得不错，可能是长的不怎么样的缘故。

q*y2010-10-01 07:10

6 楼

thank you!

m*g2010-10-01 07:10

7 楼

谢谢楼主！
这些题目确实很考验水平的，楼主应该是有不少工作经验的。因为他家申请的人太多
，可能只要很出彩或者很match的

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

m*a2010-10-01 07:10

8 楼

cool, thanks!

f*s2010-10-01 07:10

9 楼

memcpy 不解决地址overlap的情况， memmove才会考虑
生成迷宫，好像design pattern里面有例子，不过挺复杂的。。。

q*02010-10-01 07:10

10 楼

thanks

k*o2010-10-01 07:10

11 楼

mark

z*q2010-10-01 07:10

12 楼

thx

【在 l********a 的大作中提到】

: 不知道贴过没有，刚收到的
: JOINNOW4REWARDS

x*92010-10-01 07:10

13 楼

这个迷宫太非主流了。
记得是union-find，从来没实现过.....

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

a*y2010-10-01 07:10

14 楼

可以用，谢谢了！！

c*r2010-10-01 07:10

15 楼

mark

m*r2010-10-01 07:10

16 楼

thank you!

E*g2010-10-01 07:10

17 楼

请问楼主是fresh graduate, 还是有若干年工作经验呢？题目感觉好难啊！

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

D*92010-10-01 07:10

18 楼

nice

r*c2010-10-01 07:10

19 楼

生成迷宫对迷宫有要求吗？如果没有的话就先找一个path，随机取往右往下，path好了
以后在开始在path上得点随机加点

M*62010-10-01 07:10

20 楼

thanks

s*t2010-10-01 07:10

21 楼

请问生死棋盘是什么？

L*n2010-10-01 07:10

22 楼

thanks

【在 l********a 的大作中提到】

: 不知道贴过没有，刚收到的
: JOINNOW4REWARDS

A*c2010-10-01 07:10

23 楼

据我观察，G 家的题目variance 太大了。碰上不同的人，出的题目真是天上地下。
lz的题都是高级题。Bless！

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

d*72010-10-01 07:10

24 楼

thanks!

d*n2010-10-01 07:10

25 楼

int[] arr=new int[10];
memcpy(arr,arr+2,5);
这个怎么解？

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

x*g2010-10-01 07:10

26 楼

3x

l*u2010-10-01 07:10

27 楼

神马是生死棋盘。。。

e*b2010-10-01 07:10

28 楼

Thanks!

k*u2010-10-01 07:10

29 楼

生成迷宫这个看起来挺有意思，想到一个简单思路：
假设enter在左下角，exit在右上角。
从enter的点开始，看看四周有哪些点可以到达，然后随机生成下一步，比如当前正在
起点处，那么只有往上走和往右走两种选择，就跑一个2种结果的random generator。
后面每一步都做同样的随机选择，当然这个过程中要记录哪些已经走过了。
另外如果我们碰到了第一行的元素，那么我们只能往右或者往下（否则无解）
同样的，如果我们碰到了最后一列，我们只能往上或者往左（否则无解）
当我们到达exit之后，这条路径就是迷宫的解。然后我们给所有的其他方块随机生成0/
1。

s*s2010-10-01 07:10

30 楼

thanks

w*s2010-10-01 07:10

31 楼

memcpy那题，
简单来说就是，一句汇编实现的。
REP MOVS DWORD PTR ES:[EDI],DWORD PTR DS:[ESI]
你可以问一下那个面试的，还有啥更快的么？

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

c*i2010-10-01 07:10

32 楼

Thanks!

r*b2010-10-01 07:10

33 楼

Will this cause any array out of boundary problem, if the array size cannot
be divided by sizeof(DWORD)?

【在 w********s 的大作中提到】

: memcpy那题，
: 简单来说就是，一句汇编实现的。
: REP MOVS DWORD PTR ES:[EDI],DWORD PTR DS:[ESI]
: 你可以问一下那个面试的，还有啥更快的么？

k*y2010-10-01 07:10

34 楼

太好用了，呵呵谢谢

r*b2010-10-01 07:10

35 楼

Here are some links on Maze generation:
http://www.4ngel.net/article/17.htm

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

h*i2010-10-01 07:10

36 楼

太感谢了！

w*s2010-10-01 07:10

37 楼

switch基本上就是
CMP XXX, VALUE
JUMP XXXXXX
举个例子，
void dummy(int s)
{
switch (s)
{
case 0:
std::cout << "this is 0.";
break;
case 1:
std::cout << "this is 1.";
break;
default:
std::cout << "default.";
break;
}
}
步骤：
parameter s(SS:[EBP+8]) -> EAX
move EAX to the stack
compare the value (s, which is in SS:[EBP-0F4] to switch values 0)
jump if equal (the code for handling case 0)
compare the value to 1
jump if equal
if there is no jump, then the default code executed.
00BC1B85 8B45 08 MOV EAX,DWORD PTR SS:[EBP+8]
00BC1B88 8985 0CFFFFFF MOV DWORD PTR SS:[EBP-0F4],EAX
00BC1B8E 83BD 0CFFFFFF 0 CMP DWORD PTR SS:[EBP-0F4],0
00BC1B95 74 0B JE SHORT 00BC1BA2
00BC1B97 83BD 0CFFFFFF 0 CMP DWORD PTR SS:[EBP-0F4],1
00BC1B9E 74 17 JE SHORT 00BC1BB7
00BC1BA0 EB 2A JMP SHORT 00BC1BCC
00BC1BA2 68 4C78BC00 PUSH OFFSET 00BC784C
; ASCII "this is 0."
00BC1BA7 A1 04A3BC00 MOV EAX,DWORD PTR DS:[0BCA304]
00BC1BAC 50 PUSH EAX
00BC1BAD E8 A2F5FFFF CALL 00BC1154
00BC1BB2 83C4 08 ADD ESP,8
00BC1BB5 EB 28 JMP SHORT 00BC1BDF
00BC1BB7 68 3C78BC00 PUSH OFFSET 00BC783C
; ASCII "this is 1."
00BC1BBC A1 04A3BC00 MOV EAX,DWORD PTR DS:[0BCA304]
00BC1BC1 50 PUSH EAX
00BC1BC2 E8 8DF5FFFF CALL 00BC1154
00BC1BC7 83C4 08 ADD ESP,8
00BC1BCA EB 13 JMP SHORT 00BC1BDF
00BC1BCC 68 3078BC00 PUSH OFFSET 00BC7830
; ASCII "default."
00BC1BD1 A1 04A3BC00 MOV EAX,DWORD PTR DS:[0BCA304]
00BC1BD6 50 PUSH EAX
00BC1BD7 E8 78F5FFFF CALL 00BC1154

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

m*y2010-10-01 07:10

38 楼

thanks

s*c2010-10-01 07:10

39 楼

楼主的题都很难阿。
第3题里：
文件记录格式，node, parent, weight.
那个node是什么？是树的每个节点都有一个id号吗？ "parent"就是父节点的id号？那
么如何区分左右孩子？还是说已知是一个排好序的树？

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。

q*62010-10-01 07:10

40 楼

thanks!

w*s2010-10-01 07:10

41 楼

shr bytesToMove, 2
rep movs dword ptr xxx, xxx
对于剩余的byes，继续copy，用的办法差不多是
1004CB15 8D49 00 LEA ECX,[ECX]
1004CB18 8A06 MOV AL,BYTE PTR DS:[ESI]
1004CB1A 8807 MOV BYTE PTR DS:[EDI],AL
1004CB1C 8A46 01 MOV AL,BYTE PTR DS:[ESI+1]
1004CB1F 8847 01 MOV BYTE PTR DS:[EDI+1],AL
1004CB22 8A46 02 MOV AL,BYTE PTR DS:[ESI+2]
1004CB25 8847 02 MOV BYTE PTR DS:[EDI+2],AL
1004CB28 8B45 08 MOV EAX,DWORD PTR SS:[EBP+8]
1004CB2B 5E POP ESI

cannot

【在 r*****b 的大作中提到】

: Will this cause any array out of boundary problem, if the array size cannot
: be divided by sizeof(DWORD)?

i*y2010-10-01 07:10

42 楼

thanks

【在 l********a 的大作中提到】

: 不知道贴过没有，刚收到的
: JOINNOW4REWARDS

w*s2010-10-01 07:10

43 楼

扫1遍的时候生成所有node，可以记录到某个map里
扫第二遍的时候生成边。
parent=null的那个是root。

【在 s***c 的大作中提到】

: 楼主的题都很难阿。
: 第3题里：
: 文件记录格式，node, parent, weight.
: 那个node是什么？是树的每个节点都有一个id号吗？ "parent"就是父节点的id号？那
: 么如何区分左右孩子？还是说已知是一个排好序的树？

e*h2010-10-01 07:10

44 楼

thanks

k*u2010-10-01 07:10

45 楼

酷！和我刚刚想的方法基本思路是一样的。

【在 r*****b 的大作中提到】

: Here are some links on Maze generation:
: http://www.4ngel.net/article/17.htm

l*s2010-10-01 07:10

46 楼

thanks

q*x2010-10-01 07:10

47 楼

啥是生死棋盘？
memcpy不是很经典吗？

【在 B***n 的大作中提到】

: 悲剧了，贴出来攒点人品
: 顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
: leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
: 一跳。
: 1. switch的工作原理流程。
: 2. 估计挂在这里了。
: 1）. 生死棋盘游戏。
: 我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
: 法吗？
: 2）. 生成迷宫，基本上不怎么会。