logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
一道FB的followup 问题
avatar
一道FB的followup 问题# JobHunting - 待字闺中
s*t
1 楼
上个月末从隔壁州dealer那里买二手车，dealer说要交我所在的州的tax，名目上标的
是他们州的tax，将近500刀，但是dealer给了我们一个transfer title的东西，还有临
时的tag 和registratin card，说是让我们自己去本州DMV注册，但是我们已经把注册
的tax交给了dealer了，dealer说交tax这是程序，等他们把tax核实一下没问题会给我
们写张支票寄过来，快一个月了也没收到支票，打电话去问，第一次说支票寄了，一个
礼拜内到，但是都过了两个礼拜还没收到，再打过去问不是hold on 然后自动挂掉，就
是没人接。很担心dealer故意不给这笔钱，请问异州买车的手续一般是什么样子的呢，
大家有没有过这种dealer把支票寄回来的case？
非常感谢！
avatar
c*d
3 楼
可以自己去交或者dealer帮你交
avatar
b*n
4 楼
想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
avatar
z*m
5 楼
我见过的解法，不管是DFS还是用hash的，都需要run一次多余的求最左最右的范围，如
果不让求的话，感觉有点难。
avatar
s*l
6 楼
你在国内 还是美国啊？
为什么总被 老中面
我怎么没这种事呢~

【在 b******n 的大作中提到】
: 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
avatar
b*n
7 楼
我去他妈的twitter面， 四五轮， 反正有三个老中， 把我拒了。 我也不是特别好，
但也不是特别差。。。 一个twitter老中， 看我简历， 还他妈的婉转的说， 你毕业
好多年了啊。。。 意思是， 你年纪好大啊
我去pure storage， 一道iterator和那个processtask的那题， 两个老中， 从
microsoft出来的，一个iterator， 做的一点都没错。 那个process task的题，
unlock没写的最optimal。 然后第二天就说move on
反正如果你不是猥琐男， 或者刚毕业的新鲜中国女逼， 遇到老中， 别想过!

【在 s********l 的大作中提到】
: 你在国内 还是美国啊？
: 为什么总被 老中面
: 我怎么没这种事呢~
avatar
b*n
8 楼
void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);

helper(node.left, m, level-1);
helper(node.right, m, level+1);
}
avatar
p*g
9 楼
这不还是map 的解法吗？

【在 b******n 的大作中提到】
: void helper (TreeNode node, TreeMap m, int level) {
: List nodesAtThisLevel = m.get(level);
: if (nodesAtThisLevel == null) ...
: nodesAtThisLevel.add(node);
:
: helper(node.left, m, level-1);
: helper(node.right, m, level+1);
: }
avatar
p*g
10 楼
我想起来了， 用双向链表。
左子树就向左走，右子树就向右走。 走到头就创建新节点。
不知道对不对？
avatar
h*0
11 楼
目测正确

【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
avatar
z*m
12 楼
烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
啊。
估计被烙印带阴沟。

【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
avatar
w*u
13 楼
牛肉好厉害，这么多家hot的公司
avatar
k*n
14 楼
public class BinaryTree {
TreeNode root;
Vector path;

public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
PrintPath();
path.removeElement(curNode);
};
}
avatar
z*m
15 楼
你这是在打印所有root到path的节点吧，vertical print不是这个意思。
还是谢谢你的code。

【在 k*******n 的大作中提到】
: public class BinaryTree {
: TreeNode root;
: Vector path;
:
: public void FindPath() {
: if (root!=null) FindPath(root);
: };
: public void FindPath(TreeNode curNode) {
: boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
: if (!isLeaf) {
avatar
g*y
16 楼
Follow up 如何做？有人能够详细解释下么？
avatar
w*e
17 楼
只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
avatar
g*y
18 楼
我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。

【在 w******e 的大作中提到】
: 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
avatar
k*r
19 楼
recursive，
用list《List《Integer》》 res纪录结果，
用一个mostleft记录目前最左边的index，
如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
static int mostLeft = 0;
public static void printTreeInVerticalOrder(TreeNode root) {
List> res = new ArrayList<>();
//res.add(new ArrayList());
printHelper(root, 0, res);
printTree(res);
}
public static void printHelper(TreeNode root, int curr, ListInteger>> res) {
if (root == null) return;
else if (curr < mostLeft) {
List list = new ArrayList<>();
list.add(root.val);
res.add(0, list);
mostLeft = curr;
} else if (curr - mostLeft >= res.size()) {
List list = new ArrayList<>();
list.add(root.val);
res.add(list);
} else {
int idx = curr - mostLeft;
List list = res.get(idx);
list.add(root.val);
}
printHelper(root.left, curr - 1, res);
printHelper(root.right, curr + 1, res);
}
public static void printTree(List> res) {
for (List list : res) {
for (Integer i : list) {
System.out.print(i + ",");
}
System.out.println();
}
}
avatar
b*b
20 楼
I feel "cannot use hashmap" is an unnecessary constraint. we will need a
container to store the values anyway (cannot think up a way without use a
container), use hashmap or list of list really doesn't make much difference,
hashmap actually is faster, list of list won't buy you anything, cpu or
memory.

【在 k****r 的大作中提到】
: recursive，
: 用list《List《Integer》》 res纪录结果，
: 用一个mostleft记录目前最左边的index，
: 如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
: static int mostLeft = 0;
: public static void printTreeInVerticalOrder(TreeNode root) {
: List> res = new ArrayList<>();
: //res.add(new ArrayList());
: printHelper(root, 0, res);
: printTree(res);
avatar
k*r
21 楼
hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
list of list多用了点memory ：）

difference,

【在 b******b 的大作中提到】
: I feel "cannot use hashmap" is an unnecessary constraint. we will need a
: container to store the values anyway (cannot think up a way without use a
: container), use hashmap or list of list really doesn't make much difference,
: hashmap actually is faster, list of list won't buy you anything, cpu or
: memory.
avatar
b*b
22 楼
yeah, that's what i'm thinking, hashmap is HashMap>, it'
s almost same as the code in previous post, except use the level as index.

【在 k****r 的大作中提到】
: hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
: list of list多用了点memory ：）
:
: difference,
avatar
g*y
23 楼
我感觉也是，这个constraint应该是没有必要的。

it'

【在 b******b 的大作中提到】
: yeah, that's what i'm thinking, hashmap is HashMap>, it'
: s almost same as the code in previous post, except use the level as index.
avatar
T*U
24 楼
这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 20);
root = insert(root, 70);
root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 7);
root = insert(root, 80);
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, 0);
VerticalOrder(root, 0);
cout <int i, j;
//printing first half
for(i = 100; i >= 0; i--) {
int flag = 0;
for(j = 0; j < v1[i].size(); j++) {
cout << v1[i][j] <flag = 1;
}
if(flag == 1)
cout << endl;
}
// printing second half
for(i = 0; i < 100; i++) {
int flag = 0;
for(j = 0; j < v2[i].size(); j++) {
cout << v2[i][j] <flag = 1;
}
if(flag == 1)
cout << endl;
}
}

onepass

【在 z***m 的大作中提到】
: 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
: 啊。
: 估计被烙印带阴沟。
avatar
t*e
25 楼
这个用java 怎么改写？

【在 T****U 的大作中提到】
: 这应该是烙印的版本，给两个100的vectors
: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 后面问答区一个烙印贴的
: vector v1[100];
: vector v2[100];
: void VerticalOrder(struct BstNode* root, int index) {
: if(!root) return;
: if(index < 0) {
: v1[-1*index].push_back(root->data);
: }
avatar
b*n
27 楼
想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
avatar
z*m
28 楼
我见过的解法，不管是DFS还是用hash的，都需要run一次多余的求最左最右的范围，如
果不让求的话，感觉有点难。
avatar
s*l
29 楼
你在国内 还是美国啊？
为什么总被 老中面
我怎么没这种事呢~

【在 b******n 的大作中提到】
: 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
avatar
b*n
30 楼
我去他妈的twitter面， 四五轮， 反正有三个老中， 把我拒了。 我也不是特别好，
但也不是特别差。。。 一个twitter老中， 看我简历， 还他妈的婉转的说， 你毕业
好多年了啊。。。 意思是， 你年纪好大啊
我去pure storage， 一道iterator和那个processtask的那题， 两个老中， 从
microsoft出来的，一个iterator， 做的一点都没错。 那个process task的题，
unlock没写的最optimal。 然后第二天就说move on
反正如果你不是猥琐男， 或者刚毕业的新鲜中国女逼， 遇到老中， 别想过!

【在 s********l 的大作中提到】
: 你在国内 还是美国啊？
: 为什么总被 老中面
: 我怎么没这种事呢~
avatar
b*n
31 楼
void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);

helper(node.left, m, level-1);
helper(node.right, m, level+1);
}
avatar
p*g
32 楼
这不还是map 的解法吗？

【在 b******n 的大作中提到】
: void helper (TreeNode node, TreeMap m, int level) {
: List nodesAtThisLevel = m.get(level);
: if (nodesAtThisLevel == null) ...
: nodesAtThisLevel.add(node);
:
: helper(node.left, m, level-1);
: helper(node.right, m, level+1);
: }
avatar
p*g
33 楼
我想起来了， 用双向链表。
左子树就向左走，右子树就向右走。 走到头就创建新节点。
不知道对不对？
avatar
h*0
34 楼
目测正确

【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
avatar
z*m
35 楼
烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
啊。
估计被烙印带阴沟。

【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
avatar
w*u
36 楼
牛肉好厉害，这么多家hot的公司
avatar
k*n
37 楼
public class BinaryTree {
TreeNode root;
Vector path;

public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
PrintPath();
path.removeElement(curNode);
};
}
avatar
z*m
38 楼
你这是在打印所有root到path的节点吧，vertical print不是这个意思。
还是谢谢你的code。

【在 k*******n 的大作中提到】
: public class BinaryTree {
: TreeNode root;
: Vector path;
:
: public void FindPath() {
: if (root!=null) FindPath(root);
: };
: public void FindPath(TreeNode curNode) {
: boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
: if (!isLeaf) {
avatar
g*y
39 楼
Follow up 如何做？有人能够详细解释下么？
avatar
w*e
40 楼
只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
avatar
g*y
41 楼
我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。

【在 w******e 的大作中提到】
: 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
avatar
k*r
42 楼
recursive，
用list《List《Integer》》 res纪录结果，
用一个mostleft记录目前最左边的index，
如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
static int mostLeft = 0;
public static void printTreeInVerticalOrder(TreeNode root) {
List> res = new ArrayList<>();
//res.add(new ArrayList());
printHelper(root, 0, res);
printTree(res);
}
public static void printHelper(TreeNode root, int curr, ListInteger>> res) {
if (root == null) return;
else if (curr < mostLeft) {
List list = new ArrayList<>();
list.add(root.val);
res.add(0, list);
mostLeft = curr;
} else if (curr - mostLeft >= res.size()) {
List list = new ArrayList<>();
list.add(root.val);
res.add(list);
} else {
int idx = curr - mostLeft;
List list = res.get(idx);
list.add(root.val);
}
printHelper(root.left, curr - 1, res);
printHelper(root.right, curr + 1, res);
}
public static void printTree(List> res) {
for (List list : res) {
for (Integer i : list) {
System.out.print(i + ",");
}
System.out.println();
}
}
avatar
b*b
43 楼
I feel "cannot use hashmap" is an unnecessary constraint. we will need a
container to store the values anyway (cannot think up a way without use a
container), use hashmap or list of list really doesn't make much difference,
hashmap actually is faster, list of list won't buy you anything, cpu or
memory.

【在 k****r 的大作中提到】
: recursive，
: 用list《List《Integer》》 res纪录结果，
: 用一个mostleft记录目前最左边的index，
: 如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
: static int mostLeft = 0;
: public static void printTreeInVerticalOrder(TreeNode root) {
: List> res = new ArrayList<>();
: //res.add(new ArrayList());
: printHelper(root, 0, res);
: printTree(res);
avatar
k*r
44 楼
hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
list of list多用了点memory ：）

difference,

【在 b******b 的大作中提到】
: I feel "cannot use hashmap" is an unnecessary constraint. we will need a
: container to store the values anyway (cannot think up a way without use a
: container), use hashmap or list of list really doesn't make much difference,
: hashmap actually is faster, list of list won't buy you anything, cpu or
: memory.
avatar
b*b
45 楼
yeah, that's what i'm thinking, hashmap is HashMap>, it'
s almost same as the code in previous post, except use the level as index.

【在 k****r 的大作中提到】
: hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
: list of list多用了点memory ：）
:
: difference,
avatar
g*y
46 楼
我感觉也是，这个constraint应该是没有必要的。

it'

【在 b******b 的大作中提到】
: yeah, that's what i'm thinking, hashmap is HashMap>, it'
: s almost same as the code in previous post, except use the level as index.
avatar
T*U
47 楼
这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 20);
root = insert(root, 70);
root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 7);
root = insert(root, 80);
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, 0);
VerticalOrder(root, 0);
cout <int i, j;
//printing first half
for(i = 100; i >= 0; i--) {
int flag = 0;
for(j = 0; j < v1[i].size(); j++) {
cout << v1[i][j] <flag = 1;
}
if(flag == 1)
cout << endl;
}
// printing second half
for(i = 0; i < 100; i++) {
int flag = 0;
for(j = 0; j < v2[i].size(); j++) {
cout << v2[i][j] <flag = 1;
}
if(flag == 1)
cout << endl;
}
}

onepass

【在 z***m 的大作中提到】
: 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
: 啊。
: 估计被烙印带阴沟。
avatar
t*e
48 楼
这个用java 怎么改写？

【在 T****U 的大作中提到】
: 这应该是烙印的版本，给两个100的vectors
: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 后面问答区一个烙印贴的
: vector v1[100];
: vector v2[100];
: void VerticalOrder(struct BstNode* root, int index) {
: if(!root) return;
: if(index < 0) {
: v1[-1*index].push_back(root->data);
: }
avatar
p*n
49 楼
two vector, leftside and rightside of the root
traverse one pass

【在 z***m 的大作中提到】
: 问题本身是print a tree in vertical order具体如http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 用hashmap很好解决
: 问题来了，follow up要one pass (不能找最左有多远，最右有多远)， 不要hashmap
相关阅读
裁员的话，总是先裁research和dev的请教OPT前三个月没工作的问题求c/c++的embedded相关的面试题有些小公司打着面试的旗号套idea美国就业形势大好, h1b签证名额将很快用完 (转转转转转转转转转转转)Is there some difference of salary with green card?A家的H1B批了要申H1B了，需要改Job Description的学历要求怎么办？nVidia SW Engineer提供Google内部推荐（长期有效）教授在美国，博士后去新加坡？ (转载)关于涉及Export License的问题美國老土的付费课程怎么样？请问OPT和H1B招聘嵌入式控制软件工程师google的码农job security怎么样？ (转载)NV Paypal G F面经（F G onsite我不能透题 对不起）急问：能同时投一个公司两个position吗？环境工程MS，讲讲我的on siteH-1b file了, 能和fragmon要张 receipt notice吗
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。