一亩三分地论坛

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

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

fb 电面

[复制链接] |试试Instant~ |关注本帖
whisperty 发表于 2016-10-26 06:15:01 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
刚面完来回馈一下地里。
1面 国人放水
No1. Move zero. 要求最少write次数. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
No2. AddBinary

2面 土耳其那边的?
No1. 二叉树边双向链表,首尾也连的
No2. 双向链表变平衡二叉树

第二题见地里很少人提过,也没放在心上,所以也没练过,今天遇到了
我用的方法是二分,但是找中间值的时候遇到了麻烦。
对双链表不太熟,脑子也没转直接用单链表的方法去找中间值,然后意识到这种双向链表里面是没有null的。然后脑子就卡在这儿了。
写完了时间也到了,对方说我明白你想干嘛,问问题吧。然后测了一下自己的代码都无语了。。。

面完发现这题用个queue做前序,依次把每一层补齐不就好了吗。。我真是愚蠢

哎,但求三面吧。。。。
感觉还是要亲手写写,紧张的时候脑子不灵活的。。。

评分

1

查看全部评分

111180611 发表于 2016-10-26 06:35:16 | 显示全部楼层
二叉树变双向链表,是按照什么顺序呢?是要另外造一个链表吗?
. From 1point 3acres bbs二叉树变单向链表可参考leetcode 114
回复 支持 0 反对 1

使用道具 举报

 楼主| whisperty 发表于 2016-10-26 06:37:53 | 显示全部楼层
111180611 发表于 2016-10-26 06:35
二叉树变双向链表,是按照什么顺序呢?是要另外造一个链表吗?. Waral 鍗氬鏈夋洿澶氭枃绔,
二叉树变单向链表可参考leetcode 114

In place. 就是在114的基础上多加个左指针。right表示向右,left表示向左。
回复 支持 反对

使用道具 举报

 楼主| whisperty 发表于 2016-10-26 06:40:23 | 显示全部楼层
遇到不爱说话的面试官以及没见过的题 = 悲剧
回复 支持 反对

使用道具 举报

111180611 发表于 2016-10-26 06:46:25 | 显示全部楼层
whisperty 发表于 2016-10-26 06:40-google 1point3acres
遇到不爱说话的面试官以及没见过的题 = 悲剧
. Waral 鍗氬鏈夋洿澶氭枃绔,
就是left指向父节点,right指向子节点呗
回复 支持 反对

使用道具 举报

gaoyikai90 发表于 2016-10-26 06:57:34 | 显示全部楼层
如果是一个sorted list变成BST, 应该要用找中点再递归的方法把。如果只是build普通二叉树,用个queue一层一层连下去就行了对吧?
回复 支持 反对

使用道具 举报

 楼主| whisperty 发表于 2016-10-26 06:59:55 | 显示全部楼层
111180611 发表于 2016-10-26 06:46
就是left指向父节点,right指向子节点呗

Inorder 顺序的双向链表,忘了说清题意,不好意思啊
回复 支持 反对

使用道具 举报

 楼主| whisperty 发表于 2016-10-26 07:00:21 | 显示全部楼层
gaoyikai90 发表于 2016-10-26 06:57
如果是一个sorted list变成BST, 应该要用找中点再递归的方法把。如果只是build普通二叉树,用个queue一层 ...
. 1point3acres.com/bbs
我觉得是这样
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-26 07:21:34 | 显示全部楼层
你是怎么减少move zeros的writes的次数的?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-26 07:25:07 | 显示全部楼层
  1. 这样减少了writes次数吗?
  2. -google 1point3acres
  3. public void moveZeroes(int[] nums) {
  4.     int z = 0;
  5.     for (int i = 0; i < nums.length; i++) {
  6.         if (nums[i] != 0) {
  7.             swap(nums, i, z++);
  8.         }
  9.     }
  10. }
  11. private static void swap(int[] arr, int i, int j) {
  12.     int temp = arr[i];
  13.     arr[i] = arr[j];
  14.     arr[j] = temp;
  15. }
复制代码
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-26 07:47:18 | 显示全部楼层
whisperty 发表于 2016-10-26 06:37. more info on 1point3acres.com
In place. 就是在114的基础上多加个左指针。right表示向右,left表示向左。

问下BST变DLL是按pre order还是in order的顺序?

第二题是让你按什么顺序反转化成BST?in order吗?
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-26 11:56:19 | 显示全部楼层
请问楼主第二题的输入类型是DoublyListNode吗?这种双链表是没有null的意思是,面试官给的输入是circular的?
回复 支持 反对

使用道具 举报

 楼主| whisperty 发表于 2016-10-27 00:41:30 | 显示全部楼层
Badger96 发表于 2016-10-26 11:56
请问楼主第二题的输入类型是DoublyListNode吗?这种双链表是没有null的意思是,面试官给的输入是circular的 ...
. more info on 1point3acres.com
是的 。。。字数
回复 支持 反对

使用道具 举报

 楼主| whisperty 发表于 2016-10-27 00:42:14 | 显示全部楼层
iPhD 发表于 2016-10-26 07:47
问下BST变DLL是按pre order还是in order的顺序?

.鐣欏璁哄潧-涓浜-涓夊垎鍦第二题是让你按什么顺序反转化成BST?in order吗?

第一题in order,第二题没有说,只说要somehow balanced
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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