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出来 |
|