facebook面经题，求教。＋40大米

就是那2道经典的题。
一个是dot product的优化。我开始一看是leetcode原体，但是发现题目要求是非常巨大的2个matrix,不能直接求？？？

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

smilieid="108" border="0" alt="" />

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

我写了  字数字数字数

woshixuyoudan 发表于 2016-3-4 06:11
我写了  字数字数字数

在哪呢，妹子

xiaozhuxiaozhu 发表于 2016-3-4 06:21
在哪呢，妹子

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

double linked list  转回 tree  不需要考虑双向链表的属性，直接当成单向链表来做就可以了~

我当时给出了两个方法， 一个已经私信发给你了，另一个方法就是
public void solution(TreeNode root){
  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++){
     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

Jester_Z 发表于 2016-3-4 06:36
binary tree to double direction linked list 是这个 O(N) 中序走一下就可以了
http://articles.leetcode ...

谢谢层主和大家！但还是对二分查找不是很清楚，层主或者各位大神能否分享一下code，先谢过了！！

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

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

你好，请问第二题convert要求回的是Binary Tree而不是BST是吗? 然后直接当做是一个单向链表变成一颗 balanced binary tree就好了是吗?