## Google Interview Question for Interns

• 6

Country: United States
Interview Type: Phone Interview

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

The key point that makes O(1) time& space possible is that the array is sorted.

The idea is, if the element that repeated >n/2 time (half-major element), they must be next to each other in the array. And they must cross some "land-mark", that is the middle of the array.

So, checking the middle element A[n/2], comparing it with A[0] and/or A[n] can tell whether it's major element. EDITED: A[n/2] must be the answer given if half-majority exists.

For the case of majority > n/4 (quarter-majority): Same idea, however we need more "land-marks". I believe checking position k*n/8 for k = 0..8 will sufficient to check for the majority element.

For the case array is NOT sorted, I think O(1) time is not possible. However, O(n) time, O(1) space algorithm exists. Check this post about majority elements: capacode. com/array/major-element-in-array/ Thanks!

EDITED for the case n/4-majority:
- Check if there is a repeated segment S crosses at least 2 landmarks.
- If S crosses 3 landmarks or more: length of S must be >n/4, found S, done.
- If S crosses only 2 landmarks u and u+1:
Reduce the problem into the case "half-majority" with array from landmark u-1 to landmark u+2.

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

Be careful if the array doesn't have majority element.

If it doesn't guarantee to have the majority element (>n/2 time), we need to check more positions: k*n/4, k=0..4, to make sure the majority segment cross 2 of our land-marks.

If it guarantees to have majority element, just check middle element is enough.

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

We don't have to think about the case when there is not majority element because the question mentions that your algo may assume that the array has a majority element.

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

In case of n/2 there is no need to check, the a[n/2] is the majority element. In fact if you check that might lead to unwanted results like A = 1, 2, 2, 2, 2, 3, 4.
Here n = 7 and A[n/2] is not equal neither A[0] nor A[n]

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

Yes, of course O (n) time is the minimum if the array is unsorted, since all or most elements will have to be inspected in the general case.

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

more...on... wrong solution for >n/4 .... there could be two or more items with multiple points....

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

Your solution for n/4 is incorrect. If you check for k*n/8 elements, there is a probability that you would find 2 sequential equal elements, while the total count of these element is only n/8 or n/8+1. While having 3 elements of the same value from this sample array is a corner case when a group of n/4 elements starts with the point where you sample at.

There is no solution with O(1) for the problem as it is stated, because having k*n/8 samples you have to check the exact size of each group having two n/8 sequential equal sample values. Corner case is when "all the other elements of the array except by repeating one are unique" - then yes, you can use sampling solution

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

Since the array is sorted, and we have a guarantee that such an element exists, then the answer is always

``input[Math.ceil(n/2)]``

Examples: (Realize that the repeated element always takes up >= n/2 elements.)
Input: {1,2,3,3,3,3,3,3,4,5,6}
Input: {3,3,3,3,3,3,4,5,6,7,8}
Input: {1,2,3,4,5,6,6,6,6,6,6}

Ceil(n/2) = Ceil(11/2) = 6
input[6-1] = repeated elements in all cases. There are some edge cases depending on the array length (0, 1, 2)

I'll update with the n/4 solution.

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

What about an array with size 4 , {1, 2, 3, 3}

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

@coolhaitechie, that's a good observation - thank you! The array index should be Ceil(n/2) not Ceil(n/2) -1

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

how about {3,3,4,5}? or {3,3,4} ?

I think we have to do some comparisons

``````def most_common(lst):
return max(set(lst), key=lst.count)
def find_repeat_half(num_list):
mid = num_list[len(num_list)//2]
mid_left = num_list[len(num_list)//2 -1]
if len(num_list)% 2 != 0:
return mid
else:
return most_common([num_list[0], num_list[-1], mid, mid_left])``````

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

``````# Given a sorted array of size N of int32, find an element that repeats > ceil(N / 2) times. #Your algo may assume that there will be always such element. Space/time O(1).
# Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1)

def find_repeat(a):
b = len(a)
print(b)
if((a[int(b/4)] == a[int(b/2)])or(a[int(b/2)] == a[int(3*b/4)-1])
or(a[int(3*b/4)-1] == a[b-1])):
return 1
else:
return 0

#x = [1,1,1,1,2,2,2,3,3]
x = [1,2,3,4,5,6,7,89]
if(find_repeat(x) == 1):
print("Yes")
else:
print("No")``````

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

Suppose your input array contains repetitive elements from [3n/8] to [5n/8+1] then your solution will return false.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

x = [1,2,3,3,3,3,4,5]

no it won't . Returns yes for this.

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

You have to choose larger set in order to reproduce it. Take this example,
1,1,2,2,2,2,2,3,4,5,6,7,8,9,10,11

And, it returns false.

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

For first, it's the middle element.

For second, it's a bit trickier. Suppose we have splitted the array into 8 portion, the the array will looks like this,

``(start element)1----2----3----4----5----6----7----8(end element)``

If any of the alternate position's element matches with each other then it definitely has that element. We need atmost six comparison to determine the exact element.
[1---- to ----3] or,
[2------4] or,
[3------5] or
[4------6] or
[5------7] or
Since the array must have the element, then it must be any element from [6 --- to --- 8] range.

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

can you explain more with examples?

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

Suppose you have an array like this,
1,1,2,2,2,2,2,3,4,5,6,7,8,9,10,11

Then your element is [2]. Break the array in 8 ranges.
range 1 : index 0 to index 3
range 2 : index 2 to index 5
range 3 : index 4 to index 7
range 4 : index 6 to index 9
range 5 : index 8 to index 11
range 6 : index 10 to index 13
range 7 : index 12 to index 15 (last element)

So, if you compare the elements in the in those index, then the element [2] lies in range 2.

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

How about if you have this:
1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Array length 16, need element repeating at least 4 times, in this case: 2.
Your solution would not find this.

I think it's on the right track, limitations are similar to how you can't just check a[0], a[mid], a[end] in the n/2 case. You'll need more checks to cover all cases. Therein lies the more interesting part of this problem.

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

In O(n) time/space , try to transform the array in this form x, a, x, b, x, c, x, ... when 'x' will be the element that you want.
BTW: I think you need to see all the elements so the time at least is O(n)

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

I was wrong my idea is when is non-sorted.

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

Are we sure this is O(1) time? The Misra-Gries algorithm that is generally used to solve this problem is O(n) time and O(1) space.

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

This is indeed a O(1) problem. Note the key is that the array is already sorted. So if an element repeats ceiling(N/2) times in the array, then no matter it is placed, the center element will be that element. If number of element is even so there is no precise center, then exam if the center two elements are the same or not. If they are not the same, pick up one more element on either side to compare. The element that has an identical peer is the answer.

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

Center - 1 :)
Check out my solution.

However it gets interesting when the ceiling factor is 4.

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

I think he is asking to find the Majority Element

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

Could we do in the following way . First check ceil(n/2)-1 element if it is majorant more than ceil(n/2) repeats.If is such then we return. Otherwise we split array in two halves and check in both if ceil(m/2)-1 is majorant where m should be n/2.

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

How would you know if the element is majorant in O(1)?

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

How would you check if element is majorant in O(1)?

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

For the N/2 case, the center element is definitely the answer.
For the N/4 case, divide the array into 8 equal pieces, we have 6 marking points plus start and end of the array. The repeating element is the one which repeats at least 3 times in any of these 8 marking points (definitely the repeats will be in sequential order) like

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

wrong.... fail

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

Why does gen-x-s have to be a douche?

I wrote the code for this solution, and it works just fine

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

``````public int findRepN4(int[] arr)
{
if(arr==null)
{
throw new NullPointerException();
}
int mid=(arr.length-1)/2;
int idx=-1;
idx=getRep(0,mid,arr);
if(arr.length%2==0)
{
return(idx!=-1)?arr[idx]:arr[checkSub(mid+1,end,arr)];

}
return arr[checkSub(mid,end,arr)];
}

private int checkSub(int start,int end,int[] arr)
{
int mid=end+start/2;
if(end-start+1%2==0)
{
if(arr[mid]==arr[start])
{
return start;
}
return(arr[end]==arr[mid+1]?end:-1);
}
return(arr[mid]==arr[start]||arr[end]==arr[mid])?mid:-1;

}``````

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

``````void findRepeatEleN4(int arr[N])
{
int i = ceil(N/4);
cout << "\n repeated elements are";
for(int j=0;j<N;j++)
{
if(arr[j] == arr[j+i])
{
cout << arr[j];
j=j+i;
}
}
}``````

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

you can solve it in O(n) time and constant space using Fast Majority algorithm. Read this algorithm.

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

why did u assume continuous repitition??

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

Because the problem clearly states the input is sorted.

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

Because the problem clearly states the input is sorted.

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

``````def findRepeatCeilHalf( sorted_array ):
return sorted_array[len(sorted_array) // 2]``````

``````def findRepeatCeilQuarter( sorted_array ):

if len(sorted_array) < 5:
return sorted_array[0]

step_size = int(np.ceil(len(sorted_array) / 4.0) // 2)
termination_crit = int(np.ceil(np.ceil(len(sorted_array) / 4.0) / step_size))

cons_val = sorted_array[0]
cons_ct = 1
pos = step_size

while True:
curr_pos = min(pos, len(sorted_array) - 1)
curr_val = sorted_array[curr_pos]
if (curr_val == cons_val):
cons_ct += 1
if cons_ct >= termination_crit:
return curr_val
else:
cons_val = curr_val
cons_ct = 1

if curr_pos == len(sorted_array) - 1:
#this should never happen
break

pos += step_size

return ""``````

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

return middle

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.