D****3
发帖数: 611 | 1 刚看板上一大牛的帖说 Amazon的SDE1 onsite没人指望你DP 背包问题和longest
common substring只要暴力解就行了 这个真的假的啊？ |
w****x
发帖数: 2483 | 2 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数), 不过很简单了.
还有一题是输出random permutation, 也要求O(n),
Longest Increasing subsequence nlogn就可以了
都是常见题 |
D****3
发帖数: 611 | 3
大神 吃午饭的时候 要注意什么。。。有人一直问你问题么 还是你得主动和附近吃饭
的都打成一片
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
C***U
发帖数: 2406 | 4 第一个bottum up?
第二个shuffle algorithm?
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
w****x
发帖数: 2483 | |
w****x
发帖数: 2483 | 6
对啊,简单吧
【在 C***U 的大作中提到】
: 第一个bottum up?
: 第二个shuffle algorithm?
|
C***U
发帖数: 2406 | 7 要写对也不简单哦。。。你拿到他们家offer了？
【在 w****x 的大作中提到】
:
: 对啊,简单吧
|
D****3
发帖数: 611 | 8
准备哪些问题问 才能让他们感觉到你是非常想进amazon的？ 然后现在amazon的核心产
品是哪些呢？
【在 w****x 的大作中提到】
: 午饭别想吃好了, 一边吃一边问
|
p*****2
发帖数: 21240 | 9
我真不认可。你说人家都给最优解，你给暴力的，难道给你offer不给别人？
【在 D****3 的大作中提到】
: 刚看板上一大牛的帖说 Amazon的SDE1 onsite没人指望你DP 背包问题和longest
: common substring只要暴力解就行了 这个真的假的啊？
|
w****x
发帖数: 2483 | 10
AWS啦, 我觉得Kindle都不是很好. 貌似AWS才2个月recruiter就说没位置了.
你就说你想去internet company, 传统软件公司都不考虑的, (主要是FB， google，
Twitter搞不定，哈哈)
【在 D****3 的大作中提到】
:
: 准备哪些问题问 才能让他们感觉到你是非常想进amazon的？ 然后现在amazon的核心产
: 品是哪些呢？
|
|
|
p*****2
发帖数: 21240 | 11
AWS也不一定都好吧？得进核心组才行吧？
【在 w****x 的大作中提到】
:
: AWS啦, 我觉得Kindle都不是很好. 貌似AWS才2个月recruiter就说没位置了.
: 你就说你想去internet company, 传统软件公司都不考虑的, (主要是FB， google，
: Twitter搞不定，哈哈)
|
w****x
发帖数: 2483 | 12
哎~~~~ 就像你说的看具体的小环境了， 进核心组做烂活也没用，
最保险的是选一个做新项目的组，其他都是扯淡。 要给个front end的可以直接辞职了
【在 p*****2 的大作中提到】
:
: AWS也不一定都好吧？得进核心组才行吧？
|
w****x
发帖数: 2483 | 13
bar raiser有要求用DP， 看面试的组。都给brutal force哪成
【在 D****3 的大作中提到】
: 刚看板上一大牛的帖说 Amazon的SDE1 onsite没人指望你DP 背包问题和longest
: common substring只要暴力解就行了 这个真的假的啊？
|
D****3
发帖数: 611 | 14
比方说aws吧 怎么问面试官问题 才能让他看出来 你是精心准备过的。。。多谢！
【在 w****x 的大作中提到】
:
: bar raiser有要求用DP， 看面试的组。都给brutal force哪成
|
w****x
发帖数: 2483 | 15
不用谢， 因为我不知道， 嘿嘿 =o=
【在 D****3 的大作中提到】
:
: 比方说aws吧 怎么问面试官问题 才能让他看出来 你是精心准备过的。。。多谢！
|
c*****a
发帖数: 808 | 16 什么是shuffle algorithm啊 random permutation
能说说吗 |
w****x
发帖数: 2483 | 17
a[0] .... a[n]
a[0]随机和0...n的单元swap
然后
a[1]随机和1...n的单元swap
然后
a[2]随机和2...n的单元swap
....
如此类推
【在 c*****a 的大作中提到】
: 什么是shuffle algorithm啊 random permutation
: 能说说吗
|
c*****a
发帖数: 808 | 18 int i = 0,index;
while i
index = 10*rand(n-i)
swap(a[i],a[index])
i++
大概这样? |
g*****e
发帖数: 282 | 19 “Longest Increasing subsequence nlogn就可以了”是极限了，容易想到的是DP O(N
^2)
"找树的unival个数(就是这个节点开始所有子树都一样的节点数)“这类题用递归写就
可以了吧，不用搞stack？
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
w****x
发帖数: 2483 | 20
(N
说错了O(n^2)就可以了
unival不用stack啊
【在 g*****e 的大作中提到】
: “Longest Increasing subsequence nlogn就可以了”是极限了，容易想到的是DP O(N
: ^2)
: "找树的unival个数(就是这个节点开始所有子树都一样的节点数)“这类题用递归写就
: 可以了吧，不用搞stack？
|
|
|
s***y
发帖数: 203 | 21 求教他家设计题咋答？
【在 w****x 的大作中提到】
:
: (N
: 说错了O(n^2)就可以了
: unival不用stack啊
|
h*********n
发帖数: 46 | 22 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数), 不过很简单了.
这题你能说清楚点吗，没太明白意思，写个代码看看，谢谢！
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
c*****a
发帖数: 808 | 23
我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数), 不过很简单了.
这题英文是啥，有些词看不懂
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
w****x
发帖数: 2483 | 24
1
2 3
2 2 1 1
1 11
8个unival
2 2 2 1 1 1 1 1
【在 h*********n 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 这题你能说清楚点吗，没太明白意思，写个代码看看，谢谢！
|
e****e
发帖数: 418 | 25 我没看出来8个unival, 只看出来３个２，４个１。
【在 w****x 的大作中提到】
:
: 1
: 2 3
: 2 2 1 1
: 1 11
: 8个unival
: 2 2 2 1 1 1 1 1
|
g*****e
发帖数: 282 | 26 嗯。这样应该就可以了
int count=0
getNodeNum(root);
output(count);
int getNodeNum(node root)
{
if (root == null)
{
return 0;
}
int numOfNodesFromLeft = getNodeNum(root.left);
int numOfNodesFromRight = getNodeNum(root.right);
if (numOfNodesFromLeft == numOfNodesFromRight)
{
count++;
}
return numOfNodesFromLeft + numOfNodesFromRight + 1; }
【在 w****x 的大作中提到】
:
: 1
: 2 3
: 2 2 1 1
: 1 11
: 8个unival
: 2 2 2 1 1 1 1 1
|
e********3
发帖数: 229 | 27 找树的unival个数(就是这个节点开始所有子树都一样的节点数)
可以详细说下题意吗？ |
e********3
发帖数: 229 | 28 如果是这样呢?
1
2 3
2 2 1 1
3 3 1 1 1 |
p*****2
发帖数: 21240 | 29
这个肯定不行吧？
【在 g*****e 的大作中提到】
: 嗯。这样应该就可以了
: int count=0
: getNodeNum(root);
: output(count);
: int getNodeNum(node root)
: {
: if (root == null)
: {
: return 0;
: }
|
p*****2
发帖数: 21240 | 30
7
【在 e********3 的大作中提到】
: 如果是这样呢?
: 1
: 2 3
: 2 2 1 1
: 3 3 1 1 1
|
|
|
p*****2
发帖数: 21240 | 31 null return 0
leaf return 1
l=dfs(left)
r=dfs(right)
ans=l+r
以下情况ans+1
left && right && l && r && left.val=root.val && right.val==root.val
left && !right && l && left.val==root.val
right && !left && right.val=root.val |
e********3
发帖数: 229 | 32
7是指 3 3 1 1 1 1 1 吧。就是子树里的每一个值都要和此根节点值一样是吧？如果把
3换成4应该还是7吧？因为所有叶子节点都应该是单独一个的
【在 p*****2 的大作中提到】
: null return 0
: leaf return 1
: l=dfs(left)
: r=dfs(right)
: ans=l+r
: 以下情况ans+1
: left && right && l && r && left.val=root.val && right.val==root.val
: left && !right && l && left.val==root.val
: right && !left && right.val=root.val
|
p*****2
发帖数: 21240 | 33
看我上边的解
leaf return 1
【在 e********3 的大作中提到】
:
: 7是指 3 3 1 1 1 1 1 吧。就是子树里的每一个值都要和此根节点值一样是吧？如果把
: 3换成4应该还是7吧？因为所有叶子节点都应该是单独一个的
|
q****x
发帖数: 7404 | 34 找树的unival个数(就是这个节点开始所有子树都一样的节点数)
啥意思。
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
w****x
发帖数: 2483 | 35
就是一个树， 如果一个节点代表的子树所有节点都和这个节点值一样那么这个节点就
算一个unival
3
2 3
2 2 3
2 2 2 3 3 五个
【在 q****x 的大作中提到】
: 找树的unival个数(就是这个节点开始所有子树都一样的节点数)
: 啥意思。
|
q****x
发帖数: 7404 | 36
不懂。这不是四个吗？三个叶节点加三个2的子树。
【在 w****x 的大作中提到】
:
: 就是一个树， 如果一个节点代表的子树所有节点都和这个节点值一样那么这个节点就
: 算一个unival
: 3
: 2 3
: 2 2 3
: 2 2 2 3 3 五个
|
p*****2
发帖数: 21240 | 37
3有两个树符合条件。 话说回来，大牛怎么又开始做题了。
【在 q****x 的大作中提到】
:
: 不懂。这不是四个吗？三个叶节点加三个2的子树。
|
w****x
发帖数: 2483 | 38
你都做了两年了。。。。
【在 p*****2 的大作中提到】
:
: 3有两个树符合条件。 话说回来，大牛怎么又开始做题了。
|
p*****2
发帖数: 21240 | 39
这可是造谣呀。我基本上刚刚一年吧。
【在 w****x 的大作中提到】
:
: 你都做了两年了。。。。
|
h****n
发帖数: 1093 | 40 第一题
vector GetNumOfUnival(TreeNode * root)
{
vector res;
helper(root, res);
return res;
}
int helper(TreeNode * root, vector & res)
{
if(root==NULL)
return 0;
int leftNum = helper(root->left);
int rightNUm = helper(root->right);
if(leftNum==-1||rightNum==-1)
return -1;
else if(leftNum!=rightNum)
return -1;
else
{
res.push_back(root);
return leftNum+rightNum+1;
}
}
第二题
string GetRandomPermutation(string input)
{
int i;
int tmpIndex;
srand(time(NULL));
for(i=input.size()-1;i>=0;i--)
{
tmpIndex = rand()%(i+1);
swap(input[i],input[tmpIndex]);
}
return input;
}
【在 w****x 的大作中提到】
: 我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
: 一样的节点数), 不过很简单了.
: 还有一题是输出random permutation, 也要求O(n),
: Longest Increasing subsequence nlogn就可以了
: 都是常见题
|
|
|
l*****a
发帖数: 14598 | 41 冒昧的问一下，你第一次做就想处这个答案了吗？
【在 w****x 的大作中提到】
:
: 你都做了两年了。。。。
|
h****n
发帖数: 1093 | 42 和值有关系么，理解错了，以为是所有子树一样的节点，不过道理都一样
代码如下
vector GetAllUnivalNodes(TreeNode * root)
{
vector res;
helper(root, res);
return res;
}
bool helper(TreeNode * root, vector & res)
{
if(root==NULL)
return true;
bool leftRes = helper(root->left, res);
bool rightRes = helper(root->left, res);
if(!leftRes||!rightRes)
return false;
if(root->left&&root->val!=root->left->val)
return false;
if(root->right&&root->val!=root->right->val)
return false;
res.push_back(root);
return true;
}
【在 w****x 的大作中提到】
:
: 你都做了两年了。。。。
|
h****n
发帖数: 1093 | 43 careercup 150上的原题，没什么好说的
编程珠玑上也有说这题
【在 l*****a 的大作中提到】
: 冒昧的问一下，你第一次做就想处这个答案了吗？
|
g*****e
发帖数: 282 | 44 看了讨论，题意理解错了 =)
【在 p*****2 的大作中提到】
:
: 这可是造谣呀。我基本上刚刚一年吧。
|
h****n
发帖数: 1093 | 45 估计你最初的理解的跟我一样，理解成所有子节点的左右子树节点数一样。
【在 g*****e 的大作中提到】
: 看了讨论，题意理解错了 =)
|
l*****a
发帖数: 14598 | 46 你看上面的题不想想，直接看答案？
【在 h****n 的大作中提到】
: careercup 150上的原题，没什么好说的
: 编程珠玑上也有说这题
|
h****n
发帖数: 1093 | 47 当然想了，这个算法是标准算法，而且很好证明随机性
设1到N个数，易证明每个数在放在每个位置上的概率是相等的
初始对于任意一个数，第一次被选上的概率是1/N
对于第二个数，第一次没被选上的概率是(N-1)/N,第二次选上的概率是1/(N-1)
乘起来概率还是1/N
以此类推
易证明每个数每次被选上的概率是一样的
【在 l*****a 的大作中提到】
: 你看上面的题不想想，直接看答案？
|
l*****a
发帖数: 14598 | 48 就是说你当时一看题就想到了,right?
【在 h****n 的大作中提到】
: 当然想了，这个算法是标准算法，而且很好证明随机性
: 设1到N个数，易证明每个数在放在每个位置上的概率是相等的
: 初始对于任意一个数，第一次被选上的概率是1/N
: 对于第二个数，第一次没被选上的概率是(N-1)/N,第二次选上的概率是1/(N-1)
: 乘起来概率还是1/N
: 以此类推
: 易证明每个数每次被选上的概率是一样的
|
h****n
发帖数: 1093 | 49 也看了提示
其实和抽签是一个道理，先抽后抽的概率是一样的
【在 l*****a 的大作中提到】
: 就是说你当时一看题就想到了,right?
|
w****x
发帖数: 2483 | 50
这个和Google的无限输入流随机取一样
【在 l*****a 的大作中提到】
: 冒昧的问一下，你第一次做就想处这个答案了吗？
|
