FB onsite挂经

FB onsite 挂经， 面的是research scientist，（好像SDE wit

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dertraversal的iterator.

二叉树后序遍历的Iterator
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
  class Iterator {
  
  public:
    stack<TreeNode *> mystack;
    TreeNode * last_visited = NULL;
    Iterator(TreeNode *root) {
      insert(root);
    }
    void insert(TreeNode * p){
      if(!p)
        return;
      while(true){
        while(p->left){
          mystack.push(p);
          p = p->left;
        }
        mystack.push(p);
        if(p->right){
          p = p->right;
        }
        else{
          return;
        }
      }
      return;
    }
  
    bool hasNext() {
      return !mystack.empty();
    }
  
    int next() {
      TreeNode * p = mystack.top();
      if(!p->right || p->right == last_visited){
        mystack.pop();
        last_visited = p;
        return p->val;
      }
      else{
        insert(p->right);
        p = mystack.top();
        mystack.pop();
        last_visited = p;
        return p->val;
      }
    }
  };
  vector<int> postorderTraversal(TreeNode* root) {
    Iterator iter(root);
    vector<int> result;
    while(iter.hasNext()){
      result.push_back(iter.next());
    }
    return result;


  }
};

#include <vector>
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <queue>
#include <climits>
#include <algorithm>
#include <string.h>
#include <stack>

using namespace std;

struct TreeNode{
  int val;
  TreeNode *left, *right;
  TreeNode(int v) {
    val=v;
    left=right=nullptr;
  }
};

stack<TreeNode *> st;

bool hasNext() {
  return !st.empty();
}

TreeNode *Next() {
  auto root = st.top();
  st.pop();

  if (!st.empty() && root->right==st.top()) {

     auto cur = st.top();
     st.pop();

     st.push(root);
     while (cur) {
       if (cur->right)
         st.push(cur->right);
       st.push(cur);
       cur=cur->left;
    }
    return Next();
  }
  else{
    return root;
  }
}

void buildPostIterator(TreeNode *root) {
  while (root) {
    if (root->right) {
      st.push(root->right);
    }
    st.push(root);
    root=root->left;
  }

}

main() {
    TreeNode* root = NULL;
    root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    buildPostIterator(root);
    while (hasNext()) {
      printf ("%d \n", Next()->val);
    }
}

ydxu16 发表于 2017-11-17 00:39
那个意思就是说比如1代表abcd，你输入一个1得到a输入两个1得到aa or b， 三个1： aaa ab ba c 诸如此类

感谢楼主，针对你给的例子，我是不是可以理解成，存在这样的mapping关系
1 ---> a
11 ---> b
111 ---> c
1111  ---> d
然后输入 111
可以输出 aaa; ab; ba, c
因为可以看成
1 1 1
1 11
11  1
111
感觉很像decode way的变种。是么？
请问最后输出所有decode的方案么？

请教LZ post order traversal 那题怎么解呀？是binary tree的iterator么？

king_lm 发表于 2017-11-15 04:00
请教LZ post order traversal 那题怎么解呀？是binary tree的iterator么？

是的，这个是比较经典的题但要求的是iterator而我只记得一遍过。

postorder iterator 不是一般的复杂啊...  如果用stack做的话, 需要记住节点是只往左走, 还是左右都走过了, 楼主是写了wrapper class做的吗?

ydxu16 发表于 2017-11-15 04:07
是的，这个是比较经典的题但要求的是iterator而我只记得一遍过。

嗯嗯多谢， 那第一题那个完成输入法请问是什么意思呀？

phone letter combination+词典绝对是高频了，可能楼主比较忙。第二题有点偏了，楼主方便介绍一下ML面的什么吗？

kevintong 发表于 2017-11-16 15:06
phone letter combination+词典绝对是高频了，可能楼主比较忙。第二题有点偏了，楼主方便介绍一下ML面的什 ...

嗯第一题我看过原题，变形版没见过，我面的是infastructure 没有ml， infastructure面的是如何design twitter

king_lm 发表于 2017-11-15 23:08
嗯嗯多谢， 那第一题那个完成输入法请问是什么意思呀？

那个意思就是说比如1代表abcd，你输入一个1得到a输入两个1得到aa or b， 三个1： aaa ab ba c 诸如此类

请问lz什么时候能知道自己面的组？机票酒店已经定了，后面会有另外的关于具体面试的邮件吗