Interview questions for python – Second max value in a list

I have an epiphany on why I struggle with getting started solving coding challenges. I notice my struggle with getting started when I am solving the problem: Find Second Maximum Value in a List. My problem is that I tend to worry too much about all the little details in the beginning when I should be focusing instead on the big picture. I want to get the fastest most efficient solution right in the beginning. This is counter productive and puts an unnecessary pressure on me when I need to find the correct solution first. Optimizing my algorithm can come later. It is okay not to get the perfect solution at once.

It is a bit like a painter focusing on drawing the little, tiny leaves on a tree when she is trying to draw a forest. The leaves are an important detail to get right for sure but not as important as mapping out where things should go on the canvas. The details can be filled in later.

It is much easier to solve the problem now that I have overcome the hurdle of expecting to get the perfect solution all at once. My first order of business is to understand the requirement of problem: Find Second Maximum Value in a List. The requirement is to implement a function find_second_maximum(lst) which will return the second largest element in a given list. I can now come up with some sample of input and output to the function so I can better visualize the problem. The sample input and output will also come in handy later when I test my implementation.

Input: A list of integers	Output: The second maximum value in the list
[10,1,3,4,5,8]	8
[0,4,9, 1,2,5,6]	6
[123,4,789,53,9000,40000]	9000

I think I have a good initial grasp of the problem now. I am sure there are other samples and edge cases that I have not thought about and will bite me later. However, that is okay at this stage, I just want to see what a solution to the problem will look like. I can improve and optimize my solution later to handle edge cases and make it more efficient.  

The first idea that comes to mind is to simply brute force it. The algorithm here will be something like this. Traverse the list twice. In the first traversal, find the maximum integer in a list. In the second list traversal, find the next maximum integer that is less that the maximum integer found in the first traversal. Here is my brute force solution:

import sys

def find_second_maximum(input_list):
    # set the largest negative integer supported by python
    first_max = -sys.maxsize - 1
    second_max = -sys.maxsize - 1
    # find first max
    for item in input_list:
        if item > first_max:
            first_max = item
    # find second maximum
    for item in input_list:
        if item != first_max and item > second_max:
            second_max = item
    return second_max

print(find_second_maximum([9, 2, 3, 6]))

This is very inefficient since I must traverse the list twice. Let’s say I want to extend the problem to find the nth maximum integer in the list. I will then need to traverse the list n times to find the solution.

I can optimize my solution if I can figure out a way to find the second maximum integer in the list in just one traversal. One way to do this is to keep track of the maximum value that I encounter so far as I traverse the list. I can keep track of two variables max_int and second_max_int. As I traverse the list, I will set the second_max_int to max_int and max_int to the current element in the list if the current element in the list is greater than max_int. If the current element in the list is not greater than max_int but it greater than second_max_int, I will update second_max_int to store the current element in the list. By the end of the list traversal, second_max_int will hold the second maximum value in the list.

def find_second_maximum_efficient(input_list):
   if (len(input_list) < 2):
       return
   # set the largest negative integer supported by python
   max_int = second_max_int = -sys.maxsize - 1
   for i in range(len(input_list)):
       # update the max_int if current element is greater that max_int
       if (input_list[i] > max_int):
           second_max_int = max_int
           max_int = input_list[i]
       # check if the current element greater than second_max_int and not equal to max_int
       elif (input_list[i] > second_max_int and input_list[i] != max_int):
           second_max_int = input_list[i]
   if (second_max_int == -sys.maxsize - 1):
       return
   else:
       return second_max_int

I am happy with my solution to the programming problem at this point. It is time to write some test cases to validate that it is correct. I can refer to the sample input and output I thought of earlier to write my test cases. Here is what I came up with:

def test_find_second_maximum():
    input_list1 = [10, 1, 3, 4, 5, 8]
    input_list2 = [0, 4, 9, 1, 2, 5, 6]
    input_list3 = [123, 4, 789, 53, 9000, 40000]

    max1 = find_second_maximum(input_list1)
    max2 = find_second_maximum(input_list2)
    max3 = find_second_maximum(input_list3)

    assert max1 == 8
    assert max2 == 6
    assert max3 == 9000

The sample input and output I came up with is very rudimentary. I am not testing for negative values, duplicate values, very large size of list and empty list for example. At this stage, I would want to refine my test cases to cover edge cases that I did not think of earlier. However, I will leave that as an exercise for another day. Today, I simply want to illustrate the importance of keeping the big picture in mind when approaching a programming interview question. I find that this approach helps me from blanking out in the middle of an interview because I have put an unnecessary burden of getting a perfect solution from the get-go. I do this by breaking out my process in 3 stages. I explained this process in detail here. First, understand the problem. Second, come up with a step-by-step algorithm to solve the problem and translate that into code. Third, test for correctness and efficiency of my solution.