## Microsoft Interview Question

• 1
of 1 vote

Country: -

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

You are welcome to check my solution on this problem:
computationalpuzzles.wordpress.com/2011/12/05/algorithms-longest-contiguous-subarray-which-can-be-rearranged-to-form-a-contiguous-list/

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

What do you mean by numbers that can be arranged in a sequence, all numbers can be arranged in a sequence

Comment hidden because of low score. Click to expand.
0

consecutive elements sequence... this is a google interview question... this was discussed earlier.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

id=9783960

Comment hidden because of low score. Click to expand.
0

I think the Google interview asked for a subset of the array, this question asks for a subarray. The obvious solution is checking all possible subarrays, but there must be a better solution...

Comment hidden because of low score. Click to expand.
0

'id=9783960' it's a different problem.
Here it is asked to find a SUBARRAY (contiguous part) that can be transformed to a sequence of consecutive integers, i.e.:

a = {4,5,1,5,7,4,3,6,3,1,9}
the subarray is: {5,7,4,3,6} because these numbers can be arranged as: {3,4,5,6,7}

Comment hidden because of low score. Click to expand.
0

ok, here is an algorithm I had in mind:

The idea is if the numbers of a subarray can be arranged in consecutive way that their sum can be evaluated as follows:
max*(max+1)/2 - min*(min-1)/2
where 'max' and 'min' are the maximal and minimal numbers in a subarray.

So the algorithm is go through the array updating 'max' and 'min', as well as the current sum.
In each step we check if computed sum equals to the value returned by the formula above.
If so, we have found a subarray with the given properties.
We keep the longest one seen so far.

Since we have to consider all possible array suffixes, the complexity is O(n^2)

Comment hidden because of low score. Click to expand.
0

Anonymous (above): what if an integer is repeated?

Comment hidden because of low score. Click to expand.
0

that's the trick:

if the number is repeated in subarray, the actual sum
will differ from the one provided by the formula.
Consider:

{5,7,4,3,6}
min = 3, max = 7. The sum is 25 which agrees with the formula.

suppose now we have a subarray: {5,7,4,3,4}
min/max are the same but the sum now is: 23, hence this
subarray is wrong.

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

Sum doesn't work. What if
{6,7,3,3,6} => sum = 25 with min = 3, max = 7

Learn to test a method b4 posting!

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

If just sum doesn't work, how about using both sum and product? 2520 is the product for min = 3 and max = 7.. 6,7,3,3,6 yields 2268.. So the series isn't apt for 3 - 7.. If both sum and product should be same, I can't think of a case that would break this..

Comment hidden because of low score. Click to expand.
0

but as this algorithm is O(n^2) I believe there must be a better way to do it..

Comment hidden because of low score. Click to expand.
0

yeah, but the product can easily overflow 32-bit ints

Comment hidden because of low score. Click to expand.
0

we can use some kinda of Chinese remaindering, that is
computing the product modulo two or more prime numbers
which give the correct result with high probability..

Comment hidden because of low score. Click to expand.
0

another idea: besides computing the sum
between min and max, we can also xor
all numbers in the subarray with consecutive ints in [min..max]
to check if the result is 0

Comment hidden because of low score. Click to expand.
0

nothing but all crappy idea! What the fuck of using xor? Sum+Mul together fails for many inputs. Search stackoverflow.

Comment hidden because of low score. Click to expand.
0

ok @anonymous2: can you break this ?
here I use the combination of sum and xor tests
to avoid situations like {6,7,3,3,6} as above

I'd appreciate if you can find a counterexample that does not work

``````// find a longest subarray which consists of consecutive ints
// of a given array
void longest_subarray(int *a, int n) {
int p1 = 0, p2 = 0; // bounds for subarray found so far
int i, j;
for(i = 0; i < n - 1; i++) {
int ch = a[i], sum = ch, xsum = ch;
// indices of min-max chars in the range [i; j]
int minc = ch, maxc = ch, xorc = ch;
for(j = i + 1; j < n; j++) {
int ch = a[j];
xsum ^= ch,  sum += ch; // compute two sums '+' and 'xor'
if(ch < minc)
minc = ch;
else if(ch > maxc)
maxc = ch;
// if no of elements is not equal => no need to make tests
if(maxc - minc != j - i)
continue;

int sum_check = maxc*(maxc+1) / 2 - minc*(minc-1)/2;
if(sum_check == sum && j - i > p2 - p1) {
int xcheck = 0;
for(int m = minc; m <= maxc; m++)
xcheck ^= m;
if(xsum == xcheck) {
p1 = i, p2 = j; // found a match
printf("found match: %d %d\n", p1, p2);
}
}
}
}
for(i = p1; i <= p2; i++) {
printf("%d ", a[i]);
}
printf("\n");
}

int main() {
int a[] = {11,1,23,6,7,3,3,6,3,3,4,2,235,2,234,234};
//{5,5,1,6,7,3,2,4,3,1,9};
int n = sizeof(a) / sizeof(int);
longest_subarray(a, n);
return 1;
}``````

Comment hidden because of low score. Click to expand.
0

So are you saying first find the expected sums & xor of [min..max] and then see if they are the same as the subarray with the same min & max?

If so, consider {1 2 2 5 5 6}. I think it will produce the same sum & xor, assuming my program below works properly. Basically given a min & max, my program will try to generate a random array with numbers between min & max, then explicitly set the first element to min and last element to max. Then it computes their sum & xor and checks if it's unique.

I have seen others suggest computing sum of squares etc as well, which also don't work. Even if they do, trying to prove that it works will probably be very difficult during an interview.

``````static void test(int min, int max) {
int expectedSum = 0;
int expectedBits = 0;
for(int i=min; i<=max; i++) {
expectedSum += i;
expectedBits ^= i;
}
int diff = max-min;
int len = diff+1;
int arr[] = new int[len];
Random r = new Random();
while(true) {
for(int i=1; i<len-1; i++) {
arr[i] = r.nextInt(diff) + min;
}
arr = min;
arr[arr.length-1] = max;
int sum = 0;
int bits = 0;
for(int i=0; i<len; i++) {
sum += arr[i];
bits ^= arr[i];
}

if(sum == expectedSum && bits == expectedBits) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i : arr) {
}
if(set.size() != len) {
for(int i : arr)
System.out.print(" " + i);
break;
}
}
}
}``````

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

For every different indices of subarray i, j => O(n2)
For each subarray you have, find if all the elements of that subarray is consecutive: O(n)

Hence, naive soln. comes out to be: O(n3)

Comment hidden because of low score. Click to expand.
0
of 2 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

but how do you precisely determine if elements in the queue form a sequence ?

suppose you array starts with '6 8 4 5 7' (which form a sequence 4 5 6 7 8)
so at the beginning min = 6 and max = 8
but the next element we encounter is 4 which is neither one above
max nor one below min..

furthermore you cannot just simply pop up elements from the queue
if they do not form a sequence at this step as they can be a part of, perhaps, longer sequence

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

Then how to solve??

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

Then how to solve??

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

Why dont we consider Sorting in ascending order first?
that it will be easy .

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

One approach could be to sort the array - O(nlogn). Once we have sorted the array we can then start from the array beginning to maintain the longest sequence seen thus far.

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

I have the solution to the problem :
Input :
4,5,1,5,7,4,3,6,3,1,9, 5, 7, 2 - Array
0 1 2 3 4 5 6 7 8 9 10,11,12,13 - Index
1) Sort the array
1,1, 2,3,3,4,4,5,5, 5,6,7, 7,9 - Array
2,9,13,6,8,0,5,1,3,11,7,4,12,10 - Original Indexes
2) Is the array continuous by value?
If not find the subarrays that are continuous :
1,1, 2,3,3,4,4,5,5, 5,6,7, 7
and
9
3) for each continuous subarrays (by value), sort them by indexes:
The sorted indexes will be :
0,1,2,3,4,5,6,7,8,9,11,12,13 - Indexes
4,5,1,5,7,4,3,6,3,1, 5, 7, 2 - Values
4) Is the array continuous by index ?
We have two seq :
0,1,2,3,4,5,6,7,8,9 and
11,12,13
5) for each seq, sort the array by value:
1,1,3,3,4,4,5,5,6,7 - Values check at step 3 to see if it is correct
2,9,6,8,0,5,1,3,7,4 - Indexes
6) Again there are two possible subarrays to search :
1,1 and (this will fail because when we will sort the indexes they will not be continuous)
3,3,4,4,5,5,6,7
7) Sort the array by values :
5,7,4,3,6,3 - values
3,4,5,6,7,8 - indexes
8) is it continuous by value (sort and check)? Yes
9) is it continuous by index ? Yes
WE HAVE A WINNER!

I will post the Java Code

Comment hidden because of low score. Click to expand.
0

This is not bullet proof and lot of sort calls are used. The code can be improved but the general idea is important.

``````public class ContiniousSubarray {

public ContiniousSubarray() {

}

public void start() {
int[] arr = new int[] { 4, 5, 1, 5, 7, 4, 3, 6, 3, 1, 9, 5, 7, 2 ,11,15,12,14,14,15,13};
calculate(this.fromArray(arr));
}

private void calculate(List<IntStruct> original) {

if (original.size() < 2) {
return;
}

boolean contIdx = isContinuousIndex(original);
boolean cont = isContinuous(original);

if (cont && contIdx) {
// Solution !!
System.out.println("*******SOLUTION FOLLOWING*************");
printArray(original);
return;
}

if (contIdx) {
for (LinkedList<IntStruct> l : subArrays) {
calculate(l);
}
}else if(cont){
for (LinkedList<IntStruct> l : subArrays) {
calculate(l);
}
}

}

//		System.out.println("Looking in the following array for continuous subarrays:");
//		printArray(original);
Collections.sort(original, valuesComparator);
//		printArray(original);

IntStruct cur = null;

for (int i = 1; i < original.size(); i++) {
cur = original.get(i);
IntStruct prev = original.get(i - 1);

if (cur.value - prev.value > 1) {
} else {
}
}

if(null != cur) {
}

Collections.sort(original, indexComparator);

return subarrays;
}

//		System.out.println("Looking in the following array for continuous subarrays:");
//		printArray(original);
Collections.sort(original, indexComparator);
//		printArray(original);

IntStruct cur = null;

for (int i = 1; i < original.size(); i++) {
cur = original.get(i);
IntStruct prev = original.get(i - 1);

if (cur.index - prev.index > 1) {
} else {
}
}

if (null != cur) {
}

//		Collections.sort(original, indexComparator);

return subarrays;
}

private boolean isContinuous(List<IntStruct> list) {
boolean ret = true;

Collections.sort(list, valuesComparator);

for (int i = 1; i < list.size(); i++) {
if (list.get(i).value - list.get(i - 1).value > 1) {
ret = false;
break;
}
}

Collections.sort(list, indexComparator);
return ret;
}

private boolean isContinuousIndex(List<IntStruct> list) {

Collections.sort(list, indexComparator);

for (int i = 1; i < list.size(); i++) {
if (list.get(i).index - list.get(i - 1).index > 1) {
return false;
}
}
return true;
}

private void printArray(List<IntStruct> structure) {
System.out.println("Array : ");
StringBuilder sb = new StringBuilder();

for (IntStruct str : structure) {
sb.append(str.value);
sb.append(";");
}
System.out.println(sb.toString());
}

for (int i = 0; i < array.length; i++) {
IntStruct str = new IntStruct(array[i], i);
}

return list;
}

public static class IntStruct {
int value;
int index;

/**
* @param value
* @param index
*/
public IntStruct(int value, int originalIdx) {
super();
this.value = value;
this.index = originalIdx;
}
}

private Comparator<IntStruct> valuesComparator = new Comparator<ContiniousSubarray.IntStruct>() {

@Override
public int compare(IntStruct o1, IntStruct o2) {
return o1.value - o2.value;
}
};

private Comparator<IntStruct> indexComparator = new Comparator<ContiniousSubarray.IntStruct>() {

@Override
public int compare(IntStruct o1, IntStruct o2) {
return o1.index - o2.index;
}
};

}``````

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

one solution to this is
sort the array
lets take an example
array is 3 4 6 7 8 10 9 15 5 (store the index as well)
sort it list will be (element, index)
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)(15,7)

so 2 possible solutions are
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
and
(15,7)
now check these option if they are correct
get max and min index for each option and check if max-min+1 = length of the option then this is correct

for eg (15,7)
max and min index is 7 so 7-7+1 =1 so this can be one correct option
else use divide and conquer algo
for eg
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
8-0+1 != 8
divide it as
[(3,0)(4,1)(5,8)(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
[[(3,0)(4,1)] [(5,8)(6,2)] ] and [(7,3)(8,4)(9,6)(10,5)]
[[(3,0)(4,1)] [[(5,8)] [(6,2)]] ] and [(7,3)(8,4)(9,6)(10,5)]

[(3,0)(4,1)] [(5,8)] [(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
start merging now
[(3,0)(4,1)] [(5,8)] [(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
get the result
[(3,0)(4,1)] [(5,8)] and [(6,2)(7,3)(8,4)(9,6)(10,5)]
so possible solutions are
[(15,7)] [(3,0)(4,1)] [(5,8)] and [(6,2)(7,3)(8,4)(9,6)(10,5)]
now final solution is depending on the max length is
[(6,2)(7,3)(8,4)(9,6)(10,5)]

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

Use Kandane Alogrithm.

complexity: O(n)

Comment hidden because of low score. Click to expand.
0

Sorry! posted at wrong location

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

Let's start from the naive solution. Suppose we have a helper function is_Consequence(vector<int>& v) to tell if the vector v is the consecutive sequence or not. It takes O(n) to finish the test. Then we iterate all n^2 subarray to find the longest subarray that is a sequence. That will take O(n^3) time and O(1) space.

Now we take the general strategy of space for time. Also we notice that the question doesn't ask for the index of the elements of the array rather the actual value. I come up the following solution:

``````vector<int> Array::Longest_Subarray_Sequence(vector<int>& v){
sort(v.begin(),v.end());
std::map<int,int> map;
int n=v.size(),max_len=0,start=0;

for(int i=0;i<n;i++){
int left=(map.find(v[i]-1)==map.end()?0:map[v[i]-1]);
int right=(map.find(v[i]+1)==map.end()?0:map[v[i]+1]);
int len=left+right+1;
map[v[i]]=len;

if(len>max_len){
max_len=len;
start=v[i]-left;
}

}

vector<int> result;
for(int i=0;i<max_len;i++) result.push_back(start+i);

return result;
}``````

Input: {4,5,1,5,7,4,3,6,3,1,9}, Output: {3,4,5,6,7}

The ideas are:

1) first sort the array
2) build a hashmap which counts the current length of consecutive sequence
3) for each element, we check its left element-1 and right element+1 to see if they are in the array, if not, len=0 otherwise len=current length
4) mark the max_len and start point on the fly

The code is tested and welcome bug finding

Comment hidden because of low score. Click to expand.
0

The time complexity is O(nlogn) and space is O(n), most of time is spent in sorting

Comment hidden because of low score. Click to expand.
0

I didn't had time to test your code, but supposing you add a "2" at the end of the list, then your result would be 2,3,4,5,6,7 which I don't think is the desired result. In this case the solution should still be 3,4,5,6,7 (if I understood the requirements correctly).

Comment hidden because of low score. Click to expand.
0

PS: In the problem description, the hint answer is sorted in it's original position :
a = {4,5,1,----5,7,4,3,6----,3,1,9}
max subarray = {5,7,4,3,6}

So I am pretty much convinced that we are talking about a contiguous array. The example was given in this way because they wanted to make their lives simpler and have the counter-example at their fingertips (a 2 at the end of the array) and they also wanted the naive sort then search for contiguous array solution to work.

Comment hidden because of low score. Click to expand.
0

On first thought. If the requirement is continuous subarray, then my result is not right. In your counter-example, adding 2 will result in 1,2,3,4,5,6. But if we add the requirement that we should output its original position, then I don't think sorting will be possible here because we can't locate their original positions even with hashmap because of duplicate elements.

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

In the problem statement nothing has been mentioned that sub-array elements should be contagious.. But example gives answer as contagious Array..So for the example One solution could be
Ex - {4,5,1,5,7,4,3,6,3,1,9}

Find the max and min value in the array
max = 9
min=1
Now make a count array of size max-min+1;
So here we make array of size 9 and initialize it to 0 first.
Now scan the array and mark count[min+i]++
So array would be
1 0 1 1 1 1 1 0 1 for elements 1 to 9.
Now scan the count array. Find the indices between which there are all 1's
So range is for min+lower i = 2 and min+higher i =8.
Now we develop final answer by scanning the initial array and store elements in some container say vector
So array is {4,5,1,5,7,4,3,6,3,1,9}
answer vector be v ..Every Element must be between 3 and 8 to be considered.
SO first we see 4 we push it into v and decrement the count array ,
then 5 ..push again decrement the count array
when we see 1 as its not in range we dont put it inside,we clear the vector by popping out elements and increment the count array as this cant be our answer
We start from 5 push it again into v .V is 5
Push 7
Push 4
Push 3
Push 6 .

I am assuming here the sub array needs to be contagious.
This method has an anomaly when the numbers will be very high.If Min is INT_MIN and max is INT_MAX then this method wont work as you cant allocate such a big array.For this we can sort the array . Find Min and then check which is the first consecutive element not present .

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

In the problem statement nothing has been mentioned that sub-array elements should be contagious.. But example gives answer as contagious Array..So for the example One solution could be
Ex - {4,5,1,5,7,4,3,6,3,1,9}

Find the max and min value in the array
max = 9
min=1
Now make a count array of size max-min+1;
So here we make array of size 9 and initialize it to 0 first.
Now scan the array and mark count[min+i]++
So array would be
1 0 1 1 1 1 1 0 1 for elements 1 to 9.
Now scan the count array. Find the indices between which there are all 1's
So range is for min+lower i = 2 and min+higher i =8.
Now we develop final answer by scanning the initial array and store elements in some container say vector
So array is {4,5,1,5,7,4,3,6,3,1,9}
answer vector be v ..Every Element must be between 3 and 8 to be considered.
SO first we see 4 we push it into v and decrement the count array ,
then 5 ..push again decrement the count array
when we see 1 as its not in range we dont put it inside,we clear the vector by popping out elements and increment the count array as this cant be our answer
We start from 5 push it again into v .V is 5
Push 7
Push 4
Push 3
Push 6 .

I am assuming here the sub array needs to be contagious.
This method has an anomaly when the numbers will be very high.If Min is INT_MIN and max is INT_MAX then this method wont work as you cant allocate such a big array.For this we can sort the array . Find Min and then check which is the first consecutive element not present .

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

O(n) time / O(n) space

void max_subarray(int *a, int n, int **p, int **q)
{
int i;
int max_ending_here=0;
int current_max=0;

*p=*q=a;

for(i=0i<n;i++)
{
max_ending_here+=a[i];
if(max_ending_here<0)
{
max_ending_here=0;
// Reset p,q;
*p=*q=a+i;
}
if(current_sum<max_ending_here)
{
current_sum=max_ending_here;
(*q)++;
}
}
// p,q will now contain the list of nos...
// current_sum will contain the max sum...
/* This is a DP approach, kindly feel free to correct me if you have a solution better than O(n)*/
}

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

codechef.com/problems/CHEFTOWN

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

If array contains numbers from 1-100 or something that we can use bool array to mark [T/F] for present elements in first go. And then, in second go, we can count the maximum consecutive [T] values.

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

can u give the solution of this

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

Wat about using a procedure of matrix multiplication. i.e by dividing the sequence and find a solution.

Comment hidden because of low score. Click to expand.
0

could you elaborate more on your soln ?

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

u guys suck!
it's straightforward to use a dp.

Comment hidden because of low score. Click to expand.
0

just don't say dp.. talk more about the recursive function..

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

Was this even asked in an interview? I dont think so. Interview questions tend to be relatively easy as they are to be solved there and then.

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

one solution to this is
sort the array
lets take an example
array is 3 4 6 7 8 10 9 15 5 (store the index as well)
sort it list will be (element, index)
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)(15,7)

so 2 possible solutions are
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
and
(15,7)
now check these option if they are correct
get max and min index for each option and check if max-min+1 = length of the option then this is correct

for eg (15,7)
max and min index is 7 so 7-7+1 =1 so this can be one correct option
else use divide and conquer algo
for eg
(3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
8-0+1 != 8
divide it as
[(3,0)(4,1)(5,8)(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
[[(3,0)(4,1)] [(5,8)(6,2)] ] and [(7,3)(8,4)(9,6)(10,5)]
[[(3,0)(4,1)] [[(5,8)] [(6,2)]] ] and [(7,3)(8,4)(9,6)(10,5)]

[(3,0)(4,1)] [(5,8)] [(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
start merging now
[(3,0)(4,1)] [(5,8)] [(6,2)] and [(7,3)(8,4)(9,6)(10,5)]
get the result
[(3,0)(4,1)] [(5,8)] and [(6,2)(7,3)(8,4)(9,6)(10,5)]
so possible solutions are
[(15,7)] [(3,0)(4,1)] [(5,8)] and [(6,2)(7,3)(8,4)(9,6)(10,5)]
now final solution is depending on the max length is
[(6,2)(7,3)(8,4)(9,6)(10,5)]

Comment hidden because of low score. Click to expand.
0

Just a little modification to above algo.
after we have (3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)

start splitting at each position one by one and see if maxIndex -minIndex + 1 == length of partition
1. partition is (3,0) and (4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left it is 0-0+1 == 1, so possible with len = 1
for right it is 8-1+1 !=7
2. partition is (3,0)(4,1) and (5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left, 1-0+1 ==2, len = 2, maxlen becomes 2
for right, 8-2+1 != 6
3. partition is (3,0)(4,1)(5,8) and (6,2)(7,3)(8,4)(9,6)(10,5)
for left, 8-0 + 1 != 3
for right, 6-2 +1 == 5, len = 5, maxlen becomes 5
and so on

at the end you have the ans.

Comment hidden because of low score. Click to expand.
0

You didn't handle duplications

Comment hidden because of low score. Click to expand.
0

Your solution will fail for input: {10, 16, 9, 14, 15, 16, 17, 12, 18} in more than 1 place.
You didn't handle duplication and no one promises that 2 partitions will solve it. for this one the right partitioning is:
(9,1)(10,0)(12,7) - (14,3)(15,4)[(16,1)|(16,5)](17,6) - (18,8)

Comment hidden because of low score. Click to expand.
0

(9,2)*

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.

### 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.