We use cookies to ensure you get the best experience on our website. Please review our Privacy Policy to learn more.
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 what we’ll cover today:
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.
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)
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.
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. |
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)
In Python, the term monkey patch only refers to dynamic modifications of a class or module at run-time.
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.
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.
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
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:
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.
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.
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.
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.
PEP stands for Python Enhancement Proposal. It is a set of rules that specify how to format Python code for maximum readability.
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.
__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.
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:
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)
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
.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.
@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.
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.
Python 2 | Python 3 |
---|---|
String Encoding Python 2 stores them as ASCII. Unicode is a superset of ASCII and hence, can encode more characters including foreign ones. |
String Encoding Python 3 stores strings as Unicode by default. |
Division 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 Division in Python 3 returns the expected output, even if it is in decimals. |
Printing Python 2 does not require parentheses. |
Printing The syntax for the print statement is different in Python 2 and 3. Python 3 requires parentheses around what is to be printed. |
Libraries Many older libraries were built specifically for Python 2 and are not “forward compatible.” |
Libraries 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.
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)
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:
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)
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.
shallow copy
deep copy
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
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"
if-in
statementThis 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"
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))
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 lengt 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.
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))
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 ofor
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))
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 ofand
conditions.
The Python docstrings provide a suitable way of associating documentation with:
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 objecthelp
functionExample
def hello_world(): """Demonstrating docstring.""" return None # printing using __doc__ method print "Using __doc__ method:" print hello_world.__doc__ # printing using help function print "Using help function:" help(hello_world)
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
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.
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:
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
# 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)
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)
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])
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
orlist
as the parameters
A Python module is a Python file containing a set of functions and variables to be used in an application. The variables can be of any type (arrays, dictionaries, objects, etc.)
Modules can be either:
Built in
User-defined
Benefits of modules in Python
There are a couple of key benefits of creating and using a module in Python:
Structured Code
Reusability
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.
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
This is just one method to reverse a string in Python. Other two notable methods are Loop and Use Join.
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))
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')
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:
visited
list and the queue
.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.
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')
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:
visited
set.dfs
function is invoked again.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.
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)
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)
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:
The list is divided into left
and right
in each recursive call until two adjacent elements are obtained.
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.
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.
This way, the values being assigned through k
are all sorted.
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.
Basic algorithm
For more on Python algorithms for coding interviews, check out our article Master Algorithms with Python for Coding Interviews
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
# 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]))
The solution above is a more intuitive way to solve this problem.
Start by creating a new empty list. This list will be filled with all the elements of both lists in sorted order and returned.
Then initialize three variables to zero to store the current index of each list.
Then compare the elements of the two given lists at the current index of each, append the smaller one to the new list and increment the index of that list by 1.
Repeat until the end of one of the lists is reached and append the other list to the merged list.
Time Complexity The time complexity for this algorithm is O(n+m)O(n+m) where nn and mm are the lengths of the lists. This is because both lists are iterated over at least once.
Note that this problem can also be solved by merging in place.
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))
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 $a_{0}$, then we will do a binary search for k-$a_{0}$ . The search is repeated for every $a_{i}$ up to $a_{n}$ 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.
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]))
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).
from Node import Node class LinkedList: def __init__(self): self.head_node = None def get_head(self): return self.head_node def is_empty(self): if(self.head_node is None): # Check whether the head is None return True else: return False def insert_at_head(self, dt): temp_node = Node(dt) temp_node.next_element = self.head_node self.head_node = temp_node return self.head_node def print_list(self): if(self.is_empty()): print("List is Empty") return False temp = self.head_node while temp.next_element is not None: print(temp.data, end=" -> ") temp = temp.next_element print(temp.data, "-> None") return True def length(self): # start from the first element curr = self.get_head() length = 0 # Traverse the list and count the number of nodes while curr is not None: length += 1 curr = curr.next_element return length
Here you can use two pointers which will work simultaneously.
Think of it this way:
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).
from Queue import myQueue from Stack import myStack # 1.Push first k elements in queue in a stack. # 2.Pop Stack elements and enqueue them at the end of queue # 3.Dequeue queue elements till "k" and append them at the end of queue def reverseK(queue, k): if queue.isEmpty() is True or k > queue.size() or k < 0: # Handling invalid input return None stack = myStack() for i in range(k): stack.push(queue.dequeue()) while stack.isEmpty() is False: queue.enqueue(stack.pop()) size = queue.size() for i in range(size - k): queue.enqueue(queue.dequeue()) return queue # testing our logic queue = myQueue() queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) queue.enqueue(6) queue.enqueue(7) queue.enqueue(8) queue.enqueue(9) queue.enqueue(10) print("the queue before reversing:") print(queue.queueList) reverseK(queue, 10) print("the queue after reversing:") print(queue.queueList)
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:
myStack()
push(int)
to add elements to the stack.pop()
to remove or pop the top element from the stack.isEmpty()
returns true if the stack is empty and false otherwise.back()
returns the element that has been added at the end without removing it from the stack.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:
myQueue(size)
size should be an integer specifying the size of the queue.enqueue(int)
dequeue()
isEmpty()
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
Here you can use recursion to find the heights of the left and right sub-trees.
class Node: def __init__(self, val): self.val = val self.leftChild = None self.rightChild = None def insert(self, val): if val < self.val: if self.leftChild: self.leftChild.insert(val) else: self.leftChild = Node(val) return else: if self.rightChild: self.rightChild.insert(val) else: self.rightChild = Node(val) return def search(self, val): if val < self.val: if self.leftChild: return self.leftChild.search(val) else: return False elif val > self.val: if self.rightChild: return self.rightChild.search(val) else: return False else: return True return False def delete(self, val): if val < self.val: if(self.leftChild): self.leftChild = self.leftChild.delete(val) else: print(str(val) + " not found in the tree") return self elif val > self.val: if(self.rightChild): self.rightChild = self.rightChild.delete(val) else: print(str(val) + " not found in the tree") return self else: # deleting node with no children if self.leftChild is None and self.rightChild is None: self = None return None # deleting node with right child elif self.leftChild is None: tmp = self.rightChild self = None return tmp # deleting node with left child elif self.rightChild is None: tmp = self.leftChild self = None return tmp # deleting node with two children else: # first get the inorder successor current = self.rightChild # loop down to find the leftmost leaf while(current.leftChild is not None): current = current.leftChild self.val = current.val self.rightChild = self.rightChild.delete(current.val) return self
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.
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))
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 $\frac{n}{2}$
nodes so this solution takes O(nlog(n)) time.
from LinkedList import LinkedList from Node import Node def detect_loop(lst): # Used to store nodes which we already visited visited_nodes = set() current_node = lst.get_head() # Traverse the set and put each node in the visitedNodes set # and if a node appears twice in the map # then it means there is a loop in the set while current_node: if current_node in visited_nodes: return True visited_nodes.add(current_node) # Insert node in visitedNodes set current_node = current_node.next_element return False # ------------------------------ lst = LinkedList() lst.insert_at_head(21) lst.insert_at_head(14) lst.insert_at_head(7) print(detect_loop(lst)) head = lst.get_head() node = lst.get_head() # Adding a loop for i in range(4): if node.next_element is None: node.next_element = head.next_element break node = node.next_element print(detect_loop(lst))
Explanation
Iterate over the whole linked list and add each visited node to a visited_nodes
set. At every node, we check whether it has been visited or not.
By principle, if a node is revisited, a cycle exists!
Time Complexity
We iterate the list once. On average, lookup in a set takes O(1) time. Hence, the average runtime of this algorithm is O(n). However, in the worst case, lookup can increase up to O(n), which would cause the algorithm to work in $O(n^{2})$.
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!
A free, bi-monthly email with a roundup of Educative's top articles and coding tips.