一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2761|回复: 22
收起左侧

分享facebook的一道电面题

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2014-3-14 02:21:32 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
interleave two linked-list
for example
Given
1->2->3->4;
5->6;
return 1->5->2->6->3->4;
我写的是iterative的版本。为了处理head结点,还加了个哨兵,最后没有delete,面试官挑memory leak.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 1point 3acres 璁哄潧
这个题如果不用递归写,会比较冗余
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Node * interleave(Node *p, Node *q)
{
    if(!p && !q) return NULL;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    if(!p) return q;
    if(!q) return p;
    q->next=interleave(p->next,q->next);. more info on 1point3acres.com
    p->next=q;
    return p;
}. 1point 3acres 璁哄潧

评分

6

查看全部评分

 楼主| Linzertorte 发表于 2014-3-19 13:27:51 | 显示全部楼层

C++里你delete dummy后。dummy就自然是NULL了。在Java里你写dummy=null. dummy原来指向的heap区的node的reference count就是0 (即没有任何reference指向他)就会被garbage collector回收。不过面试这玩意吧。用我一个同学的名言说就是“看脸,面试前记得洗脸。“有人会挑,有人不会挑。
回复 支持 1 反对 0

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-19 13:41:47 | 显示全部楼层
tacit 发表于 2014-3-19 13:16
需要加dummy = NULL;吗?

如果面试的时候类似这种题用java写的话可以吗?面试官会不会强调用c++之类的 ...

刚才说的不对,delete后.dummy的值不对。不过dummy指向的heap区地址已经被OS认为是free了。下次new的时候就可能会用到这个地址的内存了。
写了个小程序。. visit 1point3acres.com for more.
Screen Shot 2014-03-19 at 1.38.35 AM.png
Screen Shot 2014-03-19 at 1.38.35 AM.png
回复 支持 1 反对 0

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-14 07:02:54 | 显示全部楼层
还有leetcode里的Merge Two Sorted Lists
如果用递归写也很清楚。
  1. /**
  2. * Definition for singly-linked list.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3. * struct ListNode {
  4. *     int val;
  5. *     ListNode *next;
  6. *     ListNode(int x) : val(x), next(NULL) {}. 1point3acres.com/bbs
  7. * };
  8. */
  9. class Solution {
  10. public:
  11.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  12.         if(!l1)return l2;
  13.         if(!l2)return l1;
  14.         if(l1->val<l2->val){
  15.             l1->next=mergeTwoLists(l1->next,l2);.1point3acres缃
  16.             return l1;
  17.         }else{
  18.             l2->next=mergeTwoLists(l1,l2->next);. 1point3acres.com/bbs
  19.             return l2;
  20.         }
  21.     }
  22. };
复制代码
回复 支持 反对

使用道具 举报

hujiafeng 发表于 2014-3-14 23:44:52 | 显示全部楼层
ym~ 怎么加大米啊~
回复 支持 反对

使用道具 举报

snowhws 发表于 2014-3-18 22:13:43 | 显示全部楼层
不用递归,可以用队列,逻辑比较简单,如下:
Node* interleave(Node* n1, Node* n2) {
    Node dummy(0);. more info on 1point3acres.com
    queue<Node*> nq;
    if( n1!=NULL ) nq.push( n1 );
    if( n2!=NULL ) nq.push( n2 );
    Node* cur = (Node *)&dummy;
    while( nq.size()>0 ) {
        Node* top = nq.front();.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if( top->next!=NULL ) nq.push(top->next);
        nq.pop();
        cur->next = top;
        cur = cur->next;
    }
    return dummy.next;. visit 1point3acres.com for more.
}
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-19 04:54:56 | 显示全部楼层
snowhws 发表于 2014-3-18 22:13 . Waral 鍗氬鏈夋洿澶氭枃绔,
不用递归,可以用队列,逻辑比较简单,如下:
Node* interleave(Node* n1, Node* n2) {
    Node dummy(0 ...

你这个dummy最后没有释放。。虽然我一般也不在乎。但是我当时面的时候那个面试官就说这是一个问题
回复 支持 反对

使用道具 举报

tacit 发表于 2014-3-19 05:21:18 | 显示全部楼层
Linzertorte 发表于 2014-3-19 04:54
你这个dummy最后没有释放。。虽然我一般也不在乎。但是我当时面的时候那个面试官就说这是一个问题

可以用java写吗?
回复 支持 反对

使用道具 举报

elementary 发表于 2014-3-19 06:06:04 | 显示全部楼层
Linzertorte 发表于 2014-3-18 15:54
你这个dummy最后没有释放。。虽然我一般也不在乎。但是我当时面的时候那个面试官就说这是一个问题

去除Dummy有一个办法,再loop 一遍把所有值都往前挪,free掉最后一个node即可,貌似是ctci上一道题说只知道ll的某一个节点不知道前一个,如何remove,就是直接把后面值copy到前面。不过这样比较蛋疼就是了,复杂度没变,只是变成2n。java就松松了
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-19 06:14:38 | 显示全部楼层
elementary 发表于 2014-3-19 06:06
去除Dummy有一个办法,再loop 一遍把所有值都往前挪,free掉最后一个node即可,貌似是ctci上一道题说只知 ...

去dummy不是非常简单吗。。
Node *head=dummy.next;
delete dummy;
return head;
回复 支持 反对

使用道具 举报

elementary 发表于 2014-3-19 10:23:56 | 显示全部楼层
Linzertorte 发表于 2014-3-18 17:14
去dummy不是非常简单吗。。
Node *head=dummy.next;. 1point 3acres 璁哄潧
delete dummy;

恩,nice
回复 支持 反对

使用道具 举报

tacit 发表于 2014-3-19 13:16:28 | 显示全部楼层
Linzertorte 发表于 2014-3-19 06:14
去dummy不是非常简单吗。。
Node *head=dummy.next;
delete dummy;

.1point3acres缃需要加dummy = NULL;吗?

如果面试的时候类似这种题用java写的话可以吗?面试官会不会强调用c++之类的?望lz指点。thx~
回复 支持 反对

使用道具 举报

snowhws 发表于 2014-3-20 23:57:06 | 显示全部楼层
Linzertorte 发表于 2014-3-19 04:54 . 鍥磋鎴戜滑@1point 3 acres
你这个dummy最后没有释放。。虽然我一般也不在乎。但是我当时面的时候那个面试官就说这是一个问题

你仔细看看,我写的是局部变量,不是指针,不用delete。。。最后返回的是一个指针,那个指针是不用释放的,是传进来的链表。
回复 支持 反对

使用道具 举报

Lisepher 发表于 2014-3-21 01:13:33 | 显示全部楼层
Delete 就行,dummy在stack上,function return后自然会释放,不存在dangling pointer的问题
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-3-21 02:29:58 | 显示全部楼层
snowhws 发表于 2014-3-20 23:57
你仔细看看,我写的是局部变量,不是指针,不用delete。。。最后返回的是一个指针,那个指针是不用释放的 ...

I see. make sense..
回复 支持 反对

使用道具 举报

joy9088 发表于 2014-7-25 16:36:31 | 显示全部楼层
受教了,长知识
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-2 13:35:21 | 显示全部楼层
while(left != NULL && right != NULL){
            left_nt = left->next;
            right_nt = right->next;
            left->next = right;
            right->next = left_nt;
            left = left_nt;
            right = right_nt;
}
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-3 00:18:54 | 显示全部楼层
这个题目的难点在什么地方?望指点.
iterative version:
  1. public ListNode interleave(ListNode n1, ListNode n2) {
  2.                 if(n1 == null)        return n2;
  3.                 if(n2 == null)        return n1;.1point3acres缃
  4.                 ListNode newHead = new ListNode(0);
  5.                 ListNode curr = newHead;
  6.                 while(n2 != null) {
  7.                         curr.next = n1;
  8.                         curr = curr.next;
  9.                         n1 = n2;
  10.                         n2 = curr.next;
  11.                 }
  12.                 curr.next = n1;
  13.                 return newHead.next;
  14.         }
复制代码
recursive version
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-3 00:19:39 | 显示全部楼层
recursive version
  1. public ListNode interleaveRec(ListNode n1, ListNode n2) {
  2.                 if(n1 == null)        return n2;
  3.                 if(n2 == null)        return n1;
  4.                 ListNode newHead = new ListNode(0);
  5.                 newHead.next = n1;
  6.                 newHead.next.next = interleaveRec(n2, n1.next);
  7.                 return newHead.next;
  8.         }
复制代码
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-1-4 15:21:51 | 显示全部楼层
Linzertorte 发表于 2014-3-14 07:02
还有leetcode里的Merge Two Sorted Lists
如果用递归写也很清楚。

没有让你排序啊, 不需要比较l1->val l2->val
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 18:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表