Coding Test : A quirky way of using Python Lists!

Kruthika Kulkarni 22 Jul, 2022 • 5 min read

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

Coding test | image

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.

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. 

Frequently Asked Questions

Lorem ipsum dolor sit amet, consectetur adipiscing elit,

Responses From Readers

Clear

anon
anon 23 May, 2021

"However, if you see the question on LeetCode, it says- do not store the integer as a string. Hence, the solution." [int(num) for num in str(x)] Seems to me like that's exactly what you did there (the str(x) part) I'm sorry, but this is just a more inelegant way to reverse the string. If you do str(something) that something is then stored as a string this fact does not change just because you don't explicitly assign it to a variable. Converting the string back to an integer after doesn't make it right.

wPregliasco
wPregliasco 23 May, 2021

You can do the same even shorter using the casting of integres into strings: xs = str(x) return xs==xs[::-1] Even works fines with negatives. I know this is not the point of tour usefull post, but it's a pretty solution.

Jim Dennis
Jim Dennis 24 May, 2021

This is simpler: def is_palindrome(item): its = str(item) return its == its[::-1] Works with strings, number, or anything with a string representation that could meaningfully be evaluated as a possible palindrome.

Julian
Julian 24 May, 2021

Both solutions actually have the same time complexity. If n is the number of digits in x, then they are both O(n). It is likely that the second approach will run faster than the first (though one would have to test it to be sure) as the loop through the digits of x is done in C (in the list comprehension and the str(x) call) rather than in Python (the explicit loop).

Grrr
Grrr 24 May, 2021

A palindrome test can be short-circuited if you compare digits rather than simply reverse the whole number. Therefore an improved brute force method compares first and last digit of number and then removes them, stopping as soon as these digits are not equal. def isPalindrome(x): import math if type(x) != int: raise ValueError("Int expected") if x < 0 or (x % 10 == 0): return False if x 0: first_digit= x // 10**(digs-1) last_digit = (x % 10) if first_digit != last_digit: return False x=(x - (first_digit * 10**(digs-1))) // 10 digs -=2 return True