## A9 Interview Question for Area Sales Managers

• 0
of 0 votes

Team: none
Country: India
Interview Type: Written Test

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

This boils down combination problem, try nCn/2 combinations and on each output, just compare the diff with the desired result(it is array total/2) if it's closest to it then this is one group.

I know I missed the ordering, but that can be handled it's not a big deal.

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

In this question, it's a matter of establishing your if's in the correct order. The primary constraint is that the number of boxes must be even and keep relative order(or within 1 of each other). The weight is a secondary consideration. So to complete the algorithm establish two lists and cycle through the boxes one a time and:

1. compare the size of list1 and list2. If list1.size() > list2.size() add to list 1 and go to next box(or list2.size() > list1.size() add to list 2 and go to next box).
2. if the lists are the same size compare weights of the lists. Add the box to the list with the lowest weight.

This is a greedy approach that operates in O(n) time and by inserting the items to the same point of your list each time, you maintain the ordered criteria. Note that you can also replace the list with a Queue if you want to enforce a FIFO constraint. Space complexity will be O(n) additional space for the two lists.

``````public void sortBoxes(Box[] boxes){
LinkedList set1 = new LinkedList();
LinkedList set2 = new LinkedList();

int weight1 = 0;
int weight2 = 0;

for(int i = 0; i < boxes.length; i++){
if(set1.size() < set2.size()){
set1.add(box[i]);
weight1 += box[i].weight;
continue;
}

if(set2.size() < set1.size()){
set2.add(box[i]);
weight2 += box[i].weight;
continue;
}

if(weight1 <= weight2){
set1.add(box[i]);
}
else{
set2.add(box[i]);
}
}
}``````

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

As far as I know, It's a NP-complete problem.

A good aproximation can be done like this.
first sort the array in second one, keep the position of each box from the original array.
(the sorted array contains the whieght and the original position of each box (pos)).

you need two arrays first and secnd and the total firstSum and secondSum.
if n is odd:
add the first box from the sorted array to first array in position (pos+1)/2. add its weight to the firstSum.

if n is even start here.

now distribute recursivly 4 boxes to the two arrays. (two from the end sorted array and two from the start).
if firstSum > secondSum then
{ secondArr[pos/2] = a[end] secondSum += a[end]}
{ firstArr[pos/2] = a[end-1] firstSum += a[end-1].}
else vice versa
if firstSum > secondSum then
{ firstArr[pos/2] = a[start] }
{ secondArr[pos/2] = a[start+1] }
else vice versa

now call recursively to function with start+2 and end-2.

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

1)take the total sum of the array and divide it by two.
2)divide the array into two equal parts as said.
3) now each two parts should be as close as possible to the total sum/2.
4)consider the first part of array.
5)pick the first element from the array and subtract it from sum/2 say it comes as y..
6)now find the closest element to the y from the entire array.
7)go on doing the same till you reach the sum/2.

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