Athena Health Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

This is a variation of well-known NP-problem (en.wikipedia.org/wiki/Partition_problem). So the only solution is backtracking.

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

There's a well known dynamic programming solution too, when the weights are constrained to relatively small numbers. I think that usually the dynamic programming approach is what interviewers look for in problems like this one.

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

I allowed myself to write the implementation using DP approach:

``````public static void main(String[] args) {

// int[] arr = { 5, 7, 3, 3 };
int[] arr = { 3, 2, 1 };
// int[] arr = { 1, 5, 11, 5 };
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("Sum: " + sum);
boolean[][] sums = new boolean[arr.length][sum + 1];
for (int i = 0; i < sums.length; i++) {
sums[i][0] = true;
}
sums[0][arr[0]] = true;
for (int i = 1; i < sums.length; i++) {
for (int j = 0; j < sums[0].length; j++) {
if (sums[i - 1][j] == true) {
sums[i][j] = true;
sums[i][j + arr[i]] = true;
}
}
}
// printMatrix(sums);
int half = sum / 2;
while (!sums[sums.length - 1][half]) {
half--;
}
System.out.println("Closest to half of the sum: " + half);
Set<Integer> firstHalfIndexes = new HashSet<Integer>();
int rowWithHalf = sums.length - 1;
while (half > 0) {
while (rowWithHalf >= 0 && sums[rowWithHalf][half]) {
rowWithHalf--;
}
rowWithHalf++;
half -= arr[rowWithHalf];
}
List<Integer> firstHalf = new ArrayList<Integer>(firstHalfIndexes.size());
List<Integer> secHalf = new ArrayList<Integer>(arr.length - firstHalfIndexes.size());
for (int i = 0; i < arr.length; i++) {
if (firstHalfIndexes.contains(i)) {
} else {
}
}
System.out.println("First team: " + firstHalf);
System.out.println("Sec team: " + secHalf);
System.out.println("Diff: " + Math.abs(firstHalf.size() - secHalf.size()));
}``````

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

Can you please explain your code a bit? In particular, I'm having a lot of difficulty following what you are doing here:

[code]
Set<Integer> firstHalfIndexes = new HashSet<Integer>();
int rowWithHalf = sums.length - 1;
while (half > 0) {
while (rowWithHalf >= 0 && sums[rowWithHalf][half]) {
rowWithHalf--;
}
rowWithHalf++;
half -= arr[rowWithHalf];
}
[/code]

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

Isn't this limiting the question to finding sums of only 2 elements?

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

{
General Approach:-
Sort the elements into descending order.
Divide the array into 1 and n-1 sub arrays
Find the sum difference if it is equal you got the solution otherwise move the smallest element from set 2 to set one and keep on checking until you got the sum equal.

}

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

Avinash- consider the following array--> [1,2,3,5,9];

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

Here is some code about the problem.

int splitPlayers(int[] set) {

int n = set.length;
int sum = 0;

for(int s:set) {
sum += s;
}
sum /= 2;
boolean[][] subset = new boolean[sum+1][n];
int[][] count = new int[sum+1][n];

subset[set[0]][0] = true;
count[set[0]][0] = 1;

for (int i = 1; i <= sum; i++) {
for (int j = 0; j < n; j++) {
if (set[j] == i) {
subset[i][j] = true;
count[i][j] = 1;
} else if (j > 0) {
if (i >= set[j]) {
subset[i][j] = subset[i][j-1] || subset[i - set[j]][j-1];
if (subset[i - set[j]][j-1] == true) {
count[i][j]=count[i - set[j]][j-1]+1;

} else if(subset[i][j-1]==true) {
count[i][j] = count[i][j-1];
}
}
else {
subset[i][j] = subset[i][j-1];
}
}
}
}
if(!subset[sum][n-1]){
return 0;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (count[sum][i] != 0) {
int onepart = n - count[sum][i];
int other = n - onepart;
min = Math.min(min, Math.abs(onepart-other));
}

}
return min;

}

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

Many thanks EP, it's a good solution!

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

I implemented in dp but i couldnt find bug in my code can anybody help.Logic for every value from last i check whether to put in which optimal team.
#include<stdio.h>
int findMin(int a,int b){
if(a<b)
return a;
else
return b;
}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){
if(firstsum == secondsum){
printf("%d\n",firstsum );
return firstcount -secondcount;
}
}
else
findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),
findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));
}

int main()
{
int arr[]={3,1,6,3,1};
int size=3;
printf("%d\n",findDifference(arr,3,0,0,0,0) );

}

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

#include<stdio.h>
int findMin(int a,int b){
if(a<b)
return a;
else
return b;
}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){
if(firstsum == secondsum){
printf("%d\n",firstsum );
return firstcount -secondcount;
}
}
else
findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),
findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));
}

int main()
{
int arr[]={3,1,6,3,1};
int size=3;
printf("%d\n",findDifference(arr,3,0,0,0,0) );

}

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.