k*****7
发帖数: 72 | 1 找Maximum sum of non-conjoint subsets of a integer array,non-conjoint就是
说所选择的两个item在原数组中不相邻， 比如【1,2,3,4,5】，选5就不能选4，选3就
不能选
2,4。。。。这个case的结果就应该是9，选【1,3,5】. （全负数数组，取空集子集，
结果为
0）。
这道题给我的时候大概只剩10分钟了，我连第一版都没写完。。。。。请教谁有比较好
的解法？
实在很想抱怨一下，版里潜水很久了，看了很多前辈们的面经，但我phone interview
和on-site
的时候总是遇不到大家常讨论到的经典算法、经典数据结构或者其变形，比如BST，
HashMap，
LinkedList什么的，这些题我基本都能一次写对，有点tricky的变形题也能有思路，不
一定直接
就是最优但可马上写个解出来。可我实际遇到的，从第一轮电面起要么是很high level
的设计题要
么是繁琐的编程。。。都是fresh grad无工作经验咋待遇就不能一样呢？？？
提供最近遇到的其他一些还记得的题给大家参考，攒攒人品。倒是比上一个好些，我都
当场做出来
了，但有的是在提示下做的：
1.实现文本（以String形式）在一定宽度的窗口散列对其（在本行内所有单词间均匀的
增加空白
符），散列成的段落，最后一行左对齐。这个不难，就是coding很繁。。。
2.实现tree的iterator的next（）方法，o(n)。先序怎么做，中序怎么做。
3.设计一个购物网站中的“购物车功能”，支持大量用户，用户购物流程不一定，可将
商品加入或移出
自己的购物车，要求可靠性和“结账”时迅速响应。用什么数据结构，系统怎么设计以
满足可靠性和快
速响应，每个用户的“购物车”数据存储在哪里，这样设计的优点缺点trade off
4.给公式：
F(X,K) = A[K]*X + B[K]
U(X) = max { F(X,K) : 0 <= K < N }
D(X) = min { F(X,K) : 0 <= K < N }
S(X) = U(X) - D(X)
实现一个方法：double minfuds(int[] A, int[] B);
that given two arrays A and B returns the minimum value of S(X) where X
can be any real number. | b******n
发帖数: 4509 | 2 这题简单的递归就可以吧，代码应该不难：
intpu arr[0]...arr[n]
f(n) = max (f(n-1), arr[n] + f(n-2))
interview
level
【在 k*****7 的大作中提到】
: 找Maximum sum of non-conjoint subsets of a integer array,non-conjoint就是
: 说所选择的两个item在原数组中不相邻， 比如【1,2,3,4,5】，选5就不能选4，选3就
: 不能选
: 2,4。。。。这个case的结果就应该是9，选【1,3,5】. （全负数数组，取空集子集，
: 结果为
: 0）。
: 这道题给我的时候大概只剩10分钟了，我连第一版都没写完。。。。。请教谁有比较好
: 的解法？
: 实在很想抱怨一下，版里潜水很久了，看了很多前辈们的面经，但我phone interview
: 和on-site
| k*****7
发帖数: 72 | 3 解释一下？
另外忘了说，数组元素不是有序的
【在 b******n 的大作中提到】
: 这题简单的递归就可以吧，代码应该不难：
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level
| b******n
发帖数: 4509 | 4 根据最后一个数字选还是不选分成两种情况
【在 k*****7 的大作中提到】
: 解释一下？
: 另外忘了说，数组元素不是有序的
| r********r
发帖数: 2912 | 5 f(n)=max(f(n-2)+a(n), //if a(n) is contained,
f(n-1)) //if a(n) is not contained,
Base case:
f(2)=max(a(1),a(2))
f(1)=a(1)
【在 k*****7 的大作中提到】
: 解释一下？
: 另外忘了说，数组元素不是有序的
| k*****7
发帖数: 72 | 6 很好。是我之前想歪，分了3个一组去递归所以判断不完。。。。
代码贴下来抛砖了：
int MNCS(int a[]){
if(a==null)
return 0;
else if(a.length>2)
return
Math.max((a[0]>0?a[0]:0)+MNCS_helper(a,2), MNCS_helper(a,1));
else if(a.length == 2)
return Math.max(0, Math.max(a[0], a[1]));
else if(a.length == 1 && a[0]>0)
return a[0];
else
return 0;
}
int MNCS_helper(int[] a, int i) {
if(i == a.length-1)
return a[i]>0?a[i]:0;
else if (i == a.length-2)
return
0>(a[i]>a[i+1]?a[i]:a[i+1])?0:(a[i]>a[i+1]?a[i]:a[i+1]);
else
return
Math.max(0,Math.max((a[i]>0?a[i]:0)+MNCS_helper(a,i+2),
MNCS_helper(a,i+1)));
}
【在 r********r 的大作中提到】
: f(n)=max(f(n-2)+a(n), //if a(n) is contained,
: f(n-1)) //if a(n) is not contained,
:
: Base case:
: f(2)=max(a(1),a(2))
: f(1)=a(1)
| g***y
发帖数: 764 | 7 ur codes are pretty weird and messy...
if you need a MNCS_helper (for recursive purpose), you should put main
logic there, and make your main method as clean as possible..
【在 k*****7 的大作中提到】
: 很好。是我之前想歪，分了3个一组去递归所以判断不完。。。。
: 代码贴下来抛砖了：
: int MNCS(int a[]){
: if(a==null)
: return 0;
: else if(a.length>2)
: return
: Math.max((a[0]>0?a[0]:0)+MNCS_helper(a,2), MNCS_helper(a,1));
: else if(a.length == 2)
: return Math.max(0, Math.max(a[0], a[1]));
| g*********s
发帖数: 1782 | 8 复杂度不低。不过估计楼主写递归就够了。
【在 b******n 的大作中提到】
: 这题简单的递归就可以吧，代码应该不难：
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level
| g*********s
发帖数: 1782 | 9 1.实现文本（以String形式）在一定宽度的窗口散列对其（在本行内所有单词间均匀的
增加空白符），散列成的段落，最后一行左对齐。这个不难，就是coding很繁。
2.实现tree的iterator的next（）方法，o(n)。先序怎么做，中序怎么做。 | d*****o
发帖数: 28 | 10 The question is hard and challenging, although it's hard at first, if you
can learn from it, you will have a good result.
your rp will accumulate and more chance in the future you will get easy
question.
>> Maximum sum of non-conjoint subsets of a integer array,non-conjoin
Is a DP problem
>> 1.实现文本（以String形式）在一定宽度的窗口散列对其（在本行内所有单词间均
匀的 增加空白
is also DP
>>3.设计一个购物网站中的“购物车功能”，支持大量用户，用户购物流程不一定，可将
商品加入或移出
自己的购物车，要求可靠性和“结账”时迅速响应。用什么数据结构，系统怎么设计以
满足可靠性和快
速响应，每个用户的“购物车”数据存储在哪里，这样设计的优点缺点trade off
is very hard design problem. Data structure: for Shopping cart, use hash
table, each user has a unique key associated with a shopping cart.
Shopping cart is a collection of items - can be represented by list,set,etc.
for large scale, the hash table may be distributed in different machine, use
distributed hash table / consistent hashing.
The system should always take the order, use queue to handle transaction
process. use eventual consistence to resolve the conflicts in transaction
4.给公式：
F(X,K) = A[K]*X + B[K]
U(X) = max { F(X,K) : 0 <= K < N }
D(X) = min { F(X,K) : 0 <= K < N }
S(X) = U(X) - D(X)
实现一个方法：double minfuds(int[] A, int[] B);
that given two arrays A and B returns the minimum value of S(X) where X
can be any real number.
seems also a DP | | | b*******8
发帖数: 37364 | 11 这个应该是最佳解答了，程序也简单，循环一次就行了，出错不容易。
【在 b******n 的大作中提到】
: 这题简单的递归就可以吧，代码应该不难：
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level
| m**********r
发帖数: 122 | 12
这个DP 是怎么构造得？
【在 d*****o 的大作中提到】
: The question is hard and challenging, although it's hard at first, if you
: can learn from it, you will have a good result.
: your rp will accumulate and more chance in the future you will get easy
: question.
: >> Maximum sum of non-conjoint subsets of a integer array,non-conjoin
: Is a DP problem
: >> 1.实现文本（以String形式）在一定宽度的窗口散列对其（在本行内所有单词间均
: 匀的 增加空白
: is also DP
: >>3.设计一个购物网站中的“购物车功能”，支持大量用户，用户购物流程不一定，可将
| c******t
发帖数: 391 | 13 I think the previous posted recursion may not work well when input array
contains negative elements, for example {-4,-3,-2,1} would output -2 rather
than 1. How about modify as following?
max(sum(a,k-1),sum(a,k-2)+a(k),a(k)) | a********e
发帖数: 508 | 14 原来那个没问题吧
全负的数组，结果取空集，题目里有写
rather
【在 c******t 的大作中提到】
: I think the previous posted recursion may not work well when input array
: contains negative elements, for example {-4,-3,-2,1} would output -2 rather
: than 1. How about modify as following?
: max(sum(a,k-1),sum(a,k-2)+a(k),a(k))
| c******t
发帖数: 391 | 15 刚才那个例子不是全负，{-4,-3,-2,1}，会返回(-3+1)=-2
【在 a********e 的大作中提到】
: 原来那个没问题吧
: 全负的数组，结果取空集，题目里有写
:
: rather
| c******t
发帖数: 391 | 16 请问那个文本散列对齐的题用DP是什么思路啊，字符串中的一个单词能跨行么？
interview
【在 k*****7 的大作中提到】
: 找Maximum sum of non-conjoint subsets of a integer array,non-conjoint就是
: 说所选择的两个item在原数组中不相邻， 比如【1,2,3,4,5】，选5就不能选4，选3就
: 不能选
: 2,4。。。。这个case的结果就应该是9，选【1,3,5】. （全负数数组，取空集子集，
: 结果为
: 0）。
: 这道题给我的时候大概只剩10分钟了，我连第一版都没写完。。。。。请教谁有比较好
: 的解法？
: 实在很想抱怨一下，版里潜水很久了，看了很多前辈们的面经，但我phone interview
: 和on-site
| a********e
发帖数: 508 | 17 sum(a,k-2)=0
没必要多加一个判断a(k)
【在 c******t 的大作中提到】
: 刚才那个例子不是全负，{-4,-3,-2,1}，会返回(-3+1)=-2
|
|
