 # 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] squeakyboots

Great comments! They took me down a rabbit hole =D

The one liners were fun, but when I checked them out more closely they are both at least O(n^2) right?

Marcus’s solution was the fastest when I used a list of 128000 values. It surprised me that it was all that much faster than danielzlacky’s since they’re both O(n). They seemed to be the same speed when running only 2000 values but Marcus’s pulled away pretty well once the length of the list increased significantly. I also like how concise and easy to read his solution is.

Some observations I got from diving on this exercise:

1. `count()` appears faster than `Counter` but if the solution calls `count()` more than ~5 times `Counter` seems to be better. If I knew my data was only 2-3 of the same values repeating `count()` might offer a small performance advantage, but more unique values make `Counter` come out on top.

2. `count()` is pretty significantly faster than trying to implement a Python loop that does the same thing. This made me abandon trying to take advantage of some kind of short circuit approach to stop counting and return [] when it’s clear there won’t be enough of any value. From Googling it the reason seems to be because count() uses C which is quite a bit faster than Python.

3. `enumerate()` and other generators are O(1) to call: it took me 0ns to make an enumerate object regardless of the data size. This was unintuitive for me at first, but made sense after I thought more about what a generator is. Iterating over the resulting generator adds the time complexity. This highlighted to me that I should probably use the tools that result in a generator to iterate across something where possible rather than make a new list or dict using a list comprehension. Or use () instead of [] or {} when doing the comprehension, which makes a generator. I’ll be paying more attention when that scenario comes up in the future. riancvb

Hello James! Thanks for your great content.

I wrote a test that does not pass using your solution, e.g.:

``````Failed example:
majority_element_indexes([1, 1, 2, 3, 1, 4, 4, 4, 4])
Expected:
[5, 6, 7, 8]
Got:
[]
``````

I did an implementation that probably is not the O(n) complexity (actually idk how to measure this), but at least it works for more use cases, here it is:

``````maj_indexes = []
if(math.floor((len(lst) - 1) / 2) == 0):
return []
else:
# var with majority number and how many times it is in lst
maj_elem = Counter(lst).most_common(1)
for i, x in enumerate(lst):
if(maj_elem == x):
maj_indexes.append(i)
return maj_indexes
`````` mdwikira

My solution. From what I gather fairly simillar to ones already posted.

``````def major_element_indexes(lst):
if not lst: return []
counted = Counter(lst)
threshold = len(lst) // 2
return [i for i, v in enumerate(lst) if counted[v] > threshold]
`````` mdwikira

Also there is the question : is the majority element one that satisfies the condition of `count > len(lst) // 2` or one that has the most occurences in the list ? These are two different cases, I think.

to join the conversation.