一亩三分地论坛

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

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

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

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

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

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

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

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大米
. 1point 3acres 璁哄潧
woshixuyoudan 发表于 2016-3-4 06:11:38 | 显示全部楼层
我写了  字数字数字数

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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%列数 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-3-4 06:39:15 | 显示全部楼层
.1point3acres缃
忽然发现第一个我只写了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 | 显示全部楼层
我当时给出了两个方法, 一个已经私信发给你了,另一个方法就是
public void solution(TreeNode root){
  if(root == null){
      return;
}. 1point 3acres 璁哄潧
Stack<TreeNode> stack = new Stack<TreeNode>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  List<TreeNode> list = new ArrayList<>();
  TreeNode  curr = root;
  while(!stack.isEmpty() || curr != null){
      if(curr != null){-google 1point3acres
          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){.1point3acres缃
        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 ...
. 1point 3acres 璁哄潧
谢谢层主和大家!但还是对二分查找不是很清楚,层主或者各位大神能否分享一下code,先谢过了!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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