This post was written by Cameron Wilson, and was originally published at Educative.io

This post will cover interview questions on the Python programming language. While this list isn't exhaustive, it should give you a good idea of what types of questions you can expect.

Here's a list of the questions that will be covered:

Python Language Basics

• Question 1: What is the difference between a list and a tuple?
• Question 2: How would you convert a list into a tuple?
• Question 3: What is the difference between an array and a list?
• Question 4: How would you convert a list to an array?
• Question 5: How is memory managed in Python?
• Question 6: How do you achieve multithreading in Python?
• Question 7: What is monkey patching?
• Question 8: What is a lambda function? Give an example of when it's useful and when it's not
• Question 9: What is pickling and unpickling?
• Question 10: What advantages do NumPy arrays offer over (nested) Python lists?
• Question 11: Explain inheritance in Python with an example
• Question 12: What is polymorphism in Python?
• Question 13: Explain the difference between range() and xrange()
• Question 14: Explain the differences between Flask and Django
• Question 15: What is PYTHONPATH?
• Question 16: What is PEP 8?
• Question 17: What are Python decorators?
• Question 18: What is init?
• Question 19: What is the ternary operator?
• Question 20: What are global and local variables in Python?
• Question 21: What is the @property in Python?
• Question 22: How is try/except used in Python?
• Question 23: Explain the differences between Python 2 and Python 3
• Question 24: What is the join method in python?
• Question 25: What is dictionary comprehension?
• Question 26: How would you make a deep copy in Python?
• Question 27: How would you check if a key exists in a Python dictionary?
• Question 28: How would you achieve memoization in Python?
• Question 29: How would you sort a dictionary in Python?
• Question 30: How and when would you use any() and all()?
• Question 31: What is a Python Docstring?
• Question 32: Write a Python function and explain what’s going on.
• Question 33: Explain the difference between a generator and an iterator in Python.
• Question 34: What is defaultdict in Python?
• Question 35: What are Python modules?

Python Coding Questions

• Question 36: Reverse a string in Python
• Question 37: Check if a Python string contains another string
• Question 38: Implement breadth first search (BFS) in Python
• Question 39: Implement depth first search (DFS) in Python
• Question 40: Implement wildcards in Python
• Question 41: Implement merge sort in Python
• Question 42: Implement Dijkstra’s algorithm in Python
• Question 43: Merge two sorted lists
• Question 44: Find two numbers that add up to ‘k’
• Question 45: Find the first non-repeating integer in a list
• Question 46: Find the middle value of the linked list
• Question 47: Reverse first ‘k’ elements of a queue
• Question 48: Find the height of a binary search tree (BST)
• Question 49: Convert max heap to min heap
• Question 50: Detect loop in a linked list

Python Interview Questions - Language specific

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

When to use each:

A tuple should be used whenever the user is aware of what is inserted in the tuple. Suppose that 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 would 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?

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

During 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?

1. Memory management in python is managed by Python private heap space. All Python objects and data structures are located in a private heap. The programmer does not have access to this private heap. The python interpreter takes care of this instead.
2. The allocation of heap space for Python objects is done by Python’s memory manager. The core API gives access to some tools for the programmer to code.
3. 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?

1. 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.
2. 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.
3. This happens very quickly so to the human eye it may seem like your threads are executing in parallel, but they are really just taking turns using the same CPU core.
4. All this GIL passing adds overhead to execution. This means that if you want to make your code run faster then using the threading package often isn’t a good idea.

Question 7: What is monkey patching?

In Python, the term monkey patch only 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:

The purpose of lambdas

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

The beauty of lambda functions lies 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 dump function, this process is called pickling. While the process of retrieving original Python objects from the stored string representation is called unpickling.

Keep the learning going.

Practice the most common Python interview questions and watch your confidence soar. Educative's text-based courses are easy to skim and feature live in-browser coding environments - making learning quick and efficient.

Grokking the Coding Interview: Patterns for Coding Questions

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

1. 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.
2. 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.
3. NumPy is not just more efficient; it is also more convenient. You get a lot of vector and matrix operations for free, which sometimes allow one to avoid unnecessary work. And they are also efficiently implemented.
4. NumPy array is faster and You get a lot built in with NumPy, 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 are inheriting is called super-class and the class that is inherited is called a derived / child class.

They are different types of inheritance supported by Python:

1. Single Inheritance – where a derived class acquires the members of a single super class.
2. Multi-level inheritance – a derived class d1 in inherited from base class base1, and d2 are inherited from base2.
3. Hierarchical inheritance – from one base class you can inherit any number of child classes
4. 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. So, for instance, if the parent class has a method named ABC then the child class also can 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 are the exact same in terms of functionality. They both provide a way to 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 like 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. Some features it offers are user authentication, templating engine, routing, database schema migration, and much more.

The Django framework is incredibly flexible in which you can work with MVPs to larger companies. 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 less “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 is 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.

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

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

Question 24: What is 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.

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 is the unconditional merging.

The general syntax is as follows:

Example

The following example runs for the college’s data base and uses simple merging. Imagine that there is a college’s database storing lots of data. For example student’s address, grades, section, fees, roll number and so on. Now we need to identify each student uniquely and create a new dictionary which 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 are 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.

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 is 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.

import timeit

def memoize_fib(func):
    cache = {}
    def inner(arg):
        if arg not in cache:            
            cache[arg] = func(arg)
        return cache[arg]
    return inner


def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fib(num-1) + fib(num-2)

fib = memoize_fib(fib)


print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))

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()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'pango'

lst = dict.keys()

# Sorted by key
print("Sorted by key: ", sorted(lst))

values()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'pango'

lst = dict.values()

#Sorted by value
print("Sorted by value: ", sorted(lst))

items()

dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'strawberry'

lst = dict.items()

# Sorted by key
print("Sorted by key: ", sorted(lst, key = lambda x : x[0]))

#Sorted by value
print("Sorted by value: ", sorted(lst, key = lambda x : x[1]))

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

What is any()?

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 True can 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 and conditions.

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 is a specified document for the written code. Unlike conventional code comments, the doctoring should describe what a function does, not how it works.

The docstring can be accessed using

• __doc__ method of the object
• help function

Example

def Examplefunc(str): #function that outputs the str parameter
  print "The value is", str 
  #no return statement needed in this function

def 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 above takes a variable str as parameter and then prints this value. Since it only prints the value there is 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 back 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.

Apart from the obvious syntactic differences, the following are some noteworthy differences:

Implementation of Iterator

# Function to generate all the non-negative numbers
# up to the given non-negative number.
class UpTo:
    # giving the parameter a default value of 0
    def __init__(self, max = 0):
        self.max = max
    def __iter__(self):
        self.n = 0
        return self
    def __next__(self):
        # The next method will throw an
        # exception when the termination condition is reached.
        if self.n > self.max:
            raise StopIteration
        else:
            result = self.n
            self.n += 1
            return result
for number in UpTo(5):
    print(number)

Output:
0
1
2
3
4
5

Implementation of Generator

# Function to generate all the non-negative numbers
# up to the given non-negative number
def upto(n):
  for i in range(n+1):
    # The yield statement is what makes a function 
    # a generator
    yield i
for number in upto(5):
  print(number)

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. According to the specified data type, the dictionary is created and when any key, that does not exist in the defaultdict is added or accessed, it is assigned a default value as opposed to giving a KeyError.

Example

The first code snippet below shows a simple dictionary and how when a key that does not exist in the dict is accessed, it gives an error.

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

Now let’s introduce a defaultdict and see what happens.

from collections import defaultdict

defaultdict_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:

1. Built in

2. User-defined

Benefits of modules in Python

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

• Structured Code

  • Code is 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 recreate 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. Let’s dive in.

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:

stringname[stringlength::-1] # method 1 

Or write without specifying the length of the string:

stringname[::-1] # method2

The slice statement means start at string length, end at position 0, 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. Other two notable methods are Loop and Use Join.

Question 37: Check if a Python string contains another string

There are a couple ways to check this. For this post, 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:

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 breadth first search (BFS) in Python

Consider the​ graph which ​is implemented in the code below:

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

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 to use 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:

# Using a Python dictionary to act as an adjacency list
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

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 yes, it is 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 case of DFS on a tree, the time complexity is O(V), where V is the number of nodes.

Keep the learning going.

Practice the most common Python interview questions and watch your confidence soar. Educative's text-based courses are easy to skim and feature live in-browser coding environments - making learning quick and efficient.

Grokking the Coding Interview: Patterns for Coding Questions

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. Hence,​ to search for all words matching the color pattern, the code would look something like as follows.

# Regular expression library
import re

# Add or remove the words in this list to vary the results
wordlist = ["color", "colour", "work", "working",
            "fox", "worker", "working"]

for word in wordlist:
        # The . symbol is used in place of ? symbol
        if re.search('col.r', word) : 
                print (word)

Output: color

Question 41: Implement merge sort in Python

Here is the code for merge sort in Python:

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0

        # Iterator for the main list
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)

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

Explanation

This is the recursive approach for implementing merge sort. The steps needed to obtain the sorted array through this method can be found below:

1. The list is divided into left and right in each recursive call until two adjacent elements are obtained.

2. Now begins the sorting process. The i and j iterators traverse the two halves in each call. The k iterator traverses the whole lists 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 traversed completely. 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 steps 1 and 2 until all the vertices are visited.

Here's the implementation

import sys

# Function to find out which of the unvisited node 
# needs to be visited next
def to_be_visited():
  global visited_and_distance
  v = -10
  # Choosing the vertex with the minimum distance
  for index in range(number_of_vertices):
    if visited_and_distance[index][0] == 0 \
      and (v < 0 or visited_and_distance[index][1] <= \
      visited_and_distance[v][1]):
        v = index
  return v

# Creating the graph as an adjacency matrix
vertices = [[0, 1, 1, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 1],
            [0, 0, 0, 0]]
edges =  [[0, 3, 4, 0],
          [0, 0, 0.5, 0],
          [0, 0, 0, 1],
          [0, 0, 0, 0]]

number_of_vertices = len(vertices[0])

# The first element of the lists inside visited_and_distance 
# denotes if the vertex has been visited.
# The second element of the lists inside the visited_and_distance 
# denotes the distance from the source.
visited_and_distance = [[0, 0]]
for i in range(number_of_vertices-1):
  visited_and_distance.append([0, sys.maxsize])

for vertex in range(number_of_vertices):
  # Finding the next vertex to be visited.
  to_visit = to_be_visited()
  for neighbor_index in range(number_of_vertices):
    # Calculating the new distance for all unvisited neighbours
    # of the chosen vertex.
    if vertices[to_visit][neighbor_index] == 1 and \
     visited_and_distance[neighbor_index][0] == 0:
      new_distance = visited_and_distance[to_visit][1] \
      + edges[to_visit][neighbor_index]
      # Updating the distance of the neighbor if its current distance
      # is greater than the distance that has just been calculated
      if visited_and_distance[neighbor_index][1] > new_distance:
        visited_and_distance[neighbor_index][1] = new_distance
    # Visiting the vertex found earlier
    visited_and_distance[to_visit][0] = 1

i = 0 

# Printing out the shortest distance from the source to each vertex       
for distance in visited_and_distance:
  print("The shortest distance of ",chr(ord('a') + i),\
  " from the source vertex a is:",distance[1])
  i = i + 1

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

# Merge list1 and list2 and return resulted list
def merge_lists(lst1, lst2):
    index_arr1 = 0
    index_arr2 = 0
    index_result = 0
    result = []

    for i in range(len(lst1)+len(lst2)):
        result.append(i)
    # Traverse Both lists and insert smaller value from arr1 or arr2
    # into result list and then increment that lists index.
    # If a list is completely traversed, while other one is left then just
    # copy all the remaining elements into result list
    while (index_arr1 < len(lst1)) and (index_arr2 < len(lst2)):
        if (lst1[index_arr1] < lst2[index_arr2]):
            result[index_result] = lst1[index_arr1]
            index_result += 1
            index_arr1 += 1
        else:
            result[index_result] = lst2[index_arr2]
            index_result += 1
            index_arr2 += 1
    while (index_arr1 < len(lst1)):
        result[index_result] = lst1[index_arr1]
        index_result += 1
        index_arr1 += 1
    while (index_arr2 < len(lst2)):
        result[index_result] = lst2[index_arr2]
        index_result += 1
        index_arr2 += 1
    return result


print(merge_lists([4, 5, 6], [-2, -1, 0, 7]))

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

The solution above is a more intuitive way to solve this problem.

1. Start by creating a new empty list. This list will be filled with all the elements of both lists in sorted order and returned.

2. Then initialize three variables to zero to store the current index of each list.

3. 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.

4. 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'

def binarySearch(a, item, curr):
    first = 0
    last = len(a) - 1
    found = False
    index = -1
    while first <= last and not found:
        mid = (first + last) // 2
        if a[mid] == item:
            index = mid
            found = True
        else:
            if item < a[mid]:
                last = mid - 1
            else:
                first = mid + 1
    if found:
        return index
    else:
        return -1


def findSum(lst, k):
    lst.sort()
    for j in range(len(lst)):
        # find the difference in list through binary search
        # return the only if we find an index
        index = binarySearch(lst, k -lst[j], j)
        if index is not -1 and index is not j:
            return [lst[j], k -lst[j]]



print(findSum([1, 5, 3], 2))
print(findSum([1, 2, 3, 4], 5))

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

we will do a binary search for

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:

[9,2,3,2,6,6]

def findFirstUnique(lst):
    counts = {}  # Creating a dictionary
    # Initializing dictionary with pairs like (lst[i],(count,order))
    counts = counts.fromkeys(lst, (0,len(lst)))
    order = 0
    for ele in lst:
        # counts[ele][0] += 1  # Incrementing for every repitition
        # counts[ele][1] = order
        counts[ele] = (counts[ele][0]+1 , order)
        order += 1 # increment order
    answer = None
    answer_key = None
    # filter non-repeating with least order
    for ele in lst:
        if (counts[ele][0] is 1) and (answer is None):
            answer = counts[ele]
            answer_key = ele
        elif answer is None:
            continue
        elif (counts[ele][0] is 1) and (counts[ele][1] < answer[1]):
            answer = counts[ele]
            answer_key = ele
    return answer_key


print(findFirstUnique([1, 1, 1, 2]))

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 counts dictionary 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

To see the code solution in action, go to the original post.

Here you can use two pointers which will work simultaneously. Think of it this way:

• 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

Using 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 are traversing the linked list at twice the speed, so it is certainly faster. However, the bottleneck complexity is still O(n).

Question 47: Reverse first 'k' elements of a queue

To see the code solution in action, go to the original post

Explanation

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.

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:

• Constructor: myQueue(size) size should be an integer specifying the size of the queue.

• Enqueue: enqueue(int)

• Dequeue: dequeue()

• Check if empty: isEmpty()

• Check size: size()

Now, moving on to the actual logic, dequeue the first k elements from the front of the queue and push them in the stack we created earlier using stack.push(queue.dequeue()) in line 8.

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 will be left with an empty stack and the k reversed elements will be appended to the back of the queue.

Now we need to 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.

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 Min Heapify all Parent Nodes.

def minHeapify(heap, index):
    left = index * 2 + 1
    right = (index * 2) + 2
    smallest = index
    # check if left child exists and is less than smallest
    if len(heap) > left and heap[smallest] > heap[left]:
        smallest = left
    # check if right child exists and is less than smallest
    if len(heap) > right and heap[smallest] > heap[right]:
        smallest = right
    # check if current index is not the smallest
    if smallest != index:
        # swap current index value with smallest
        tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        # minHeapify the new node
        minHeapify(heap, smallest)
    return heap


def convertMax(maxHeap):
    # iterate from middle to first element
    # middle to first indices contain all parent nodes
    for i in range((len(maxHeap))//2, -1, -1):
        # call minHeapify on all parent nodes
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap


maxHeap = [9, 4, 7, 1, -2, 6, 5]
print(convertMax(maxHeap))

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

Explanation

Remember that we can consider the given maxHeap to be a regular list of elements and reorder it so that it represents a min heap accurately. We do exactly that 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

nodes so this solution takes O(nlog(n)) time.

Question 50: Detect loop in a linked list

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

Don't stop here

Your learning and preparing has just begun. Take your confidence to a whole new level by practicing the most frequently asked questions in a Python interview. Grokking the Coding Interview: Patterns for Coding Questions has helped countless software engineers prepare and land jobs at Microsoft, Amazon, Google, and others.

In this course you will discover the 16 overarching patterns that underlie coding questions. Once you understand a pattern, you can apply it to hundreds of other questions that are similar but different. Click the link above for a free preview.

Good Luck!

Additional resources

• Python Concurrency: Making sense of asyncio
• Data Structures for Coding Interviews in Python
• Python Concurrency for Senior Engineering Interviews
• Data Structures and Algorithms in Python
• CodingInterview.com