Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
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.
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.
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]
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.
more...on... wrong solution for >n/4 .... there could be two or more items with multiple points....
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
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.
@coolhaitechie, that's a good observation - thank you! The array index should be Ceil(n/2) not Ceil(n/2) -1
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])
# 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")
Suppose your input array contains repetitive elements from [3n/8] to [5n/8+1] then your solution will return false.
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.
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.
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.
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)
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.
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.
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
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;
}
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 ""
The key point that makes O(1) time& space possible is that the array is sorted.
- ninhnnsoc January 19, 2016The 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.