Python Quick Interview Guide: Top Expert-Led Coding Interview Question Bank for Python Aspirants (English Edition)

By Shyamkant Limaye

Python is the most popular programming language, and hence, there is a huge demand for Python programmers. Even if you have learnt Python or have done projects on AI, you cannot enter the top companies unless you have cleared the Algorithms and data Structure coding test.

This book presents 75 most frequently asked coding questions by top companies of the world. It not only focuses on the solution strategy, but also provides you with the working code. This book will equip you with the skills required for developing and analyzing algorithms for various situations. This book teaches you how to measure Time Complexity, it then provides solutions to questions on the Linked list, Stack, Hash table, and Math. Then you can review questions and solutions based on graph theory and application techniques. Towards the end, you will come across coding questions on advanced topics such as Backtracking, Greedy, Divide and Conquer, and Dynamic Programming.

After reading this book, you will successfully pass the python interview with high confidence and passion for exploring python in future.

• Language: English
• Publisher: BPB Online LLP
• Release date: Apr 10, 2021
• ISBN: 9789389423310

Book preview

CHAPTER 1

Lists, Binary Search, and Strings

Most of the coding interview questions are based on lists, binary search, and strings. In this chapter, we will solve many problems on these. If you have brushed up your knowledge on these topics, it is good. But even if you haven’t, don’t worry we will give you tips as we proceed.

Structure

The concepts of time complexity and space complexity are very important in competitive coding. We will introduce these concepts first and do some warm up exercises during that process. After you have mastered a few problems, we will take a little diversion and present a wonderful topic on practical measurement and the plotting of time complexity.

Then, we will end the chapter with some more problems. In the course of solving these problems, you will be introduced to binary search and sliding window algorithms. We will cover the topics in the following order:

Time and space complexity

Linear data structures in Python

Searching and sorting

Question 1: What is the position of a target in a given sorted array?

Question 2: Is the given integer a valid square?

Question 3: How will you move zeroes in a given array to the end?

Question 4: How many boats are required to save people?

Question 5: Is the given array a valid mountain array?

Question 6: Which container can store maximum water?

Question 7: Which was the first faulty version of the software?

Question 8: What are all the subsets of a given set of integers?

Background: Measuring execution time and time complexity

Question 9: What is the maximum sum of a sub-array of a given array?

Question 10: What is the integer part of the square root of a given integer?

Question 11: What are the first and last positions of a target number in a given sorted array?

Question 12: What is the position of a search target in a 2D matrix?

Question 13: How will you convert an integer into a roman numeral?

Question 14: How will you construct Pascal’s triangle?

Objectives

After studying this chapter, you will be able to understand the concepts of time and space complexities; practically measure time complexity; acquire the skills to analyze and solve questions on lists, binary search, and strings

1.1 Time and Space Complexity

There are always different approaches to solve a problem. All of them produce the same result, but some are smart, that is, they consume fewer resources, like time and memory. We need to find the approaches that are smart. When we execute a student program on a PC, we don’t bother how long it takes to execute it or how much memory it consumes. We always find the computer memory to be big enough for us and also that we get the answer in a few seconds. But real-life problems are bigger. They will test the limitations of the hardware. Therefore, we should be interested in knowing how the execution time of an algorithm behaves when the size of the input – n, becomes arbitrarily large. A practical thumb rule is if the execution time is proportional to n, then a typical computer can solve a problem of size n = 1 million in a reasonable time. But, if the execution time is proportional to n², then the reasonable size reduces to n = 1000, and if the execution time is proportional to 2n, then the reasonable size reduces to n = 20 only.

Suppose a function f(n), describes the relationship between the execution time and the size of the input to be processed. We want to find a simplified function g(n), which can compare the performance of various approaches. The function should be independent of the CPU speed and it should estimate the order of growth of the execution time for large values of n. Such estimates are called asymptotic estimates. But the execution time does not depend on n alone. It also depends on the nature of the data. For example, if the input to a Bubble Sort algorithm is already sorted, then the function just makes one pass through the data and finishes. The time required is proportional to n. But if the input data is sorted in the reverse order, then the function has to do a lot of work in rearranging it. The time required here is proportional to n². A typical input will be partially ordered. Thus, there is a best case timing, a worst case timing, and an average case timing for any algorithm based on the nature of the input data. To represent these cases, we use the big Ω notation, big O notation, and big θ notation respectively. The same notations are also used to describe the relationship between the memory requirement and n. Sometimes we can trade in space for getting a better time.

To understand the asymptotic behavior, consider that the worst case time estimate of an algorithm to run on one computer is described by the following relation:

f(n) = 2n² + 6n + 100 microseconds

If we run the same algorithm on another computer which is half as fast, the timing relationship will be as follows:

f2(n) = 4n² + 12n + 200 microseconds

Let us define a simplified function g(n), and a constant c, such that c * g(n) is greater than f(n) for large values of n. Actually, we could find a number n0 such that if n > n0, c * g(n) > f(n). We can get such a function by ignoring the lower order terms of f(n) and the constant multiplier of the highest order term. Thus, g(n) = n² and the constant c will be as follows:

c > Lim f(n)/g(n)

n->∞

Thus, c can be chosen as 3. For small values of n, g(n) is less than f(n). For example, for n = 1, c * g(n) = 3, and f(n) = 108. But we are interested in large values. As n grows, c * g(n) catches up. For n > 7, 3g(n) is greater than f(n). In Big O notation, we write the following:

Worst case time complexity = O(g(n)) = O(n²).

If f(n) represents the best case values, then, in Big Ω notation, we write the following:

Best case time complexity = Ω(n²).

If f(n) represents the average values, then, in Big θ notation, we write the following:

Average case time complexity = θ(n²).

In practice, we are generally interested in estimating the worst case performance. So we will concentrate on the big O notation.

Let us take a look at the complexity function g(n).

1.1.1 O(n)

O(n) means the execution time of a program varies linearly with the size of the data. For example, say we want to find the sum of all the elements in an array. Then the execution time will be proportional to the number of elements in the array. If Ta is the additional time, then, the total time T is given by:

T = Ta  n

We are generally not interested in the constant Ta as it depends on the clock speed of the CPU, word length of the CPU, compiler, operating system, and so many other things. So, we drop the constant Ta and just say that the time complexity is O(n).

Here are some examples of the O(n) time complexity:

A program that calculates the dot product of two arrays, that is, element by element multiplication.

Searching an item in an unsorted array (linear search).

Note that searching an unsorted array will not always take n operations. It may be anywhere between 1 to n. But for the O(n) calculations, we always consider the worst case scenario.

1.1.2 O(1)

If the algorithm takes the constant K seconds, irrespective of the size of the input, its time complexity is O(1). For example, the time required to insert a new item at the head of the list is constant. It does not depend on the length of the list. This does not mean that an O(1) operation is always faster. This just means that it is independent of the input size. For example, consider searching an item in a hash table (which is called a dictionary in Python). The time required for 1 search is independent of the size of the table, so we will describe it as O(k). However, it needs to spend a lot of time on the hashing function that computes the address. It is quite high compared to a simple retrieval from an array. For a small number of items, a linear search might even be faster than a hash table search. Beyond a certain size, the hash table will be faster. As we can drop the constants, the time complexity of the algorithm is said to be O(1), rather than O(k).

1.1.3 O(n²)

Now, suppose we want to find the sum of all the elements of an n X n matrix. The Python code for this is as follows:

Note: If you pasate the code in the Python interpreter, remove the line numbers.

1. a = [[1,2,3],[4,5,6],[7,8,9]]

2. sum = 0

3. for i in range(3):

4.     for j in range(3):

5.         sum += a[i][j]

6. print(sum)

Output: 45

Refer to the following screenshot:

Figure 1.1: Screenshot for the example of O(n²)

Whenever we see two nested loops, we can conclude that there will be n² iterations. We will require n² additions. Assume that K is the initial set up of the time needed for creating the matrix and initializing the sum to 0. The execution time T will be as follows:

T = n² Ta + K

Remember that we are interested in finding the run time when n becomes very large. Therefore, when the run time dependency is expressed as a polynomial in n, we are interested only in the highest power of n. So we can drop the second term from the preceding expression:

T = n² Ta

As stated above, the constant Ta can also be dropped. The time complexity is simply O(n²).

Similarly, in many cases, we get the time complexity as O(n (n-1)/2). It is simplified as O(n²).

1.1.4 O(n³)

Now, consider the multiplication of two matrices. First, we will write a C style program for this so that we can understand the complexity. Later, we will see the Python shortcuts. In Python, a matrix is created as a list of lists. Let us create 3X3 matrices, X and Y. We also need a result matrix to hold the result. Then, we will write two nested loops to cover all the row and column indices, and a third loop to calculate the dot product of the ith row and the jth column. The Python code to do this is as follows:

1. # Program to multiply two matrices using nested loops

2. # Create 3x3 matrix X

3. X = [[9,7,3],

4.     [4,1,6],

5.     [7,8,9]]

6. # Create 3x3 matrix Y

7. Y = [[5,8,1],

8.     [6,1,3],

9.     [4,5,9]]

10. # Create empty result matrix

11.

12. result = [[0,0,0],

13.          [0,0,0],

14.          [0,0,0]]

15.

16. for i in range(len(X)):

17.    # iterate through columns of Y

18.    for j in range(len(Y[0])):

19.        # iterate through rows of Y

20.        for k in range(len(Y)):

21.            result[i][j] += X[i][k] * Y[k][j]

22. print(result)

Output:

[[99, 94, 57], [50, 63, 61], [119, 109, 112]]

Refer to the following screenshot:

Figure 1.2: Screenshot for the example of O(n³)

The result is correct but not neatly formatted in a matrix form. Remember that the result is a list of lists. We can print each list separately to get a neat print. Replace the last line with these two lines:

for r in result:

print(r)

The output is as follows:

[99, 94, 57]

[50, 63, 61]

[119, 109, 112]

Due to the three nested loops, the innermost statement is executed n³ times. The time complexity of a matrix multiplication is therefore O(n³).

Now, let us take the advantage of the NumPy package. The simplified code is as follows:

1. import numpy as np

2. x = np.array([[9,7,3],

3.               [4,1,6],

4.               [7,8,9]])

5. y = np.array([[5,8,1],

6.              [6,1,3],

7.              [4,5,9]])

8. result = np.matmul(x, y)

9. print(result)

Output:

[[99, 94, 57]

[50, 63, 61]

[119, 109, 112]]

Refer to the following screenshot:

Figure 1.3: Screenshot for the example of O(n³) using NumPy

The time complexity is still O(n³), but the details are hidden in the library implementation.

Note: Make sure to use the np.matmull function to multiply the matrices. If you use a simple * operator, it results in the element by element multiplication.

1.1.5 O(n log n)

Now, consider that we are given an array of integers sorted in ascending order.

For example, a = [-4,-1,3,7,13,2,5]

We want to find the position (index) of the number 13 in the array. If the number does not exist, the program should return -1. There are two well-known approaches to this, namely linear search and binary search.

In the linear search method, we examine each element of the array and see if it is 13. If a match is found, we return its index. In the best case, the target may be found in the first index. In the worst case, we will do n compare operations. For big O notation, we always consider the worst case. So, the time complexity is O(n).

The binary search method is more efficient, but it requires the array to be sorted. Here, we create the left and right pointers initially set to 0 and n-1. Then, we compute mid = (left + right)/2, and examine a[mid]. If a[mid] = 13, then we have found our answer. If a[mid] < 13, then we know that the target index is more than the mid. So, we drop the lower half by replacing left with mid. If a[mid] > 13, then we know that the target index is less than the mid. So, we will replace right with mid. We will continue this process till we find a match or till left = right.

In this method, the size of the array to be searched gets halved in each iteration. So, the worst case number of the required iterations is log2n. We are not interested in the base of the logarithm. So, we write that the time complexity = O(log n). This is better than O(n).

Another example is the Fourier transform. The time complexity of the discrete Fourier Transform is O(n²) and that of the fast Fourier Transform is O(n log n).

1.1.6 O(2n)

Now, consider that we want to find the nth Fibonacci number. We can find the nth Fibonacci number using the recurrence relation:

Fibo(n) = Fibo(n-2)+Fibo(n-1) and Fibo(0) = Fibo(1) = 1.

Let us write a recursive Python function for it:

1. def recur_fibo(n):

2.    if n <= 1:

3.        return n

4.    else:

5.        return(recur_fibo(n-1) + recur_fibo(n-2))

6. recur_fibo(6)

Output:

6

Refer to the following screenshot:

Figure 1.4: Screenshot for the example of Fibonacci numbers

Here, we observe that each iteration is spawning two more iterations. Thus, if we increase n by 1, it will double the number of iterations. Therefore, the time complexity is O(2n).

1.1.7 Space complexity

The concept of space complexity is similar to that of time complexity. Here, we find how much extra memory space is required by the algorithm as a function of n. It is also expressed in the big O notation.

If the algorithm does not require any extra space or requires a constant space irrespective of the size, then, the space complexity will be O(1).

If an algorithm allocates extra space proportional to n, then, its space complexity is O(n).

1.2 Linear Data Structures in Python

The data structure is a way of organizing data in the computer memory. We choose a data structure depending on the efficiency of intended operations on the given data. The most common operations are insertion, deletion, updating, sorting, and searching. If we can organize the data in a sequential manner such that each element has a predecessor and a successor, and the collection has a first and a last element, it is called a linear data structure. They can be traversed in a single run. The simplest linear structure is a 1-dimensional array. A 2-D array, that is, a matrix is also a linear data structure, though it has two dimensions because an element (m, n) is mapped to a single dimension array element (mN + n), assuming the row and the column numbering starts from 0. Other examples of linear data structures are dynamic array (where the size grows according to the requirement), queue, deque (Double-ended queue), stack, and linked list. The examples of non-linear data structures are hash tables, trees, and graphs. In Python, the dynamic array, queue, and stack are implemented by a single class, named list. The class deque is available in a module, named collections. The string is a special case of the dynamic array where the data elements are ASCII characters and a special set of operations are defined for them. We will study them in detail in the coming sections.

1.2.1 The list class

Python has a large set of useful functions for lists. The most frequently used functions are described here. For the complete list, the reader may refer to the Python documentation.

An object of the list class can be created by enclosing a set of elements in the square brackets. For example:

A = [3, 5, 7]

A structure similar to the list is a tuple. It can be created by enclosing the items in round brackets instead of the square brackets. For example:

t = (3,4,5,6)

A tuple is immutable, that is, it cannot be changed after it is declared. We cannot add or delete its elements or alter its values. We can only access individual elements just like the list elements. For example:

t[0] means integer 3

a = t[1:] means a tuple a = (4,5,6)

The elements of a list need not be of the same type. For example:

a=[1,’e’,(1,2,3),[4,5,6]]

The elements of a tuple also need not be of the same type. For example:

t=(1,’e’,(1,2,3),[4,5,6])

If we enclose the elements in braces, it creates a set that is a non-linear data structure. For example:

s = {1,2,3}

We will study sets in the next chapter.

The list is basically an array. The individual elements of a list can be accessed by specifying the index in the square brackets. For example:

a = [1,2,3,4,5]

a[0] means 1, a[1] means 2, and so on. Indices can be also negative. a[-n] means nth element from the end. a[-1] means the last element.

A subset of the array can be obtained by specifying the range of indices. For example:

b= a[1:3] assigns value [2,3] to b. Note that the element at the end of index 3 is not included.

The Length of an array is obtained by the len function.

print(len(a)) prints 5.

The indices of a are in the range 0 to len(a) – 1.

If we give a command a[5] = 8, we get an error because there is no element with index 5. For adding elements, we must use the append function. For example:

a.append(8)

This is equivalent to pushing an element on a stack. The inverse operation pop is also available.

b = a.pop() removes the last element in the array (8) and assigns it to b. Both append and pop operations take place with the time complexity of O(1).

In general, pop(n) removes the nth element from the array. The default value of n is -1.

The insert(n, element) function inserts the element at index n. The function insert(0, element) inserts the element at the beginning. The insert(0, element) and pop() pair can be used to implement a queue. When you insert an element at index 0, all the existing elements have to be pushed by one place. Therefore, the time complexity of the enqueue operation is O(n).

1.2.2 NumPy arrays

The built-in list class is useful as a dynamic array, queue, or stack. But, if you want to do mathematical operations like matrix multiplication, it is better to use arrays from the NumPy module. The NumPy arrays take less memory space and perform faster mathematical operations.

1.2.3 Strings

In Python, the strings are one-dimensional arrays of ASCII characters. Python has a large set of useful functions for strings. The most frequently used functions are described here. For the complete list, the reader may refer to the Python documentation.

A string literal is declared by enclosing the characters in double quotes or single quotes. For example:

s = Hello

s = ‘Hello’

But basically, it is a list, so it can also be expressed as:

s = [‘H’,’e’,’l’,’l’,’o’]

The individual elements can be accessed just like list objects. For example:

s[1] means ‘e’

s[2:] means ‘llo’

The function len(s) return returns the length of the string s.

The strings can be concatenated by the ‘+’ operator. Thus ‘abc’+’123’ gives ‘abc123’.

The string class has a useful function "zfill(n)" which pads zeroes to the left of a string to make its length equal to n. For example:

a = abc

a.zfill(5) gives 00abc.

We will use this function in question 8.

1.3 Sorting and Searching

Sorting and searching are the two most widely used operations on data in practice. Sorting means rearranging the elements of an array in ascending or descending order. Searching means finding a data item in a collection. A lot of different sorting algorithms have been developed. Each has its own merits and demerits with respect to the nature of the data. We have to choose an algorithm that suits our particular data distribution. A comparison of the complexities of various algorithms is as follows:

Searching

The purpose of searching can be one of the following:

We want to check if the given data item exists in a collection.

The data consists of a collection of key:value pairs. We want to retrieve the value corresponding to a given key.

If the collection is in the form of a haphazard unsorted array, in that case, the only way of searching an item is by scanning each element of the array and comparing it with the search target. This is called linear search. The number of comparisons in the worst case will be n, where n is the size of the array. In the best case, we will hit the target in the first comparison, and in the average case, we will need n/2 comparisons. The worst case time complexity is thus