d**********6
发帖数: 4434 | 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几分钟就搞明白了。 |
l*******i
发帖数: 57 | |
g***s
发帖数: 3811 | 3 O(N).
【在 l*******i 的大作中提到】
: 请问第一轮那题有比o(n^2)更好的解法吗？
|
d**********6
发帖数: 4434 | 4 参考leetcode的题目，综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
iq350总结的100sulution里第37题)
【在 l*******i 的大作中提到】
: 请问第一轮那题有比o(n^2)更好的解法吗？
|
l*******i
发帖数: 57 | 5
谢谢。对的，用哈希表存储所有sum(0,i)->i就可以了
【在 d**********6 的大作中提到】
: 参考leetcode的题目，综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
: iq350总结的100sulution里第37题)
|
C****t
发帖数: 53 | 6 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
sum -= nums[left]
left += 1
if sum == target:
res = max(res, right - left + 1 )
return res
【在 l*******i 的大作中提到】
:
: 谢谢。对的，用哈希表存储所有sum(0,i)->i就可以了
|
b**********5
发帖数: 7881 | 7 我也一开始想这个， 但你这个不大对
如果是 -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
|
C****t
发帖数: 53 | 8 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
|
c*****y
发帖数: 27 | 9 我见过的例题是说array全非负。如果有负数，我先想想。 |
b**********5
发帖数: 7881 | 10 恩， 以前在这板上看到过相似的另外一题， 就是只要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
|
|
|
U***A
发帖数: 849 | 11 这个怎么样？
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;
} |
d**********6
发帖数: 4434 | 12 有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
|
d**********6
发帖数: 4434 | 13 有点麻烦了
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
|
C****t
发帖数: 53 | 14 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]
|
d**********6
发帖数: 4434 | 15 看你第二遍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.
|
n*****g
发帖数: 178 | 16
不太懂，什么是nums[:i+1]? 求个完整点的解法，多谢楼主！
【在 d**********6 的大作中提到】
: 看你第二遍iter的时候的方向，如果是从i=0开始i++，就要取较大的key
: 如果从i=s.size开始i--，就可以像你说那样
: 不过这不是重点，只要能达到O(n)就行
:
: record
|
d**********6
发帖数: 4434 | 17 nums[:i+1]有点类似python的语法，应该说的是到index=i为止所有的nums集合
具体办法，参考版友iq350总结的100sulution里第37题Maximum Sum of All Sub-
arrays
【在 n*****g 的大作中提到】
:
: 不太懂，什么是nums[:i+1]? 求个完整点的解法，多谢楼主！
|
j******o
发帖数: 4219 | 18 如果科班出生的应该都知道Big and Little Endian，别只顾刷题了。在工作中这类问
题反而更容易碰到。 |
d**********6
发帖数: 4434 | 19 其实是知道的，但一时想不起来。想起来就是有点挫啊
【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian，别只顾刷题了。在工作中这类问
: 题反而更容易碰到。
|
R**T
发帖数: 784 | 20 请问这个100 solution在哪里啊？我搜了下精华区iq350没有找到
【在 d**********6 的大作中提到】
: 参考leetcode的题目，综合2 sum和经典题目Maximum Sum of All Sub-arrays(版友
: iq350总结的100sulution里第37题)
|
|
|
d**********6
发帖数: 4434 | 21 http://www.mitbbs.com/article_t/JobHunting/32899043.html
【在 R**T 的大作中提到】
: 请问这个100 solution在哪里啊？我搜了下精华区iq350没有找到
|
R**T
发帖数: 784 | |
s***c
发帖数: 1926 | 23 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);
}
} |
D***n
发帖数: 149 | 24 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);
|
l****h
发帖数: 1189 | 25 这个烙印太恶心。
这不过是一个名词而已，用一句话说谁都知道是啥意思。
不知道这个名词，就算完了，这是什么面试？于人于公司都没有好处，唯一的用处就达
到拒人的目的。 |
s***c
发帖数: 1926 | 26 这个怎么样？
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.
|
a******d
发帖数: 82 | 27 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#的经验。想起来真有些郁闷
|
d**********6
发帖数: 4434 | 28 连续
【在 a******d 的大作中提到】
: Sub array具体是指？
: 一段连续的数 还是可以从不连续的位置取？
: 前者 on 后者只能dp 还要backtracking 求最长路径
|
S*******C
发帖数: 822 | 29 高手，你的这个算法没错，能讲一下原理吗？
【在 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);
|
a*****u
发帖数: 1712 | 30 汗，我就不知道
★ 发自iPhone App: ChineseWeb 8.7
【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian，别只顾刷题了。在工作中这类问
: 题反而更容易碰到。
|
|
|
a*****u
发帖数: 1712 | 31 能解释下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#的经验。想起来真有些郁闷
|
a*****u
发帖数: 1712 | 32 连续的话，O(n)就够了。用leetcode best time to buy and sell stock 那题做法就
行了
★ 发自iPhone App: ChineseWeb 8.7
【在 d**********6 的大作中提到】
: 连续
|
n****2
发帖数: 307 | 33 这个问题和科班有关系吗？
【在 j******o 的大作中提到】
: 如果科班出生的应该都知道Big and Little Endian，别只顾刷题了。在工作中这类问
: 题反而更容易碰到。
|
D***n
发帖数: 149 | 34 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];
|
j***8
发帖数: 1 | 35 如果数组是{2,3,4},目标是100或者是1，这个找不到吧？！
“题目是给出一个数组s和一个值y，找出s当中最长的sub数组的长度，使sub数组的sum
等于某一个值y。”，这个问题缺条件吧！？ |
z***e
发帖数: 58 | 36 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;
} |
j**********3
发帖数: 3211 | 37 第一题难道不是拿两个pointer么？大概也就走两遍？ |
j**********3
发帖数: 3211 | |
J**9
发帖数: 835 | 39 没有冒犯的意思
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#的经验。想起来真有些郁闷
|
B*******1
发帖数: 2454 | 40 的确是
★ 发自iPhone App: ChineseWeb 1.0.1
【在 J**9 的大作中提到】
: 没有冒犯的意思
: Big and Little Endian 不懂的确不应该
|
|
|
d**********6
发帖数: 4434 | 41 说说思路
【在 j**********3 的大作中提到】
: 第一题难道不是拿两个pointer么？大概也就走两遍？
|
d**********6
发帖数: 4434 | 42 找不到属于特殊情况，要你自己考虑
我大概也是因为没有考虑到所以第一轮美没算过
也很简单，返回-1就可以了
sum
【在 j***8 的大作中提到】
: 如果数组是{2,3,4},目标是100或者是1，这个找不到吧？！
: “题目是给出一个数组s和一个值y，找出s当中最长的sub数组的长度，使sub数组的sum
: 等于某一个值y。”，这个问题缺条件吧！？
|
d**********6
发帖数: 4434 | 43 当时一下子想不起来，其实是学过的，回头看wiki也几分钟就搞懂
所以挺郁闷的
【在 J**9 的大作中提到】
: 没有冒犯的意思
: Big and Little Endian 不懂的确不应该
|
c********5
发帖数: 26 | |
b*****y
发帖数: 846 | 45 这老印的问题很善良了， big endian 都不知道确实不能过。
【在 l****h 的大作中提到】
: 这个烙印太恶心。
: 这不过是一个名词而已，用一句话说谁都知道是啥意思。
: 不知道这个名词，就算完了，这是什么面试？于人于公司都没有好处，唯一的用处就达
: 到拒人的目的。
|
m******e
发帖数: 201 | 46 两轮电面是正常程序，不是因为第一轮不顺畅
【在 d**********6 的大作中提到】
: 毫无准备的情况下收到F家电面
: 第一次是个同胞面试，题目是给出一个数组s和一个值y，找出s当中最长的sub数组的长
: 度，使sub数组的sum等于某一个值y。磕磕碰碰，同胞提示了两个关键点做出来了。但
: 由于做的不是很顺畅，F家决定再让我电面一次。
: 第二轮遇到一个烙印，由于之前没啥准备，突击了一周的数据结构和算法。没想到烙印
: 一上来第一个问题居然是问我一个概念问题，什么叫Big and Little Endian。我没答
: 上来，于是烙印就说算了。我奇怪为啥问这个问题，他说所有熟悉C++的人都应该会这
: 个。我说我没在简历上写我会C++啊，他说他看到第一行写的就是C++。最后随便给我一
: 个题叫我写了个binary search结束。
: 我回头再看我的简历，我的确没有写C++，我只说我有些VC#的经验。想起来真有些郁闷
|
s****a
发帖数: 794 | 47 big endian 不应该不知道 但是也不应该考 就像没理由不知道什么是queue什么是
stack。
但是就算不知道google一下十秒钟后就知道了，有什么考的意义。。。 |
j**********3
发帖数: 3211 | 48 我下边自己说了。。。想错了。。。两个pointer是最短。。人家要最长。。
【在 d**********6 的大作中提到】
: 说说思路
|
s**********5
发帖数: 19 | 49 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;
} |
d**********6
发帖数: 4434 | 50 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;
|
|
|
J****n
发帖数: 937 | 51 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#的经验。想起来真有些郁闷
|
j******o
发帖数: 4219 | 52 问题是如果来面试的一个人说不知道queue和stack，估计没人会给过吧。
【在 s****a 的大作中提到】
: big endian 不应该不知道 但是也不应该考 就像没理由不知道什么是queue什么是
: stack。
: 但是就算不知道google一下十秒钟后就知道了，有什么考的意义。。。
|
