Author |
Topic: google ques (Read 1449 times) |
|
rahul_832
Newbie
Gender: 
Posts: 18
|
 |
google ques
« on: Dec 25th, 2009, 7:37am » |
 Quote  Modify
|
Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum ?
|
|
 IP Logged |
|
|
|
fiddler
Newbie
Posts: 17
|
|
Re: google ques
« Reply #1 on: Dec 25th, 2009, 12:14pm » |
Quote Modify
|
1. take sum of whole array..."sum"
2. sum2=0; mindiff=~0; (i.e. max possible)
3. start from index 0 to n... i=0 -> n
a. subtract a[i] from sum and add to sum2
b. if abs(sum2-sum)<abs(mindiff) ,then change mindiff.
|
| « Last Edit: Dec 25th, 2009, 12:14pm by fiddler » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: google ques
« Reply #2 on: Dec 25th, 2009, 12:54pm » |
Quote Modify
|
Its a famous partition problem and its a NP-complete problem. There are methods to solve it (when range of values is limited) with dynamic programming. read this
http://en.wikipedia.org/wiki/Partition_problem
@fiddler
Please explain your solution in more detail, i think it wont work 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
fiddler
Newbie
Posts: 17
|
|
Re: google ques
« Reply #4 on: Dec 25th, 2009, 1:33pm » |
Quote Modify
|
i hope i have got the ques correct... dis is what i think the ques requires...
abs(sum of a[0]->a[i]) - abs(sum of a[i+1]->a[n]) is least ... we hav to give the value of "i"...?
or is it that we have to randomly pick up integers 4m the array and then find the least difference?
|
| « Last Edit: Dec 25th, 2009, 1:33pm by fiddler » |
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: google ques
« Reply #5 on: Dec 26th, 2009, 5:19pm » |
Quote Modify
|
on Dec 25th, 2009, 1:33pm, fiddler wrote:i hope i have got the ques correct... dis is what i think the ques requires...
abs(sum of a[0]->a[i]) - abs(sum of a[i+1]->a[n]) is least ... we hav to give the value of "i"...?
or is it that we have to randomly pick up integers 4m the array and then find the least difference? |
|
Seems the start and end of 2 subarrays are not fixed. it need not be a[0] , a[n].
In any case... this problem is not NP complete. since we just need to try all possible start1, end1 for first subarray with all possible start2, end2 of second subarray. and a trivial naive solution would be O(n^4).
Can this be done better?
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: google ques
« Reply #6 on: Dec 27th, 2009, 4:08pm » |
Quote Modify
|
This problem can be solved like edit-distance problem. Just as we align strings to reduce the distance between two strings, in this case you can try to minimize the difference between the horizontal and the vertical sum.
A B C D
A
B
C
D
Suppose you are trying to partition an array which contains A,B,C and D. Now the cost function in this edit distance will insertion and deletion are 0 cost, but match and substitution have infinite cost. So, you will be performing insertions and deletions. The recurrence relation will be as below.
MinSum = min(val(i,j-1)+1,val(i-1,j)+1)
Now traversing from last cell to first gives you the elements in each array.
Please let me know if this is correct.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: google ques
« Reply #7 on: Dec 28th, 2009, 1:24am » |
Quote Modify
|
on Dec 27th, 2009, 4:08pm, bmudiam wrote:This problem can be solved like edit-distance problem. Just as we align strings to reduce the distance between two strings, in this case you can try to minimize the difference between the horizontal and the vertical sum.
A B C D
A
B
C
D
Suppose you are trying to partition an array which contains A,B,C and D. Now the cost function in this edit distance will insertion and deletion are 0 cost, but match and substitution have infinite cost. So, you will be performing insertions and deletions. The recurrence relation will be as below.
MinSum = min(val(i,j-1)+1,val(i-1,j)+1)
Now traversing from last cell to first gives you the elements in each array.
Please let me know if this is correct. |
|
I cannot match what you write to the problem the thread is solving. So I would say it is not correct.
Easy solution (with O(n) space requirements) is to calculate flying sums
 j=1ivalj and j=invalj in O(n) and search for minimal difference of corresponding sums again in O(n).
|
| « Last Edit: Dec 28th, 2009, 1:29am by Hippo » |
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: google ques
« Reply #8 on: Dec 28th, 2009, 5:27am » |
Quote Modify
|
on Dec 28th, 2009, 1:24am, Hippo wrote:
I cannot match what you write to the problem the thread is solving. So I would say it is not correct.
Easy solution (with O(n) space requirements) is to calculate flying sums
j=1ivalj and j=invalj in O(n) and search for minimal difference of corresponding sums again in O(n). |
|
I am trying to solve the problem, where the elements in each sub arrays need not be contiguous in the original array. In that case, maintaining sum won't help and dynamic programming will be the option I think.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: google ques
« Reply #9 on: Dec 28th, 2009, 5:39am » |
Quote Modify
|
on Dec 28th, 2009, 5:27am, bmudiam wrote:
I am trying to solve the problem, where the elements in each sub arrays need not be contiguous in the original array. In that case, maintaining sum won't help and dynamic programming will be the option I think. |
|
In that case you are working on NPcomplete one as mentioned in the 2nd reply.
|
| « Last Edit: Dec 28th, 2009, 5:40am by Hippo » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: google ques
« Reply #10 on: Dec 30th, 2009, 10:08am » |
Quote Modify
|
on Dec 26th, 2009, 5:19pm, inexorable wrote:
Seems the start and end of 2 subarrays are not fixed. it need not be a[0] , a[n].
In any case... this problem is not NP complete. since we just need to try all possible start1, end1 for first subarray with all possible start2, end2 of second subarray. and a trivial naive solution would be O(n^4).
Can this be done better? |
|
if this is the problem, then it can be done easily on O(n^2) time and space complexity.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: google ques
« Reply #11 on: Dec 30th, 2009, 1:37pm » |
Quote Modify
|
Birbal..please explain your O(N^2) algorithm..
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
tombstone
Newbie
Posts: 14
|
|
Re: google ques
« Reply #12 on: Jan 31st, 2010, 5:10am » |
Quote Modify
|
I think a slight modification to the problem will help us solve this.
If the array has a negative number, find the least negative number, add the magnitude of least (-)ve number to all the numbers.
After doing this if the size of the array and the magnitude of the number permits , perform the normal balanced partition dp.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: google ques
« Reply #13 on: Feb 2nd, 2010, 9:25am » |
Quote Modify
|
on Dec 30th, 2009, 1:37pm, bmudiam wrote:| Birbal..please explain your O(N^2) algorithm.. |
|
Store the sum[i,j] = sum of array from a[i] to a[j].
Now find two same sums.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print