Redian新闻
>
问个面试题,加些小抱怨
avatar
问个面试题,加些小抱怨# 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.
avatar
b*n
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

avatar
k*7
3
解释一下?
另外忘了说,数组元素不是有序的

【在 b******n 的大作中提到】
: 这题简单的递归就可以吧,代码应该不难:
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level

avatar
b*n
4
根据最后一个数字选还是不选分成两种情况

【在 k*****7 的大作中提到】
: 解释一下?
: 另外忘了说,数组元素不是有序的

avatar
r*r
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 的大作中提到】
: 解释一下?
: 另外忘了说,数组元素不是有序的

avatar
k*7
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)

avatar
g*y
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]));

avatar
g*s
8
复杂度不低。不过估计楼主写递归就够了。

【在 b******n 的大作中提到】
: 这题简单的递归就可以吧,代码应该不难:
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level

avatar
g*s
9
1.实现文本(以String形式)在一定宽度的窗口散列对其(在本行内所有单词间均匀的
增加空白符),散列成的段落,最后一行左对齐。这个不难,就是coding很繁。
2.实现tree的iterator的next()方法,o(n)。先序怎么做,中序怎么做。
avatar
d*o
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
avatar
b*8
11
这个应该是最佳解答了,程序也简单,循环一次就行了,出错不容易。

【在 b******n 的大作中提到】
: 这题简单的递归就可以吧,代码应该不难:
: intpu arr[0]...arr[n]
: f(n) = max (f(n-1), arr[n] + f(n-2))
:
: interview
: level

avatar
m*r
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.设计一个购物网站中的“购物车功能”,支持大量用户,用户购物流程不一定,可将

avatar
c*t
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))
avatar
a*e
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))

avatar
c*t
15
刚才那个例子不是全负,{-4,-3,-2,1},会返回(-3+1)=-2

【在 a********e 的大作中提到】
: 原来那个没问题吧
: 全负的数组,结果取空集,题目里有写
:
: rather

avatar
c*t
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

avatar
a*e
17
sum(a,k-2)=0
没必要多加一个判断a(k)

【在 c******t 的大作中提到】
: 刚才那个例子不是全负,{-4,-3,-2,1},会返回(-3+1)=-2
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。