Google Interview Question






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

Observing the insanity of above posts which claim to develop a greedy O(nlogn) solution for a variation of partition problem, I was compelled to code the program. Being NP-hard by nature, the solution falls into pseudo-polynomial time algorithm with complexity O(n^2W) where n = # of elements, W = sum of elements.

//constraints: n is even
void fun (int items[], int n)
{
	int total = accumulate (items, items+n, 0) / 2;
	int maxSubsetSz = n/2 ;
	
	vector< vector<int> > T (maxSubsetSz+1, vector<int> (total+1, 0) );

	//T[i][j] is set if there exists subset of size i that sum up to j
	T[0][0] = 1;	

	for(int i = 0; i < n; i++) //consider taking i-th item 		
           for(int k = maxSubsetSz-1; k >= 0; k--) //each item must be taken once, hence loop backwards
	       for(int j = 0; j <= total-items[i]; j++)  
	           if ( T[k][j] && items[i]+j <= total )		      		    
                         T [k+1] [j+items[i]] = 1;

	for(int j = total; j >= 1; j--)
	   if ( T [maxSubsetSz][j] ) {
		cout << "sum : " << j << endl; 
		break;
	}
}

- anon August 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Brute force for this is n^2 ... Why bother DP ...

- galoa April 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

In the partition problem, the partitions can be of any size hence it is an NP-Complete problem. In the given question, there is a constraint that the two sets should have equal number of elements so it can be solved in O ( n log n )

- GP November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is an NP-Hard problem.

- Anonymous August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Number of elements in set(N) is even, and assume it could be 1,000,000. So, O(n^2) is ruled out!

- anonymous August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

spelling issues :) "can't be arbitrary" and "smaller one in the set with the bigger sum"

- Anonymous August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we have a pseudo polynomial dynamic programming based solution to this?

- Myth August 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain the algorithm for the solution a different way please?

Not understanding how the supersonglj solution works.

- confused August 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe a three-dimension DP could solve this problem? let f[i][j][k] denotes if the value k could be formed, where i denotes the i-th position in the array, j denotes there are j numbers have been chosen previously.
Then we could try to find the f[n][n/2][k] where f[n][n/2][k] == 1 and abs(k - sum / 2) is minimum.

- PlayerOne August 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are right. But why should we use 3D array, when 2D suffices. Read my above post with code. Feel free to test it, and let me know if you encounter anything wrong!

- anon August 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with you. I'm only using the 3D array for the convenience of describing the algorithm, it could be reduced to 2D array in implementation.

- PlayerOne September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@anon, NP-Hard guy.
What you are saying is correct about NP-Hardness of the problem.

Instead of criticizing others about posting solution.
Suggest what should interviewee respond, when this kind of question appears.
He cant simply say its NP-Hard so no solution exists.

BTW: I haven't seen any solution to problem or constructive comment other than using slang here.

- Anonymous October 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Google13_FindMinDiffSets {

/*
* In my opinion,
* First, we find the first two numbers which have the min diff.
* Then recursive on the following set, find another two, compare which set should add these two new value,
* Then continue until all elements have been assigned
*/
private static ArrayList<Integer> zero = new ArrayList<Integer>();
private static ArrayList<Integer> one = new ArrayList<Integer>();

public ArrayList<ArrayList<Integer>> getMinSumDiffSets(int[] array) {
if (array.length % 2 != 0) {
return null;
}

ArrayList<ArrayList<Integer>> result ;
if (array.length == 2) {
if (Math.abs((sum(zero)+array[0])-(sum(one)+array[1])) < Math.abs((sum(zero)+array[1])-(sum(one)+array[0]))) {
zero.add(array[0]);
one.add(array[1]);
} else {
zero.add(array[1]);
one.add(array[0]);
}
result= new ArrayList<ArrayList<Integer>>();
result.add(zero);
result.add(one);
return result;
} else {
int[] min = findMinDiff(array);
if (Math.abs((sum(zero)+array[min[0]])-(sum(one)+array[min[1]])) < Math.abs((sum(zero)+array[min[1]])-(sum(one)+array[min[0]]))) {
zero.add(array[min[0]]);
one.add(array[min[1]]);
} else {
zero.add(array[min[1]]);
one.add(array[min[0]]);
}
result = getMinSumDiffSets(deleteElements(array, min[0], min[1]));
return result;
}
}

public int[] findMinDiff(int[] a) {
int min = Integer.MAX_VALUE;
int[] result = new int[2];
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[j]-a[i] < min) {
min = a[j]-a[i];
result[0] = i;
result[i] = j;
}
}
}

return result;
}

public int sum (ArrayList<Integer> a) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i);
}
return sum;
}

public int[] deleteElements(int[] a, int i, int j) {
int[] result = new int[a.length-2];
int index = 0;
for (int k = 0; k < a.length; k++) {
if (k == i || k == j) {
continue;
} else {
result[index++] = a[k];
}
}
return result;
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,2,3,100};
Google13_FindMinDiffSets g = new Google13_FindMinDiffSets();
ArrayList<ArrayList<Integer>> result = g.getMinSumDiffSets(a);
System.out.println(g.sum(result.get(0)));
System.out.println(g.sum(result.get(1)));
}

}

- shiqing881215 August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a while I really thought a greedy solution may be helpful here, however take for example an array like: 0,1,2,3,4,5,6,7,8,9,10...100,10000000. The correct solution is to sum the 10000000 with the 0..49

- Demo May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this actually seems simple, no? your method looks right to me except you're missing a simplification. the problem is essentially recursive - at each step you're looking to minimize a pair. so, sort the way you did and then take the biggest two elements (or smallest - doesn't matter).

minimize the distance between them, taking the current set sum into account, which is currently zero. now take the next two biggest and put them into the right sets - it can be arbitrary, you have to put the bigger one in the set with the smallest sum and the bigger one in the set with the bigger sum.

do that until your list of numbers is exhausted

the proof is that at any one step you have a number that must go into a set and you're looking to pair it with a number that minimizes the difference, which is the next biggest one - there's no other choice because you can only select one, since both sets have to have the same number of elements.

O((n log n) + n / 2) so, nlogn

- Anonymous August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, as stated before, this is NP-Hard.

Lookup partition problem on the web.

- Anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think you are wrong.
in your method, every neighbouring pair(1st and 2nd, 3rd and 4th, ...) will be put into different set. consider this case:
1 2 3 4 5 9
the answer should be {1,2,9} vs {3,4,5}
according to your method, the final result will be {1,4,5} vs {2,3,9}

- supersonglj August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, bloody hell... yup, thanks.

(And, as for the NP-Hard guy... you're a friggin moron. Say something useful or shut the hell up).

- Anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon It is NP-Hard. So if you get an O(nlogn) time algorithm, you are either a genius (doubtful in your case) or your algorithm is wrong.

It was mentioned before: lookup partition problem on the web. The first link on google to searching partition problem is a wiki page describing this.

F***ing idiot.

- Anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're NP-Hard.

- Anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's right that problem is NP-hard, but it doesn't look same as partition problem (though it is just a simple reduction away)

- SpeedX August 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this problem can be solved using a DP method, something like a knapsack problem.
let n be the number of elements, a[1..n] be the list
let sum be the sum of all n elements
denote bool f[i][j] means choose i numbers, whether the sum can be j or not.
initially, all f are false except f[0][0]=true

for (i=1;i<=n;i++) {
    for (j=min(i,n/2)-1;j>=0;j--) {
        for (k=sum/2;k>=0;k--) if (f[j][k] && k+a[i]<=sum/2) f[j+1][k+a[i]]=true;
    }
}

for (i=sum/2;;i--) if (f[n/2][i]) {
    // found the minimal diff
    // the diff is sum/2-i;
    break;
}

if the detailed numbers in each set is needed, just record it in another array when doing DP

- supersonglj August 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont know why there are 3 for loops
Here's my code.

/*
Author : SRIRAM S
*/
// Libs 
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,A,n) for(int i=A;i<n;i++)
#define sz(c) (signed int) c.size()
#define pb(c) push_back(c)
#define INF (int) 1e9
#define all(c) c.begin(),c.end()
#define GI(t) scanf("%d",&t)
#define VI vector<int>
#define PII pair <int,int>
typedef long long LL;

using namespace std;

// Global Vars 

// End of Global Vars

// Function Declarations

int Solve();
int Partition(int A[], int n);

// End of Function Declarations

// Functions Used

int main() {
    clock_t start = clock();
    int ret=Solve();
    clock_t end = clock();
    cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
    return 0;
}

int Solve() {
    int n;
    GI(n);
    int A[n];
    for(int i=0;i<n;i++) GI(A[i]);
    sort(A,A+n);
    int ret = Partition(A,n);    
    return 0;
}

int Partition(int A[], int n) {
    int sum = 0;
    REP(i,n) sum += A[i];
    bool memo[n+1][sum+1];
    memset(memo, 0, sizeof(memo));
    memo[0][0] = true;
    for(int i=1;i<=n;i++) {
        for(int j=sum/2;j>=0;j--) {
            if(j>=A[i-1])
            memo[i][j] = max(memo[i-1][j], memo[i-1][j-A[i-1]]);
            else memo[i][j] = memo[i-1][j];
        } 
    }

    int ans = INF;
    int j;
    int setsum = INF;
    for(j=sum/2;j>=0;j--) {
        if(memo[n][j]) {
            if(ans > abs(sum/2 - j)) ans = sum/2 - j, setsum = j;    
        }
    }
    cout<<"ans = "<<ans<<endl;

    cout<<"the sums are  = "<<setsum<<" "<<sum - setsum<<endl;
    return ans;
}

- Sriram S August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you cannot ensure the sizes for two sets be the same
try this data:
4
1 2 3 6
your code will return diff=0, but this is based on {1,2,3} and {6}

in your code, memo[i][j] means using up to i numbers, the sum can be j, but in my method, f[i][j] means choosing exactly i numbers.
the difference is here

- supersonglj August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I can't get your recurrence. What is the size of f[][] matrix? I think it's of size n/2 * sum/2. Is it correct?

Could you pls write the recurrence (in sentence) for f[j][k] which as you mentioned to check if any subset of j elements sum up to k.

- anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, the size of f[][] is n/2*sum/2.
what do you mean by "recurrence (in sentence)"?

- supersonglj August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If size of f[][] is n/2*sum/2 I see obvious problem in your solution.

if (f[j][k] && k+a[i]<=sum/2) 
    f[j+1][k+a[i]]=true

When you access last line, k+a[i] could > sum/2. I'm not sure how you didn't get "Array boundary exceed" problem when ran this code.

As you must know, solution to DP is expressed as a recurrence relation that relates one subproblem to previously computed subproblem. To solve this problem, I used O(n^3) time and space using below recurrence:

partition[k][i][j] is 1 if we there exists some subset of size 
k using the set of elements {1,2,...,i} that sum to j. 
partition [k][i][j] = partition [k][i-1][j] |  
                      partition [k-1][i-1][j-item[i]]

I couldn't grasp how the recurrence is built up in your solution, specially how/why did you assign j=min(i,n/2)-1. It seemed some reason that the solution may include some of the input twice. I'm interested how yours works as it's with O(n^2) space.

- anonymous August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For your first question, the actual size of f[][] is (n/2+1)*(sum/2+1). And in IF sentence, I restricted "k+a[i]<=sum/2", so it won't exceed. This is also why in my for loop for j, the maximum value is min(i,n/2)-1, this ensures j+1 will smaller than or equal to n/2.

As I stated before, f[i][j] in my method means choosing exactly i elements, the sum can be j or not. And our final target is to see if f[n/2][sum/2] is true, or find the maximum k(<=sum/2) that f[n/2][k] is true. So for f[i][j] where i>n/2 or j>sum/2, it doesn't need to calculate.

In addition, my for loops for j and k are backwards(from max value to 0), this ensures no input will be counted twice. If these for loops are forwards, then that means all the input will be counted arbitrary many times.

I'm not sure if I explained clearly. @_@

- supersonglj August 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

in C#
orig.Sort();
for (int i = orig.Count - 1; i >= 0; --i)
{
if (set1.Sum() > set2.Sum())
{
set2.Add(orig[i]);
}
else
{
set1.Add(orig[i]);
}
}

- phil August 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

obviously, cannot ensure that set1.size() equals to set2.size()
e.g.
1 2 3 6

- supersonglj August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Sort Elements of Array.
2. SET1 & SET2 contains zero elements.
3. For each pairs(e.g. e1, e2) of element from beginning of sorted array do following
	a. SUM1 = SUMMATION(SET1) + e1;
	b. SUM2 = SUMMATION(SET2) + e2;
	c. SUM3 = SUMMATION(SET1) + e2;
	d. SUM4 = SUMMATION(SET2) + e1;
	e. if(MOD(SUM1, SUM2) < MOD(SUM3, SUM4))
			Add e1 to SET1 & e2 to SET2
		else
			Add e2 to SET1 & e1 to SET2
	
Result: SET1 & SET2 contains final elements.

Time Complexity: N*log(N) + (N/2)

- SRB August 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What's the proof that greedy works? In general inputs, greedy will fail for partition problems :)

- anonymous August 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another genius trying to prove P=NP...

- Anonymous August 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude, Where you find the solution proofing P=NP ? Go through the solution well before put your stupid comments.

- SRB August 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Shreyas:Analyze your solution atleast for some basic inputs man. Consider numbers {1,2,3}. Acc to your Algo, in the first step the set will be Set1={1} and Set2={2}. In the second step 3 has to go with Set1 to give the lowest sum and the final partition is Set1={1,3} and Set2={2} and the difference is 4-2=2. THIS IS INCORRECT! The correct partition will be Set1={1,2},and Set2={3}, which will give me a difference of 0. This is an NP complete problem.

- RR August 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@RR ... Dude read the question again. Each set have equal number of elements. So the example which you are consider is not applicable.

- SRB August 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Abbe ch***iye Shreyas. Read the whole thread. This is NP-Hard.

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does Shreyas saying this as P problem with solution or proved it P=NP problem ? He only suggest a solution. What makes you so much worry ?

- Swamy August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Swamyji,

Problem is NP-Hard. Any solution solving in O(nlogn) time shows it is in P. In P and NP-Hard implies P=NP...

Please, you and shreyas do some readings before getting offendings.

This is a site with a lot of junk posts. Don't feel bad if that gets called out. It is for the good of the readers.

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hummm .. But the thing is, the solution provided by Shreyas is not bad even though this is NP-Hard problem. I went through whole conversation and you measleading the conversation.

Anyone can suggest solution, which does not mean that you are here to guide every one.

- Swamy August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Swamyji.

A miss is as good as a mile.

Once it has been pointed out that it is NP-Hard, you better take a good look at your O(nlogn) time algorithms...

Calling it "Not bad" is ridiculous.

It is NP-Hard. It is the partition problem with equal sized subsets.

See: en.wikipedia.org/wiki/Partition_problem

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh I see... According to your concept any solutions to NP problems are bad.

- Swamy August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL @swamy.

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Swamyji,

Looks like you don't really understand what NP-Hard means.

No more on this. Please do some reading and try to understand what it means to get a polynomial time algorithm for an NP-Hard problem. (Hint: Usually it means the algorithm is _wrong_).

- Anonymous August 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Amazed to see how many JUNKS are on CC who doesn't know what is NP-hardness. Which companies hire this type of guy, I just wonder :-O

- anon August 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well... I very well know what is NP problem. The thing is you are not accepting any solution to NP Hard problem even it is not bad(I am not saying this is excellent solution). Understand one thing is: "any thing is better than nothing".

@anon... Stop your nonsense post here.

- Swamy August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Com'on genius, Swamy! You should stop hunting for "silly" software engineer. Rather apply to MIT for a faculty position claiming that YOU GOT A SOLUTION OF COMPLEXITY O(NLOGN) TO SOME NP-HARD PROBLEM....

So talented you are, dude! Glad to meet you here :D

- anon August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks anon. . . Finally you know me who am I. That's true I am genius only for ppl like you. Thx for suggestion about MIT, I must try out and will give your references for getting entry.

What is your title ?

- Swamy August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks anon. . . Finally you know me who am I. That's true I am genius only for ppl like you. Thx for suggestion about MIT, I must try out and will give your references for getting entry.

What is your title ?

- Swamy August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lols....... hilarious!

- anonymous August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For IDIOTS like SSS and Swamy, this is the input to PROVE that greedy sucks!

array[10] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 15
sum = 60
greedy partitions first 8 items as below:
partition1 : 1, 4, 5, 8 ; sum = 18
partition2 : 2, 3, 6, 7 ; sum = 18

so far, so good! But when the final 2 elements are considered, 9 goes to partition1 and 15 to partition2. So, it gives 27 and 33 as solution, whereas it should be :

partition1 : 1, 5, 7, 8, 9 ; sum = 30
partition2 : 2, 3, 4, 6, 15 ; sum = 30

I can't realize why these type of stupid fellows can't verify their approach working with few inputs. All junky assholes!

- anonymous August 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I found the original IDIOT who post this idea earlier used nick "SSS"... this asshole now changed nick to "CBI". What a freak!

- anonymous August 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool.. Love to see some Dog are barking to my solution with there mother language & some Dog keep following me. Keep it up, good work & continue my pet dog.

But the solution & approach is very excellent.

Let me know any other slang you know.

- SRB August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you claim

the solution & approach is very excellent

you won't ever get a job in top-notch companies ever. Believe it, or not - but that would be the fact. Top-ranked companies don't need a shit like you who being a (at best) average-graded programmer just come to CC to brag that they know everything... even some O(nlogn) solution for some NP-hard problem.... wow! how genius you are, Mr. CBI :~O

- anonymous August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Dude. This is not claim, but a bread for stray dog who are barking here with there mother language.

And first look on yourself for top-ranked company then think about me.

- SRB August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess your monitor is basically a mirror, and whatever you see through it, basically a reflection of yourself. Perhaps once upon a time you were a real human with brain to think... but now I see you are carrying mutant genes, utterly lacking skills to do deep reasoning. This leads you to brag bombastically with silly solution for a well-known NP hard problem. Perhaps it's attributed to your parents, or ancestors who carried such ill-formed genes and passed it to you. Go to watch "Rise of the Planet of Apes" - you would meet forefathers there!

Just to let you know, I'm going to one of the top-15 schools in US. I had been interned at Intel this year at their CA research lab. I was hired by my ex-labmate who is a fulltime research at programming language & platform lab. He has published papers in MICRO, ISCA, ASPLOS and HPCA (all top tier conferences). We submitted our work to ASPLOS-2012 last month. Thank you.

- anonymous August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where ever you go(top 15 or top 5) and what you did, its does not matter. Matter is how you deal with situation. I have not told about myself, and don't want to do it here as well. And don't think that everyone lesser than you.

Keep all your credit or achieviement in your pocket. From your response its reflecting how dirty mind you have.

I was silent from long days, and some stupid ppl keep on using slangs here ... what you say over this ? Is it there genetic problem ? Is this forum for this ?

- SRB August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My motivation is pretty simple. Keep crappy replies away from CC (as far as possible, it's impossible due to self-claimed geniuses like you), 'coz I believe most candidates come here to get quality answers.

How many people are visiting CC every day? It could be perhaps 10000+. If person X doesn't know a solution (or probably he knows, but doesn't wish to help others), he should simply keep his mouth shut. NO ONE is asked to respond to a problem - which misleads others.. like YOU. Well, it may be the case that a problem seems appealing to use some greedy approach (like u did), but when others say that greedy is not suitable, a SANE programmer would check himself, rather bombastically criticize others for catching errors in their silly approach. Trust me, in this way, you wont learn something. To learn, explore problems and think yourself first to convince that a solution is CORRECT (atleast for many inputs). Don't just think the solution is PRETTY EAAAAAAAAAASY......and show everyone how genius you are by typing some garbage. For good reference, (as many others noted before) go and explore WU forum (CS section) - most revered forum for digging into CS interview problems (launched by some UC Berkeley grad).

- anonymous August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where you find claiming for genius ?

There are other way to stop such crap reply, and using slangs for this is not the best way.

- SRB August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lols.... as I told you before you look at yourself first. Your response :

Dude, Where you find the solution proofing P=NP ? Go through the solution well before put your stupid comments.

Even though the guy (who I dont know), was RIGHT to say that if you could get a solution to ONE NP-complete problem in O(nlogn) time it implies (due too Karp reduction), all problems of NPC fall in P, which eventually implies P = NP. If you can't UNDERSTAND, then ask why is he saying so; rather call him a "stupid" when it's you! If you've so doubt on a topics, why can't u ask on Stackoverflow? No one knows everything, so asking never means one is below than others. It only means "i don't know this". That's why so many experts reply on SO even on simple problems. Try new ways to learn everyday!

- anonymous August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To make you clear stupid is called to comments and not to him.

- SRB August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

When a person makes a stupid comment, he naturally is assumed to be treated as stupid folk (for that time being).

Just final advice: to be treated properly, next time make sane responses to any question you find here. Work on paper, learn more, and share with others (if you are generous). But, don't mislead people posting wrong materials. And as you agreed, "quality" people visit this site; they expect "quality" replies!

- anonymous August 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i m guessing O(nlogn) solution pls comment if i m wrong

Ex 2,12,16,20,24,4,6,10
sort 2,4,6,10,12,16,20,24
set 1 : put 2
set2 put 4

now 6 and 10 to be distributed between set 1 and set 2
let put 6 in set 1 and 10 in set 2 or put 10in set 1 and 6 in set 2
choose whichone is best means diff is minimum
repaet this for every two next elemnts
we get the solution

- kamal August 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What r u smoking out dude? An idiot SSS above posted same solution. Why the F*** u need to post same reply? I gave input to show it's WRONG to use greedy.

- anonymous August 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I scan all above posts. I think o(nlogn) is achievable. Following is the step
1. scan the array get the sum and size. time O(n)
2. sort this array. O(nlogn)
3. scan the sorted array. get every (n/2) neighbor sub_sum. O(n);
4 choose the (n/2) with min(abs(sum/2-sub_sum)) O(n)

for example: 1 ,4 ,5 ,3 ,2 ,9

1. sum=24, n=6
2. sort 1 2 3 4 5 9
3. get every 3 neighbor sum: 6, 9 , 12 , 18
4. we find 3+4+5 is most near 24/2 then we put 3,4,5 in one set and others in another set.
{3,4,5} {1,2,9}

- Jove February 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about {1,2,3,7,8,9} ?
The answer will be {1,7,8} = 16, {2,3,9} = 14

- souravdasgupt April 30, 2012 | Flag


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