在线等 - 微软面试问题 - 急

内核

上次电话interview时被问到这个问题，结果回答I don't know. 现在email又来问，各位xdjm快帮忙！多谢了！

Write a function that would:    return the 5th   element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function.

riverSide

in what language? How about

p5th = null;
pFrom = head;
count = 0;
while (pFrom!=null) {
pFrom = pFrom.next;
count++;
if (count==5) p5th = head;
else if(count>5) p5th = p5th.next;
}
return p5th;

[ 本帖最后由 riverSide 于 2007-11-13 20:34 编辑 ]

riverSide

抛砖引玉。

内核

Yes, in C. That's similar to my code. I just want to know if there's some tricky code to do this in 2 or 3 lines. But it seems that I'm day-dreaming...

Anyway, thanks mate.

Then, what do you think about the test cases? I think if the function prototype is:

PSINGLE_LIST FindLastFifth(PSINGLE_LIST Head);

then the head should be:

1. NULL
2. With 0 elements
3. With 1 elements
4. With 5 elements
5. With 6 elements
6. With 10 elements
7. With random elements

What do you think?

[ 本帖最后由 内核 于 2007-11-13 20:45 编辑 ]

内核

原帖由 riverSide 于 2007-11-13 20:30 发表
in what language? How about

p5th = null;
pFrom = head;
count = 0;
while (pFrom!=null) {
pFrom = pFrom.next;
count++;
if (count==5) p5th = head;
else if(count>5) p5th = p5th.next;
...

But BTW, that guy from MS asked me this question on the phone. How could I explain this code just by mouth? So weird...

riverSide

For test case set, I think
1. NULL
2. With 0 elements
3. With 1 elements
4. With 5 elements
5. With 6 elements

is enough. It's important to initialize list to be testable.


Also I think you can express well in replying email this time.

Good luck.

degra

" 5th   element from the end, in single pass", I would expect candidate to use recursion

内核

原帖由 gandu 于 2007-11-15 23:17 发表
" 5th   element from the end, in single pass", I would expect candidate to use recursion

Recursion will definitely cause stack overflow in Windows kernel. So usually we avoid this when coding.

sujiea

我考过类似的题，但是要求reverse the list. And the list is a complicated one with sublist inside. Like:

(1,2,3,(1,(1,2)),4,5,.6)

And I think the only way of doing this is to use Recursion. But I lost the points during the interview.

黑山老妖

Yes, recursion is probably the only way.
Not good programming practice but sometimes unavoidable.

cattor

哪位能不能翻译一下题目啊？什么叫in one pass？什么又是a set of test cases？

是不是表示，你先取一个我看看，然后再给我个一般的方法我可以一直用下去？

[ 本帖最后由 cattor 于 2007-12-3 15:57 编辑 ]

bffbffbff

原帖由 gandu 于 2007-11-15 23:17 发表
" 5th   element from the end, in single pass", I would expect candidate to use recursion

C.D.

if recursion is not allowed. probably we can copy at most 10 elements into 2 size-5 array, 5 elements each time, it is an integer list, so memory shouldn't be too much, the test case would be the different number of elements in the list, total number is: 0, 4, 5, 9, 10, 11, I am from Java background, i don't know whether Microsoft has some built-in library which can help to simplify the task

jsg

Bang Ding

taoyuan

原帖由 jsg 于 2007-12-3 20:15 发表
Bang Ding

不懂也顶！支持找工！

sujiea

搂主这道题riverside的方法很好啊。我觉得in one pass是不是就是说一次循环检索完成。

C.D.

why can't we use recursion?

[ 本帖最后由 C.D. 于 2007-12-4 20:28 编辑 ]