Twitter面试经验分享和解析|S1

手机屏幕–我

1.

不使用数组的斐波那契数列–这是一个典型的最喜欢的问题你将在哪里询问动态编程

不要使用备忘或任何额外的存储来存储先前迭代的值。

(同一个问题的更复杂的版本：使用二维N x N数组生成不带Pascal三角形的第N行)

2.N元树：查找树中是否存在值= x的节点。如果是, 则返回true, 否则返回false。

手机屏幕– II

1.

查找二叉树的最低共同祖先

答案：做了10次🙂解释了如何做！

2.克隆图形并分析时间和空间的复杂性(因为基于DFS的方法利用更短的时间以更大的内存为代价)

public class Node {
   public int data;
   List neighbhors;

   public Node (int data) {…}
   setNeighbors(List neighbhors) {…}
}

// HashMap created = new HashMap();

public Node clone(Node oldGraph) {

  if (created.get(oldGraph))
    return created.get(oldGraph);

  Node newGr = new Node(oldGraph.data);
  List nbors = new ArrayList();

  created.put(oldGraph, newGr);

  List adj = oldGraph.getNeighbhors();
  for (Node n : adj) {
     nbors.add(clone(n));
  }

  newGr.setNeighbors(nbors);
  return newGr;
}

手机屏幕III

设计Bloom过滤器, 以从未排序的数组中删除重复项！

现场

1.(类似于问题)。在2D数组(M x N, 在给定的3×3中), 找到从指定的原始像元(1, 0)到指定的目标像元(0, 2)。数组可能包含重复项, 因此解决方案应适用于重复项。

2.a.

为Twitter中的每个推文设计一个独特的哈希函数, 该函数将用作服务的一部分。

2.b.

查找有向图是否具有循环。编写一个具有布尔返回类型的函数。

3.休闲午餐面试。

4.使用包含字符(a到z)以及" *", "？"和"。"的模式进行模式匹配

5.a.

描述如何进行外部排序->得出map-reduce的解决方案。每台计算机有10M个数字(总计100M), 共有10台计算机。每个m / c具有20MB RAM和50GB内存。

5.b.

N皇后问题：找到并打印女王所有可能的不冲突职位。

6.a.

给定一个输入二叉树并引用该树中的一个节点, 请为该输入节点找到下一个有序继承者。如果没有, 则输出null。

6.b.

排序k排序数组的最佳方法是什么？针对时间复杂度进行优化。

(我的提示：使用大小为k的优先级队列)

7.a.

招聘经理：为a。设计服务。耐用性b。一致性

7.b．

说明C ++的多重继承问题。