Directi Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 7 vote

time complexity O(n) and space complexity O(n)

ex: 4 11 7 6 3 9 8 12 and K=5, N=8 (array size)

get the remainder of all elements by dividing with K, so the array becomes
4 1 2 1 3 4 3 2

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 March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- algos March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It fails the following case => k = 6 and arr = {2, 4, 1, 4, 4, 3}. The above algorithm will give 1 which is wrong.

- hissar March 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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 March 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

@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.

- aka March 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good logic!

- alex March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sam March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You missed (1, 9) in the first example and (1, 5), (2, 7) in the second example

- Anonymous March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

whats ur point?

- sam March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- aasshishh March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- chenlc626 March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hissar March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- direct-i interview FEEDBACK April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You may also want to look at this question: question?id=14820665

- Anonymous July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Shyamrag July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A small update:
Int a[]={2,5,3,5,2,7,9,6};
k=3;n=8;
int b[k]={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]++;
}

- Shyamrag July 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a=[int(x) for x in raw_input().split(' ')]
k=int(raw_input())
a=[x%k for x in a]
a.sort()
print a
j=len(a)-1
i=0
c=0;
while a[i]==0:
c+=1;
i+=1;
c=c/2;	
while i<j:
if a[i]+a[j]==k:
c+=2;
i+=1;
j-=1;
elif a[i]+a[j]<k:
i+=1;
elif a[i]+a[j]>k:
j-=1;
print "pairs",c/2

- harshit.knit November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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]

- Expressions March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- sam March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You missed (1, 9) in the first example and (1, 5), (2, 7) in the second example

- anon March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I misunderstood the question.

- Expressions March 22, 2013 | Flag


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