Coding Test : A quirky way of using Python Lists!

This article was published as a part of the Data Science Blogathon

Source: https://resources.workable.com/

An Overview of Internet coding test

We have all prepared for a coding interview at some point in our lives. If you are reading this article today, you are mostly giving an interview soon. Best of luck! May the force be with you!

What is a coding test? If you are giving a coding test for the first time, let me tell you what to expect. Coding test usually comprises of algorithmic questions which test your skills in data structures and code optimization.

The questions asked in this segment may not be directly related to your work. In fact, it is almost certain you will never write codes to check if a number is prime, code to find the palindrome or a code to find the longest common substring from 1000 strings at work. The purpose of this test is to gauge your thought process and your programming level.

Remember one thing before you start any coding test. This suggestion holds in the cases where your interviewer is present while taking the test or having your interviewer’s contact details.

In the unfortunate case where you had an algorithm in mind but could not write the program, explain your thought process (algorithm) to your interviewer. It is not a black and white situation. Ideating loudly or expressing your ideas to the interviewer might give the interviewer a better understanding of your abilities.

How to prepare for the coding test?

It is suggested by many veteran coders that practising a lot of problems will help build intuition and equip you with tools to solve new problems. Many websites like HackerRank and LeetCode let you practice your code and understand how optimized your solution is.

You now know what to expect from this stage of the hiring process and you know a few sites that will help you along the way. However, how do you solve such problems? I will explain the train of steps to follow that has personally helped me.

It is impossible to prepare for a coding interview and not try this problem statement

“Given an integer x, return true if x is palindrome integer.“

I came across this problem while practising for one of my coding interviews using LeetCode.You can find the question here. I will use this problem to explain the steps.

Since I wanted to have fun while coding, I decided to experiment with lists. I do not know if this code has been written before, however, this was my personal effort.

After watching a few videos and understanding the approach that a few coders take in solving these algorithmic problems, I have consolidated the following steps to solve this problem. The steps mentioned below can be used for any algorithmic problem. The palindrome problem is only used as an example to show the steps to approach any coding problem.

1. Do I understand the question – What is a palindrome?

According to Merriam-Webster, a palindrome is defined as follows-

a word, verse, or sentence (such as “Able was I ere I saw Elba”) or a number (such as 1881) that reads the same backward or forward

We only consider integers in this problem.

Examples: 12321, 22, 56877865

2. What are the constraints to consider before I start writing the code?

The constraints here refer to the assumptions we make before writing the code. We will not check if these conditions are met. It is assumed that the arguments passed to the function will satisfy the below conditions. Constrains vary based on the problem statements. I have narrowed down the following constraints to focus on the main topic of discussion – the use of a list in this problem.

i. Only integers are passed as arguments.

ii. Negative integers are not considered as palindromes.

3. Brute Force Method

The brute force approach is defined in Merriam-Webster as-

relying on or achieved through the application of force, effort, or power in usually large amounts instead of more efficient, carefully planned, or precisely directed methods

The brute force approach is usually the first approach that comes to our mind when we take up any programming question.

Here, the approach I considered was to reverse the integer and compare it with the original integer.

#Brute Force Approach
def isPalindrome(x):
    #First make sure that the result is False when the integer is negative
    if x<0:                      
        return False
    #Initialising the reversed string to 0
    rev = 0 
    #Assigning x to original as we will be modifying x in the below steps
    original = x   
    #This while loop is used to get the reverse of an integer.
    while x>0:   
        # x%10 (reminder when x is divided by 10) will give the last digit of x
        rev = rev*10 + x%10    
        #Remove the last digit from x to use if for the next step of the while loop 
        x = int(x/10)            
    #Check if  the reversed integer is equal to the original integer   
    if int(rev) == original:
        return True
    else:
        return False

The code can be explained as below-

I. If the integer is negative, return false.

II. Initialize an integer (rev) to 0. this variable will be used to store the reverse of the integer to be checked.

III.  Start a while loop. In the while loop, we obtain the reverse of the original integer

IV.  Check if the list created in Step II and III are equal. If yes, the number is a palindrome.

This code is of time complexity O(log n).

4. The Fun begins here

The fourth step is optimization. However, I decided to use lists for the same and review its outcome.

My code was as follows-

#Solution using Lists
def isPalindrome(x):
    #First make sure that the result is False when the integer is negative
    if x<0:
        return False
    #Convert the integer into a list : 123 becomes [1, 2, 3]
    lst_int = [int(num) for num in str(x)]
    #Reverse the list : [1,2,3] becomes [3,2,1]
    reverse_lst = lst_int[::-1]
    #Check if the reversed list is the same as the original list
    if lst_int == reverse_lst:
        return True
    else:
        return False

The code can be explained as below:

I. If the integer is negative, return false

II. Convert the integer x to a list: 123 becomes [1,2,3]

III. Reverse the list: [1,2,3] becomes [3,2,1]

IV. Check if the list created in Step II and III are equal. If yes, the number is a palindrome.

It might seem like we could have directly used the string function on the integer and reversed the string instead of using the list. However, if you see the question on LeetCode, it says- do not store the integer as a string. Hence the solution.

Each line of this code is of O(n) complexity. Adding multiple O(n) complexity statements does not increase the complexity of the algorithm. Hence this is O(n) solution.

Clearly, this solution is worse than the brute force method which has a complexity of O(log n). This step is the hardest for a reason. Because we need to think a lot to ensure we do not make things worse than it already is. Step four is an iterative step that repeats itself till a certain amount of improvement is seen in the time complexity or the space complexity of the code.

Visit here to see the discussions of your fellow coders and get inspired to optimize the above code

Conclusion

This is not the optimized solution you should be trying at your next interview. It is only a stepping stone to tell you how to think. I am a learner like you and learning one new thing a day. Also, I do not want to wait till I become an expert to share what I learn.

I urge you to try every idea that comes to your mind. You might have the next big idea!

Happy Coding!

The media shown in this article are not owned by Analytics Vidhya and is used at the Author’s discretion.