An interesting Google interview algorithm I found online that requires linear time?

Nt: Look at Boyer and Moore's Linear Time Voting Algorithm.

Nt: Look at Boyer and Moore's Linear Time Voting Algorithm Better nt: Think about solving the majority problem first. That is, try to find an element that occurs at least n/2 times. The basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist until the end if it is a majority element.

FindCandidate(a, size) //Initialize index and count of majority element maj_index = 0; count = 1; for I = 1 to n–1 { if amaj_index == ai count++; else count--; if count == 0 { maj_index = i; count = 1; } } return amaj_index This algorithm loops through each element and maintains a count of amaj_index. If the next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. Next you need to check that this element indeed occurs at least n/2 times, but that can be done in one pass.

Good hint. Not sure exactly how to apply to n/3 yet, but definitely great to know algorithm. Thanks!

Will use this to try to come up with solution to n/3. But why did this question get closed? I think this is an excellent question to learn about.... – Newbie_code Dec 2 at 20:46 @Newbie_code I think it was the way you phrased the question.

Generally, on SO, you should show some effort in solving the question yourself rather than ask the community to write code for you. I voted to re-open it. – PengOne Dec 2 at 20:47 @Newbie_code To get the n/3 case, just think a bit about how this algorithm works.It's not too hard to generalize it, but I will warn you that the difficult part IMO is that 2 different elements could work.

– PengOne Dec 2 at 20:48 I posted this question here just because I think it's interesting, and hard, and I'd like share it to everyone else who would like to discuss and know how to solve it. It could be easily solved with hashing but w/o it and in linear time?Hmm... I'm sure whoever read your answer will learn something if they did not know this before. – Newbie_code Dec 2 at 20:53 I'm quite familiar with the Majority Voting algorithm, but I'm not sure I see how to adapt it here.

The correctness proof hinges on a lemma that says that you can rearrange the elements of the array such that you can pair up the majority element in a way that cancels out everything else. This lemma fails if you're looking for an element that appears a third of the time. Can you be a bit more specific about how you're generalizing the algorithm?

– templatetypedef Dec 27 at 19:49.

Not the most efficient, but amusing idea: 1) sort them 2) loop from index 0 to (2*n/3)-1 to find elements ai that are equal to ai+n/3 (you can skip indices I to i+n/3 whenever you find one) Please note that I didn't fully respect the linear constraint: if we use Collections.sort(), sorting time is only quasilinear.

2 This ignores half the constraints in the question. – Sign Dec 2 at 20:28 Which one? I used comparisons (sorting), linear time (standard java sorting), no hashing, no excessive space... – ymajoros Dec 2 at 20:30 3 What is your linear time sort?

– Sign Dec 2 at 20:32 You're right, collections.sort() is quasilinear. Let's indicate in my answer that I didn't observe all constraints. – ymajoros Dec 2 at 20:43.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.