Directi Interview Question for Software Engineer / Developers


Country: India




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

Because the time limit is 1sec.It may fail if the algorithm is O(N^2) where the max N is 10^4.the following alg is O(K^2) where K = (1<<11)=2048,it can insure the time limit 1sec.
1)represent each number with a integer from 0 to (1<<11)-1.where ith bit of the integer will be set 1 if the number contains the digit i.for instance 11330 will be represented by (1<<1)|(1<<3)|(1<<0)=11.
2)we have an array to accord the count of each integer
3)two for loops the array of the integer to count.

#include <iostream>
#include <sstream>
#include <string>
using namespace std;
size_t const NN = (1<<11);
int cnt[NN];
int main()
{
    
    int T;
    cin >> T;
    for (int t = 0 ;t < T ;++t){
        int N;
        cin >> N;
        memset(cnt ,0 ,sizeof(cnt));
        int res = 0;
        for (int i = 0 ;i < N ;++i){
            long long v;
            cin >> v;
            stringstream ss;
            ss << v;
            string digits ;
            ss >> digits;
            int hv = 0;
            for (int j = 0 ;j < digits.length() ;j++){
                hv |= (1<<(digits[j]-'0'));
            }
            ++cnt[hv];
        }
        for (int j = 1 ;j < NN ;j++){
            if (cnt[j] > 0){
//update here.
                res += (cnt[j]*(cnt[j]-1))/2;
                for (int k = j + 1 ;k < NN ;k++){
                    if ((j & k) != 0){
                        res += cnt[j]*cnt[k];    
                    }
                }
            }
        }
        cout <<  res << endl;
    }
}

- notbad July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

add a condition when more than one number map to same value..
for ex->
123,132,213,231,312,321

- Abhishek July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Abhishek yeah!I should add res += (cnt[j]*(cnt[j]-1))/2 before the second loop. thank you for your correcting.

- notbad July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey @notbad,really good implementation ..but one bug if a no. is repeated again like
123,132,213,231,312,321,321
It should give 15 but its giving 21,dat means its treating last 321 as a separate number. Provide corrected code asap .

- bond July 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@bond I'm not quite sure how to process duplicate numbers.If the duplicate numbers can only be counted once,we should sort the numbers first and uniq them. If we should count every number no matter whether they are the same or not, the code above is Okay.Off course, promising no duplicate numbers will be appreciated.

- notbad July 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Represent each digit of a number with a bit.
Compare bit-representation of each number with the bit-representation every other number

struct bit
{
        unsigned int num:10;
};
 
void find(int* a,int size)
{
        struct bit b[size];
        int i,num,j,count=0;
        for(i=0;i<size;i++) b[i].num=0;
 
        for(i=0;i<size;i++)
        {
                num=a[i];
                while(num)
                {
                        b[i].num|=1<<(num%10);
                        num/=10;
                }
        }
 
        for(i=0;i<size;i++)
        {
                for(j=i+1;j<size;j++)
                {
                        if(b[i].num&b[j].num)
                                count++;
                }
        }
        printf("%d ",count);
}

Complete code here: ideone.com/nEeTG

- Aashish July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't know if this would meet the requirements of this problem or not. An n^2 solution is likely to time out given the constraints. You have, however, really done some good preprocessing to make sure that the n^2 step has a really small constant factor. Maybe this solution would scrape by.

- eugene.yarovoi July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Create an array of size 10 to count the distinct appearance of digits in a given number ... While taking the input number increase the value by 1 in the array for the corresponding digit...
for e.g. if the input number is 9788 increase the count of 7,8,9th position in array by 1.

Final answer 'll be :

count=0;
for(i=0;i<10;i++)
      count += arr[i]-1;

- CookieRaider July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think it is good
just mind for negative values

- jashnil September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Number of comparisons = No of comparisons in insertion sort

while comparing two elements
1. create an array of size 10 and intialize to zero ..
2. take the first element and traverse its digits (using modulo) and set the array[digit] to 1
3. when you traverse the second element's digits and if you found array[digit] to 1 then these two elements are friends..

is my solution right?

- cobra July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) was required, O(n^2) was failing even in time limit of 10 seconds.

- L.Ppt July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is there some site where you can test code for these problems?

- anujkaliaiitd July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't look like O(n) was required when I look at the constraints. Just something slightly better than O(n^2).

- eugene.yarovoi July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Here's something complicated, but its O(N):

Construct 10 buckets (LinkedLists) where bucket i contains all numbers which contain digit i. This step is Space: O(N), time O(N).
Let us call the answer "count".

Now, for bucket i, i varies from 0 to 9:
Add bucket[i].size()*(bucket[i].size()-1)/2 to count. This is for the number of friendly pairs, which are friendly because they contain digit i. Now we need to remove pairs which have been counted earlier because they were friendly due to some digit j < i.
Create an array C[] of size i where C[j] denotes the count of numbers in this bucket (bucket[i]) whose MINIMUM digit is j.
Subtract C[j]*(C[j]-1)/2 from count, j varies from 0 to i-1.

Return count.

Its O(N) time and space.

- anujkaliaiitd July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain this line- "Create an array C[] of size i where C[j] denotes the count of numbers in this bucket (bucket[i]) whose MINIMUM digit is j. "?

- manish July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The approach was wrong, sorry.

- anujkaliaiitd July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findFriendlyNumsCount(int[] setOfNumbers){
		int[] digitsCount = new int[10];
		int friendlyNumCount = 0;
		for(int i=0; i<setOfNumbers.length; i++){
			int temp = setOfNumbers[i];
			int[] countChecker = new int[10];
			while(temp>0){
				int oldCount = digitsCount[temp%10];
				digitsCount[temp%10] = digitsCount[temp%10]+1;
				int newCount = digitsCount[temp%10];
				if(oldCount > 0 && newCount > oldCount && countChecker[temp%10] == 0){
					friendlyNumCount = friendlyNumCount+1;
					countChecker[temp%10] = 1;
					//break;
				}
				temp = temp/10;
				
			}
		}
		System.out.println(friendlyNumCount);
		
	}

- sachinjainmail July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each digit from 0 to 9, I compute the number of pairs as following : for digit i, I calculate 2 numbers : - nrused ( number of values that contains digit i, but also contain digits that are smaller than i, those are numbers that have allready been used )
- and nr_not_used ( number of values that contains digit i and doesn't contain digits smaller than i, number that haven't been used ).

now we add to the solution : nrused * nr_not_used + nr_not_used*(nr_not_used-1)/2 .

For this solution ,time complexity would be o(n * const ) , const = number of digits. Honestly I am not quite sure on the correctness of this solution, though it seems correct.

- andrew July 16, 2012 | Flag Reply


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