 # Easier Interview Question

In this lesson, you’ll use what you learned in the previous sections to solve an easy real world interview question. Easy does not mean trivial, but it means something you might find in a coding challenge or internship interview or a warm up question.

Here’s the question:

``````def majority_element_indexes(lst):
'''
Return a list of the indexes of the majority element.
Majority element is the element that appears more than
floor(n / 2) times.
If there is no majority element, return []
>>> majority_element_indexes([1, 1, 2])
[0, 1]
>>> majority_element_indexes([1, 2])
[]
>>> majority_element_indexes([])
[]
'''
``````

The entire solution will be available at the end of the course. Try to find a solution to the problem yourself and then watch the video for the solution.

You also heard about Big O analysis, which is a way to analyze the speed and memory usage of a function or block of code. See Wikipedia Time complexity for more information. AlekS

my two solutions, second pretty similar to yours.

ls = [6, 8, 1, 1, 2, 3, 8, 5, 5, 8, 8, 8, 8, 8, 8, 8] ls = [1, 1, 2] ls = [] ls = [2, 2, 2, 1, 1, 3, 2, 2] ls = [1, 3, 2, 2, 4, 5]

def majority_element_v0(lst):

``````if len(lst) == 0:
return []
``````
create list of tuples: (list_elem, index)
``````lst_dic = [(val, key) for key, val in list(enumerate(lst))]

dic = defaultdict(list)
``````
create dict with keys as unique elements of list and values as list of #indexes of unique elements
``````for key, val in lst_dic:
dic[key].append(val)
``````
find element of dict satisfying condition if len(val) > #floor(len(lst) / 2)]
``````res = [[key, val] for key, val in dic.items() if len(val) > floor(len(lst) / 2)]

if len(res) == 0:
return []
else:
return res
``````

print(majority_element_v0(ls))

def majority_element_v1(lst):

``````if len(lst) == 0:
return []

m_elem = [key for key, val in Counter(lst).items() if val > floor(len(lst) / 2)]

if len(m_elem) == 0:
return []

return [m_elem, [i for i in range(len(lst)) if lst[i] == m_elem]]
``````

print(majority_element_v1(ls)) James Uejio RP Team

Hi @AlexSch thank you for sharing! Great way to use list comprehensions. There are definitely many ways to do this and as long as you comment your code and the interviewer can follow your solution (and the runtime is reasonable/optimal), you’re good to go! belushkin

Hello fellows, Here is my solution, I hope it is right:

``````from collections import Counter

def majority_element_indexes(lst):
'''
>>> majority_element_indexes([1,1,2])
[0, 1]
>>> majority_element_indexes([1,2])
[]
>>> majority_element_indexes([])
[]
>>> majority_element_indexes([1,1,2,2,2,2])
[2, 3, 4, 5]
>>> majority_element_indexes([6, 8, 1, 1, 2, 3, 8, 5, 5, 8, 8, 8, 8, 8, 8, 8])
[1, 6, 9, 10, 11, 12, 13, 14, 15]
>>> majority_element_indexes([2, 2, 2, 1, 1, 3, 2, 2])
[0, 1, 2, 6, 7]
>>> majority_element_indexes([1, 3, 2, 2, 4, 5])
[]
'''

n = len(lst) // 2
cnt = Counter(lst)
return [index for index, element in enumerate(lst) if cnt[element] > n]
`````` James Uejio RP Team

@belushkin it looks right! James Uejio RP Team

For anyone while we upload video descriptions, I talk about Big-O analysis which is a way to analyze the speed and memory usage of a function or block of code. See Wikipedia Time complexity for more information. Pygator

Didn’t understand why you flipped - sign for the key fcn. danielzlacky

Hey, here is my solution, which should run O(n) in worst case scenario

``````from collections import defaultdict

def majority_element_indexes(lst):
majority_count = len(lst) // 2
elm_dict = defaultdict(list)
for i, v in enumerate(lst):
elm_dict[v] += [i]
if len(elm_dict[v]) > majority_count:
return elm_dict[v]
return []
`````` James Uejio RP Team

Hi @Pygator I flipped the sign because by default the sort method sorts in ascending order (so [1, 2, 3]) but in my head I wanted the largest element at the front. However you are right I could have accessed it just with [-1] instead.

@danielzlacky great concise solution without using Counter! Marcus Reaiche

Thanks for the great course! Here is my solution. I used the most_common method of the Counter instance. Hopefully the method was implemented in a smart way so that it runs in O(n) when passing the argument 1.

``````from collections import Counter

def majority_element_indexes(lst):
"""
Return a list of indexes of the majority element.
Majority element is the element that appears more than floor(n / 2) times.
If there is no majority element, return [].
>>> majority_element_indexes([1, 1, 2])
[0, 1]
>>> majority_element_indexes([1, 2])
[]
>>> majority_element_indexes([])
[]
"""
if lst:
most_frequent_elem, n = Counter(lst).most_common(1)
if n > len(lst) // 2:
return [k for k, x in enumerate(lst) if x == most_frequent_elem]
return []
`````` rickfencl

You said yourself that the the floor calculation constrains the majority element. Since we just want the index of where the majority elements appear in the input, I don’t see the point of finding the max number of occurrences. Or actually determinine what the majority element is. This whole exercise is just a one-liner:

print([i for i, v in enumerate(lst) if Counter(lst)[v] > len(lst)//2]) James Uejio RP Team

@Marcus Reaiche great solution and using the built in Counter methods.

@rickfencl That is a cool one line solution! I would probably not come up with that during an actual interview, and also you want to make sure that your interviewer can follow the logic. MichaelKareev

As Pythonic as it gets. The idea is to create a defaultdict with a list as a value and append to the list the frequencies and the indices. Then filter out on frequencies and return only the indices.

``````def major_element(nums):
if len(nums) == 0: return []
if len(nums) == 1: return 
thr = len(nums) // 2
d = defaultdict(list)
for n_ix in range(len(nums)):
if nums[n_ix] not in d:
d[nums[n_ix]].append(1)
d[nums[n_ix]].append([n_ix])
else:
d[nums[n_ix]] += 1
d[nums[n_ix]].extend([n_ix])
return [v if v > thr else [] for k,v in d.items()]
`````` a5zima

Hi, is it right solution?

return [x for x in range(len(lst)) if lst.count(lst[x]) > len(lst) / 2]

to join the conversation.