p********n
发帖数: 165 | 1
这个变种是用原数组求 count array 用merge sort做可以。
但反方向，用count array 求原来数组 O(nlogn)比较麻烦，应该分好几步，有一步是
建立一个balanced BST,每个node存储它left subtree的node的个数。 |
|
C******m
发帖数: 213 | 2 here is mine...
(1) build a trie
(2) locate the first node in the trie corresponding to the last character of
the user input string
(3) print out the user input + all the paths in the subtree of this node
e.g.,
a
b c l
d e f
user input: ab
the find b first,
print out
a + all paths(bd, be)
--> abd abe |
|
m****t
发帖数: 23 | 3 stack based approach
TreeNode* buildTreeStack(string &A) {
stack s_nodes;
stack s_operators;
int index = 0;
while (index
if (A[index]=='?') {
s_operators.push(A[index]);
index++;
} else if (A[index]==':') {
if (s_operators.top()=='?') {
s_operators.push(A[index]);
} else {
// pop three things from the s_no... 阅读全帖 |
|
d*******8
发帖数: 23 | 4 版中大多数面经都是针对北美new graduate的, 在此贡献一下本人国内找北美工作的一
些经验吧, 也算是答谢mitbbs上分享面经的朋友对我的帮助. 更希望攒攒人品能够抽到
h1b签证 :)
[背景]
国内4年工作经验. 硕士毕业后一直在某做存储的外企工作.
14年7月份开始有出国打算并开始准备.
[准备]
在工作之余每天坚持至少刷3~4道算法题, 并关注各个公司的blog及github上的开源项
目.
1. 算法
Leetcode自然不必说, 必刷. 先是用了将近两个月的时间把leetcode刷了1.5遍, 然
后每次电面和onsite面之前挑一些觉得做得不好的题再刷.
其次就是看geeksforgeeks上题. 这是个老印host的网站, 但是上面的题目分类明晰
,有很多分类底下的题目非常好, 比如DP (印象最深的就是m个鸡蛋n层楼测在哪层楼鸡
蛋会被摔碎的问题)和graph (印象最深的就是单源/多源最短/最长路径和欧拉环). 每
天看一下还是能学到不少新鲜的知识的.
其他就没有了, career up和glass door也断断续续看了一些, ... 阅读全帖 |
|
d*******8
发帖数: 23 | 5 版中大多数面经都是针对北美new graduate的, 在此贡献一下本人国内找北美工作的一
些经验吧, 也算是答谢mitbbs上分享面经的朋友对我的帮助. 更希望攒攒人品能够抽到
h1b签证 :)
[背景]
国内4年工作经验. 硕士毕业后一直在某做存储的外企工作.
14年7月份开始有出国打算并开始准备.
[准备]
在工作之余每天坚持至少刷3~4道算法题, 并关注各个公司的blog及github上的开源项
目.
1. 算法
Leetcode自然不必说, 必刷. 先是用了将近两个月的时间把leetcode刷了1.5遍, 然
后每次电面和onsite面之前挑一些觉得做得不好的题再刷.
其次就是看geeksforgeeks上题. 这是个老印host的网站, 但是上面的题目分类明晰
,有很多分类底下的题目非常好, 比如DP (印象最深的就是m个鸡蛋n层楼测在哪层楼鸡
蛋会被摔碎的问题)和graph (印象最深的就是单源/多源最短/最长路径和欧拉环). 每
天看一下还是能学到不少新鲜的知识的.
其他就没有了, career up和glass door也断断续续看了一些, ... 阅读全帖 |
|
S********0
发帖数: 5749 | 6 从去年11月份开始，一直在本版向各位大牛取经学习。 最近刚刚接了M家的offer，job
hunting终于告一段落，虽然失败了很多，面试拿的也少，但对于一个非cs phd的背景
，已经很知足了。我背景是engineering，主要就是写code，做模拟，能转行主要是因
为学了些并行计算的东西，研究中写了大量的code，读了我们这个领域的一个famous
open source code，从professional programmer里学到了很多实践经验。 虽然有些经
验，但实际找工作工程中大多数公司理都不会理我，Airbnb一个recruiter跟我说过一
些，大概意思就是说每天收到太多简历，对于非CS学生，仅仅从从简历上很难看出什么
， 所以非CS学生争取能多修几门cs的课，把keyword放上去。不然就像我一样，就是内
推也被拒或者石沉大海，这里面包括了很多本版好心的人帮我内推的，有ebay，
linkedin, twitter, oracle 等。 在这里也想对帮助过我的人说声谢谢，以后我也会
帮助国人。
leetcode是从去年11月份yahoo是onsite失败后开始刷的... 阅读全帖 |
|
S**********n
发帖数: 22 | 7 1. 先post-traversal，把每次经过的点放在stack里面。比如ls的树，假如5是保留的
leaf，那么先把1放到stack里，再把2放到stack里，4也放到stack里，但4的子节点中
不包含5，所以4最终从stack中去掉。
2.找到5。
3.此时stack里面只有1,2。然后pop出下一个元素2,2作为5的left child。用stack中的
下一个node取代2包含5的那个subtree。
4. 重复3直到stack空 |
|
G*****m
发帖数: 5395 | 8 第二题我也碰到了，就是merge吧，最后注意四种颜色同样的subtree要再merge一次
狗狗貌似出的都是大题，如果思路对了，不难，比背题有意思多了 |
|
b*******w
发帖数: 56 | 9 最后一题是问是否有identical subtree? |
|
l****c
发帖数: 782 | 10 面试时遇到的leetcode原体和在板上见过的面经题就不罗列了，贡献下面试中遇到的我
没有见过的题：
故意中英文混杂～
1. 实现一个iterator，可以按照距离原点的曼哈顿距离输出所有的点。－FB
2. 查找binary tree中有多少个uni－valued subtree，uni－valued tree的定义是所
有其中node value值一样。
3. 打印JSON object，object有层层嵌套的。
4. max points in a line, 和leetcode不完全一样，输入包括精度，也就是说要考虑
两个double slope的差值和精度大小。－L
5. 打印一个数的所有factor, 这个出现好多次了，重点是follow up 要cut branch降
低复杂度，然后估计复杂度, 标准答案是O(n3)。－L
可能还有一些，一时想不起来，稍后再update。 |
|
k****r
发帖数: 807 | 11 是recursive吗？
看左边也是uni，右边也是uni，同时他们的val都喝root的一样，就整个夜市uni
uni的定义是null，or 单个val的节点。 |
|
T******7
发帖数: 1419 | 12 写了一个很丑的code.
求拍。
public class uniValueTree {
public int countUniTree(TreeNode root){
if(root.left == null && root.right == null) return 1;
return helper(root);
}
private int helper(TreeNode node){
if(node.left == null && node.right == null){
return 1;
}
if(node.left == null){
if(isUni(node.right)){
if(node.val == node.right.val){
return 1 + helper(node.right);
... 阅读全帖 |
|
f*y
发帖数: 876 | 13 post-order travesal，return the path to the current max in the subtree.
public static void maxPath(TreeNode root) {
if (root == null) return;
ArrayList path = get(root);
System.out.println(path);
}
public static ArrayList get(TreeNode root) {
if (root == null) return null;
ArrayList left = get(root.left);
ArrayList right = get(root.right);
ArrayList list;
if (left == null && ri... 阅读全帖 |
|
s*******r
发帖数: 9 | 14 for this case [5,5,5,5,5,null,5] the tree should be like
5
/
5 5
/
5 5 5
Sorry I still not get your answer.
My understanding is
the bottom three nodes contributes 3
the second left node subtree contribute 1
so the total is 4? |
|
C*********o
发帖数: 119 | 15 hash + stack
hash: key is the parent node, value is the vector of the children nodes
hash can be constructed by traverse the array once. space O(n), time O(n)
stack is used to traverse the subtree. space O(n), time O(n)
Push the first node into stack;
while( stack.size() > 0 ) {
Pop the first node, mark it deleted;
Use the hash to find its children nodes and push them into stack
} |
|
f**********e
发帖数: 288 | 16 上周面的， 全是面金题，
1. 一元二次方
2. dictionary and license plate.
3. html ds
4. frog game
5. remove node subtree, node only has parentid
面试官都在抄代码。。汗， 我哭了， 他们这是要回去找bug吗。。。跪了。。。面试
中， 已指出一推bug来了。。 |
|
k****r
发帖数: 807 | 17 I finished one following the similar idea in LC maxPathInTree. Use a wrapper
to return the current closeMax and farMax of each subTree. At the same time
, calculate the currentMaxPathSum:
public static int maxPath = Integer.MIN_VALUE;
public static int maxJumpPathinTree(TreeNode root) {
maxJumpPathHelper(root);
return maxPath;
}
public static SumWrapper maxJumpPathHelper(TreeNode root) {
if (root == null) return new SumWrapper(0, 0);
SumWrapper left = ... 阅读全帖 |
|
k****r
发帖数: 807 | 18 I finished one following the similar idea in LC maxPathInTree. Use a wrapper
to return the current closeMax and farMax of each subTree. At the same time
, calculate the currentMaxPathSum:
public static int maxPath = Integer.MIN_VALUE;
public static int maxJumpPathinTree(TreeNode root) {
maxJumpPathHelper(root);
return maxPath;
}
public static SumWrapper maxJumpPathHelper(TreeNode root) {
if (root == null) return new SumWrapper(0, 0);
SumWrapper left = ... 阅读全帖 |
|
c*********y
发帖数: 135 | 19 这是我写的代码。大体测了下。
class Solution {
public:
int helper(TreeNode * root, int &global_max){
//this returns max value of the subtree root
//global_max is the results value we are looking for
if(root==NULL)return 0;
int left = max(0,helper(root->left, global_max)); // the key point
is here that we make the return value always larger than or equal to zero.
int right = max(0,helper(root->right, global_max));
int left_next = root->left?max(helper(root->le... 阅读全帖 |
|
D***0
发帖数: 138 | 20 网上投的，一开始是做online的两道题，一个是求树的Amplitude
In a binary tree T, a path P is a non-empty sequence of nodes of tree such
that, each consecutive node in the sequence is a subtree of its preceding
node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two
paths, while [12, 8, 2] is not. The amplitude of path P is the maximum
difference among values of nodes on path P. The amplitude of tree T is the
maximum amplitude of all paths in T. When the tree is empty, it contains no
path, and its ampl... 阅读全帖 |
|
发帖数: 1 | 21 Largest BST Subtree 的 best solution， 哪位大神给我讲讲最后那个 result 是怎
么构造的？为什么是那么构造的？
public class Solution {
class Result {
int res;
int min;
int max;
public Result(int res, int min, int max) {
this.res = res;
this.min = min;
this.max = max;
}
}
public int largestBSTSubtree(TreeNode root) {
Result res = BSTSubstree(root);
return Math.abs(res.res);
}
private Result BSTSubstree(TreeNode root) {
... 阅读全帖 |
|
发帖数: 1 | 22 534 Design TinyURL 0.0% Medium
283 Move Zeroes 50.7% Easy
301 Remove Invalid Parentheses 35.5% Hard
273 Integer to English Words 22.4% Hard
621 Task Scheduler 42.4% Medium
67 Add Binary 33.2% Easy
325 Maximum Size Subarray Sum Equals k 43.1% Medium
689 Maximum Sum of 3 Non-Overlapping Subarrays 41.2% Hard
253 Meeting Rooms II 39.3% Medium
17 Letter Combinations of a Phone Number 35... 阅读全帖 |
|
发帖数: 1 | 23 我的名字叫雷锋。My name is Feng Lei.
# Title Solution Acceptance Difficulty Frequency
2
Add Two Numbers 28.2% Medium
3
Longest Substring Without Repeating Characters 24.5% Medium
535
Encode and Decode TinyURL 74.0% Medium
5
Longest Palindromic Substring 25.2% Medium
15
3Sum 21.8% Medium
238
Product of Array Except Self 50.0% Medium
17
Letter Combinations of a Phone Number ... 阅读全帖 |
|
d**********o
发帖数: 1321 | 24 报告：Decision Tree
// CS570 05/08/2013
// me~me~me~~!!! Project 4 Decision Trees
Decision Prediction for Robot Decisions
Abstract
In this project, a decision tree algorithm is developed using the ID3
information gain algorithm, and it was implemented using c++ language. The
algorithm selects decision split attributes based on information gain, and
selects the variable with highest information gain from the available
variable attribute open list. The algorithm wil... 阅读全帖 |
|
d**********o
发帖数: 1321 | 25 第二次作业
我以为自己对这门课的戒备心到第一个项目交上去就可以平复了，可我高兴得还太早，
到了第二个项目时，subproject2a, subproject2b也都还是很简单的，可到了写最后一
个项目的时候，就赫然发现subproject2a写的copy subtree的函数prototype并不满足
最后一个小版块的要求，于是对我来说，这个项目的最后一小版块就需要从头再来（重
新再了更好用的copy函数）。
写到这个项目的最后一步，就真正体会老师基础代码的良苦用心，没有这个葫芦的存在
，不知道有多少人能真正完成这个项目（至少我也还是有所倚耐的），每一步都不难，
但很tedious~~ 比如，我想sub-tree mutation, mutation 的 terminal 与 non-
terminal 的比例分别是 10% & 90% respectively。这个很好控制，就是概率嘛；可在
90%里，我产生non-terminal sub-tree mutation 节点的方法是先产生随机数，再根据
随机数去寻找定位那个节点(把 root 数为1)，返回指向这个节点的指针，和指向该... 阅读全帖 |
|
d**********o
发帖数: 1321 | 26 报告：Decision Tree
// CS570 05/08/2013
// me~me~me~~!!! Project 4 Decision Trees
Decision Prediction for Robot Decisions
Abstract
In this project, a decision tree algorithm is developed using the ID3
information gain algorithm, and it was implemented using c++ language. The
algorithm selects decision split attributes based on information gain, and
selects the variable with highest information gain from the available
variable attribute open list. The algorithm wil... 阅读全帖 |
|
d**********o
发帖数: 1321 | 27 第二次作业
我以为自己对这门课的戒备心到第一个项目交上去就可以平复了，可我高兴得还太早，
到了第二个项目时，subproject2a, subproject2b也都还是很简单的，可到了写最后一
个项目的时候，就赫然发现subproject2a写的copy subtree的函数prototype并不满足
最后一个小版块的要求，于是对我来说，这个项目的最后一小版块就需要从头再来（重
新再了更好用的copy函数）。
写到这个项目的最后一步，就真正体会老师基础代码的良苦用心，没有这个葫芦的存在
，不知道有多少人能真正完成这个项目（至少我也还是有所倚耐的），每一步都不难，
但很tedious~~ 比如，我想sub-tree mutation, mutation 的 terminal 与 non-
terminal 的比例分别是 10% & 90% respectively。这个很好控制，就是概率嘛；可在
90%里，我产生non-terminal sub-tree mutation 节点的方法是先产生随机数，再根据
随机数去寻找定位那个节点(把 root 数为1)，返回指向这个节点的指针，和指向该... 阅读全帖 |
|
|
发帖数: 1 | 29 学校没有买SIAM的数据库，一片早年的论文求 pdf 全文
Frank Ruskey, Listing and Counting Subtrees of a Tree, SIAM Journal on
Computing, vol. 10, no. 1, pp:141-150, 1981
Link:
http://epubs.siam.org/doi/abs/10.1137/0210011
[email protected]/* */
万分感谢！ |
|
d****n
发帖数: 130 | 30 /* Inserts the node pointed to by "newNode" into the subtree rooted at "tre
eNode" */
void InsertNode(Node *&treeNode, Node *newNode)
{
if (treeNode == NULL)
treeNode = newNode;
else if (newNode->key < treeNode->key)
InsertNode(treeNode->left, newNode);
else
InsertNode(treeNode->right, newNode);
}
The above "destructive" procedural variant modifies the tree in place. It us
es only constant space, but the previous version of the tree is lost.
我不懂为什么是destructive |
|
k*****2
发帖数: 252 | 31 记得本科教材的数据结构里就有简单的用binary tree来实现tree
binary tree的left指向subtree，而right指向的是sibling |
|
c****e
发帖数: 1453 | 32 If you put the whole thing in memory, it's best. Or you can put your trie db
on SSD. The disk IO response will be much much better. The uniram, bigram,
N-gram subtrees are essentially a hash-map based cache. You can tweak that
later.
For your complete trie When the depth is larger than a threshold, at each node you can remember top 5 from its children. Since you rebuild the whole thing everyday, computiation is not a concern. You can adjust the threshold to manage storage whithin your budget.
To... 阅读全帖 |
|
p**o
发帖数: 3409 | 33
Below is some BST C code that I wrote in the past.
In the iterative version (O(1) space), finding the successor
of a given node is definitely not an O(1) time operation.
Recursion would trade space for time though.
/* Binary Search Tree struct */
typedef struct node {
int value;
struct node * parent;
struct node * left;
struct node * right;
} node_t;
/* Find the smallest node from a given subtree. */
node_t * min (node_t * n)
{
if (!n) return NULL;
while (n->left) n = n... 阅读全帖 |
|
p**o
发帖数: 3409 | 34
Below is some BST C code that I wrote in the past.
In the iterative version (O(1) space), finding the successor
of a given node is definitely not an O(1) time operation.
Recursion would trade space for time though.
/* Binary Search Tree struct */
typedef struct node {
int value;
struct node * parent;
struct node * left;
struct node * right;
} node_t;
/* Find the smallest node from a given subtree. */
node_t * min (node_t * n)
{
if (!n) return NULL;
while (n->left) n = n... 阅读全帖 |
|
|
h*i
发帖数: 3446 | 36 基本属实。几个月以前我的一个post解释过为什么ClojureScript人士会喜欢这个：
react js的这个模式类似于3D图形学里面的渲染方法, 每个frame要重新画，为了效率
，需要只重新画在frame之间发生了变化的那部分数据结构，也就是需要一个diffing算
法。
如果数据是immutable的话，这个diffing算法就可以变的很简单和高效率。因为，在
immutable数据结构里面（也就是一个巨大的trie），如果你有一个node的先后两个
references, 你比较这两个references, 如果现在这两个reference的值是一样的，那
么，你不用遍历这个node下面的结构就可以知道，以这个node为根的整个结构都是没有
变化的，所以diffinng很高效，比一下指针，如果一样，整一个subtree就可以被砍掉
了，不用遍历。 |
|
|
k*******d
发帖数: 1340 | 38 第三题是6/11吗？觉得有点没把握，凭感觉是6/11
1.存储方式，access方式，插入删除复杂度
2.找第二大，那干脆扫描两次,2n
4.derived 还是abstract,不能create object
5.做一次遍历，对每个subtree如果那个node在sub tree中，就print root
这种FO developer 是IT的position还是FO的啊？ |
|
r******n
发帖数: 81 | 39 我设计的一个app，最外面是一个UITabView，第一个Tab里放了一个UITableView，用来
显示一个列表，点击列表的一项，可以打开详细的View。一切都是好好的，从tab到
list到detail，然后返回list。
后来吧，我就加了一个search bar controller在那个TableView里面。先开始是search
的results里面的cell不能点击，后来看了网上的资料后加了关于segus处理的代码好了
，但是现在有个问题，就是从detail返回的时候会crash，报告的错误是navigation
subtree corupted。感觉是detail view被push了多次，但是又没有找到是哪里。
有没有遇到过相同情况的？ |
|
