Directi Interview Question for Software Engineer / Developers






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

Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold de req number

- Sathya January 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Concept Satya

- Tarun May 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent algo!

- anonymous February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent algo!

- anonymous February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not O(1) like it's mentioned in the question.

- Deepak March 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

HOW IN THE WORLD IS THE ABOVE ALGORITHM O(1)? It's an O(n) algo!

- whatchyallthinking! March 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

HOW IN THE WORLD ONE CAN SOLVE THE ABOVE PROBLEM IN O(1) TIME? :P

the above one is the best solution . . ..

- karthik November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's right. its moors voting algorithm and element is called as Majority element.

- champ September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

the above algorithm works because:
when freq=0, selected number and the other numbers (which may have the right numbers in it) are in equal number, so no harm in neglecting them (we are neglecting at max the number of neglected unwanted numbers), so start over from this point forgetting previous numbers.
if you proceed this way, at some point of time, you'll select right answer, and the other numbers cant outnumber it, because we've lost more of other numbers than the required number in the process above.

- jack July 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

there is an alternate solution .

(1) Select pairs of elements i.e 1, 2; 3, 4; 5, 6; ....
(2) compare if elements of pair are equal. If equal keep one element. Else remove that pair. Do this recursively until there is one element left.

ex:

Given array ->
10, 20 , 10, 10, 20, 20, 10, 10
Step 1 : (10, 20) , (10, 10), (20, 20), (10, 10)
Step 2 : (), (10), (20), (10) => 10, 20, 10
Step 3 : (10, 20), 10
Step 4 : (), 10 => 10

Hence 10 is the number.

- jackass October 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please clarify: O(n) time O(1) space complexity or the other way around? Or both O(n) then O(1) time complexity?

- Anonymous January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

majority element finding algorithm.

- Anonymous January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use a hash table to count an element's occurences. for every element if count greater than maxCount then store current element as the max.
finally maxCount element is the one occurring frequently.

- gekko gordan January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

worst case linear time selection of the median (i.e. the index n/2) will find the element occuring >n/2 times. Time complexity O(n). Space complexity O(1) can be achieved by eliminating tail recursion, This algo is also inplace.

- Anonymous January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold de req number

- Sathya January 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good logic..

- keshav January 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome.
But how does this work!!!
what if conditions were n/3???

- Anonymous March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But what if there is no element that repeats more than n/2 times

- Shruti August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

there is some mistake in your algo.

It didn't test the unsuccessful cases.

- manish sharma September 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above given algorithm lies on the fact that, if a list contains an element that is repeated more than n/2 times in the list, then the required element will be present consecutively atleast once or the list will end with the required element.

Eg: Let's say size of the list is 10

1st possibility:

1,3,2,3,3,4,5,3,6,3 (3 repeated in location 3&4)
OR
1,3,2,3,4,3,5,3,6,3 (List ends with 3)

Super Cool Algorithm, I must say :-)

- karthic January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how does it work for 4,4,4,3,3,3,3,3,3,4

- Anonymous January 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- pankaj March 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it wont work for all the cases!!!!!!!!!!

- Anonymous July 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

It doesnot work for 10,20,10,30,10,20,10,20..

- Sonal September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

sonal you must check question first.it say (repeats more than (>)n/2 times)h so i think satya algo always work

- kapil September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi can someone say, how this can be achieved in O(1) time. Is there any alternative ???

- Lokesh chandrakumar March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can anyone hv sol in O(1)...?? every1 talkin in O(n).

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

Here...
h t t p : / / flashing-thoughts.blogspot.in/2010/06/problem-array-of-size-n-contains.html

- Srikant Aggarwal October 24, 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