推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2465|回复: 9
收起左侧

[实习] facebook面经题,求教。+40大米

[复制链接] |试试Instant~ |关注本帖
xiaozhuxiaozhu 发表于 2016-3-4 04:05:38 | 显示全部楼层 |阅读模式

2016(7-9月)-[15]CS硕士+3个月-1年 - 内推| 码农类实习@Facebookfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
就是那2道经典的题。
一个是dot product的优化。我开始一看是leetcode原体,但是发现题目要求是非常巨大的2个matrix,不能直接求???(http://www.1point3acres.com/bbs/thread-117371-1-1.html). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一个是把binary tree convert to double linked list,然后再把double linkedlist convert back成 tree. (http://www.1point3acres.com/bbs/thread-175000-1-1.html
.1point3acres缃
一题,40大米
. 1point3acres.com/bbs
woshixuyoudan 发表于 2016-3-4 06:11:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我写了  字数字数字数

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| xiaozhuxiaozhu 发表于 2016-3-4 06:21:31 | 显示全部楼层
关注一亩三分地微博:
Warald
woshixuyoudan 发表于 2016-3-4 06:11
我写了  字数字数字数

.鏈枃鍘熷垱鑷1point3acres璁哄潧在哪呢,妹子
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-3-4 06:36:41 | 显示全部楼层
binary tree to double direction linked list 是这个 O(N) 中序走一下就可以了
http://articles.leetcode.com/convert-binary-search-tree-bst-to/
double direction linked list to binary tree 应该类似这个 这样是尽量平衡的 O(N) 应bottom-up的递归
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/. Waral 鍗氬鏈夋洿澶氭枃绔,
点乘的题应该是这样
表示方法用(index, value) 如果是两个差不多长的 那么就存到哈希表里 然后对于一组元素建立好之后 遍历另一组 然后查询对应的index有没有
如果是一个长一个短  那么就用数组把长的(index, value)建立起来 然后短的每个元素二分查找
如果把一维向量扩展到二维的矩阵 如果要存数组的话 就可以用公式把坐标换成一维的.1point3acres缃
r,c 变成 r*列数 + c 变回来的话 用i/列数, i%列数. 鍥磋鎴戜滑@1point 3 acres


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-3-4 06:39:15 | 显示全部楼层

忽然发现第一个我只写了tree --> doubly linked list  没有倒着写= =  sorry
第二个我是用map嵌套map的。。然后是O(n*m)的时间复杂度。。. 鍥磋鎴戜滑@1point 3 acres
不知道对不对。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

DJ963 发表于 2016-3-4 09:01:32 | 显示全部楼层
double linked list  转回 tree  不需要考虑双向链表的属性,直接当成单向链表来做就可以了~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

DJ963 发表于 2016-3-4 09:09:37 | 显示全部楼层
我当时给出了两个方法, 一个已经私信发给你了,另一个方法就是
public void solution(TreeNode root){
  if(root == null){
      return;
}. 1point3acres.com/bbs
Stack<TreeNode> stack = new Stack<TreeNode>();. more info on 1point3acres.com
  List<TreeNode> list = new ArrayList<>();
  TreeNode  curr = root;
  while(!stack.isEmpty() || curr != null){. Waral 鍗氬鏈夋洿澶氭枃绔,
      if(curr != null){
          stack.push(curr);
          curr = curr.left;
      }else{
         curr = stack.pop();
         list.add(curr);
         curr = curr.right;
      }
  }
  for(int i = 0; i < list.size(); i++){
     curr = list.get(i);
     if(i == 0){
         curr.right = list.get(i+1);
     }else if(i == list.size()-1){
        curr.left = list.get(i-1);
     }else{
         curr.right = list.get(i+1);
         curr.left = list.get(i-1);
     }
  }
}


补充内容 (2016-3-4 09:11):
还有一点忘记写了~  就是如果输入的root节点的左右两个子节点都是空的话,也直接return

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sjph 发表于 2016-8-2 08:37:54 | 显示全部楼层
Jester_Z 发表于 2016-3-4 06:36
binary tree to double direction linked list 是这个 O(N) 中序走一下就可以了
http://articles.leetcode ...

谢谢层主和大家!但还是对二分查找不是很清楚,层主或者各位大神能否分享一下code,先谢过了!!
回复 支持 反对

使用道具 举报

xsh6528 发表于 2017-1-20 05:57:53 | 显示全部楼层
DJ963 发表于 2016-3-4 09:01. more info on 1point3acres.com
double linked list  转回 tree  不需要考虑双向链表的属性,直接当成单向链表来做就可以了~

请问,“double linked list  转回 tree”,面试官就没有要求仍然保持是BST了吗?那就层次遍历,一层一层排下去就可以?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 14:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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