一道挺简单的题给搞砸了 - 未名空间MITBBS历史存档

p*22012-05-22 07:05

1 楼

被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
PNode reverse(PNode head)
{
PNode newhead=null;
while(head)
{
PNode n=head;
head=head->next;
n->next=newhead;
newhead=n;
}
return newhead;
}
等了几分钟那人一进门就说，“二爷，你怎么写的这么复杂呢？你怎么用了这么多指针
呢？你能不能少用一些指针呢？“，
我说”你的意思是让我用一个指针变量来完成“，他说”是的，你用了太多指针了“。
我说”好吧，我看看“。
结果不看还好，越看越心惊，压力无限大，脑子短路，啥思路也没有，当即就跪了。
本来一道挺简单的题，咋做成个这样子呢？昨晚一晚没睡好，郁闷呀。

y*u2012-05-22 07:05

2 楼

写的挺好啊
这个b看着像是找茬的

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

p*i2012-05-22 07:05

3 楼

想让你用recursion？
有些面试官真心喜欢recursion

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

p*22012-05-22 07:05

4 楼

郁闷呀，平时不注意学习leetcode的经典解法，以为自己有思路就可以了，没想到这么
个结局。大家要引以为戒呀。

v*n2012-05-22 07:05

5 楼

recursive?

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

j*92012-05-22 07:05

6 楼

这都不行，唉，继续看题，背题。。。

v*n2012-05-22 07:05

7 楼

但是递归的空间开支其实比北京的大

【在 p*i 的大作中提到】

: 想让你用recursion？
: 有些面试官真心喜欢recursion

p*22012-05-22 07:05

8 楼

我咋碰不到你这样的面试官呢？

【在 y**********u 的大作中提到】

: 写的挺好啊
: 这个b看着像是找茬的

p*i2012-05-22 07:05

9 楼

这些都没关系的。
俺就遇到过这样的面试官，本来写的iterative的已经最优了，除了代码稍微多几行
人一定要找出俺的问题，说俺的代码不好看，为什么不用recursion，然后吧唧吧唧吹
recursion多好多好
后来发现此人不知道很多recursive的算法可以改造成iterative的

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

: 但是递归的空间开支其实比北京的大

v*n2012-05-22 07:05

10 楼

恩，换我就问问他如果他做编译器要怎么实现recursion
哈哈哈

【在 p*i 的大作中提到】

: 这些都没关系的。
: 俺就遇到过这样的面试官，本来写的iterative的已经最优了，除了代码稍微多几行
: 人一定要找出俺的问题，说俺的代码不好看，为什么不用recursion，然后吧唧吧唧吹
: recursion多好多好
: 后来发现此人不知道很多recursive的算法可以改造成iterative的

y*u2012-05-22 07:05

11 楼

碰到这样找茬的直接开骂了
有些面试官自以为知道茴字的几种写法，不要鸟

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

:
: 我咋碰不到你这样的面试官呢？

y*u2012-05-22 07:05

12 楼

我真看不出他这样多用一个指针，最多分配一个寄存器变量和内存地址的
和面试官无数次recursion, 建立activation record,保存当前的局部变量，跳转
activation record有什么劣势
这样的面试官估计就是找艹

了吗
才对

【在 p*i 的大作中提到】

: 想让你用recursion？
: 有些面试官真心喜欢recursion

h*e2012-05-22 07:05

13 楼

二爷，只能说你和他chemistry不合。

c*p2012-05-22 07:05

14 楼

二爷不必太烦恼了。我也遇到过这样的面试官，他就是要他想要的答案，别的一概不
行。稍微好一点的，就不断地加限制，逼你最后说出他想要的答案。差的，就像你遇到
的这个面试官，就是说你的方法不好。
其实现在的编译器已经很强大了，多用个把变量，编译器会做优化的。因此，在减少变
量上面费力是不值得的。如果面试官懂这个，还要让你优化变量，那他就是有意想为难
为难你了。人为刀俎，我为鱼肉。没什么好讲的了。而且，这样的人，你愿意和他合
作吗？

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

:
: 我咋碰不到你这样的面试官呢？

t*h2012-05-22 07:05

15 楼

这。。。

p*i2012-05-22 07:05

16 楼

呵呵，人家不会是不会，还是能吹的天花乱坠的

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

: 恩，换我就问问他如果他做编译器要怎么实现recursion
: 哈哈哈

p*i2012-05-22 07:05

17 楼

嗯，就是那种不懂多少还装nb的

【在 y**********u 的大作中提到】

: 我真看不出他这样多用一个指针，最多分配一个寄存器变量和内存地址的
: 和面试官无数次recursion, 建立activation record,保存当前的局部变量，跳转
: activation record有什么劣势
: 这样的面试官估计就是找艹
:
: 了吗
: 才对

l*82012-05-22 07:05

18 楼

it's a single-linked list or double-linked list?

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

M*t2012-05-22 07:05

19 楼

single

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

: it's a single-linked list or double-linked list?

g*u2012-05-22 07:05

20 楼

下面这个是不是更好一点啊，网上看到的。我觉得应该用指针啊，你的代码里怎么head
和newhead都不是指针呢？
//single-linked list
Element *reverse(Element *old_list)
{
Element *new_list = NULL;
while (old_list != NULL) {
// Remove element from old list.
Element *element = old_list;
old_list = old_list->next;
// Insert element in new list.
element->next = new_list;
new_list = element;
}
return new_list;
}

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

w*x2012-05-22 07:05

21 楼

这个逼就是存心找碴, 你不这么认为就是自虐

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

H*r2012-05-22 07:05

22 楼

Is this real story?

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

a*o2012-05-22 07:05

23 楼

啥公司啊？

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

t*h2012-05-22 07:05

24 楼

这个时候就要靠扯淡了，遇到这种人。看扯淡能不能抗过去，讲个笑话，打个哈哈就过
去了。如果还过不去，就只能跪了。。。

p*22012-05-22 07:05

25 楼

刚才看了一下leetcode的正解，好像我还少用了一个指针呀。

p*22012-05-22 07:05

26 楼

head
没看到P吗？

【在 g**u 的大作中提到】

: 下面这个是不是更好一点啊，网上看到的。我觉得应该用指针啊，你的代码里怎么head
: 和newhead都不是指针呢？
: //single-linked list
: Element *reverse(Element *old_list)
: {
: Element *new_list = NULL;
: while (old_list != NULL) {
: // Remove element from old list.
: Element *element = old_list;
: old_list = old_list->next;

p*22012-05-22 07:05

27 楼

递归的我上星期练过一次，还有纪录呢。不过做题做得太快了，给忘记了。当时一紧张
也没想起来呀。要不leetcode说我做那么快不好，果然遭到报应了。leetcode真是大神
呀。
ListNode reverse(ListNode head)
{
if(head==null || head.next==null)
return head;

ListNode node=reverse(head.next);
head.next.next=head;
head.next=null;

return node;
}

H*r2012-05-22 07:05

28 楼

Any advantage for the recursive version?

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

:
: 递归的我上星期练过一次，还有纪录呢。不过做题做得太快了，给忘记了。当时一紧张
: 也没想起来呀。要不leetcode说我做那么快不好，果然遭到报应了。leetcode真是大神
: 呀。
: ListNode reverse(ListNode head)
: {
: if(head==null || head.next==null)
: return head;
:
: ListNode node=reverse(head.next);

p*22012-05-22 07:05

29 楼

可以少定义一个指针变量呀。

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

: Any advantage for the recursive version?

H*r2012-05-22 07:05

30 楼

besides that? Recursion works like a stack from my understanding and it
consumes resource to manage...

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

:
: 可以少定义一个指针变量呀。

p*22012-05-22 07:05

31 楼

除了这个就是可以通过面试吧？不然这还通过不了那就活不下去了。

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

: besides that? Recursion works like a stack from my understanding and it
: consumes resource to manage...

b*h2012-05-22 07:05

32 楼

recursive solution?
linknode* Inverse_link(linknode* head){
if (head->next==NULL) return head;
else{
linknode* new_head=Inverse_link(head->next);
(head->next)->next=head;
head->next=NULL;
returen new_head;
}
}

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

p*22012-05-22 07:05

33 楼

how about input is null?

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

: recursive solution?
: linknode* Inverse_link(linknode* head){
: if (head->next==NULL) return head;
: else{
: linknode* new_head=Inverse_link(head->next);
: (head->next)->next=head;
: head->next=NULL;
: returen new_head;
: }
: }

b*h2012-05-22 07:05

34 楼

oh, I didn't consider that :-(
maybe change the line
if (head->next==NULL||head==NULL) can solve the problem?

p*22012-05-22 07:05

35 楼

这个也不行吧？

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

: oh, I didn't consider that :-(
: maybe change the line
: if (head->next==NULL||head==NULL) can solve the problem?

l*a2012-05-22 07:05

36 楼

这题我拿手
2种写法各写过不下5次

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

: 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
: ？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
: 吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
: PNode reverse(PNode head)
: {
: PNode newhead=null;
: while(head)
: {
: PNode n=head;
: head=head->next;

t*h2012-05-22 07:05

37 楼

膜拜大牛。。。

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

: 这题我拿手
: 2种写法各写过不下5次

l*a2012-05-22 07:05

38 楼

这是最基本的题

【在 t**********h 的大作中提到】

: 膜拜大牛。。。

p*22012-05-22 07:05

39 楼

膜拜。怪不得那么多大offer呢。

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

: 这是最基本的题

c*l2012-05-22 07:05

40 楼

我感觉有的考官在挑毛病
似乎心中已经决定拒了再找理由

呢？你能不能少用一些指针呢？“，
我说”你的意思是让我用一个指针变量来完成“，他说”是的，你用了太多指针了“。
我说”好吧，我看看“。
结果不看还好，越看越心惊，压力无限大，脑子短路，啥思路也没有，当即就跪了。
本来一道挺简单的题，咋做成个这样子呢？昨晚一晚没睡好，郁闷呀。

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

:
: 膜拜。怪不得那么多大offer呢。