s******o
发帖数: 2233 | 1 for {1,1,0} your method returns 3 |
|
b***e
发帖数: 1419 | 2 Modified boundary condition. |
|
c****9
发帖数: 164 | 3 写了一个，感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
{
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
{
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
{
sum = a[currentleft]+a[currentright];
if(currentleft==... 阅读全帖 |
|
m********g
发帖数: 272 | 4 如题，例子：[0,1,1,1,1,0,0,1], and the result should be [1,1,0,0]
有没有O(n)runtime and O(1) space的solution？
谢谢！ |
|
|
s******n
发帖数: 3946 | 6 不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。 |
|
s**********e
发帖数: 326 | 7 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous |
|
|
s**********e
发帖数: 326 | 9 public static void longestSubarray(int[] arr){
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
if(i-preLen-1 >= 0 && arr[i] == 1-arr[i-preLen-1]){
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
... 阅读全帖 |
|
e*****e
发帖数: 1275 | 10 你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。 |
|
|
s******n
发帖数: 3946 | 12 其实有一邪招：用原数组作为DP用，把0/1放最高位，最后恢复。 |
|
e*****e
发帖数: 1275 | 13 这个题目不要DP。
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目）
0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字（有相同的0,1）
0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘，因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1 |
|
e*****e
发帖数: 1275 | 14 上面我的办法稍微改动一下，就是O(N) O(1)space的solution. |
|
|
e*****e
发帖数: 1275 | 16 O(1)不难啊，搞一个
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10. |
|
H****r
发帖数: 2801 | 17 max diff might be of the order of the size of the array
so does min diff |
|
e*****e
发帖数: 1275 | 18 不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢，还是O(n). |
|
|
b***e
发帖数: 1419 | 20 His answer is not too far from being correct. In fact, it'd be much easier
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though. |
|
c****l
发帖数: 138 | 21 Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here. |
|
l****o
发帖数: 43 | 22 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？ |
|
|
|
b***e
发帖数: 1419 | 25 /*
You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
*/
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: -1}; // <-- here is the O(n) space needed
for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum]);
}
}
return max;... 阅读全帖 |
|
s******o
发帖数: 2233 | 26 for {1,1,0} your method returns 3 |
|
b***e
发帖数: 1419 | 27 Modified boundary condition. |
|
c****9
发帖数: 164 | 28 写了一个，感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
{
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
{
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
{
sum = a[currentleft]+a[currentright];
if(currentleft==... 阅读全帖 |
|
f**********2
发帖数: 2401 | 29 如果subarray是指的位置连续的integer，正解。其实就是遍历所有可能，brute force？ |
|
f**********2
发帖数: 2401 | 30 满足要求的不存在，就输出－1,退出。
就是max sum subarray，agree |
|
m*****k
发帖数: 18 | 31 编了一下O(n)的maximum subarray问题：
int maxSubArray(int A[], int n) {
int max = A[0], max_neg = A[0], sum = 0;
bool flag = false; // test all negtive integers
for (int i = 0 ; i < n; i++)
{
if (A[i] >= 0)
flag = true;
else if (A[i] > max_neg)
max_neg = A[i];
sum += A[i];
if (sum < 0)
sum = 0;
else if (sum > max)
max = sum;
... 阅读全帖 |
|
|
g*********e
发帖数: 14401 | 33 void closestSum(int arr[], int n, int t){
int prev=0;
int post=0;
int curSum=arr[0];
int resPrev, resPost;
int closeSum=arr[0];
while(1){
if(curSum==t){
resPrev=prev;
resPost=post;
break;
}
else if(curSum
if(prev==n-1)
break;
else{
prev++;
curSum+=arr[prev];
}
}
else{
curSum-=arr[post+... 阅读全帖 |
|
w****o
发帖数: 2260 | 34 是8.10
给一个数组(数组的数没有任何的限制) 和一个target，要求一个subarray with the
sum closest to the target.
提示是说要用到cululative array,就是可以先算出来a[0...i]的和。 |
|
z*********8
发帖数: 2070 | 35 subarray 是指连续的数吧？ 你sort之后顺序不就乱了？
下 |
|
x*******5
发帖数: 152 | 36 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
x*******5
发帖数: 152 | 37 很好的test case，不过我再次阅读pearl发现，在原始题目中，即找subarray such
that its sum is maximal中有一个限制条件就是数组不能全为负，经过思考，我的程
序同样要满足这个限制条件，否则会出错。因为在这种情况，只要求出数组最大值就可
以了，o(n)解法。所以代码修改如下
def Subvector_k(v,k):
"find the subvector whose sum is k"
All_Negative=True
if [c for c in v if c>0]:
All_Negative=False
if All_Negative:
return max(v)
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
print v... 阅读全帖 |
|
|
|
l****c
发帖数: 782 | 40 void kAwaySort(int s[], int n)
{
quickSort(0,k-1);
int i = k;
while(i
merge(s, i-k, i-1, i) //merge s[i] into the subarray s[i-k,i-1];
i++;
} |
|
b*******d
发帖数: 750 | 41 是个start up，不说名字了，不太好。
题目并不是太难。服务器端接受用户的刷卡服务。
customer1 使用了card1 make了一个purchase
customer2 使用了card2 make了一个purchase
customer3 使用了card1 make了一个purchase
customer1 使用了card2 make了一个purchase
。。。
这是个graph，里面有customer node和card node，上边的客户1 2 3 都是related
customer （connected in the graph）。
设计一个类，query customer id，返回所有related customer；添加一个新的
purchase （就是一个新的customer+card pair），能很快的将其index了。
我的做法是：所有connected 的customer构成一个cluster，created一个cluster id，
Map> M1 表达 （clusterId，customers）。
... 阅读全帖 |
|
j********g
发帖数: 244 | 42 3. 白板：找到sum是0的subarray，N^2 --> linear，写code。
这个是2sum吗。。。其他还有什么是可以linear的呀?。。。恕我愚钝。。 |
|
t**g
发帖数: 1164 | 43 如何找出subarray，使得元素之和最大
比如{-2,3,-1,3,-4}
那么答案应该是{3,-1,3}
感觉有点复杂，求教！ |
|
J***u
发帖数: 18 | 44 DP。 假设给定数组是a[]
先判断a[]是不是全是non-positive,如果是的话，找出最大的数并返回。
否则dp[0] = a[0], dp[i] = max((dp[i-1] + dp[i]), 0); 然后扫一遍dp[]找最大的
数作为返回subarray的重点，再向左找第一个0后面的位置作为起始,如果左侧找不到0
就以a[0]为起始。O(n)。
看标题还以为是之前听说的非负m*n矩阵找最大子矩阵。。。 |
|
h*******e
发帖数: 1377 | 45 是matrix找 sub matrix 還是 array 找連續subarray 前者 o(n^3) 後者 o(n)
都是用dp啊 |
|
s******y
发帖数: 72 | 46 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
s******y
发帖数: 72 | 47 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
g****u
发帖数: 252 | 48 我觉得你的算法是对的. 一个小优化是找两个subarray的分界点可以用二分查找. 但是
在递归过程中必须维护当前子树的值的上下界,一旦越界就报错. 我觉得不值得这么折
腾.
还有一个办法就是反向读数组, 然后重建BST. 每读一个数都应该可以找到二叉树中唯
一插入的位置, 如果找不到的话就报错. 但是找插入位置的过程的复杂度至少是树的高
度,也就是O(log N), 所以总体还是O(N logN), 实现的复杂度就差多了. |
|
e****e
发帖数: 418 | 49 So true. I thought about this question for some time. Today finally I found
some solution on the Internet.
stackoverflow.com/questions/6945105/search-matrix-for-all-rectangles-of-
given-dimensions-select-blocks-of-seats
In the second pass, the "Largest Rectangle in Histogram" can be used to
calculate the num of elements in maximum subarray. LRIH should be applied to
each row. |
|
O******i
发帖数: 269 | 50 题目很水，就是那个泛滥的maximum subarray sum (1D array)的题。
Gayle可是一上来各种自我介绍都免了直接问这题。也不知道那个白人老兄是真没见过
这题的O(n)解法还是故意装不知道，反正吭哧吭哧费了好大尽用了很复杂的方法，然后
又一一否决。连我看的人都为他着急啊。
最后在Gayle的提示下，bingo! 在30多分钟的时候他终于想到了那个对大家来说都已不
是秘密的Kadane算法O(n)完成了白板代码并进行了test
不料Gayle的评价很高，说他的commnunication很好，对这个结果很满意。
要是换成我们，如果整个40分钟才做这一水题，或者不会做，或者后续问题做不好，早
让面试官鄙视了。
看来面试的主观性很大，关键是要遇到一个赞赏而不是鄙视你的面试官。 |
|
