May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2248|回复: 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

一题,40大米

woshixuyoudan 发表于 2016-3-4 06:11:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我写了  字数字数字数

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

. From 1point 3acres bbs

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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 | 显示全部楼层
我当时给出了两个方法, 一个已经私信发给你了,另一个方法就是
public void solution(TreeNode root){. 1point3acres.com/bbs
  if(root == null){
      return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
  List<TreeNode> list = new ArrayList<>();
  TreeNode  curr = root;
  while(!stack.isEmpty() || curr != null){
      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++){.1point3acres缃
     curr = list.get(i);
     if(i == 0){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
         curr.right = list.get(i+1);. from: 1point3acres.com/bbs
     }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
double linked list  转回 tree  不需要考虑双向链表的属性,直接当成单向链表来做就可以了~
. 1point 3acres 璁哄潧
请问,“double linked list  转回 tree”,面试官就没有要求仍然保持是BST了吗?那就层次遍历,一层一层排下去就可以?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 08:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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