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.
00:00 In this video, you’ll use what you learned in the course so far to solve an easy interview question. What I mean by easy doesn’t mean trivial—it means something you might see in a coding challenge, or maybe a internship question, or a warm-up question.
00:26 The majority element is defined as the element that appears more than floor(n / 2) times, where n is the length of the list. So for example, in a list with five elements, the majority element has to appear more than 5 / 2—floor() would be 2 times. It has to appear more than 2 times.
So, 3, 4, or 5 times. If there is no majority element, return an empty list. Here’s the test case:
majority_element_indexes([1, 1, 2]). So, the majority is
1 appears twice, and the indexes that
1 appears are [
01:00 Make sure to go through all test cases and make sure that you understand them and ask any questions. Also, it’s good to write some more test cases to make sure that you understand what the function’s supposed to do.
Writing another test case
majority_element_indexes() of maybe a list
[1, 2]—which has no majority element—should return the empty list, and verify with the interviewer that this is the case, and then, maybe, an empty list—returns an empty list.
I will go over the solution in five, four, three, two, one. So, let’s get started. First, I write some comments with my thought process because then I can refer back to them when I’m coding. For example, I know I’ll probably have to find the majority element, so
# find majority element.
So now, ideally, the majority element will be
top_elems. So moving to step two, how do you know if there is no majority element? While scrolling at the top, the majority element is defined to be […]
"the element that appears more than
floor(n / 2) times." So,
if count[maj_elem] <= n // 2 (floordiv
2), then you know that this condition is not
True, because the count of the majority element is less than or equal to
n // 2. Then, return
So, it’s good to write comments when you’re coding—something like
# there exists a
majority element. Okay, so now that we know there is a majority element, what do we need to do? Find the indexes of the majority element, put them in a list.
Whenever you have to put something in a list and maybe loop through something and just put them in—list comprehension should come to mind. Do this all in one line. Return the indexes, so
i for i, elem in lst because we need access to the element to check if
Okay, two failed.
cannot unpack non-iterable int object. Oops. This should be
enumerate(). So, actually forgot to use something that you learned a couple videos ago, but basically, if you want to get the index and the value, you need to use
enumerate(). Now, one failure.
list index out of range.
top_elems, here. Okay, well it’s because we’re passing in a empty list. It goes down here, it goes in here, tries to access the zeroth element of an empty list.
Let’s just delete this code to make it a little cleaner. Okay, so now that it seems to work, let’s do a runtime analysis of what’s going on. The
Counter class should take O(n) because it just has to loop through and build a dictionary.
Here, this is constant time, this is constant time, and this is n. I guess, technically, this is not n log n because n would be the length of the
lst, while here we’re iterating over the
count, and so if numbers appear more frequently, this length will be smaller than
lst, but let’s just leave it as n log n, as sort of an upper bound of what the length of this iterable could be.
07:13 The interviewer might ask you, “Okay, is there any way to speed this up?” I mean, n log n is not bad and n is not bad, so maybe they’ll just say, “Okay, this is fine,” and move on. But in order to speed this up, there’s a way to do this in O(n) time. Instead of sorting it, we could just loop through all the counts, find the top count, and then find the element that corresponds to that top count.
And then something like the majority element—instead of being
top_elems, which we don’t have anymore—is just list comprehension,
elem for elem, count in count.items—let’s make it cleaner, like this—
if count == top_count,
This is safe to do because this
top_count will get the max of
count.values(), and so that means there will always be a count here, and then looping through this guarantees that because we’re looping through the same dictionary, that this list will have at least one element.
It could have multiple elements that have this
top_count and then just get one of them—it’s fine because this check right here is going to guarantee that there is only one majority element. Because if there were two majority elements, then the count of the majority element would not be greater than half of the list. Now, looking at runtime, this runs in O(n)—again—n being sort of an upper bound of what the possible length of
count.values could be. And this is just a
for loop, so this would be O(n).
Become a Member to join the conversation.