Python Interview Questions — Language specific

 

Question 1: What is the difference between a list and a tuple?

Press enter or click to view image in full size

When to use them

A tuple should be used whenever the user is aware of what is inserted in the tuple. Suppose a college stores the information of its students in a data structure — in order for this information to remain immutable it should be stored in a tuple.

Since lists provide users with easier accessibility, they should be used whenever similar types of objects need to be stored. For instance, if a grocery needs to store all the dairy products in one field, it should use a list.

Question 2: How do you convert a list into a tuple?

my_list = [50, "Twenty", 110, "Fifty", "Ten", 20, 10, 80, "Eighty"]my_tuple = (my_list[0], my_list[len(my_list) - 1], len(my_list))
print(my_tuple)

Output: 50, ‘Eighty’, 9

All we have to do is create a tuple with three elements. The first element of the tuple is the first element of the list, which can be found using my_list[0].

The second element of the tuple is the last element in the list. my_list[len(my_list) - 1] will give us this element. We could also have used the pop() method, but that would alter the list.

Question 3: What is the difference between an array and a list?

Press enter or click to view image in full size

Question 4: How would you convert a list into an array?

When programming, there will be instances when you will need to convert existing lists to arrays in order to perform certain operations on them (arrays enable mathematical operations to be performed on them in ways that lists do not).

Here we’ll be using numpy.array(). This function of the numpy library takes a list as an argument and returns an array that contains all the elements of the list. See the example below:

import numpy as np
my_list = [2,4,6,8,10]
my_array = np.array(my_list)
# printing my_array
print my_array
# printing the type of my_array
print type(my_array)

Output: [ 2 4 6 8 10]

Question 5: How is memory managed in Python?

• Memory management is handled by the Python private heap space. All Python objects and data structures are located in a private heap. The programmer doesn’t have access to this private heap. The Python interpreter takes care of this instead.
• Heap space for Python objects is allocated by Python’s memory manager. The core API gives access to some tools for the programmer to code.
• Python also has an inbuilt garbage collector, which recycles all the unused memory and so that it can be made available to the heap space.

Question 6: How do you achieve multithreading in Python?

• Python has a multi-threading package but if you want to multi-thread to speed your code up, then it’s usually not a good idea to use it.
• Python has a construct called the Global Interpreter Lock (GIL). The GIL makes sure that only one of your threads can execute at any one time. A thread acquires the GIL, does a little work, then passes the GIL onto the next thread.
• This happens very quickly. It may seem like your threads are executing in parallel, but they’re really taking turns using the same CPU core.
• All this GIL passing adds overhead to the execution. This means that if you want to make your code run faster then using the threading package is often not a good idea.

Question 7: What is monkey patching?

In Python, the term monkey patch refers to dynamic modifications of a class or module at run-time.

Question 8: What is a lambda function? Give an example of when it’s useful and when it’s not.

A lambda function is a small anonymous function, which returns an object. The object returned by lambda is usually assigned to a variable or used as a part of other bigger functions.

Instead of the conventional def keyword used for creating functions, a lambda function is defined by using the lambda keyword. The structure of lambda can be seen below:

Press enter or click to view image in full size

The purpose of lambdas

A lambda is much more readable than a full function since it can be written in-line. So it’s a good practice to use lambdas when the function expression is small.

The beauty of lambda functions is in the fact that they return function objects. This makes them helpful when used with functions like map or filter, which require function objects as arguments.

Lambdas aren’t useful when the expression exceeds a single line.

Question 9: What is pickling and unpickling?

Pickle module accepts any Python object and converts it into a string representation and dumps it into a file by using the dump function. This process is called pickling, while the process of retrieving original Python objects from the stored string representation is called unpickling.

Question 10: What advantages do NumPy arrays offer over (nested) Python lists?

• Python’s lists are efficient general-purpose containers. They support (fairly) efficient insertion, deletion, appending, and concatenation, and Python’s list comprehensions make them easy to construct and manipulate.
• They have certain limitations. They don’t support “vectorized” operations like elementwise addition and multiplication, and the fact that they can contain objects of differing types mean that Python must store type information for every element, and must execute type dispatching code when operating on each element.
• NumPy is not only more efficient — it’s also more convenient. You get a lot of vector and matrix operations for free, which sometimes allow one to avoid unnecessary work. They’re also efficiently implemented.
• NumPy array is faster and you get a lot built-in — FFTs, convolutions, fast searching, basic statistics, linear algebra, histograms, etc.

Question 11: Explain inheritance in Python with an example

Inheritance allows one class to gain all the members (say attributes and methods) of another class. Inheritance provides code reusability, makes it easier to create and maintain an application. The class from which we’re inheriting is called super-class and the class that’s inherited is called a derived/child class.

There are different types of inheritance supported by Python:

• Single inheritance — where a derived class acquires the members of a single superclass.
• Multi-level inheritance — a derived class d1 in inherited from base class base1, and d2 are inherited from base2.
• Hierarchical inheritance — from one base class you can inherit any number of child classes.
• Multiple inheritance — a derived class is inherited from more than one base class.

Question 12: What is polymorphism in Python?

Polymorphism means the ability to take multiple forms. For instance, if the parent class has a method named ABC, the child class can also have a method with the same name ABC having its own parameters and variables. Python allows for polymorphism.

Question 13: Explain the difference between range()and xrange()

For the most part, xrange and range have exactly the same functionality. They both generate a list of integers for you to use. The only difference is that range returns a Python list object and xrange returns an xrange object.

This means that xrange doesn’t actually generate a static list at run-time, as range does. It creates the values as you need them with a special technique called yielding. This technique is used with a type of object known as generators.

Question 14: Explain the differences between Flask and Django

Django is a Python web framework that offers an open-source, high-level framework that “encourages rapid development and clean, pragmatic design.” It’s fast, secure, and scalable. Django offers strong community support and detailed documentation.

The framework is an inclusive package, in which you get an admin panel, database interfaces, and directory structure right when you create the app. Furthermore, it includes many features, so you don’t have to add separate libraries and dependencies. Features it offers include user authentication, templating engine, routing, database schema migration, and much more.

The Django framework, in which you can work with MVPs to larger companies, is incredibly flexible. For some perspective, some of the largest companies that use Django are Instagram, Dropbox, Pinterest, and Spotify.

Flask is considered a microframework, which is a minimalistic web framework. It’s not “batteries-included,” meaning that it lacks a lot of features and functionality that full-stack frameworks like Django offer, such as a web template engine, account authorization, and authentication.

Flask is minimalistic and lightweight, meaning that you add extensions and libraries that you need as you code without automatically being provided with it by the framework. The philosophy behind Flask is that it gives only the components you need to build an app so that you have the flexibility and control. In other words, it’s un-opinionated. Some features it offers are a build-int dev server, Restful request dispatching, HTTP request handling, and much more.

Question 15: What is PYTHONPATH?

It’s an environment variable, which is used when a module is imported. Whenever a module is imported, PYTHONPATH is also looked up to check for the presence of the imported modules in various directories. The interpreter uses it to determine which module to load.

Question 16: What is PEP 8?

PEP stands for Python Enhancement Proposal. It is a set of rules that specify how to format Python code for maximum readability.

Question 17: What are Python decorators?

A decorator is a design pattern in Python that allows a user to add new functionality to an existing object without modifying its structure. Decorators are usually called before the definition of a function you want to decorate.

Question 18: What is init?

__init__ is a method or constructor in Python. This method is automatically called to allocate memory when a new object/instance of a class is created. All classes have the __init__ method.

Question 19: What is the ternary operator?

The ternary operator is a way of writing conditional statements in Python. As the name ternary suggests, this Python operator consists of three operands.

Note: The ternary operator can be thought of as a simplified, one-line version of the if-else statement to test a condition.

Press enter or click to view image in full size

Syntax

The three operands in a ternary operator include:

• condition: A boolean expression that evaluates to either true or false.
• true_val: A value to be assigned if the expression is evaluated to true.
• false_val: A value to be assigned if the expression is evaluated to false.

var = true_val if condition else false_val

The variable var on the left-hand side of the = (assignment) operator will be assigned:

• value1 if the booleanExpression evaluates to true.
• value2 if the booleanExpression evaluates to false.

Example

# USING TERNARY OPERATOR
to_check = 6
msg = "Even" if to_check%2 == 0 else "Odd"
print(msg) # USING USUAL IF-ELSE
msg = ""
if(to_check%2 == 0):
  msg = "Even"
else:
  msg = "Odd"
print(msg)

Output:
Even
Even

Explanation

The above code is using the ternary operator to find if a number is even or odd.

• msg will be assigned “even” if the condition (to_check % 2 == 0) is true.
• msg will be assigned “odd” if the condition (to_check % 2 == 0) is false.

Question 20: What are global and local variables in Python?

Global variables: Variables declared outside a function or in global space are called global variables. These variables can be accessed by any function in the program.

Local variables: Any variable declared inside a function is known as a local variable. This variable is present in the local space and not in the global space.

Question 21: What is the @property in Python?

The @property is a decorator. In Python, decorators enable users to use the class in the same way (irrespective of the changes made to its attributes or methods). The @property decorator allows a function to be accessed like an attribute.

Question 22: How is try/except used in Python?

An exception is an error that occurs while the program is executing. When this error occurs, the program will stop and generate an exception which then gets handled in order to prevent the program from crashing.

The exceptions generated by a program are caught in the try block and handled in the except block.

• Try: Lets you test a block of code for errors.
• Except: Lets you handle the error.

Question 23: Explain the differences between Python 2 and Python 3

Press enter or click to view image in full size

Python 2 is entrenched in the software landscape to the point that co-dependency between several pieces of software makes it almost impossible to make the shift.

Question 24: What’s the join method in Python?

The join method in Python takes elements of an iterable data structure and connects them together using a particular string connector value.

How does join work?

The join method in Python is a string method, which connects elements of a string iterable structure, which also contains strings or characters (array, list, etc.) by using a particular string as the connector.

Press enter or click to view image in full size

Example: Connecting elements using an empty string

This will join the elements in an array using an empty string between each element.

array = ['H','E','L','L','O']
connector = ""
joined_string = connector.join(array)
print(joined_string)

Output:
HELLO

Question 25: What is dictionary comprehension?

Dictionary comprehension is one way to create a dictionary in Python. It creates a dictionary by merging two sets of data which are in the form of either lists or arrays.

The data of one of the two lists/arrays will act as the keys of the dictionary while the data of the second list/array will act as the values. Each key acts as a unique identifier for each value, hence the size of both lists/arrays should be the same.

Here we’ll look at simple merging. Simple merging is merging or combining two lists without any restrictions. In other words, it’s the unconditional merging.

The general syntax is as follows:

Press enter or click to view image in full size

Example

The following example runs for the college’s database and uses simple merging. Imagine a college database storing lots of data — for example, students' addresses, grades, sections, fees, roll numbers, and so on. Now we need to identify each student uniquely and create a new dictionary that stores all students only. Our decision simply depends on two questions:

• What should be the key?
• What should be the value?

Here we will choose roll numbers as key and names as the value because roll numbers are unique and names could be repetitive. So, Alex’s roll number is 122 so the tuple will look like 122: Alex. This will be better explained once you try the code attached below.

rollNumbers =[122,233,353,456]
names = ['alex','bob','can', 'don'] 
NewDictionary={ i:j for (i,j) in zip (rollNumbers,names)}
print(NewDictionary)

Output:
{456: ‘don’, 233: ‘bob’, 122: ‘alex’, 353: ‘can’}

Question 26: How would you make a deep copy in Python?

A deep copy refers to cloning an object. When we use the = operator, we’re not cloning the object — instead, we reference our variable to the same object (a.k.a. shallow copy).

This means that changing one variable’s value affects the other variable’s value because they are referring (or pointing) to the same object. This difference between a shallow and a deep copy is only applicable to objects that contain other objects, like lists and instances of a class.

Method

To make a deep copy (or clone) of an object, we import the built-in copy module in Python. This module has the deepcopy() method which simplifies our task.

Syntax

This function takes the object we want to clone as its only argument and returns the clone.

Press enter or click to view image in full size

import copy# Using '=' operator
x = [1, 2, 3]
y = x
x[0] = 5    # value of 'y' also changes as it is the SAME object
x[1] = 15
print "Shallow copy: ", y# Using copy.deepcopy()
a = [10, 20, 30]
b = copy.deepcopy(a)
a[1] = 70   # value of 'b' does NOT change because it is ANOTHER object
print "Deep copy: ", b

Output:
Shallow copy: [5, 15, 3]
Deep copy: [10, 20, 30]

Question 27: How would you check if a key exists in a Python dictionary?

It’s a safe practice to check whether or not the key exists in the dictionary prior to extracting the value of that key. For that purpose, Python offers two built-in functions:

• has_key()

The has_key method returns true if a given key is available in the dictionary, otherwise, it returns false.

Fruits = {'a': "Apple", 'b':"Banana", 'c':"Carrot"}
key_to_lookup = 'a'
if Fruits.has_key(key_to_lookup):
  print "Key exists"
else:
  print "Key does not exist"

Output: Key exists

• if-in statement

This approach uses the if-in statement to check whether or not a given key exists in the dictionary.

Fruits = {'a': "Apple", 'b':"Banana", 'c':"Carrot"}
key_to_lookup = 'a'
if key_to_lookup in Fruits:
  print "Key exists"
else:
  print "Key does not exist"

Output: Key exists

Question 28: How would you achieve memoization in Python?

Consider this computationally expensive code:

# Fibonacci Numbers
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fib(num - 1) + fib(n - 2)

Memoization can be achieved through Python decorators. Here’s the full implementation.

Output:
4.9035000301955733e-05
1.374000021314714e-06
1.2790005712304264e-06

Question 29: How would you sort a dictionary in Python?

We can sort this type of data by either the key or the value and this is done by using the sorted() function.

First, we need to know how to retrieve data from a dictionary to be passed on to this function. There are two basic ways to get data from a dictionary:

Dictionary.keys(): Returns only the keys in an arbitrary order.
Dictionary.values(): Returns a list of values.
Dictionary.items(): Returns all of the data as a list of key-value pairs.

Sorted() syntax

This method takes one mandatory and two optional arguments:

• Data (mandatory): The data to be sorted. We will pass the data we retrieved using one of the above methods.
• Key (optional): A function (or criteria) based on which we would like to sort the list. For example, the criteria could be sorting strings based on their length or any other arbitrary function. This function is applied to every element of the list and the resulting data is sorted. Leaving it empty will sort the list based on its original values.
• Reverse (optional): Setting the third parameter as true will sort the list in descending order. Leaving this empty sorts in ascending order.

keys()

values()

items()

Question 30: How and when would you use any() and all()?

any() is a function that takes in an iterable (such as a list, tuple, set, etc.) and returns True if any of the elements evaluate to True, but it returns False if all elements evaluate to False.

Passing an iterable to any() to check if any of the elements are Truecan be done like this:

one_truth = [True, False, False]
three_lies = [0, '', None]print(any(one_truth))print(any(three_lies))

Output:
True
False

The first print statement prints True because one of the elements in one_truth is True.

On the other hand, the second print statement prints False because none of the elements are True; i.e. all elements are False.

Use any() when you need to check a long series of or conditions.

What is all()?

all() is another Python function that takes in an iterable and returns True if all of the elements evaluate to True, but returns False if otherwise.

Similar to any(), all() takes in a list, tuple, set, or any iterable, ​like so:

all_true = [True, 1, 'a', object()]
one_true = [True, False, False, 0]
all_false = [None, '', False, 0]print(all(all_true))
print(all(one_true))
print(all(all_false))

Output:
True
False
False

The first function call returned True because all_true was filled with truthy values. Passing one_true to all() returned False because the list contained one or more falsy values. Finally, passing all_false to all() returns False because it also contained one or more falsy values.

Use all() when you need to check a long series of andconditions.

Question 31: What is a Python Docstring?

The Python docstrings provide a suitable way of associating documentation with:

• Python modules
• Python functions
• Python classes

It’s a specified document for the written code. Unlike conventional code comments, the doctoring should describe what a function does, not how it works.

Get The Educative Team’s stories in your inbox

Join Medium for free to get updates from this writer.

The docstring can be accessed using

• The __doc__ method of the object.
• The help function.

Example

def Examplefunc(str): #function that outputs the str parameter
  print "The value is", str 
  #no return statement needed in this functiondef Multiply(x,y): #function that computes the product of x and y 
  return x*y #returning the product of x and y#Calling the functions
Examplefunc(9) #9 passed as the parameter)
answer = Multiply(4,2) #4 and 2 passed as the parameters
print "The product of x and y is:",answer

Output:
The value is 9.
The product of x and y is 8.

Explanation

The function Examplefunc takes a variable str as a parameter and prints this value. Since it only prints the value there’s no need for a return command.

The function Multiply takes two parameters, x and y, as parameters. It then computes the product and uses the return statement to return the answer.

Question 33: Explain the difference between a generator and an iterator in Python.

An iterator in Python serves as a holder for objects so that they can be iterated over. A generator facilitates the creation of a custom iterator.

Press enter or click to view image in full size

Apart from the obvious syntactic differences, there are some other noteworthy differences.

GeneratorIteratorImplemented is using a function. It’s implemented using a class. It uses the yield keyword. Usage results in a concise code. Usage results in a relatively less concise code. All the local variables before the yield statements are stored. No local variables are used.

Implementation of iterator

Output:
0
1
2
3
4
5

Implementation of generator

Output:
0
1
2
3
4
5

Question 34: What is defaultdict in Python?

The Python dictionary, dict, contains words and meanings as well as key-value pairs of any data type. The defaultdict is another subdivision of the built-in dict class.

How is defaultdict different?

The defaultdict is a subdivision of the dict class. Its importance lies in the fact that it allows each new key to be given a default value based on the type of dictionary being created.

A defaultdict can be created by giving its declaration, an argument that can have three values: list, set or int. The dictionary is created according to the specified data type. When any key that doesn’t exist in the defaultdict is added or accessed, it’s assigned a default value rather than giving a KeyError.

Example

The code snippet below shows a simple dictionary giving an error when a key that does not exist in the dict is accessed:

dict_demo = dict()
print(dict_demo[3])

Let’s introduce a defaultdict and see what happens.

from collections import defaultdictdefaultdict_demo = defaultdict(int)
print(defaultdict_demo[3])

Output: 0

In this case, we have passed int as the datatype to the defaultdict. Hence, any key that does not already exist in defaultdict_demo will be assigned a value of 0, unless a value is defined for it.

Note: You can also have set or list as the parameters

Question 35: What are Python modules?

A Python module is a Python file containing a set of functions and variables to be used in an application. The variables can be of any type — arrays, dictionaries, objects, etc.

Modules can be either built-in or user-defined.

Benefits of modules in Python

There are a couple of benefits of creating and using a module in Python:

• Structured Code: Logically organized by being grouped into one Python file which makes development easier and less error-prone, code is easier to understand and use.
• Reusability: Functionality defined in a single module can be easily reused by other parts of the application. This eliminates the need to create duplicate code.

Python Interview Questions — Coding

In this section, we’ll take a look at common coding interview questions that pertain to lists, linked lists, graphs, trees, multithreading/concurrency, and more.

Question 36: Reverse a string in Python

Let’s reverse the string Python using the slicing method. To reverse a string, we simply create a slice that starts with the length of the string and ends at index 0.

To reverse a string using slicing, write the following:

stringname[stringlength::-1] # method 1

To reverse a string without specifying the length of the string, write:

stringname[::-1] # method2

The slice statement means start at string length, end at position 0, and move with the step -1 (or one step backward).

str="Python" # initial string
stringlength=len(str) # calculate length of the list
slicedString=str[stringlength::-1] # slicing 
print (slicedString) # print the reversed string

Output: nohtyP

This is just one method to reverse a string in Python. Two other notable methods are Loop and Use Join.

Question 37: Check if a Python string contains another string

There are a couple ways to do this. In this article, we’ll look at the find method.

The find method checks if the string contains a substring. If it does, the method returns the starting index of a substring within the string, otherwise, it returns -1.

The general syntax is as follows:

string.find(substring)a_string="Python Programming" 
substring1="Programming" 
substring2="Language" 
print("Check if "+a_string+" contains "+substring1+":")
print(a_string.find(substring1)) 
print("Check if "+a_string+" contains "+substring2+":")
print(a_string.find(substring2))

Output:
Check if Python Programming contains Programming: 7
Check if Python Programming contains Language: -1

The other two notable methods for checking if a string contains another string are to use in operator or use the count method.

Question 38: Implement a breadth-first search (BFS) in Python

Consider the​ graph implemented in the code below:

Press enter or click to view image in full size

Output: A B C D E F

Explanation

Lines 3–10: The illustrated graph is represented using an adjacency list. An easy way to do this in Python is with a dictionary data structure, where each vertex has a stored list of its adjacent nodes.

Line 12: visited is a list that is used to keep track of visited nodes.

Line 13: queue is a list that is used to keep track of nodes currently in the queue.

Line 29: The arguments of the bfs function are the visited list, the graph in the form of a dictionary, and the starting node A.

Lines 15–26: bfs follows the algorithm described above:

1. It checks and appends the starting node to the visited list and the queue.
2. Then, while the queue contains elements, it keeps taking out nodes from the queue, appends the neighbors of that node to the queue if they are unvisited, and marks them as visited.
3. This continues until the queue is empty.

Time complexity

Since all of ​the nodes and vertices are visited, the time complexity for BFS on a graph is O(V + E), where V is the number of vertices and E is the number of edges.

Question 39: Implement depth-first search (DFS) in Python

Consider this graph, implemented in the code below:

Press enter or click to view image in full size

Output: A B D E F C

Explanation

Lines 2–9: The illustrated graph is represented using an adjacency list — an easy way to do it in Python is to use a dictionary data structure. Each vertex has a list of its adjacent nodes stored.

Line 11: visited is a set that is used to keep track of visited nodes.

Line 21: The dfs function is called and is passed the visited set, the graph in the form of a dictionary and A, which is the starting node.

Lines 13–18: dfs follows the algorithm described above:

1. It first checks if the current node is unvisited — if so, it’s appended in the visited set.
2. Then for each neighbor of the current node, the dfs function is invoked again.
3. The base case is invoked when all the nodes are visited. The function then returns.

Time complexity

Since all the nodes and vertices are visited, the average time complexity for DFS on a graph is O(V + E), where V is the number of vertices and E is the number of edges. In the case of DFS on a tree, the time complexity is O(V), where V is the number of nodes.

Question 40: Implement wildcards in Python

In Python, you can implement wildcards using the regex (regular expressions) library.

The dot . character is used in place of the question mark ? symbol. So,​ to search for all words matching the color pattern, the code would look something like this:

Output: color

Question 41: Implement merge sort in Python

Here’s the code for merge sort in Python:

Output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

Explanation

This is the recursive approach for implementing merge sort. These are the steps that are taken:

1. The list is divided into left and right in each recursive call until two adjacent elements are obtained.
2. The sorting process begins. The i and j iterators traverse the two halves in each call. The k iterator traverses the whole list and makes changes along the way.
3. If the value at i is smaller than the value at j, left[i] is assigned to the myList[k] slot and i is incremented. If not, then right[j] is chosen.
4. This way, the values being assigned through k are all sorted.
5. At the end of this loop, one of the halves may not have been completely traversed —if so, its values are simply assigned to the remaining slots in the list.

Time complexity

The algorithm works in O(n.logn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.

Question 42: Implement Dijkstra’s algorithm in Python

Basic algorithm:

1. From each of the unvisited vertices, choose the vertex with the smallest distance and visit it.
2. Update the distance for each neighboring vertex, of the visited vertex, whose current distance is greater than its sum and the weight of the edge between them.
3. Repeat until all the vertices are visited.

The implementation:

Output
The shortest distance of a from the source vertex a is: 0
The shortest distance of b from the source vertex a is: 3
The shortest distance of c from the source vertex a is: 3.5
The shortest distance of d from the source vertex a is: 4.5

Question 43: Merge two sorted lists

Output: [-2, -1, 0, 4, 5, 6, 7]

This is a more intuitive way to solve this problem.

• Start by creating a new empty list. This list will be filled with all the elements of both lists in sorted order and returned.
• Then initialize three variables to zero to store the current index of each list.
• Then compare the elements of the two given lists at the current index of each, append the smaller one to the new list and increment the index of that list by 1.
• Repeat until the end of one of the lists is reached and append the other list to the merged list.

Time complexity

The time complexity for this algorithm is O(n+m)O(n+m) where nn and mm are the lengths of the lists. This is because both lists are iterated over at least once.

Note that this problem can also be solved by merging in place.

Question 44: Find two numbers that add up to ‘k’

Output:
None
[1,4]

You can solve this problem by first sorting the list. Then, for each element in the list, use a binary search to look for the difference between that element and the intended sum. In other words, if the intended sum is k and the first element of the sorted list is a0, we will do a binary search for a0. The search is repeated until one is found. You can implement the binarySearch() function however you like, recursively or iteratively.

Time complexity

Since most optimal comparison-based sorting functions take O(nlogn), let’s assume that the Python .sort() function takes the same. Moreover, since binary search takes O(logn) time for finding a single element, therefore a binary search for all n elements will take O(nlogn) time.

Question 45: Find the first non-repeating integer in a list

Here you can use a Python dictionary to keep count of repetitions.

Sample input:

Output: 2

The keys in the counts dictionary are the elements of the given list and the values are the number of times each element appears in the list. We return the element that appears at most once in the list, on line 23. We need to maintain the order of update for each key in a tuple value.

Time complexity

Since the list is only iterated over only twice and the countsdictionary is initialized with linear time complexity, therefore the time complexity of this solution is linear, i.e. O(n).

Question 46: Find the middle value of the linked list

The code solution to this problem involves multiple .py files To see the code in action, go to the original post.

Here you can use two pointers which will work simultaneously:

• The fast pointer moves two steps at a time till the end of the list.
• The slow pointer moves one step at a time.
• When the fast pointer reaches the end, the slow pointer will be at the middle.

With this algorithm, you can make the process faster because the calculation of the length and the traversal until the middle are happening side-by-side.

Time complexity

You’re traversing the linked list at twice the speed, so it’s certainly faster. However, the bottleneck complexity is still O(n).

Question 47: Reverse first ‘k’ elements of a queue

The code solution to this problem involves multiple .py files. To see the code solution in action, go to the original post.

Explanation

1. Check for invalid input, i.e., if the queue is empty, if k is greater than the queue, and if k is negative on line 2. If the input is valid, start by creating a Stack. The available stack functions are:

• Constructor: myStack().
• Push Elements: push(int) to add elements to the stack.
• Pop elements: pop() to remove or pop the top element from the stack.
• Check if empty: isEmpty() returns true if the stack is empty and false otherwise.
• Return back: back() returns the element that has been added at the end without removing it from the stack.
• Return front: front() returns the top element (that has been added at the beginning) without removing it from the stack.

2. Our function reverseK(queue, k) takes queue as an input parameter. k represents the number of elements we want to reverse. The available queue functions are:

• Enqueue: enqueue(int).
• Dequeue: dequeue().
• Constructor: myQueue(size) size should be an integer specifying the size of the queue.
• Check if empty: isEmpty().
• Check size: size().

3. Moving on to the actual logic — dequeue the first kelements from the front of the queue and push them in the stack we created earlier using stack.push(queue.dequeue())in line 8.

4. Once all the k values have been pushed to the stack, start popping them, and enqueueing them to the back of the queue sequentially. We will do this using queue.enqueue(stack.pop()) in line 12. At the end of this step, we’ll be left with an empty stack and the k reversed elements will be appended to the back of the queue.

5. We move these reversed elements to the front of the queue. To do this, we used queue.enqueue(queue.dequeue()) in line 16. Each element is first dequeued from the back.

Question 48: Find the height of a binary search tree (BST)

Here you can use recursion to find the heights of the left and right sub-trees. The code solution to this problem involves multiple .py files. To see the code solution in action, visit the original post.

Explanation

Here, we return -1 if the given node is None. Then, we call the findHeight() function on the left and right subtrees and return the one that has a greater value plus 1. We will not return 0 if the given node is None as the leaf node will have a height of 0.

Time complexity

The time complexity of the code is O(n)O(n) as all the nodes of the entire tree have to be traversed.

Question 49: Convert max heap to min heap

Here we’ll minHeapify all parent nodes:

Output: [-2, 1, 5, 9, 4, 6, 7]

Explanation

Remember, we can consider the given maxHeap to be a regular list of elements and reorder it so that it represents a minHeap accurately — which is exactyl what we do in this solution. The convertMax()function restores the heap property on all the nodes from the lowest parent node by calling the minHeapify() function on each.

Time complexity

The minHeapify() function is called for half of the nodes in the heap. The minHeapify() function takes O(log(n)) time and its called on n/2 nodes so this solution takes O(nlog(n)) time.

Question 50: Detect loop in a linked list

The code solution to this problem involves multiple .py files. To see the code solution in action, visit the original post.

Explanation

Iterate over the whole linked list and add each visited node to a visited_nodes set. At every node, we check whether it has been visited or not. By principle, if a node is revisited, a cycle exists!

Time complexity

We iterate the list once. On average, lookup in a set takes O(1) time. Hence, the average runtime of this algorithm is O(n). However, in the worst case, lookup can increase up to O(n), which would cause the algorithm to work in O(n²).

Don’t Stop Now!

Your learning and preparation have only just begun. Take your confidence to a whole new level by practicing the most frequently asked questions in a Python interview. The best way to prepare is to study the overarching patterns of coding interviews. The goal isn’t just to memorize these problems but to understand the underlying patterns that drive them. That way, you’re empowered to tackle any question that comes your way. Some of the main patterns are:

• Sliding window
• Two pointers
• Fast and slow pointers
• Merge intervals
• Cyclic sort
• Breadth-first search tree
• In-place reversal of a linked list
• Two heaps
• Bitwise XOR
• K-way merge