既然大家对Programing感兴趣,给大家做一个。不过,哪位想Progrom也可以。
Any language is ok.
(An interview question)
Given a single linked list with n items.
Find an O(n) algorithm to detect any loops.
• 这题很经典 -endofsuburbia- ♂ (32 bytes) () 05/15/2009 postreply 09:26:24
• 2X追就可了。。。 -haha2000- ♂ (0 bytes) () 05/15/2009 postreply 12:51:13
• 没错。设置两个pointers,一个追另一个。追上为有Loop。 -戏雨飞鹰- ♀ (0 bytes) () 05/15/2009 postreply 14:46:34
• 回复:没错。设置两个pointers,一个追另一个。追上为有Loop。 -外-国人- ♂ (16 bytes) () 05/17/2009 postreply 11:03:27
• a similar but harder problem -dynamic- ♂ (122 bytes) () 05/18/2009 postreply 09:43:31
• sum mod n -haha2000- ♂ (0 bytes) () 05/18/2009 postreply 09:52:57
• I asked a similar question in an interview. -乱弹- ♂ (162 bytes) () 05/18/2009 postreply 10:01:54
• you are definitely right... I need to fix it :) -dynamic- ♂ (0 bytes) () 05/18/2009 postreply 10:48:03
• fix of the problem -dynamic- ♂ (160 bytes) () 05/18/2009 postreply 10:51:26
• algorithmic complexity requirement? -haha2000- ♂ (103 bytes) () 05/18/2009 postreply 19:19:21
• can be done in linear time... -haha2000- ♂ (150 bytes) () 05/18/2009 postreply 19:42:41
• it takes a bit more than that -dynamic- ♂ (438 bytes) () 05/18/2009 postreply 19:55:29
• hmm,这个有意思:) -戏雨飞鹰- ♀ (0 bytes) () 05/18/2009 postreply 21:12:19
• 回复:it takes a bit more than that -utopian- ♂ (51 bytes) () 05/20/2009 postreply 17:23:11
• hashing needs linear memory as well. we want constant memory her -dynamic- ♂ (0 bytes) () 05/20/2009 postreply 17:28:12
• Pay attention to some key numbers. -乱弹- ♂ (0 bytes) () 05/20/2009 postreply 19:24:24
• 觉得在哪里见过这个题目 -haha2000- ♂ (19 bytes) () 05/21/2009 postreply 07:24:10
• I don't think so. -乱弹- ♂ (0 bytes) () 05/21/2009 postreply 09:52:29
• 这题目是IMB 2004 一月的一个puzzle:) -戏雨飞鹰- ♀ (79 bytes) () 05/21/2009 postreply 12:22:12
• Yes, right! thanks! -haha2000- ♂ (0 bytes) () 05/22/2009 postreply 11:05:23
• solution -dynamic- ♂ (572 bytes) () 05/20/2009 postreply 21:41:18
• hmmm,佩服. "形状像一个勺子", haha... -戏雨飞鹰- ♀ (0 bytes) () 05/21/2009 postreply 12:25:03
• 这个题目曾是微软的面试题目。但是没有了数组'read only'的条件, -戏雨飞鹰- ♀ (75 bytes) () 05/21/2009 postreply 13:12:13