InMobi Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
private int getSum(int[]arr){
int sum=0;
for (int i = 0; i < arr.length; i++) {
sum=sum+arr[i];
}
return sum;
}
private void knapsack() {
// given an array of positive integers and that you are allowed to
//change the sign of any of the integers whenever you require.
//write a program to calculate the minimum sum of this array.
int [] arr = new int[]{0,9,8,7,6,5,4,3};
//sort the array
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if(i!=j){
if(arr[i]<arr[j]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
for (int j = 1; j < arr.length; j++) {
//check total sum considering number as +ve and then -ve
//depending on the min sum consider the sign of the number
int temp = arr[j];
arr[j]=-arr[j]; //negative
int k = getSum(arr);
arr[j]=-arr[j];//positive
int l=getSum(arr);
//compare min sum
if(k<l){
if(k>0)
arr[j]=-temp;
}
else
if(l>0)
arr[j]=temp;
}
//print array
for (int j = 0; j < arr.length; j++) {
System.out.println("="+arr[j]);
}
}
Here is my solution: Run time Complexity is 0(n^2)
public class PartitionSum {
public static int minimum =0;
public static void main(String[] args){
//int[] arr = new int[]{1,5,9,10,3,6,4,2,8,7}; // input array
//int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10}; // input array
int[] arr = new int[]{4,12,22,32,42,52,62,72,82,92};
// 4,12,22,32,42,52,62,72,82,92
int n = arr.length ;
boolean[] flag = new boolean[n];
int[] par = new int[n]; // to store data after partiton
minimum = maximum(arr)- minimum(arr);
findPartition(arr, flag, n, par);
for(int i =0 ; i<n ;i++){
System.out.println(par[i]);
}
}
public static void findPartition(int[] arr, boolean[] flag,int n,int[] par){
int leftSum = 0;
int rightSum = 0;
int left =0;
int right = n-1;
for(int i=0; i<n; i++){
if(flag[i] == true) continue;
int j = findNearest(arr,flag,n,i);
System.out.println("i "+i +" j : "+j);
flag[i] = true;
flag[j] = true;
if(leftSum <= rightSum){
par[left++] = Math.max(arr[i], arr[j]);
leftSum += Math.max(arr[i], arr[j]);
par[right--] = Math.min(arr[i], arr[j]);
rightSum += Math.min(arr[i], arr[j]);
}else{
par[left++] = Math.min(arr[i], arr[j]);
leftSum += Math.min(arr[i], arr[j]);
par[right--] = Math.max(arr[i], arr[j]);
rightSum += Math.max(arr[i], arr[j]);
}
}
if(leftSum > rightSum){
for(int i = right+1; i<n;i++)
par[i] = -par[i];
}else{
for(int i = 0; i<left;i++)
par[i] = -par[i];
}
System.out.println("-------------------------------");
for(int i =0 ;i < n ; i++){
System.out.print(par[i]+",");
}
}
public static int findNearest(int[] arr, boolean[] flag, int n, int index){
int minIndex = 0;
int min = minimum;
for(int i = 0 ; i< arr.length;i++){
if(i == index)
continue;
if(flag[i] == true)
continue;
if(arr[index]-arr[i] > 0)
{ if((arr[index] - arr[i]) < min)
{
min = arr[index]-arr[i];
minIndex = i;
}
}
else
{ if(arr[i] - arr[index] < min)
{
min = arr[i] - arr[index];
minIndex = i;
}
}
}
return minIndex;
}
public static int maximum(int[] arr){
int max = 0;
for(int i=0;i<arr.length;i++){
if(max < arr[i])
max = arr[i];
}
return max;
}
public static int minimum(int[] arr){
int min = 0;
for(int i=0;i<arr.length;i++){
if(min > arr[i])
min = arr[i];
}
return min;
}
}
with Dynamic programming I have implemented it in O(n^3) + O(n^2) solution,
the solution is similar to matrix chain multiplication solution, where we calculate M(i,j){minimum possible sum when we consider the sub-array starting from "i" and ends with "j"}, But the minimum value computation will be different.
Algorithm:
1. Sort given array (say, in ascending order) ( Time: nlogn )
2. Loop once through array and find total sum - ( Time: n )
3. Start from right most element - ( Time: n )
4. See if current element can be made negative (for i = n - 1 to 0, both inclusive )
curr = a[i];
min_sum = total_sum - 2 * curr;
if ( min_sum >= 0 )
{
a[i] = curr * -1;
total_sum = min_sum; // update sum
}
if ( min_sum == 0 ) break; // because you can't minimize than that
5. When you reach first element, you would have made sufficient elements negative or you would have broke out from the loop.
TC: O(n log n)
SC: O(1)
Advantages:
1. Time complexity is nlogn
Disadvantages:
1. Modifies the input array
Here is the working C function (tested for all inputs in other answers):
int ModifyArray( int * a, int n )
{
int i, sum = 0;
if (!a) return -1;
if ( n <= 0 ) return -1;
// sort the input array in increasing order
qsort( &a[0], n, sizeof(int), compare );
// find total sum in one loop
for ( i = 0; i < n; ++i )
sum += a[i];
// actual algorithm
// scan from right to left
// see if each element's twice can be subtracted from total sum
for ( i = n - 1; i >= 0; --i ) {
int element = a[i];
int min_sum = sum - 2 * element;
if ( min_sum >= 0 ) {
a[i] = element * -1;
sum = min_sum;
}
if ( min_sum == 0 ) break; // early termination
}
return sum;
}
This is a wrong approach. For example, it breaks for {1, 2, 3, 4, 5, 6, 9}: one can negate 6 and 9 and get the sum of zero, while your algo gets 2.
@:E have you run my code on your example? or have you performed a dry run at least on your input?
Let me walk though:
1. your input is already sorted
2. find total sum = 30
3. start at 9:
min_sum = 30 - 2 * 9 = 12
a[i] = 9 * -1 = -9
total_sum = min_sum = 12
at 6:
min_sum = 12 - 2 * 6 = 0
a[i] = 6 * -1 = -6
total_sum = min_sum = 0
break;
you got 1,2,3,4,5,-6,-9
let me know which part you didn't get?!
It fails for the input 3,5,10,13,35,37. The algorithm gives answer as 3,5,10,-13,35,-37.
But 3 ,-5, -10 ,13 ,35 , -37 is the right answer
Yup Rajesh, you got me! finding counter-example for my algorithm was little bit tough, but you got it! I have to think DP!!!
Hey maq, your code's wrong. For example, take 12,13,14,15,16,50. The answer should be 12,-13,-14,-15,-16,50 (min sum = 4) but your code would give 12,13,14,15,16, -50 (min sum = 20 ). How do we do this using dp?
e.g,
4,5,10,19=sum should be zero
Greedy algo
sort the given numbers.
try to mimize the sum of the last two digits
19-10=9
new series is
4,5,9
again try to minimize the sum of last two digits
9-5=4;
new series is
4,4
again try to minimize the sum of last two digits
4-4=0
ans is 0
Check it for other cases and tell me if its write
the series now
Problem is solved using dynamic programming. We need to do a bit of pre-processing before invoking dynamic programming.
1. Sum up all the elements and let the sum be S
2. If S is odd, then the numbers can be partitioned into two sets, such that the difference of the sum of their elements is at least 1. If S is even their difference could be at least 0.
3. In either case, we need to figure out if there exists a subset of the elements in original array whose sum equals to S/2. If such a set exists, the other elements can put into another set which partitions the array into two sets and their sums would be equal.(sums would be roughly equal if S is odd an also depends on the distribution of numbers)
4.Once the set is identified, mark the elements with a -ve sign.
5. The summation of these numbers would yield a minimum number >=0.
Follows is a full implementation in java. Inputs are given using space as delimiter.
Eg: 5 3 7 2 4 6 1
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class PartitionProblem {
static ArrayList<Integer> input = new ArrayList<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);
int intval, sum = 0;
while (scanner.hasNextInt()) {
intval = scanner.nextInt();
input.add(intval);
sum += intval;
}
boolean[][] vals = new boolean[sum / 2 + 1][input.size() + 1];
for (int j = 0; j <= input.size(); j++) {
vals[0][j] = true;
}
for (int j = 1; j <= sum / 2; j++) {
vals[j][0] = false;
}
for (int i = 1; i <= sum / 2; i++) {
for (int j = 1; j <= input.size(); j++) {
vals[i][j] = vals[i][j - 1];
if (!vals[i][j]) {
if ((i - input.get(j - 1)) >= 0) {
vals[i][j] = vals[i - input.get(j - 1)][j - 1];
} else {
vals[i][j] = false;
}
}
}
}
if (vals[sum / 2][input.size()]) {
int i = sum / 2, j = input.size();
while (i >= 0 && j > 0) {
if (!vals[i][j - 1]) {
i -= input.get(j - 1);
input.set(j-1, -input.get(j - 1));
}
j--;
}
}
System.out.println(input);
}
}
I am assuming the code to be bug-free. Feel free to fix any issues.
1.- Sort the array from high to low
2.- Initialize two accumulator with the first two numbers of the array
3.- Create two arrays
4.- If (sum1 - sum2 >= 0) {sum2 += next element of array; array2.add(index of the element); }
else { sum1 += next element of array; array1.add(index of the element); }
5.- Repeat step 4 until the end of array
6.- If (sum1 >= sum2) convert to negative elements of array2
else convert to negative elements of array1
This greedy approach works for most inputs but there are inputs where it would fail. For example consider [4,14,15,16,17]. The approach would put the numbers into sets as [17, 14] and [16, 15, 4] with difference between them as 4. But the optimal arrangement would be like this [17, 16] and [15, 14, 4] with difference 0
The optimal solution would be to partition the array into two partitions with the difference between the partitions being minimum using a Knapsack like DP. Then negate all the numbers in the smaller partition to get the desired partitions.
import java.io.*;
import java.util.*;
public class Balpart
{
public static void main (String [] args) throws IOException
{
int sum = 0;
System.out.println("Enter the number of array elements");
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int[] array = new int[N];
System.out.println("Enter the Positive elements of the array");
for(int member = 0; member < N ; member++)
{
array[member] = input.nextInt();
sum += array[member];
}
boolean [] sol = new boolean [sum / 2 + 1];
sol [0] = true;//empty array
for (int i : array)
{
for (int j = sum / 2; j >= i; j--)
{
if (sol [j - i])
sol [j] = true;
}
}
int halfsumcloser = sum / 2;
for (; !sol [halfsumcloser]; halfsumcloser--);
System.out.println ("The Minimum sum After partioning the array is :" +((sum - halfsumcloser) - halfsumcloser));
}
}
import java.util.HashSet;
public class MinSumFromArrayChangingSigns {
public static void main(String[] args) {
int[] array = new int[] {1,98,99,100};
System.out.println(getMinSum(array));
}
public static int getMinSum(int[] array) {
sortInDescendingOrder(array);
HashSet<Integer> plusSet = new HashSet<Integer>();
HashSet<Integer> minusSet = new HashSet<Integer>();
int plusSetSum=0, minusSetSum=0;
for (int i : array) {
if (plusSetSum <= minusSetSum) {
plusSet.add(i);
plusSetSum += i;
} else {
minusSet.add(i);
minusSetSum += i;
}
}
return Math.abs(plusSetSum - minusSetSum);
}
public static void sortInDescendingOrder(int[] array) {
int i=0,j=0,temp=0;
for (i = 0; i<array.length; i++) {
for (j=i+1; j<array.length; j++) {
if (array[j] > array[i]) {
temp = array[i];
array[i] = array[j];
array[j]=temp;
}
}
}
}
}
I think the problem is about finding the minimum positive sum. The solution is trivial otherwise.
import java.util.Arrays;
- heena2k4 November 23, 2012import java.util.Collections;
public class MinSum {
public static void main(String[] args) {
Integer obj[] ={1,3,4,5};
int sum = 0;
Arrays.sort(obj,Collections.reverseOrder());
for(int i=0;i<obj.length;i++)
System.out.println(obj[i]);
for(int j=0;j<obj.length;j++)
{int elem = obj[j];
if(j ==0)
{
sum = obj[j];
continue;
}
if(sum > elem)
{
elem = -elem;
sum = sum + elem;
}
else
{if(sum <elem && sum > 0)
{
elem = -elem;
sum=sum+elem;
}else
{
sum = sum + elem;
}
}
}
System.out.println(Math.abs(sum));
}}