g*****k
发帖数: 623 | 1 It seems not true.
Here is a counter example.
0011111100011111
It is obvious that longest subarray is 111000 or 000111
but according to your algorithm, initially lcursor points the left most 1
and I'm not sure about what do you mean lcursor is too right.
In this case, rcursor should point to the second left 0. (is lcursor too
right?)
Anyway, when you move lcursor right, now rcursor will go the right end and
miss finding 111000.
I'm not sure if there is O(n) time and O(1) space solution for this.... 阅读全帖 |
|
s*****y
发帖数: 897 | 2 thanks
的确不work，考虑不周全。
By the way,这个subsequence就是要不要连续的啊？subarray是连续的，subsequence是不是也要连续？ |
|
g*****k
发帖数: 623 | 3 wrong,
you can't prove your second step would get the longest subarray in O(1) time.
I think you can come up with a counter example easily by yourself
disagree, please list your argument.
space.
setting i=0,j=A.length-1, then searching from both ends.
and A[j]:
set i+=1 or j-=1, and sum-=A[i], and search recursively.
step 2. |
|
UD
发帖数: 182 | 4
example
this is your example:
1100101101010111111111111
I am getting this result:
>./array_find_subseq
0 0 1 0 1 1 0 1 0 1 0 1
>Exit code: 0
it is one of the right answers.
the answer in your previous post, seems not right, there should be 6 0s.
>>the longest subarray is 1001011010. in this case, j should moves right!
and there is no guarantee, you can find j in O(1) time. |
|
A*********r
发帖数: 564 | 5 再看了一下最里面的loop, 觉得dp的方法没有办法用在全是负数的矩阵里，这跟max subarray 在一维 O(n)那个办法有一样的局限性。。 |
|
I********T
发帖数: 22 | 6 三流学校ee ms， 前几天收到bloomberg offer。经历了oncampus两个45分钟面试。 主
要问的问
题有 最大和subarray， local/global/staic variable 各存在哪里， 倒序句子单词
顺序 (I
love New York -> York New love I), 电话本问题（从名字找电话号码和电话号码找
名字，要求
输入im 也能显示出jim的电话号码） 有没有人想交流下工资，站内信联系 |
|
b*****n
发帖数: 143 | 7 Problems 8.10 on page 85:
Find a subarray whose sum is closest to a
given value t.
I can only think of a brute-force method:
fist build the cumulation array, then scan
from first element to the last element. Each
scan is O(n). So the solution is O(n^2). I
wonder whether there is a better solution.
Thanks. |
|
b*****n
发帖数: 143 | 8 Thank you for your replies, guys. So after the cumulation array is sorted,
we will ignore the original cum[0] and cum[1] during the binary search of
cum[2]+t. Is this the idea?
By the way, if my memory is correct, "Programming Pearls" claims that the
optimal solution to this kind of problem is nlog(n). So a linear-time
solution doesn't exist. (Note that we are looking for a subarray whose sum
is closest to t. So the sum could be either smaller or larger than t.)
Thanks again. |
|
f***g
发帖数: 214 | 9 parking lot的题没完全理解。
我所知道的最好的算法是
Div - Con.
1. base case: 数组只有两个数，就不用说了吧
2. merge:
两个subarray, 必定是前面正后面负的形式，
例如： [1 2 3 -4 -5] [6 7 -8 -9]
只要做rotation就行了。 |
|
c*****e
发帖数: 74 | 10 前面怎么也没想通，刚刚画了个图就明白了。
First consider a special problem: write a function
/*
In Time complexity (m+n) & Space complexity O(1), move the subarray starting
at nIdx with length of (m+n) (the first m numbers and the later n numbers)
such that (1) n numbers are ahead of m numbers and (2) the order inside the
m number and n numbers are not changed
*/
void MoveAdjacentMN(int* p, /* address of the array */
int nIdx, /* initial index for m+n numbers in the array */
int m,
... 阅读全帖 |
|
d******a
发帖数: 238 | 11 some of them might be easy to give out idea, but a little hard to write bug-
free code.
1 merge-sort without recursion
we should use loop to sovle it. we could use loop to get n/2 sorted
subarrays, then n/4 sorted arrays...I think we should be careful to consider
the boundary conditions.
2 Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
a 0, 3, 5
b 1,
c 2,
e 4... 阅读全帖 |
|
d******a
发帖数: 238 | 12 http://www.algorithmist.com/index.php/Merge_sort
Bottom-up merge sort is a non-recursive variant of the merge sort, in which
the array is sorted by a sequence of passes. During each pass, the array is
divided into blocks of size . (Initially, ). Every two adjacent blocks are
merged (as in normal merge sort), and the next pass is made with a twice
larger value of .
In pseudo-code:
Input: array a[] indexed from 0 to n-1.
m = 1
while m <= n do
i = 0
while i < n-m do
merge subarrays ... 阅读全帖 |
|
h**********d
发帖数: 4313 | 13 这题我以前看过
String replaceString(String string, String oldString, String newString){
if(string == null || oldString == null || newString == null){
throw new IllegalArgumentException("Null arguments");
}
if(oldString.equals("")){
throw new IllegalArgumentException("oldString has no content");
}
StringBuilder result = new StringBuilder();
int i = 0;
int j = 0;
while((j = string.indexOf(oldString, i)) >= 0){
... 阅读全帖 |
|
S**I
发帖数: 15689 | 14 LZ说假定这个subarray在中间；没这个假设的话当然要另当别论。 |
|
b*******s
发帖数: 5216 | 15 把0都换成-1，就变成了求一个整数序列里面和为0的最大子串长度
复杂度O(n) |
|
l*****a
发帖数: 14598 | 16 你说的这个要额外的空间吗？
不要的话怎么做，谢谢 |
|
l*****a
发帖数: 14598 | 17 你说的这个要额外的空间吗？
不要的话怎么做，谢谢 |
|
|
|
|
i**********e
发帖数: 1145 | 21 I think your method is more complicated than is needed.
The problem has a constraint that only 0's and 1's exist in the array.
We could use two counters to keep track of number of 0's and 1's met so far, and do a one-pass traverse across the array.
The length of the maximum size contiguous array with equal number of 0's and 1's must be:
2 * min( count of 0's, count of 1's ).
I know, it might seem too simple to be true, but sometimes being simple is also a virtue.
一些常见面试题的答案与总结 -
http://www.ihas1... 阅读全帖 |
|
|
|
t**d
发帖数: 352 | 24 solution for 1.)
go over array, sum up for all elements upto the current one. put the result
in a hashmap, if any value appear more than once, there's a subarray sums to
0 |
|
g*********s
发帖数: 1782 | 25 is it some high-profile startup? so what are the hints?
the 2nd one smells still like a dp.
subarray |
|
v*****d
发帖数: 348 | 26 Yes. So we do have negative numbers. Sorry the hint I gave previously is a
little bit misleading.
Suppose the original array is [-2, 2, -1, 3, -6] and k=3 then the subarrays
would be [2, -1, 3] and [3], and therefore the answer (maximal length) is 3
the idea is, first we build a sum array like before: sum=[-2, 0, -1, 2, -4],
then sort it together with the indexes, and we get (first is the number,
second is the index) x=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)], then
use two pointers i and j... 阅读全帖 |
|
b******n
发帖数: 4509 | 27 i++ j-- does not seem correct, cause you disgard the case
that the same j with a larger i, j.num - i.num >= k, and the
length can be larger, you need to check every j agaist i, or vise versa
that's O(n^2)
a
subarrays
3
],
j |
|
g*********s
发帖数: 1782 | 28 u r sorting with the sum value, not the index...
is a
subarrays
length) is 3
2, -4],
number,
then
to
i++, j |
|
m******m
发帖数: 19 | 29
借助sum数组
sum[i] = SUM{ a[i] | i = 0~i}
1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
i的值。这样遇到相同的就说明sum[i] == sum[j], j
conflit。O(n)
2. 1)还是计算sum[i]。O(n)
2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
index数组了。 O(n)
4) i = 0~n-1, 对于每个i, 在排序好的sum[i]数组中找 sum[j] 正好 <= sum[i]-
k。那么以a[i]为终点的满足条件的subarray最长的长度就是 i-min_index[i]。通过一
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 30 Very interesting question!
I recognized this problem as an exercise from the classic "Programming
pearls" 2nd edition by Jon Bentley, Prob. 10, pp. 85.
1) Just like ibread mentioned, use a cumulative array where cum[i] = A[0] +
A[1] + ... A[i], which can be built using a one-pass scan. If there exist at
least one contiguous subarray which sum is equals 0, there must exist
duplicates in the cumulative array. We can use a hash table to detect
duplicates in the cumulative array in O(N),
2) Prob. 2 ... 阅读全帖 |
|
i****d
发帖数: 35 | 31 基本思路是这样：
既然要求subarray的sum>=k，也就是说，要找 max {j-i | sum[i+1...j]>=k}
所以就遍历i，找同时满足这俩条件的j
1. sum[i+1...j]>=k。如果对sum数组排序了，就可以binary search找sum[j]<=sum[i]
-k就可以了
2. 满足第一个条件的下标j里面，我们要挑个最小的(下标)。因为已经对sum数组排序
了，假设我们找到了 *刚好* 满足第一个条件的j, 那么在排序好的sum数组中，在
sum[j]之前的都也满足第一个条件 (已经排序了。。。)
所以动机就是，我们为每个排序好的sum[j]，维持一个在sum[j]之前的最小下标就可以了 |
|
g*****k
发帖数: 623 | 32 Your solution is actually the same as ibread's solution.
in ibread's solutio's last step, j starts from n to 0, so binary search
in the sorted cum array s.t. cum[i]<= cum[j]-k. Once you find i, you just
get the smallest index by min_index[i].
min_index[i]= min{k | cum[k]
j-min_index[i] is the length of the subarray starting at min_index[i]+1.
我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumul... 阅读全帖 |
|
|
e*****3
发帖数: 610 | 34 的确不是每个算法都是论文级的。象这个MAXIMUM SUBARRAY的算法应该算是超级简单
的吧？可是
WIKIPEDIA上还留下了发现者的大名，说明在没发现之前想出来还是不容易的。面试的
人指望你没见
过又能在30分钟里想出来，在白板上把CODE写出来？这样是不是太虚伪了？
http://en.wikipedia.org/wiki/Maximum_subarray_problem
The problem was first posed by Ulf Grenander of Brown University in
1977, as a simplified model for maximum likelihood estimation of
patterns in digitized images. A linear time algorithm was found soon
afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). |
|
x*****p
发帖数: 1707 | 35 这个MAXIMUM SUBARRAY的题目这么有名啊，我今天才知道。五年前我在高盛面试的第一
题就是它，把我一下震住了。想了十五分钟，还是想出来了，而且把代码写在白板上了
，也没花到30分钟啊。不过刚才看到链接里的代码，确实比我当时写的好。 |
|
J*****u
发帖数: 30 | 36 是subarray,那从i到n的复杂度是不是就为n^2了? 谢谢 |
|
R***i
发帖数: 78 | 37 一天之内收到3封email，2据1offer
据我的是F,P,之前都发过面经
offer是A，电面也发过面经，搜我ID就知道了，看来发面经果然是攒人品的
手上还有NYC的某offer，但看来得从了A家了
A onsite面经如下，难度不大，造福后来同胞
LRU implementation
Integer to Roman number
Traffic junction simulation OOD + algorithm to shorten average wait time
Furniture store OOD
Max Sum in a subarray，这道题目居然就是我的bar raiser，我晕倒。。。
当然中午HM还有无数的behavior问题
明天下午有G的PM职位的面试。。。继续攒人品 |
|
f*********i
发帖数: 197 | 38 given is an unsorted integer array, how to divide it into two subarrays,
such that the averages of these two arrays are the same (or have minimum
difference).
what if those are positive integers only, and what happens when it is mixed
with positive and negative integers? |
|
h*********n
发帖数: 11319 | 39 s/he said subarray, so I guess s/he meant your way? |
|
f******n
发帖数: 279 | 40 SOrry, the problem should be subarray insteady of subsequence. |
|
r******g
发帖数: 13 | 41 3 way partition first puts the duplicated elements in two ends by scanning
once:
1. moving from let to find element not less < p
2. moving from right to find element not greater > p
3. exchange left and right elemnt
4. if (left elment == p) swap it with left end
5. if (right element == p) swap it with right end
=pivot, p, = pivot
my code got
5, 5, 5, 4, 3, 1, 2, 3, 5, 10, 5, 9
put the duplicated elements in the center by exchanging elements in two ends
and those in the center
3, 2, 1, 4, ... 阅读全帖 |
|
r*******y
发帖数: 1081 | 42 same as finding the subarray of max sum
the |
|
r*******y
发帖数: 1081 | 43 max sum of the subarray |
|
b**********r
发帖数: 91 | 44 Can't input Chinese, My situation was riding donkey and looking for
horse.
Interviewed several companies small or big, followings are some of the
questions as a return for what I benefit from here
(1) topological sort
(2) given an array of stock prices, find the best trading strategy.
(3) given a stream of points, find the top 10 points closest to the
origin
(4) given a BST, divide it by a given value
(5) print all the diagonals of a matrix
(6) check if 2 strings are anagram
(7) max subarray
(8)... 阅读全帖 |
|
f**********t
发帖数: 1001 | 45 有没有更好的做法？
Brute force method:
sort the array using any existed sort algorithm, just treating the array as
normal array. The best time complexity is O(nlogn)
Method2:
Among M sorted array, select the smallest number from one array, move the
pointer to the next integer of the array. repeat this routine, until all
integers are put into order.
For each integer in the output array, it's compared M times. the time
complexity is O(n*M)
The code is listed below:
void nwaymergesort(int* arr, int* out, in... 阅读全帖 |
|
s******d
发帖数: 61 | 46 什么是NP-complete呢？看网上有人说这方法？
我的想法是先sort， 然后在从两边开始比较，中途recursion |
|
|
|
S**I
发帖数: 15689 | 49 这要看要不要求子数组里的元素是连续的。连续的话是polynomial，不连续的话似乎就
是NP了。 |
|
|
