San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3386|回复: 10
收起左侧

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

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

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

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

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

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.留学论坛-一亩-三分地

一题,40大米.本文原创自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/.本文原创自1point3acres论坛
点乘的题应该是这样. 牛人云集,一亩三分地
表示方法用(index, value) 如果是两个差不多长的 那么就存到哈希表里 然后对于一组元素建立好之后 遍历另一组 然后查询对应的index有没有
如果是一个长一个短  那么就用数组把长的(index, value)建立起来 然后短的每个元素二分查找
如果把一维向量扩展到二维的矩阵 如果要存数组的话 就可以用公式把坐标换成一维的
r,c 变成 r*列数 + c 变回来的话 用i/列数, i%列数


评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

woshixuyoudan 发表于 2016-3-4 06:11:38 | 显示全部楼层
我写了  字数字数字数

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| xiaozhuxiaozhu 发表于 2016-3-4 06:21:31 | 显示全部楼层
woshixuyoudan 发表于 2016-3-4 06:11
我写了  字数字数字数

在哪呢,妹子
回复 支持 反对

使用道具 举报

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

忽然发现第一个我只写了tree --> doubly linked list  没有倒着写= =  sorry
第二个我是用map嵌套map的。。然后是O(n*m)的时间复杂度。。
不知道对不对。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

DJ963 发表于 2016-3-4 09:09:37 | 显示全部楼层
我当时给出了两个方法, 一个已经私信发给你了,另一个方法就是. From 1point 3acres bbs
public void solution(TreeNode root){
  if(root == null){
      return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
  List<TreeNode> list = new ArrayList<>();
  TreeNode  curr = root;
. visit 1point3acres for more.  while(!stack.isEmpty() || curr != null){
      if(curr != null){. Waral 博客有更多文章,
          stack.push(curr);
          curr = curr.left;
      }else{
         curr = stack.pop();
         list.add(curr);.留学论坛-一亩-三分地
         curr = curr.right;
      }. 留学申请论坛-一亩三分地
  }. visit 1point3acres for more.
  for(int i = 0; i < list.size(); i++){. visit 1point3acres for more.
     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);
     }
  }.1point3acres网
}


补充内容 (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,先谢过了!!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

legendava 发表于 2017-12-15 10:44:06 | 显示全部楼层
你好,请问第二题convert要求回的是Binary Tree而不是BST是吗? 然后直接当做是一个单向链表变成一颗 balanced binary tree就好了是吗?. Waral 博客有更多文章,
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 08:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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