Vdopia Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

How can you solve it in n^4. If I assume that I have been given nxn array then count of possible sub arrays would be (2^n -1 ) *(2^n-1), which is exponential in n, so, just probing such data would mean o(4^n).

- ghost May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

First: O((2^n-1) * (2^n-1)) is O(2^(2n)), not O(4^n).

Second: it's not necessarily true that you have to probe all possible subarrays. For instance, suppose you were given an n of length n and you wanted to find the maximum pair (i.e., the largest sum of any two elements in the array, not necessarily consecutive). There are n^2 pairs, but it would take you only O(n) time to find this -- you just find the largest two elements.

- Gayle L McDowell May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I might agree with second point but one is wrong :) O(2^(2n)) = O((2^2)^n) = O(4^n)

- ghost May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, sorry, yes, you're right. I should've thought through that more.

- Gayle L McDowell May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It can be solved in O(m^2 * n^2) which I mentioned as O(n^4) as follows :-
Iterate over the sub-array from 1 to n
Iterate over the sub-array from 1 to m
iterate over the rows
iterate over the columns

In the above 4 iterations all the possible sub-arrays can be covered. which is O(n^4).

Finding the largest 2 elements may not solve the problem. As we have to add all the elements of the sub-array, hence the two largest may contain a very low element, which could make it lesser than the individual sub-array.

- Achilles May 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Modified Kadane algorithm can perform the task.
Time Complexity: O(M^2*N)
Space Complexity: O(M)// number of rows
Check for each sub-array starting with column number i to column number j. Store the sum[elements with row 0 will be summed & stored in temp[0] & so on] in the temporary buffer. Apply kadane algorithm on the temp[] to find the maximum sum contiguous subsequence. Let maximum sum subsequence in temp[] lies between y1 & y2. Keep updating the maximum sum till now as well as y1,y2,i&j.

- Aashish July 04, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More