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皇后问题：找到并打印女王所有可能的不冲突职位。
【Twitter面试经验分享和解析|S1】6.a.
给定一个输入二叉树并引用该树中的一个节点, 请为该输入节点找到下一个有序继承者。如果没有, 则输出null。
6.b.
排序k排序数组的最佳方法是什么？针对时间复杂度进行优化。
(我的提示：使用大小为k的优先级队列)
7.a.
招聘经理：为a。设计服务。耐用性b。一致性
7.b．
说明C ++的多重继承问题。