Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
It would have been nice had you explained the logic as to how the sum of all the numbers left after getting the remainder adds up to 20.
The logic is:
Input: 4 11 7 6 3 9 8 12
Input%K : 4 1 2 1 3 4 3 2
Now if we see the result of (input%k) we see 1 1 2 2 3 3 4 4
So basically it is sum of 1 2 3 4 and 1 2 3 4 which is nothing but 2*(n*((n+1)/2))
so it boils down to n*(n+1) which is 4*5 = 20
any two numbers sum should be divisible by K means sum of remainders of two numbers should be K or 0
lets K=5, and data is 8 & 9, here sum of these numbers to be divisible by 5 (K) for below cases
1. both numbers should be divisible by 5 means remainders will be 0 & 0
2. sum of the remainders should be divisible by 5, here remainders are 3 & 4 sum of these is not divisible by 5... lets take 8 & 12, sum of remainders is 3+2, which is divisible by 5.
here we don't know which two numbers remainders sum is divisible by 5, each pair should be equal to K and there should be N/2 such pairs...each pair is a[i] & K-a[i]
lets take another example:
9 15 21 4 5 6 and K=10, and N=6
here remainders are 9 5 1 4 5 6
It fails the following case => k = 6 and arr = {2, 4, 1, 4, 4, 3}. The above algorithm will give 1 which is wrong.
for remainder array verify below conditions:
1. there should be even number of 0's
2. for every element a[i] in remainder array there should be K-a[i] exists in array. to verify this hash all elements and and keep the count of each element and check whether a[i] and K-a[i] exists in hash table and the count should be also equal for both
@algos: nice logic and I am upvoting this.Just to clarify more
for remainder array verify below conditions:
1. there should be even number of 0's
2. for every element a[i] in remainder array there should be K-a[i] exists in array. To verify this hash all elements and check only till the size/2 (size is array size).
example:
9 15 21 4 5 6 and K=10, and N=6
here remainders are 9 5 1 4 5 6
Hash all the remainders and check for N/2 elements if it is equal to K-a[i].
9 5 1 4 5 6
9+1=10 so remove 1 from the hash.
5+5=10 so remove 5 from the hash
and 4+6= 10 remove 6 from the hash
We are done as there is nothing in the hash.
So we return TRUE as all the pairs are adding up to K.
"sum is 30 and is equal to K*N/2" -this condition verification is not required.
Further positive examples are:
1) 1, 9, 5, 11, 14, 15 and K = 5 => (1, 14) (11, 9)(5, 15)
2) 1, 2, 3, 5, 7, 15 and K = 3 => (3, 15) (1,2) (7,5)
Find the complete code here.
#include<iostream>
#include<conio.h>
using namespace std;
void isort(int* array[], int size)
{
int min;
for(int i = 0; i < size; i++)
{
min = i;
for(int j = i+1; j < size; j++)
{
if((*array)[j] < (*array)[min])
{
min = j;
}
}
if(min != i)
{
int temp = (*array)[min];
(*array)[min] = (*array)[i];
(*array)[i] = temp;
}
}
}
int main()
{
int array[] = {1,9,5,6,4,15};
int size = sizeof(array)/sizeof(array[0]);
if(size%2 != 0)
{
cout << "Wrong input" << endl;
return 0;
}
int k = 5;
int* mod = new int[size];
for(int i = 0; i < size; i++)
mod[i] = array[i]%k;
isort(&mod, size);
int i = 0;
while(mod[i] == 0)
{
i++;
}
if(i == (size-1))
{
cout << "pairs exist" << endl;
getch();
return 0;
}
if(i%2 != 0)
{
cout << "pairs does not exist" << endl;
getch();
return 0;
}
int j = size - 1;
for( ; i < j; )
{
if((mod[i] + mod[j]) == k)
{
i++;
j--;
}
else
{
cout << "pairs does not exist" << endl;
getch();
return 0;
}
}
cout << "pairs exist" << endl;
getch();
return 0;
}
I would build a hash whose key is the remainder of each integer in the list divided by K, and its value is the counter left after pair is removed. If there is still some non-zero counter in the hash after all integer is checked, then the test fails, other wise, the test success. see the code as bellow:
#input=[1,5, 7,0, 4,5,9];
#input=[ 1, 9, 5, 11, 14, 15 ];
input = [1, 2, 3, 5, 7, 15];
sum=3;
print "input", input
print "sum", sum
remainderCnt={};
for elem in input:
remain=elem%sum;
if remain == 0:
if remain in remainderCnt.keys():
remainderCnt[remain]=(remainderCnt[remain]+1)%2;
else:
remainderCnt[remain]=1;
continue;
if (sum-remain) in remainderCnt.keys():
remainderCnt[sum-remain]-=1;
else:
if remain in remainderCnt.keys():
remainderCnt[remain]+=1;
else:
remainderCnt[remain]=1;
for elem in remainderCnt.keys():
print elem, ":", remainderCnt[elem];
pair_complete=1;
for elem in remainderCnt.keys():
if remainderCnt[elem]:
pair_complete=0;
break;
if pair_complete :
print "Test passed\n";
else:
print "Test Failed\n";
Time = O(n); Space = O(n)
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;
/**
* @author hissar
*
*/
public class DivisibleByK {
static boolean isPossible (Integer[] arr, int k) {
if (arr == null || k == 0) return false;
Integer[] remainders = new Integer[arr.length];
for (int i = 0; i < arr.length; i++)
remainders[i] = new Integer(arr[i].intValue() % k);
HashMap<Integer, Integer> unpaired = new HashMap<Integer, Integer>();
for (Integer i : remainders) {
Integer value = unpaired.get(i);
if (value != null)
unpaired.put(i, new Integer(value.intValue()+1));
else unpaired.put(i, new Integer(1));
}
int count = 0;
for (int i = 0; i < arr.length && count < arr.length; i++) {
Integer value = unpaired.get(remainders[i]);
if (value == null || value.intValue() == 0) continue;
unpaired.put(remainders[i], new Integer(value.intValue() - 1));
int cand = remainders[i] == 0 ? 0 : k - remainders[i];
value = unpaired.get(cand);
if (value == null || value.intValue() == 0) return false;
unpaired.put(cand, new Integer(value.intValue() - 1));
count += 2;
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[10];
Random rand = new Random();
for (int i = 0; i < 10; i++)
arr[i] = new Integer (rand.nextInt(100));
System.out.println (Arrays.toString(arr));
System.out.println (isPossible (arr, 1));
System.out.println (isPossible (arr, 7));
System.out.println (isPossible (arr, 2));
int[] tmp = {2, 4, 1, 4, 4, 3};
arr = new Integer[6];
for (int i = 0; i < 6; i++)
arr[i] = new Integer (tmp[i]);
System.out.println (isPossible (arr, 6));
}
}
Company work may be nice in some team but people are horrible.
Duffer HRs. Lacks communication skills.
Interviewers at senior level are overproud and bookish. Not even listen to interviewee completely when speaking. Not even able to speak up their name clearly.
In my experience, the only human kind that is normal is recent grads up to 3 years of experience.
After thinking a lot, rejecting their offer gives the feeling of saving my life from hell.
Int a[]={2,,5,3,5,2,7,9,6};
k=3;n=8;
int b[n]={0};
int key,check;
for(int i=0;i<n;i++)
{
key=a[i]%k;
check=k-key;
if(b[check]>0)
return TRUE;
else
b[key]++;
}
Updated the code on below suggestion
a = [1,2,3,6]
k=3
for i in range(len(a)-1):
for j in range(i+1,len(a)):
if (a[i]+a[j])%k==0:
print a[i], a[j]
The above solution wont work, as the intent is to find that .. all the elements in different pairs should be divisible by K. Example:
A = 1,2, 3, 6
K = 3,
=> (1,,2), (3,6)
=> 1+2 = 3%3 = 0
=> 3+ 6 = 9%3 = 0
Not just one pair, all the elements must be part of a pair.
- algos March 22, 2013