由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 推特新鲜店面,挂人的节奏啊
相关主题
leetcode上最搞笑的是这题最新L家面经
一道电面题,分享下, 这个题应该用哪几个data structure?好挫的F家面经
Java programming question最近变硬那家的面经
问个google面试题问一道google面经
问两道facebook面试题一个店面题
请教这么一个题:BST maximum sum path问个题
Binary Tree Maximum Path SumG电面一题
贴个自己的答案:Binary Tree Max Path Sum亚麻森店面
相关话题的讨论汇总
话题: int话题: dp话题: child话题: nums话题: max
进入JobHunting版参与讨论
1 (共1页)
D***0
发帖数: 138
1
刚刚店面的,一个老印,口音挺重的,说话好像离电话挺远的,接起电话连个自我介绍
都没有,上来就说来给我说说你的简历吧,我说完后他又问我现在的工作主要是干什么
的,解释了3遍这哥们才算明白,难道就这么浪费我宝贵的45分钟?接下来问如何给一
个网站比如尼玛推特设计一个log系统,如果用户打开尼玛推特什么也没有怎么根据你
的log系统查(心中草泥马奔腾啊),说了一堆后,这厮说ok,快到点了,做道题吧,
11
9 12
4 8 6
2 7 3 1
int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}
valid move: 9 - 4 or 8
invalid : 9 - 11 or 12 or 6
all positive numbers
find max sum in any number of possible moves
38 (11 + 12 + 8 + 7)
就是把树装数组里了,他说你可以是认为是完全三角形。好吧,我就开始说我的思路,
刚写
了如何找到左右子的公式,这厮就迫不及待的打断,说你不用解释,快写吧,我操,我
刚要说我的思路。好吧写了个递归,前序的。然后问了复杂度,一开始我说遍历每个点
,那就是O(n),他说不对,难道是O(nlogn)
看来这是要挂人的节奏啊,尼玛不想要何苦呢。
long findMax(int[] nums) {
if(nums == null || nums.length == 0) return 0;
HashMap map = new HashMap();
map.put("max", 0);
findMax(nums, 0, 0, 1, map);
return map.get("max");
}
void findMax(int[] nums, int root, long sum, int level, HashMap > map)
{
if(root < nums.length)
{
findMax(nums, root+level, sum + nums[root], level+1, map);
findMax(nums, root+level+1, sum + nums[root], level+1, map);
}
else
{
long max = map.get("max");
if(sum > max)
{
map.put("max", sum);
}
}
}
d******s
发帖数: 274
2
lg(n)吧 完全树 等于高度
l*********8
发帖数: 4642
3
这不是完全树。 比如8有两个parents: 9, 12.
你的程序会重复访问同一个节点。

【在 D***0 的大作中提到】
: 刚刚店面的,一个老印,口音挺重的,说话好像离电话挺远的,接起电话连个自我介绍
: 都没有,上来就说来给我说说你的简历吧,我说完后他又问我现在的工作主要是干什么
: 的,解释了3遍这哥们才算明白,难道就这么浪费我宝贵的45分钟?接下来问如何给一
: 个网站比如尼玛推特设计一个log系统,如果用户打开尼玛推特什么也没有怎么根据你
: 的log系统查(心中草泥马奔腾啊),说了一堆后,这厮说ok,快到点了,做道题吧,
: 11
: 9 12
: 4 8 6
: 2 7 3 1
: int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}

l*********8
发帖数: 4642
4
n个节点, 该“树”的高度是O(sqrt(n)).
你的方法的时间复杂度是 O( 2 ^ sqrt(n) )

【在 l*********8 的大作中提到】
: 这不是完全树。 比如8有两个parents: 9, 12.
: 你的程序会重复访问同一个节点。

t**r
发帖数: 3428
5
make sense

【在 l*********8 的大作中提到】
: n个节点, 该“树”的高度是O(sqrt(n)).
: 你的方法的时间复杂度是 O( 2 ^ sqrt(n) )

l*********8
发帖数: 4642
6
写了一个
int maxSum(int A[], int n) {
if (n < 1) return 0;
vector dp(n, 0);
dp[0] = A[0];

int level = 1;
for (int i = 0; i + level < n; i++) {
int child = i+level;
dp[child] = max(dp[child], A[child] + dp[i]);
if (++child < n)
dp[child] = max(dp[child], A[child] + dp[i]);
}

return *max_element(dp.begin(), dp.end());
}

【在 D***0 的大作中提到】
: 刚刚店面的,一个老印,口音挺重的,说话好像离电话挺远的,接起电话连个自我介绍
: 都没有,上来就说来给我说说你的简历吧,我说完后他又问我现在的工作主要是干什么
: 的,解释了3遍这哥们才算明白,难道就这么浪费我宝贵的45分钟?接下来问如何给一
: 个网站比如尼玛推特设计一个log系统,如果用户打开尼玛推特什么也没有怎么根据你
: 的log系统查(心中草泥马奔腾啊),说了一堆后,这厮说ok,快到点了,做道题吧,
: 11
: 9 12
: 4 8 6
: 2 7 3 1
: int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}

D***0
发帖数: 138
7
嗯,就是lc三角型往下走,这会是求最大值,复杂度是你说的。
反正是跪了。

【在 l*********8 的大作中提到】
: 写了一个
: int maxSum(int A[], int n) {
: if (n < 1) return 0;
: vector dp(n, 0);
: dp[0] = A[0];
:
: int level = 1;
: for (int i = 0; i + level < n; i++) {
: int child = i+level;
: dp[child] = max(dp[child], A[child] + dp[i]);

l*****a
发帖数: 14598
8
how do u update level?

【在 l*********8 的大作中提到】
: 写了一个
: int maxSum(int A[], int n) {
: if (n < 1) return 0;
: vector dp(n, 0);
: dp[0] = A[0];
:
: int level = 1;
: for (int i = 0; i + level < n; i++) {
: int child = i+level;
: dp[child] = max(dp[child], A[child] + dp[i]);

l*********8
发帖数: 4642
9
写错了。 Thanks for the catch!

【在 l*****a 的大作中提到】
: how do u update level?
l*********8
发帖数: 4642
10
改了一下lolhaha指出的错误。 也许还有其他错。。。
int maxSum(int A[], int n) {
if (n < 1) return 0;
vector dp(n, 0);
dp[0] = A[0];

int firstInLevel = 0;
int level = 1;
for (int i = 0; i + level < n; i++) {
if (i - firstInLevel == level) {
++level;
firstInLevel = i;
}
int child = i+level;
dp[child] = max(dp[child], A[child] + dp[i]);
if (++child < n)
dp[child] = max(dp[child], A[child] + dp[i]);
}

return *max_element(dp.begin(), dp.end());
}
相关主题
请教这么一个题:BST maximum sum path最新L家面经
Binary Tree Maximum Path Sum好挫的F家面经
贴个自己的答案:Binary Tree Max Path Sum最近变硬那家的面经
进入JobHunting版参与讨论
l*****a
发帖数: 14598
11
这个题是从root走到底,还是说中间任意一段都可以
有负数怎么办

【在 l*********8 的大作中提到】
: 改了一下lolhaha指出的错误。 也许还有其他错。。。
: int maxSum(int A[], int n) {
: if (n < 1) return 0;
: vector dp(n, 0);
: dp[0] = A[0];
:
: int firstInLevel = 0;
: int level = 1;
: for (int i = 0; i + level < n; i++) {
: if (i - firstInLevel == level) {

l*********8
发帖数: 4642
12
题目里写: all positive numbers。 这样, 答案肯定是从root走到某个"leaf"的
sum

【在 l*****a 的大作中提到】
: 这个题是从root走到底,还是说中间任意一段都可以
: 有负数怎么办

f******n
发帖数: 279
13
mark
x******1
发帖数: 155
14
DP题,就是leetcode里面triangle吧,不过那个要求minimum,这个是maximum
j**********3
发帖数: 3211
15
先马克
l********y
发帖数: 1068
16
lz的代码逻辑和复杂度分析确实是正确的,bless.

【在 D***0 的大作中提到】
: 刚刚店面的,一个老印,口音挺重的,说话好像离电话挺远的,接起电话连个自我介绍
: 都没有,上来就说来给我说说你的简历吧,我说完后他又问我现在的工作主要是干什么
: 的,解释了3遍这哥们才算明白,难道就这么浪费我宝贵的45分钟?接下来问如何给一
: 个网站比如尼玛推特设计一个log系统,如果用户打开尼玛推特什么也没有怎么根据你
: 的log系统查(心中草泥马奔腾啊),说了一堆后,这厮说ok,快到点了,做道题吧,
: 11
: 9 12
: 4 8 6
: 2 7 3 1
: int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}

1 (共1页)
进入JobHunting版参与讨论
相关主题
亚麻森店面问两道facebook面试题
这段LIS为啥崩溃?请教这么一个题:BST maximum sum path
定了的G电面不敢去肿么破Binary Tree Maximum Path Sum
一个算法题目贴个自己的答案:Binary Tree Max Path Sum
leetcode上最搞笑的是这题最新L家面经
一道电面题,分享下, 这个题应该用哪几个data structure?好挫的F家面经
Java programming question最近变硬那家的面经
问个google面试题问一道google面经
相关话题的讨论汇总
话题: int话题: dp话题: child话题: nums话题: max