## InMobi Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Written Test

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

import java.util.Arrays;
import 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));
}}

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

``````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]);
}
}``````

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

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;
}

}

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

I think its like to find the two sets of integers where sum difference between two set is min.
Then return the min difference.

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

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.

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

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)

1. Time complexity is nlogn
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, 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;
}``````

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

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.

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

@mag can you provide the correctness

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

@: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:
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?!

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

@Ifenjoy9: Yes I have, will come back later.

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

Nice approach

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

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

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

Yup Rajesh, you got me! finding counter-example for my algorithm was little bit tough, but you got it! I have to think DP!!!

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

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?

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

absolutely wrong

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

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

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

It is basically subset problem i.e can u find a subset which sums upto half of the total... have to solve using knapsack problem

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

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();
sum += intval;
}

boolean[][] vals = new boolean[sum / 2 + 1][input.size() + 1];

for (int j = 0; j <= input.size(); j++) {
vals[j] = true;
}

for (int j = 1; j <= sum / 2; j++) {
vals[j] = 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.

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

in python:

def minsum(arr):
arr2 = arr[0:]
temp = max(arr2)

for i in range(len(arr2)):
if temp >0:
if len(arr2)>1:
arr2.remove(max(arr2))
temp = temp-max(arr2)
else:
return temp
else:
if len(arr2)>1:
arr2.remove(max(arr2))
temp = temp+max(arr2)
else:
return temp
return temp

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

This is the famous Partition Set problem, where the total set is divided into two subsets such that the difference between the sum of elements is minimum. It can be easily solved in O(sum/2)(n) time using back-pointers to find out the elements in the sets.

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

This comment has been deleted.

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

Run on {1,3,4,5} and you will get -1. Only if it was this easy :)

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

I think your code is not correct for the input used in your code.

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

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

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

consider following input : {4,5,10,19}. Above approach fails :(

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

sorry my bad .. i didn't chk above line "Sort the array from high to low"

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

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

Comment hidden because of low score. Click to expand.
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.

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

Hey anirban, am I just not able to add or does the optimal grouping for your example lead to a difference of 0?

Also I coded out the solution suggested above and I got 4, 15, 17 in one and 14 and 16 in the other.

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

``````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  = 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));

}

}``````

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

this approach is wrong

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

``````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) {
plusSetSum += i;
} else {
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;
}
}
}
}

}``````

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

I think the problem is about finding the minimum positive sum. The solution is trivial otherwise.

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

I think it is written in the question..

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

Sum all abs. Take sum/2 . And standard subset problem with sum closes to sum/2 O(logn)

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

This is an NP-complete problem. If one can find the solution to the problem of "finding k numbers in an array that add upto a given sum" , this problem can be solved.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Wikipedia -> Knapsack Problem

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

It IS indeed a modificatoin of knpsack problem!

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.