## Yahoo Interview Question for Software Engineer / Developers

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

keep on inserting elements in AVL tree. when redundant element is encountered increment the count & do not add it. At the end subtract count from total elements in array & it is the answer.
Complexity O(n log n).
Any better solution. I am sure it will exist!!

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

is array elements indexes be 1, 2, 3, 4
in first iteration check adjacent elements 1 == 2, 3 ==4 or not then in second iteration check 1 == 3, 2== 4 or not & so on if there are more elements in array. So, if we know 1 != 2 && 1 != 3 then 2 != 3. Hence we will save the checks.

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

Sort the array using Quick sort.Check with condition a[i]==a[i+1];If the condition not satisfies then only count.else dont count.

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

if range of array element known (Say max no is n) Use index array say idx of size n, set to ZERO.
Iterate through given array a and set idx as idx[a[i]]++;
Count of 1 in idx is the answer. Time: O(n), Space: O(max array value).
Will take more space if range is high (And array values are sparse)
Otherwsie:
Use BST/AVL etc (As Mike said)..
Keep inserting in Tree if it is not there already (Don't insert duplicates)
and keep track of tree size.
At the end, Tree size is the answer.
Time: O(n log n), Space: O(n)

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

OR even better, Use hash table.
Iterate through the array and insert elements in hash table (Don't insert in case of collision i.e. duplicates).
Hash table size is the answer.
Time: O(n), Space: O(n)

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

Yep.. a slight modification, computing size of hash table for obtaining the count is not the optimal way.
Instead, use a count variable which is incremented if the element is inserted into hash table else dont increment.

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

Hi, I think you need to decrement the count variable if the element already exists in the hash table, as you previously counted it.

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

I guess storing element in hash and increment/decrement counter will not do here.
e.g. for input 1,2,3,4,3,5,2,2,7
Answer should be: 4 (1,4,5,7 are unique, others repeated).
So one soln would be to use index array (as told above) given that input range is known and input is not sparse (Else space wastage will be there).
Other soln would be to use hash where key is given input no and value will be count of that no (i.e. index array concept only but use hash instead of array to avoid space wastage). At the end, count the keys in hash having value ONE which will be the answer.

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

-> For every element 'i' in array
Insert in hash table, if already exists (--count) else (++count)
O(n) time and space

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

This will not work for
1,2,3,4,2,3,3
Answer should be: 2 (1 and 4 are unique)
But above will give 1.
Right soln will be as I said, put in hash with array element as key and it's count as value (value 1 if inserted 1st time, increment later on while duplicate).
At the end, just count the hash element having value 1.

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

@Anurag, the problem with iterating through hash table would add a bit more computations to it i.e. atleast 'n'
Here's a modified solution:

-> For every element 'i' in array
if key=array[i] doesn't exist in hash table
insert with value=1 and ++count
if value==2
continue loop;
if value==1
--count and set value = 2;
}

//This should give you result without iterating hash table in the end

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.