问个面试题，加些小抱怨# JobHunting - 待字闺中
k*7
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.
说所选择的两个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.
