50 Python Interview Questions and Answers
Tags: python, interview, career, codenewbie
Published: 2020-05-27 21:42:32

*This post was written by Cameron Wilson, and was originally published at [Educative.io](https://www.educative.io/blog)* 

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:

<small> Python Language  Basics
* [Question 1: What  is the  difference between a list and  a tuple?](#q1)
* [Question 2: How  would you  convert  a list into a  tuple?](#q2)
* [Question 3: What is the difference between an array and a list?](#q3)
* [Question 4: How would you convert a list to an array?](#q4) 
* [Question 5: How is  memory managed in Python?](#q5)
* [Question 6: How do you  achieve multithreading in Python?](#q6)
* [Question 7: What  is monkey  patching?](#q7)
* [Question 8: What is a lambda function? Give an example of when it's useful and when it's not](#q8)
* [Question 9: What is  pickling and unpickling?](#q9)
* [Question 10: What advantages do NumPy arrays offer over (nested) Python lists?](#q10)
* [Question 11: Explain inheritance in Python with an example](#q11)
* [Question 12: What is polymorphism in Python?](#q12)
* [Question  13: Explain the difference between range() and xrange()](#q13)
* [Question 14: Explain the differences between Flask and Django](#q14)
* [Question 15: What is PYTHONPATH?](#q15)
* [Question 16: What is PEP 8?](#q16)
* [Question 17: What are Python decorators?](#q17)
* [Question 18: What is init?](#q18)
* [Question 19: What is the ternary operator?](#q19)
* [Question 20: What are global and local variables in Python?](#q20)
* [Question 21: What is the @property in Python?](#q21)
* [Question 22: How is try/except used in Python?](#q22)
* [Question 23: Explain the differences between Python 2 and Python 3](#q23)
* [Question 24: What is the join method in python?](#q24)
* [Question 25: What is dictionary comprehension?](#q25)
* [Question 26: How would you make a deep copy in Python?](#q26)
*  [Question 27: How would you check if a key exists in a Python dictionary?](#q27)
* [Question 28: How would you achieve memoization in Python?](#q28)
* [Question 29: How would you sort a dictionary in Python?](#q29)
* [Question 30: How and when would you use any() and all()?](#q30)
* [Question 31: What is a Python Docstring?](#q31)
* [Question 32: Write a Python function and explain what’s going on.](#q32)
* [Question 33: Explain the difference between a generator and an iterator in Python.](#q33)
* [Question 34: What is defaultdict in Python?](#q34)
* [Question 35: What are Python modules?](#q35)

<small> Python Coding Questions

* [Question 36: Reverse a string in Python](#q36)
* [Question 37: Check if a Python string contains another string
](#q37)
* [Question 38: Implement breadth first search (BFS) in Python](#q38)
* [Question 39: Implement depth first search (DFS) in Python](#q39)
* [Question 40: Implement wildcards in Python](#q40)
* [Question 41: Implement merge sort in Python](#q41)
* [Question 42: Implement Dijkstra’s algorithm in Python](#q42)
* [Question 43: Merge two sorted lists](#q43)
* [Question 44: Find two numbers that add up to ‘k’](#q44)
* [Question 45: Find the first non-repeating integer in a list](#q45)
*  [Question 46: Find the middle value of the linked list](#q46)
* [Question 47: Reverse first ‘k’ elements of a queue](#q47)
* [Question 48: Find the height of a binary search tree (BST)](#q48)
* [Question 49: Convert max heap to min heap](#q49)
* [Question 50: Detect loop in a linked list](#q50)


___

## Python Interview Questions - Language specific

<a name="q1"></a>

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

|                                                     List                                                     |                                        Tuple                                        |
|:------------------------------------------------------------------------------------------------------------:|:-----------------------------------------------------------------------------------:|
|               A list consists of mutable objects. (Objects which can be changed after creation)              | A tuple consists of immutable objects. (Objects which cannot change after creation) |
|                                           List has a large memory.                                           |                              Tuple has a small memory.                              |
| List is stored in two blocks of memory (One is fixed sized and the other is variable sized for storing data) |                     Tuple is stored in a single block of memory.                    |
|                   Creating a list is slower because two memory blocks need to be accessed.                   |                   Creating a tuple is faster than creating a list.                  |
|                               An element in a list can be removed or replaced.                               |                 An element in a tuple cannot be removed or replaced.                |
|                          A list has data stored in [] brackets. For example, [1,2,3]                         |             A tuple has data stored in () brackets. For example, (1,2,3)            |

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

<br>

<a name="q2"></a>

### Question 2: How would you convert a list into a tuple?


```python
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.

<br>

<a name="q3"></a>

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

|                                                                         List                                                                         |                                                 Array                                                 |
|:----------------------------------------------------------------------------------------------------------------------------------------------------:|:-----------------------------------------------------------------------------------------------------:|
|                                              Python lists are very flexible and can hold arbitrary data.                                             |                           Python arrays are just a thin wrapper on C arrays.                          |
|                                    Lists are a part of Python’s syntax, so they do not need to be declared first.                                    |           Arrays need to first be imported, or declared, from other libraries (i.e. numpy).           |
| Lists can also be re-sized quickly in a time-efficient manner. This is because Python initializes some extra elements in the list at initialization. | Arrays cannot be resized. Instead, an array’s values would need to be copied to another larger array. |
|                                                          Lists can hold heterogeneous data.                                                          |            Arrays can only store homogenous data. They have values with uniform data types.           |
|              Mathematical functions cannot be directly applied to lists. Instead, they have to be individually applied to each element.              |                      Arrays are specially optimized for arithmetic computations.                      |
|                     Lists consume more memory as they are allocated a few extra elements to allow for quicker appending of items.                    |     Since arrays stay the size that they were when they were first initialized, they are compact.     |

<br>

<a name="q4"></a>

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

```python
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]
<type 'numpy.ndarray'>

<br>

<a name="q5"></a>

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

<br>

<a name="q6"></a>

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

<br>

<a name="q7"></a>

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

<br>

<a name="q8"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5qu5s4stgicr2sbh5lpk.png)

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

<br>

<a name="q9"></a>

### 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](https://www.educative.io/courses/grokking-the-coding-interview) </b>


<a name="q10"></a>

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

<br>

<a name="q11"></a>

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

<br>

<a name="q12"></a>

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

<br>

<a name="q13"></a>

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

<br>

<a name="q14"></a>

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

<br>

<a name="q15"></a>

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

<br>

<a name="q16"></a>

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

<br>

<a name="q17"></a>

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

<br>

<a name="q18"></a>

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

<br>

<a name="q19"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/a5qmez2ldcx9nkjmjezf.png)

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

```python
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**

```python
# 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`.

<br>

<a name="q20"></a>

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

<br>

<a name="q21"></a>

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

<br>

<a name="q22"></a>

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

<br>

<a name="q23"></a>

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

|                                                                       Python 2                                                                       |                                                                 Python 3                                                                 |
|:----------------------------------------------------------------------------------------------------------------------------------------------------:|:----------------------------------------------------------------------------------------------------------------------------------------:|
|      **String Encoding** <br> Python 2 stores them as ASCII. Unicode is a superset of ASCII and hence, can encode more characters including foreign ones.    |                                      **String Encoding** <br> Python 3 stores strings as Unicode by default.                                     |
| **Division** <br> Python 2 division applies the floor function to the decimal output and returns an integer. So dividing 5 by 2 would return floor(2.5) = 2. |                          **Division** <br> Division in Python 3 returns the expected output, even if it is in decimals.                          |
|                                                   **Printing** <br> Python 2 does not require parentheses.                                                   | **Printing** <br> The syntax for the print statement is different in Python 2 and 3. Python 3 requires parentheses around what is to be printed. |
|                        **Libraries** <br> Many older libraries were built specifically for Python 2 and are not “forward compatible.”                        |                    **Libraries** <br>  Some newer libraries are built specifically for Python 3 and do not work with Python 2.                    |

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.

<br>

<a name="q24"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/32yweq3hgu4g506uq8il.png)

**Example: Connecting elements using an empty string**

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

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

**Output:**
HELLO

<br>

<a name="q25"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/le17d8k78uuila68r4va.png)

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

```python
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'}

<br>

<a name="q26"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/h7c92olye054mi960txm.png)

```python
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]

<br>

<a name="q27"></a>

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

```python
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.


```python
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 

<br>

<a name="q28"></a>

### Question 28: How would you achieve memoization in Python?

Consider this computationally expensive code:

```python
# 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.

```python
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

<br>

<a name="q29"></a>

### 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()`**
```python
dict = {}
dict['1'] = 'apple'
dict['3'] = 'orange'
dict['2'] = 'pango'

lst = dict.keys()

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

**`values()`**

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

lst = dict.values()

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


**`items()`**

```python
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]))
```


<br>

<a name="q30"></a>

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

```python
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.

<br>

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

```python
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.

<br>

<a name="q31"></a>

### 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**

```python
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.

<br>

<a name="q33"></a>

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/p65500haomy1bu3s2nd9.png)

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

|                            Generator                            |                     Iterator                     |
|:---------------------------------------------------------------:|:------------------------------------------------:|
|                  Implemented using a function.                  |            Implemented using a class.            |
|                     Uses the `yield` keyword.                     |          Does not use 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**

```python
# 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**

```python 
# 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

<br>

<a name="q34"></a>

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

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

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

```python 
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

<br>

<a name="q35"></a>

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

___

<br>

## Python Interview Questions - Coding <a name="coding"></a>

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.

<br>

<a name="q36"></a>

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

```python
stringname[stringlength::-1] # method 1 
```
Or write without specifying the length of the string:

```python
stringname[::-1] # method2
```
The slice statement means start at string length, end at position 0, move with the step -1 (or one step backward).

```python
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.

<br>

<a name="q37"></a>

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

```python
string.find(substring)
```


```python
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.

<br>

<a name="q38"></a>

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

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/pz6mw76uzaer6oveabg0.png)

```python
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.

<br>

<a name="q39"></a>

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

Consider this graph, implemented in the code below:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/15humjemvadje2johj45.png)

```python
# 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](https://www.educative.io/courses/grokking-the-coding-interview) 
> 

<a name="q40"></a>

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

```python
# 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

<br>

<a name="q41"></a>

### Question 41: Implement  merge sort in Python

Here is the code for merge sort in Python:


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

<br>

<a name="q42"></a>

### 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**

```python
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

<br>

<a name="q43"></a>

### Question 43: Merge two sorted lists

```python
# 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.

<br>

<a name="q44"></a>

### Question 44: Find two  numbers that add up to 'k'

```python
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 {% katex %}a_{0}{% endkatex %} we will do a binary search for {% katex %}a_{0}{% endkatex %} 

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.

<br>

<a name="q45"></a>

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

```python
[9,2,3,2,6,6]
```

```python
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).

<br>

<a name="q46"></a>

### Question 46: Find the middle value of the linked list

To see the code solution in action, go to the [original post](https://www.educative.io/blog/python-interview-questions#q46). 

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

<br>

<a name="q47"></a>

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

To see the code solution in action, go to the [original post](https://www.educative.io/blog/python-interview-questions#q47)

**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

<br>

<a name="q48"></a>

### 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](https://www.educative.io/blog/python-interview-questions#q48).

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

<br>

<a name="q49"></a>

### Question 49: Convert max heap to min heap

Here we'll Min Heapify all Parent Nodes.

```python 
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 {% katex %}\frac{n}{2}{% endkatex %} nodes so this solution takes O(nlog(n)) time.

<br>

<a name="q50"></a>

### Question 50: Detect loop in a linked list

To see the code solution in action, visit the [original post](https://www.educative.io/blog/python-interview-questions#q50).

**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 {% katex %}O(n^{2}){% endkatex %}

<br>

## 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](https://www.educative.io/courses/grokking-the-coding-interview) 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!

<br>


**Additional resources**
* [Python Concurrency: Making sense of asyncio](https://www.educative.io/blog/python-concurrency-making-sense-of-asyncio)
* [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher)
* [Python Concurrency for  Senior  Engineering Interviews](https://www.educative.io/courses/python-concurrency-for-senior-engineering-interviews)
* [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python)
* [CodingInterview.com](https://www.codinginterview.com/)