avatar
这个不算贵啊# PhotoGear - 摄影器材
d*6
1
毫无准备的情况下收到F家电面
第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
由于做的不是很顺畅,F家决定再让我电面一次。
第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
个题叫我写了个binary search结束。
我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷
,其实Big and Little Endian的概念也不复杂,回头看wiki几分钟就搞明白了。
avatar
l*i
3
请问第一轮那题有比o(n^2)更好的解法吗?
avatar
s*0
4
C+的头就是多啊,又便宜.
N+的俺流口水中...
avatar
g*s
5
O(N).

【在 l*******i 的大作中提到】
: 请问第一轮那题有比o(n^2)更好的解法吗?
avatar
c*y
6
现在换,还来得及,不会亏多少的。。。

【在 s******0 的大作中提到】
: C+的头就是多啊,又便宜.
: N+的俺流口水中...

avatar
d*6
7
参考leetcode的题目,综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
iq350总结的100sulution里第37题)

【在 l*******i 的大作中提到】
: 请问第一轮那题有比o(n^2)更好的解法吗?
avatar
s*0
8
很想换5D2,但是5D2的对焦实在忒肉了.只要能有和D7000差不多的对焦,俺马上就换了.
不知道5D3的对焦能好多少.

【在 c********y 的大作中提到】
: 现在换,还来得及,不会亏多少的。。。
avatar
l*i
9

谢谢。对的,用哈希表存储所有sum(0,i)->i就可以了

【在 d**********6 的大作中提到】
: 参考leetcode的题目,综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
: iq350总结的100sulution里第37题)

avatar
c*y
10
7D啊
而且即使5D2,中心点很强的,拍鸟反正也是中心点,回家裁

【在 s******0 的大作中提到】
: 很想换5D2,但是5D2的对焦实在忒肉了.只要能有和D7000差不多的对焦,俺马上就换了.
: 不知道5D3的对焦能好多少.

avatar
C*t
11
Assume all elements are non-negative. Then there is no need of Hash.
import sys
def find( nums, target ):
m = len(nums)
res = -sys.maxsize() -1
if m==0: return res
left, right, sum = 0,0,0
for right in range(m):
sum += nums[right]
while sum > target and leftsum -= nums[left]
left += 1
if sum == target:
res = max(res, right - left + 1 )
return res

【在 l*******i 的大作中提到】
:
: 谢谢。对的,用哈希表存储所有sum(0,i)->i就可以了

avatar
G*Y
12
CN
本来是串通好的
有些地方C强
有些地方N强
但是除了旗舰机
都不把它作完美了
让你求生不能求死不得
永远不得劲儿
永远有跳船或升级的念想
施主
回头是岸呀

【在 s******0 的大作中提到】
: 很想换5D2,但是5D2的对焦实在忒肉了.只要能有和D7000差不多的对焦,俺马上就换了.
: 不知道5D3的对焦能好多少.

avatar
b*5
13
我也一开始想这个, 但你这个不大对
如果是 -1, -3, -4, -5.。。。。1
然后我要找的sum是1, 你这个永远也找不到1

【在 C****t 的大作中提到】
: Assume all elements are non-negative. Then there is no need of Hash.
: import sys
: def find( nums, target ):
: m = len(nums)
: res = -sys.maxsize() -1
: if m==0: return res
: left, right, sum = 0,0,0
: for right in range(m):
: sum += nums[right]
: while sum > target and left
avatar
s*0
14
俺下一个打算上FF.5D2的对焦速度和D700比咋样?

【在 c********y 的大作中提到】
: 7D啊
: 而且即使5D2,中心点很强的,拍鸟反正也是中心点,回家裁

avatar
C*t
15
If array contains negative element. Hash[0] = -1, Hash[sum( nums [:i+1])] =
i if the key not exists, then follow 2sum algorithm, record the largest j-i

【在 b**********5 的大作中提到】
: 我也一开始想这个, 但你这个不大对
: 如果是 -1, -3, -4, -5.。。。。1
: 然后我要找的sum是1, 你这个永远也找不到1

avatar
s*0
16
明知要被MM骗,还是甘心情愿地上.回头是不可能的.

【在 G**Y 的大作中提到】
: CN
: 本来是串通好的
: 有些地方C强
: 有些地方N强
: 但是除了旗舰机
: 都不把它作完美了
: 让你求生不能求死不得
: 永远不得劲儿
: 永远有跳船或升级的念想
: 施主

avatar
c*y
17
我见过的例题是说array全非负。如果有负数,我先想想。
avatar
r*x
18
哪壶不开提哪壶啊

【在 s******0 的大作中提到】
: 俺下一个打算上FF.5D2的对焦速度和D700比咋样?
avatar
b*5
19
恩, 以前在这板上看到过相似的另外一题, 就是只要return a boolean, whether
there's such subarray

1]

【在 C****t 的大作中提到】
: If array contains negative element. Hash[0] = -1, Hash[sum( nums [:i+1])] =
: i if the key not exists, then follow 2sum algorithm, record the largest j-i

avatar
s*0
20
我的意思是差多少?

【在 r******x 的大作中提到】
: 哪壶不开提哪壶啊
avatar
U*A
21
这个怎么样?
int maxSubY(vector &s, int y){
int size = (int)s.size();
if(size == 0) return 0;
int result = 0;
vector sum(size+1, 0);
map pos;
for(int i=1; i<=size; i++){
sum[i] = sum[i-1]+s[i-1];
if(pos.find(sum[i]) == pos.end()){
pos.insert(make_pair(sum[i], i));
}
}

for(int i=0; i<=size; i++){
if(sum[i] == y){
result = result > i ? result : i;
continue;
}
int left = y+sum[i];
if(pos.find(left) != pos.end() && pos[left] >= i){
result = result > pos[left]-i ? result : pos[left]-i;
}
}
return result;
}
avatar
r*x
22
那就不知道了。。。

【在 s******0 的大作中提到】
: 我的意思是差多少?
avatar
d*6
23
有negative

【在 C****t 的大作中提到】
: Assume all elements are non-negative. Then there is no need of Hash.
: import sys
: def find( nums, target ):
: m = len(nums)
: res = -sys.maxsize() -1
: if m==0: return res
: left, right, sum = 0,0,0
: for right in range(m):
: sum += nums[right]
: while sum > target and left
avatar
l*a
24
这个是CN+的,呵呵

【在 s******0 的大作中提到】
: C+的头就是多啊,又便宜.
: N+的俺流口水中...

avatar
d*6
25
有点麻烦了
hash的时候直接这样
currSum = sum(nums[:i+1])
Hash(y-currSum) = i
如果遇到重复hashkey, i取较大的
这样就把2sum的hash步骤提上来,一部到位

1]

【在 C****t 的大作中提到】
: If array contains negative element. Hash[0] = -1, Hash[sum( nums [:i+1])] =
: i if the key not exists, then follow 2sum algorithm, record the largest j-i

avatar
C*t
27
if the same key occurs again, no need to record it. Because we only record
the min index of the key.

【在 d**********6 的大作中提到】
: 有点麻烦了
: hash的时候直接这样
: currSum = sum(nums[:i+1])
: Hash(y-currSum) = i
: 如果遇到重复hashkey, i取较大的
: 这样就把2sum的hash步骤提上来,一部到位
:
: 1]

avatar
l*a
28
是啊,要的赶紧抢啊,我没忍住pm seller了

【在 m*****i 的大作中提到】
: $700?
avatar
d*6
29
看你第二遍iter的时候的方向,如果是从i=0开始i++,就要取较大的key
如果从i=s.size开始i--,就可以像你说那样
不过这不是重点,只要能达到O(n)就行

record

【在 C****t 的大作中提到】
: if the same key occurs again, no need to record it. Because we only record
: the min index of the key.

avatar
n*g
30

不太懂,什么是nums[:i+1]? 求个完整点的解法,多谢楼主!

【在 d**********6 的大作中提到】
: 看你第二遍iter的时候的方向,如果是从i=0开始i++,就要取较大的key
: 如果从i=s.size开始i--,就可以像你说那样
: 不过这不是重点,只要能达到O(n)就行
:
: record

avatar
d*6
31
nums[:i+1]有点类似python的语法,应该说的是到index=i为止所有的nums集合
具体办法,参考版友iq350总结的100sulution里第37题Maximum Sum of All Sub-
arrays

【在 n*****g 的大作中提到】
:
: 不太懂,什么是nums[:i+1]? 求个完整点的解法,多谢楼主!

avatar
j*o
32
如果科班出生的应该都知道Big and Little Endian,别只顾刷题了。在工作中这类问
题反而更容易碰到。
avatar
d*6
33
其实是知道的,但一时想不起来。想起来就是有点挫啊

【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian,别只顾刷题了。在工作中这类问
: 题反而更容易碰到。

avatar
R*T
34
请问这个100 solution在哪里啊?我搜了下精华区iq350没有找到

【在 d**********6 的大作中提到】
: 参考leetcode的题目,综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
: iq350总结的100sulution里第37题)

avatar
s*c
37
public class Solution {
public int findMaxLengthSubArrayEqY(int[] A, int y) {
if(A == null || A.length == 0) return 0;

int sum = 0;
int maxLen = 0;

// key=sum(0:i)+y; value=i
Map map = new HashMap();
map.put(y, -1);

for(int i = 0; i < A.length; i++) {
sum += A[i];

if(map.containsKey(sum)) {
int len = i - map.get(sum);
maxLen = Math.max(maxLen, len);
}

map.put(sum + y, i);
}

map.clear();
map.put(y, A.length);
sum = 0;
for(int i = A.length -1 ; i >= 0; i--) {
sum += A[i];

if(map.containsKey(sum)) {
int len = map.get(sum) - i;
maxLen = Math.max(maxLen, len);
}

map.put(sum + y, i);
}

return maxLen;
}
/**
* @param args
*/
public static void main(String[] args) {
// int[] A = new int[]{-1, 1, -1, 1, 2};
int[] A = new int[]{2, -1, 1, -1, 1};
Solution s = new Solution();
s.findMaxLengthSubArrayEqY(A, 2);
}
}
avatar
D*n
38
int[] s = {-1 , 1 , -1 , 1 , -1 , 1, 2};
target = 1
return 1.
Correct answer is 5.

【在 s***c 的大作中提到】
: public class Solution {
: public int findMaxLengthSubArrayEqY(int[] A, int y) {
: if(A == null || A.length == 0) return 0;
:
: int sum = 0;
: int maxLen = 0;
:
: // key=sum(0:i)+y; value=i
: Map map = new HashMap();
: map.put(y, -1);

avatar
l*h
39
这个烙印太恶心。
这不过是一个名词而已,用一句话说谁都知道是啥意思。
不知道这个名词,就算完了,这是什么面试?于人于公司都没有好处,唯一的用处就达
到拒人的目的。
avatar
s*c
40
这个怎么样?
public int findMaxLengthSubArrayEqY(int[] A, int y) {
if (A == null || A.length == 0)
return 0;
int sum = 0;
int maxLen = 0;
// key=sum(0:i)+y; value=i
Map map = new HashMap();
for (int i = 0; i < A.length; i++) {
sum += A[i];
if(sum == y) {
int len = i + 1;
maxLen = Math.max(maxLen, len);
}else if (map.containsKey(sum)) {
int len = i - map.get(sum);
maxLen = Math.max(maxLen, len);
}
if(!map.containsKey(sum + y))
map.put(sum + y, i);
}

return maxLen;
}

【在 D***n 的大作中提到】
: int[] s = {-1 , 1 , -1 , 1 , -1 , 1, 2};
: target = 1
: return 1.
: Correct answer is 5.

avatar
a*d
41
Sub array具体是指?
一段连续的数 还是可以从不连续的位置取?
前者 on 后者只能dp 还要backtracking 求最长路径

【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
: 度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅,F家决定再让我电面一次。
: 第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
: 上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷

avatar
d*6
42
连续

【在 a******d 的大作中提到】
: Sub array具体是指?
: 一段连续的数 还是可以从不连续的位置取?
: 前者 on 后者只能dp 还要backtracking 求最长路径

avatar
S*C
43
高手,你的这个算法没错,能讲一下原理吗?

【在 s***c 的大作中提到】
: public class Solution {
: public int findMaxLengthSubArrayEqY(int[] A, int y) {
: if(A == null || A.length == 0) return 0;
:
: int sum = 0;
: int maxLen = 0;
:
: // key=sum(0:i)+y; value=i
: Map map = new HashMap();
: map.put(y, -1);

avatar
a*u
44
汗,我就不知道

★ 发自iPhone App: ChineseWeb 8.7

【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian,别只顾刷题了。在工作中这类问
: 题反而更容易碰到。

avatar
a*u
45
能解释下sub数组指的连续sub数组么?
比如[1,2,3], [1,3]是其sub数组么?还是只有[1,2]这种是?

★ 发自iPhone App: ChineseWeb 8.7

【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
: 度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅,F家决定再让我电面一次。
: 第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
: 上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷

avatar
a*u
46
连续的话,O(n)就够了。用leetcode best time to buy and sell stock 那题做法就
行了

★ 发自iPhone App: ChineseWeb 8.7

【在 d**********6 的大作中提到】
: 连续
avatar
n*2
47
这个问题和科班有关系吗?

【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian,别只顾刷题了。在工作中这类问
: 题反而更容易碰到。

avatar
D*n
48
A more easy understanding solution.
================================================================
public int findMaxLengthSubArrayEqY(int[] A, int target) {
if ( A == null || A.length == 0 ) return 0;
Map> map = new HashMap>(
);
int sum = 0;
for ( int i = 0 ; i < A.length ; i++) {
sum+=A[i];
if ( map.containsKey(sum)) {
map.get(sum).add(i);
} else {
map.put(sum , new ArrayList(Arrays.asList(i)));
}
}

sum = 0 ;
int maxLen = 0 ;
for ( int i = 0 ; i < A.length ; i++) {
int tmp = target + sum ;
List tmpIndexList = map.get(tmp);
if ( map.containsKey(tmp) && tmpIndexList.get(tmpIndexList.size(
) - 1) >= i ) {
maxLen = Math.max(maxLen, tmpIndexList.get(tmpIndexList.size
() - 1) - i + 1);
}
sum += A[i];
}
return maxLen;
}
=======================================================================
tested with
int[] s = {-1, 1, -1, 1, -1, 1, 2};
target = 0 , output = 6
target = 1 , output = 5
target = 2 , output = 7

【在 s***c 的大作中提到】
: 这个怎么样?
: public int findMaxLengthSubArrayEqY(int[] A, int y) {
: if (A == null || A.length == 0)
: return 0;
: int sum = 0;
: int maxLen = 0;
: // key=sum(0:i)+y; value=i
: Map map = new HashMap();
: for (int i = 0; i < A.length; i++) {
: sum += A[i];

avatar
j*8
49
如果数组是{2,3,4},目标是100或者是1,这个找不到吧?!
“题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长度,使sub数组的sum
等于某一个值y。”,这个问题缺条件吧!?
avatar
z*e
50
public int maxSizedSubSequence(int [] num, int target){
Map map = new HashMap();
map.put(0, -1);
int sum = 0;
int maxLength = 0;
for(int i = 0 ;i < num.length; ++i){
sum += num[i];
if(!map.containsKey(sum)){
map.put(sum, i);
}
if(map.containsKey(sum - target)){
int prevIdx = map.get(sum - target);
maxLength = Math.max(maxLength, i - prevIdx);
}
}
return maxLength;
}
avatar
j*3
51
第一题难道不是拿两个pointer么?大概也就走两遍?
avatar
j*3
52
两个pointer好像得到的是最短的。。
avatar
J*9
53
没有冒犯的意思
Big and Little Endian 不懂的确不应该

【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
: 度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅,F家决定再让我电面一次。
: 第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
: 上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷

avatar
B*1
54
的确是

★ 发自iPhone App: ChineseWeb 1.0.1

【在 J**9 的大作中提到】
: 没有冒犯的意思
: Big and Little Endian 不懂的确不应该

avatar
d*6
55
说说思路

【在 j**********3 的大作中提到】
: 第一题难道不是拿两个pointer么?大概也就走两遍?
avatar
d*6
56
找不到属于特殊情况,要你自己考虑
我大概也是因为没有考虑到所以第一轮美没算过
也很简单,返回-1就可以了

sum

【在 j***8 的大作中提到】
: 如果数组是{2,3,4},目标是100或者是1,这个找不到吧?!
: “题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长度,使sub数组的sum
: 等于某一个值y。”,这个问题缺条件吧!?

avatar
d*6
57
当时一下子想不起来,其实是学过的,回头看wiki也几分钟就搞懂
所以挺郁闷的

【在 J**9 的大作中提到】
: 没有冒犯的意思
: Big and Little Endian 不懂的确不应该

avatar
c*5
58
two pointer就可以了应该
avatar
b*y
59
这老印的问题很善良了, big endian 都不知道确实不能过。

【在 l****h 的大作中提到】
: 这个烙印太恶心。
: 这不过是一个名词而已,用一句话说谁都知道是啥意思。
: 不知道这个名词,就算完了,这是什么面试?于人于公司都没有好处,唯一的用处就达
: 到拒人的目的。

avatar
m*e
60
两轮电面是正常程序,不是因为第一轮不顺畅

【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
: 度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅,F家决定再让我电面一次。
: 第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
: 上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷

avatar
s*a
61
big endian 不应该不知道 但是也不应该考 就像没理由不知道什么是queue什么是
stack。
但是就算不知道google一下十秒钟后就知道了,有什么考的意义。。。
avatar
j*3
62
我下边自己说了。。。想错了。。。两个pointer是最短。。人家要最长。。

【在 d**********6 的大作中提到】
: 说说思路
avatar
s*5
63
public int findTarget(int[] A, int sum){
int[] dp = new int[A.length];
int max = 0;
for(int i =1; i<=A.length; i++){
for(int j=0; j+i<=A.length;j++){
dp[j]=dp[j]+A[j+i-1];
if(dp[j]==sum&&i>max) max=i;
}
}
return max;
}
avatar
d*6
64
O(n^2),过不了

【在 s**********5 的大作中提到】
: public int findTarget(int[] A, int sum){
: int[] dp = new int[A.length];
: int max = 0;
: for(int i =1; i<=A.length; i++){
: for(int j=0; j+i<=A.length;j++){
: dp[j]=dp[j]+A[j+i-1];
: if(dp[j]==sum&&i>max) max=i;
: }
: }
: return max;

avatar
J*n
65
If you don't even know big and little endian, you should go back to freshman
year and start from beginning, instead of looking for a job. Where did you
get your degree?

【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试,题目是给出一个数组s和一个值y,找出s当中最长的sub数组的长
: 度,使sub数组的sum等于某一个值y。磕磕碰碰,同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅,F家决定再让我电面一次。
: 第二轮遇到一个烙印,由于之前没啥准备,突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题,什么叫Big and Little Endian。我没答
: 上来,于是烙印就说算了。我奇怪为啥问这个问题,他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊,他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历,我的确没有写C++,我只说我有些VC#的经验。想起来真有些郁闷

avatar
j*o
66
问题是如果来面试的一个人说不知道queue和stack,估计没人会给过吧。

【在 s****a 的大作中提到】
: big endian 不应该不知道 但是也不应该考 就像没理由不知道什么是queue什么是
: stack。
: 但是就算不知道google一下十秒钟后就知道了,有什么考的意义。。。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。