r****o
发帖数: 1950 | 1 是不是这种非二叉树的树也不好找路径啊,
要不然可以把路径找出来再找parent. |
|
|
k***e
发帖数: 556 | 3 楼主水平和我差不多 ：）基本上答案都一样，你不会的我也不会，哈哈
安装level打印树那题，可以就用一个vector模拟栈和队列，再用一个vector记住没层
的长度应该就可以了。似乎少点时间。
1234那题，除了穷举加backtracking似乎没有更好的方法。
list |
|
g*******y
发帖数: 1930 | 4 是MS的on campus，没料到会出那么简单的题，一激动加紧张，慌着早点写完好接着做
后面的题，写了个居烂无比的code，很多情况都没考虑(平时练习的时候我都肯定能考
虑全的)。做完了时间还有一半，考官没继续出题，开始跟我聊天了，我也忘了该再要
一道题来做。。。唉。。。 |
|
a****s
发帖数: 559 | 5 1.先把这n个unsigned integers，每个都取位反，得到n个新的unsigned integers.
2.用原来的n个旧数生成小尾羊说的二叉树。
3.把新的n个数也放入2中二叉树。如果加入某个新数时其位置已经被某旧数占据，则该
新数取反前的旧数和占据该位置的旧数之XOR为0xFFFFFFFF，最大。
4.如果没有任何新数和旧数走到同一位置，查看旧数和新数的上一层的父节点。如果出
现某新数和某旧数有同一父节点，则该新数取反前的旧数和同父的旧数之XOR为
0xFFFFFFFE.
5.如果还没有，再往上找同父节点，以此类推。
真正在编程时，可以在插入新数时就一直保持一个有同父节点的最深的新旧数对（或多
个，有可能多解）。这样新数插入完，就有了结果，不需再用4.5.的办法向上回朔。 |
|
|
t*****j
发帖数: 1105 | 7 我第一反应应该是二叉树搜索需要的节点个数。但是后来没想通为啥。
然后觉得应该是从信息论来考虑，其实现在想来都是一样的。
用二叉树应该也可以解释一个模型出来。 |
|
j**l
发帖数: 2911 | 8 好像是平面上最近点集的变体，拓展到了球面而已。
难道非要用四叉树或者K-D树来做么？ |
|
i**********e
发帖数: 1145 | 9 更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
d*********i
发帖数: 628 | 10 先排序一遍生成2叉树
然后找到12，再找到24 《--用递归前序遍历
排序建立树时间是O(n)吧，不太确定
前序遍历worst case是要找的值在叶子上，
那O=depth of the tree:
worst case是每个点只有一个child,那depth = N
其他情况，depth = Log2(N) |
|
b*******8
发帖数: 37364 | 11 后缀树的确很好，可以强行记住几个结论。但是实际面试中，会问如何构造后缀树吗？
这个就麻烦了。 |
|
t*****s
发帖数: 416 | 12 比如
1.1检查一个串有没有重复字符如果charset小的话根据抽屉原理时间是O(1)
4.7检查一个小的二叉树是不是一个大二叉树的子树可以当字符串用KMP |
|
o****d
发帖数: 2835 | 13 大致是说
如果左右子树一样 那么这棵树一样
用map就可以查到之前是否已经有同样子树的树
有的话就发现同样的子树
没有就插入
直到把每个节点都遍历 返回最大的那个就是了 |
|
o****d
发帖数: 2835 | 14 二叉树 是 binary tree
binary search tree 是 二叉查找树
题目就是你说的那个意思
这里的一样指的是结构上一样 |
|
a**********2
发帖数: 340 | 15 来自主题: JobHunting版 - 问个算法题 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
后找出最大计数路径。
其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
的出现频率
连续的话用就不知道怎么弄了 |
|
S********t
发帖数: 3431 | 16 不行啊，题目的reconstruct意思是要得到一个跟原来的树结构一模一样的树。
而你的方法里面，btr跟gt不等价，所以不可能由一个btr唯一的转换为一个gt
node |
|
q******8
发帖数: 848 | 17 文件树（非二叉树）遍历。给出一个root节点，返回一个list of file names（不包括
文件夹名）。要求：不可以使用递归。返回的list中文件名不得有重复。 |
|
f*******n
发帖数: 12623 | 18 "用树结构实现的" what? hash table = hash table. 和树结构无关系
table |
|
Z*****Z
发帖数: 723 | 19 他说的不是二叉树，所以没有左右子树的歧义性。你给的两棵树其实是一样的。 |
|
p*****2
发帖数: 21240 | 20
=
左树错误，右树正确，它自己一定是错误的。 |
|
|
i**********e
发帖数: 1145 | 22 好题。OJ 已经加上这题了。
要改动的话只要把 f 初始为 INT_MIN 就可以了。至于空树的情况，特别处理一下就行
。 |
|
Y********f
发帖数: 410 | 23 除了recursion外只能有O(1)的extra space。有什么好的方法。
我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
后找到该节点的下一个节点。但是需要O(lgN)的space。 |
|
i******e
发帖数: 273 | 24 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？ |
|
l*********8
发帖数: 4642 | 25 说说我的想法：
从末尾向前扫描，试图建立一棵BST （不一定要真正建立树结构）
当前节点A[idx]是当前子树的根，同时也维护当前子树的合法数值范围[min_val, max_
val]. 初始数值范围是 [INT_MIN, INT_MAX]。 进入A[idx]的右子树，数值范围就是[
A[idx], old max_val]; 左子树范围是[old min_val, A[idx]]
对于A[idx-1],
如果比A[idx]大，就放到试图放到右子树里面，如果不能满足数值范围, 就返回parent
节点再试。
如果 <= A[idx]，就放到试图放到左子树里面，如果不能, 就返回parent节点再试。
这样一遍扫描数组, 如果所有数值都能合法放进BST，就返回true, 否则false。 |
|
S**I
发帖数: 15689 | 26 ☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Wed Apr 11 09:32:26 2012, 美东) 提到:
BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, ... 阅读全帖 |
|
b***m
发帖数: 5987 | 27 有两个纯文本文件，其中一个较大，大约上万行，每行是一个具体的域名，比如bjhmm.
seattle.washington.usa。另外一个较小，大约一千多行，每行是一个大域名，比如
washington.usa。现在想找到一个较快的算法，迅速判断小文件中的大域名清单是否能
涵盖大文件中的所有域名。我目前想到的是用后缀树或者前缀树，大家有什么好办法？ |
|
e******i
发帖数: 106 | 28 是树那章的。
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum to a given value. Note that a path
can start or end anywhere in the tree.
书上的解法如下：
public void findSumPath(TreeNode root, int sum){
int depth = getDepth(root);
int[] path = new int[depth];
findSumPath(root, path, sum, 0);
}
public void findSumPath(TreeNode root, int[] path, int sum, int level){
if(root == null){
return null;
}
path[level] = root... 阅读全帖 |
|
h******6
发帖数: 2697 | 29 我感觉面试涉及的算法就那么几个，树，stack, queue, 排序，查找，dp。这些基本的
算法我也都明白，也能写出来，虽然当年算法考试没拿A。我觉得给5天时间的话就是得
多做题。因为感觉现在的面试题之前做过才会，不然当时也想不出来。跟中学备考模式
一样。LD认为我应该在这5天看基本算法书，认为一切都源自基础，基础精通了那些题
自然而然面试时候就会了。
各位认为呢？ |
|
r**h
发帖数: 1288 | 30 我觉得与其追求800题，不如先保证能把那些基本的给bug free了。
二分搜索，merge sort, quick sort/select，反转单链表，heapify，二叉树前中后序
层序遍历，前驱后继，stack/queue/hashmap的实现等等
面试中基本上也不会问太难的题。 |
|
L*********g
发帖数: 8 | 31 leftDepth, rightDepth初始化值从哪里来？
对于这样的树，不是complete tree, 但返回结果是true吧.
N
N N
N N |
|
k******4
发帖数: 94 | 32 level order的最大问题就是空间复杂度，指数增长.
试着用DFS写了下，空间复杂度是O(logn)，时间O(n),
//treeDepth 是树的实际高度，desiredDepth是叶子的期望高度。
//当第一次遇到一个比treeDepth高度小一的叶子，把desiredDepth的设置为treeDepth
-1,并且需要后面所有叶子的高度都是这个值。
bool validateCompleteBT(TreeNode*root, const int &treeDepth, int &
desiredDepth, int curDepth, bool &setDesiredDepthFlag)
{
curDepth++;
if(root->left == NULL && root->right == NULL)
{
if(setDesiredDepthFlag && curDepth == (treeDepth-1))
{
setDesiredDepthFlag... 阅读全帖 |
|
j*********6
发帖数: 407 | 33 为什么level traverse 的 space cost 是指数级别的呢？ 不就是O(n) 吗？ 而且
level traverse的 时间复杂度 在 树的高度很高的时候 是很有优势的
个人愚见
treeDepth |
|
z*****4
发帖数: 12 | 34 这题是电面的其中一道。题目不难，不需要写代码，只是从来没见过这么问的，一上来
有点晕，搞了挺长时间才答出来。
什么样的排序算法时间复杂度最差。先说的冒泡排序，O(n^2)。再次的想了一会。发现
通过决策树的方式可以推出来最坏情况是n!。对方问怎么排序才能达到这么次的情况。
想了半天想不出来，后来终于在一再提示下打出来了。就是列举所有可能的情况，知道
其中的一种是排序好的……
时候想想其实也不难，不知是不是刷题脑子刷木了，稍微绕点小弯就想不出来了。 |
|
r********7
发帖数: 102 | 35 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每... 阅读全帖 |
|
r********7
发帖数: 102 | 36 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每... 阅读全帖 |
|
x****g
发帖数: 1512 | 37 需要的是“没有common letter”。
无论字典树或者后缀树对于判定找出无common letter并不优。
将原来的s1....sn用26bit法转化成
A1.....An
对应的最大长度为： V1.....Vn
有两个好处：
1：判定无common letter即为：Ai & Aj == 0;
2：相同bit表示的不同字符串得到压缩，只需要记下长度最长的。
完了按Vn长度排序 N*Log(N)
V'n........V'1
A'n........A'1
从大到小搜索，如果Ai & Aj==0的话，L=V[i]*V[j].
那么大的那个下标就收缩到了k,V[k]>sqrt(L).
整体区间收缩到[l,r]满足
V[i]>V[l]
V[r]>V[j]
平均复杂度能N*Log(N)? ,最差当然还是N^2.
i =0;
j = n;
maxLen = 0;
highLen = INT_MAX;
lowLen = INT_MIN;
while(V[i]>sqrt(maxLen) && (i
{
if(V[i] < highL... 阅读全帖 |
|
l**********1
发帖数: 415 | 38 第一题不会
感觉第二题只能dfs不能dp，因为1）要一个路径作为答案而不是只要一个数字。2）因
为可以四个方向走，所以解的树有环
等待大牛解答 |
|
|
A*****i
发帖数: 3587 | 40 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了 |
|
A*****i
发帖数: 3587 | 41 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了 |
|
b******g
发帖数: 3616 | 42 还没看过答案，我写了个递归做法，可能还有更好的解。递归的思路：
假设当前节点为r，需要先递归将r->left为根的子树upside down并返回最右叶子节点n
。然后将r->right接到n->left，将r接到n->right。由于此时新树的最右叶子节点为r
，返回r供上层递归使用。代码里的newRoot是为了返回整个树upside down后的新的根。
class Solution {
public:
TreeNode *upsideDownBinaryTree(TreeNode *root) {
TreeNode *temp, *newRoot = NULL;
temp = buildUpsideDownBT(root, newRoot);
return newRoot;
}
TreeNode *buildUpsideDownBT(TreeNode *root, TreeNode *&newRoot) {
if(!root) return root;
if(!root... 阅读全帖 |
|
o***c
发帖数: 32 | 43 明显不对，ex: 3 5 1 4 2
应该是使用点树，线段树或树状数组做才能保证O(nlogn)的复杂度。 |
|
x***7
发帖数: 11 | 44
T_T打了很多字回复的时候忘记密码了。。。。然后没了。。。
线段树嘛大概这样，我们建立一个[1..n]这个区间的线段树，每个叶子节点标记为1，
其他节点的值为这个节点下面有多少个为1的叶子节点。
【查找k大】
看左子树有多少个为1的节点，如果大于等于k，那么就在左子树找。如果不到k，那么
就在右子树找k-左子树为1的叶子节点个数。
当你找到相应的叶子节点，那么他表示的区间[l,r](l == r)，l或者r就是我们要找的[
1..n]里面的第k个数啦。
【删除】
就是把那个叶子节点标记为0，其他包含这个节点的区间当然就是num--
代码上面有人也回复了的，大概差不多。
-----
我自己写了个，测了几个简单的数据，不保证是对的。
struct TreeNode {
TreeNode *left, *right;
int val;
int l, r;
TreeNode (int _l, int _r) : l(_l), r(_r), left(nullptr), right(nullptr) {
}
TreeNode (int _val,... 阅读全帖 |
|
a*****2
发帖数: 96 | 45 求最大的s[i]:
//就用二叉树就足够了吧，树的节点里记录比本节点小的个数
public int sln(){
BSTNode root = new BSTNode(a[n-1],0)
int result = 0;
for i in n-2:0{
//O(logn)
result = max(result,insert(root ,a[i],0));
}
return result;
}
class BSTNode{
int value;
int descendants;
BSTNode left = null;
BSTNode right = null;
}
public int insert(BSTNode root, int value, int cnt){
if(root == null)
return 0;
int result = 0;
if(root.value < value){
result += root.descendants+1;
... 阅读全帖 |
|
f********a
发帖数: 367 | 46 电面2：
还是一个国人大哥，LeetCode上的Insert Interval，API稍微有点变化，给的是一个链
表节点。
由于还有时间，还考了一个count tweets的设计题。需要实现如下API：
class CountingSvc {
void tweet(long timestamp, int tweetLength);
double avgLength(long begin, long end, long threshold);
};
另外给了一个hint，TreeMap，让自己customize一下object。
可惜我一看是range query就往线段树上想了，于是给出了如下结构，并解释了原理。
class Node {
long totalLen;
long count;
long begin;
long end;
Node left;
Node right;
}
最后追问了下如何去做模糊处理。我还是在线段树上想，就加了一个threshold。
double avgL... 阅读全帖 |
|
f********a
发帖数: 165 | 47 看到别人的面经：
坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何
edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就
是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区
域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的
id，区域的id自己定。用二叉树。
x,y是两个不同二叉树？Node里面存range? |
|
t*****3
发帖数: 112 | 48 x、y两个线段树，insertX（x）， insertY（y）分别是对应树的插入操作，给定一个
坐标用find(x,y)找到两个叶子节点对应的区间 |
|
M******o
发帖数: 121 | 49 1.判断树是否有cycle。
2.树，每个节点是一个字符，每个分支代表一个字符串，该字符串需要从叶子节点到根
节点，比如根是‘a'，有一个娃是’b'，字符串是‘ba’。
求所有的字符串，要求按字典顺序排列。分析复杂度
3.写lru
4.设计个数据结构可以很容易给出一堆数字的中值
5.设计google drive client |
|
c*******e
发帖数: 621 | 50 就是给一堆树的edge，把树按dfs print出来 |
|
