Accreditation Bodies
Accreditation Bodies
Accreditation Bodies
Information technology, software or technical jobs have a series of technical interviews throughout the hiring process. Most companies pay major attention to technical algorithm interviews. If you want to be a deserving candidate, you must have a strong hold on concepts related to algorithms. This article contains the most commonly asked algorithm interview questions and answers, a few data structures and algorithms interview questions. It ends with some Java and programming algorithm questions as well. The interview question in beginner, intermediate and advanced sections contain python algorithm interviews for various levels and programming algorithm questions. The questions and answers provided would make you confident in the concepts of trees, linked lists, data structures and algorithms, sorting and searching algorithms and would make your job ready for most of the positions listed along with the companies who hire for following or similar positions as listed on different job posting platforms.
Filter By
Clear all
An algorithm is a set of rules to obtain the expected output from the given input. It defines a set of rules or steps specifying the calculations, data processing, and automated reasoning, which is reusable multiple times for either one or more than one problem statement. We can also say that an algorithm is a method for calculating a function that can be represented in a finite amount of space and time.
We need algorithms in programming during analysis or development as algorithms boost the effectiveness of some existing methods. Comparing an algorithm's performance to other approaches using time and space complexity concepts is easier. Using algorithms in our work or programs provides us with a detailed description of the criteria and goals of the problems, so we are moving forward in our project systematically. Algorithms bring well-defined outputs, finiteness to our program and an unambiguous approach toward the problem statement. Along with all these, the cost of design is also optimized and reduced many times if proper algorithms are used.
To compare two algorithms solving the same problem statement, we check the complexity of both algorithms, and the one with lesser complexity is the better among the two. Complexity is the technique used to categorize the efficiency of algorithms. We have two types of complexity; one is time complexity, and another one is space complexity.
The complexity of time checks the running time of a program as a function of the size of the input—the lesser time, the better the algorithm.
The complexity of space checks the algorithms on the basis of the space they are consuming on the computer storage to perform the task. The lesser the space used, the better the algorithm.
The best case and the worst case scenarios are the asymptotic analysis of an algorithm's performance analysis. The best-case scenario can be defined as the data arrangement or data situation in which the algorithm performs the best, and the worst-case scenario, on the other hand, is the situation or arrangement of the data in which the algorithm performs the worst. For example, the best-case scenario for a general binary search problem can be the time complexity of O(1), and the worst case can be O(n^2).
This is a frequently asked question in Algorithm interview questions.
Big O notation is an asymptotic notation to denote or define an upper bound for an algorithm by bounding the function from above. It represents the time and space complexity and is useful when we just have an upper constraint on an algorithm's time complexity.
Similar to the Big O notation, we have Big theta notation. It is also an asymptotic notation defining the exact asymptotic behavior. The theta notation binds the functions from above and below to define behavior. Dropping the low-order terms and ignoring leading constants is a convenient approach to getting the theta notation for a problem.
Sure,
Let the two numbers be a and b,
We need to use the XOR function or the bitwise function as in Java to swap these, and this can be done in three steps;
This way, the values of a and b are swapped using XOR without using the third variable.
Divide and conquer is an algorithm paradigm set up so that it can handle a large amount of data, split it into smaller chunks, and determine the solution to the problem for each smaller chunk of the data. The algorithm paradigm has three parts - Divide, Conquer and Combine. These can be defined as three steps in which the paradigm processes the input data,
A greedy algorithm is a method that aims to choose the best possible decision at each step, eventually resulting in a globally optimal solution. The greedy algorithm, in simple words, chooses the best option available at a time regardless of consequences. The main goal of this algorithm is to find the best optimal solution for the complete problem and not just the subproblems. The greedy algorithm is used in a bunch of algorithms to find the solution, and some of them can be listed as the Fractional Knapsack problem or Dijkstra's algorithm.
Sure, searching algorithms are used for searching for an element or an item from a data structure or a list of elements/items. There are 2 categories based on the type of search method, i.e., Sequential Search and Interval Search. Sequential search performs the search consecutively along the data. In contrast, Interval search performs the search by splitting the data set into two equal parts each time.
The linear search algorithm is used to search for an element in a list of elements. In linear search, the algorithm traverses the List of elements from the beginning to the end and inspects the properties of all the elements noticed along the way. The algorithm follows the following steps:
Expect to come across this popular question in DSA interview questions.
Depth-first search is a search algorithm mainly used in trees and graphs. As the name suggests, this algorithm first visits nodes in depth before searching along the same level. To explain the processing of the algorithm, I would say,
The algorithm starts at the root node and checks each branch as far as possible before backtracking to check the other branches. When a dead end occurs in any iteration, the algorithm traverses backward. For remembering the next vertex to start the search, it uses Stack. The output of the DFS algorithm is a spanning tree.
We use Stack to implement the DFS algorithm. Following are the steps to implement it.
Okay, so we need to add a node in the middle of a sorted linked list. I am assuming that the linked List is sorted in ascending order. Now, adding a node in the middle of this linked List sorted in ascending order can be done in the following steps;
Dynamic programming is basically a recursion optimization. We can use it to optimize any recursive solution which involves repeated calls for the same input.
In dynamic programming, the goal is to save the results of the subproblems, so we need not recalculate them. Using dynamic programming to solve a problem also reduces the time complexity making the algorithm more efficient.
Swapping two numbers without using the third number is a small 3-step algorithm. It can be done if we store the sum of numbers in one number and then subtract the sum from another. For example,
If a and b are two numbers as
a = 2 and b = 3
Then we can swap these two numbers getting the output as
a = 3 and b = 2
By following the steps,
We have a = 2 and b = 3,
Then the first step is to add the two numbers and store the value in variable a,
a = a + b ; this would give us a = 5
The second step is to subtract a and b and store the value in variable b,
b = a - b; which will be 5 - 2 = 3
The third or final step is to now subtract a and b and store the value in a,
a = a - b; giving us 5 - 3 = 2
In the end, we now have a = 2 and b = 3, as required.
The algorithm to reverse a string gives the output by reversing the input string. For example, let the input string be "details", then the output should be "selected". The pseudocode of the algorithm can be given as this:
A hash table, as per my knowledge, is a data structure for storing values to keys of arbitrary type. The hash table has an index into an array using the hash function. These indexes are used to store the elements in the hash table. We assign each possible element to the bucket using the hash function. We can assign multiple keys to a single bucket so that all the key-value pairs are stored in the form of lists within their buckets. In simple words, the hash table contains lists mapped to strings. For each word, we add to the List at a key, or we create a new list if needed and add the word to it. This is all I know about hash tables as of now.
A must-know for anyone heading into a DS interview, this question is frequently asked in Data structure questions.
Okay, so we can use the hash table to find all anagrams in a dictionary. For this, we have to group all the words containing the same set of letters. If we map the words to strings representing their sorted letters, we can group words into lists by using the sorted letters as the key.
The pseudocode for this would be:
FUNCTION find_anagrams(words)
word_group = HashTable<String, List> FOR word in words word_group.get_or_default(sort(word),[]).push(word) END FOR anagrams = List FOR key, value IN word_group anagrams.push(value) END FOR RETURN anagrams
It's no surprise that this one pops up often in Algorithm interview questions.
Inserting a node in the binary search tree is a small three-step process. The first step is to check if the node which we are inserting with the root node is smaller or greater than the root node.
Further steps of the algorithm would be:
Okay, so counting the leaf nodes in a binary tree is also a three-step process,
"No. of lead nodes = no. of leaf nodes in left subtree + no. of leaf nodes in right subtree"
Encryption means transforming readable text into a secret code format known as "Ciphertext". This technique of encrypting a text uses a string of bits known as "keys" to convert the text into a secret code. The larger the key, the more possibility of potential patterns for producing the ciphertext. Most of the algorithms use fixed blocks of input with lengths ranging from 64 to 128 bits, while others use the stream technique. The three popular cryptographic algorithms are -
A common question in Data structure interview questions for freshers, don't miss this one.
The merge sort algorithm is a comparison-based sorting algorithm. In the algorithm, the order of equal elements in the input and output is the same. The merge sort works in the following way;
The time complexity of the mergesort is O(nlog(n)), where n is the size of the input list, and the space complexity is linear, O(n).
Quicksort is also a sorting algorithm. It is quicker than the merge sort and heapsort sorting algorithms. The quick sort algorithm is based on the divide and conquer algorithmic paradigm and operates by picking a 'pivot' element from the input array and separating the other elements into two subarrays based on whether they are greater or less than the pivot. Because of this, it is also known as the partition exchange sort. Due to its recursive nature, Quicksort must be written in such a way that it can be called for a range within a bigger array, even if the end purpose is to sort the complete array.
The following are the steps in the quicksort sorting algorithm.
Bubble sort is again a sorting algorithm, also known as sinking sort. In bubble sort, the algorithm iterates through a list, comparing neighboring elements and swapping them if they are out of order. The List is then sent through the iterations multiple times until there are no swaps done and the input list is sorted. The bubble sort algorithm can be explained using an example.
Let us assume an array (7 5 12 3 4 9). The process of the bubble sort algorithm to sort this array in ascending order can be explained as follows.
First Pass:
Second Pass:
Third Pass:
At the end of the third pass, the input list is sorted in ascending order. This is all I know about the bubble sort.
To find the maximum subarray sum for a given array, we can use Kadane's algorithm. It searches the given array from left to right, computes the largest sum at position n in the nth step, and stores this sum in a variable. The algorithm further calculates the subarray sum and keeps storing the biggest sum in the variable. In the end, the value of the variable will be the desired maximum subarray sum.
The pseudo-code for this can be
Dijkstra's algorithm is used to find the shortest path between a given node in a graph to any other node in the graph. It is a five-step algorithm to calculate the distance between 2 nodes in a graph and might also be used to depict road networks.
No, we cannot use the binary search algorithm for linked lists. The reason for this is that in the linked List, random access is not allowed. We cannot reach the middle term or element of the linked list in constant or O(1) time. Thus, making the use of binary search algorithms on a linked list impossible.
One of the most frequently posed sorting interview questions, be ready for it.
A recursive algorithm approaches a difficult problem by breaking it down into smaller subproblems until the problem is small enough to be solved quickly. A recursive algorithm involves a function that calls itself, which is why the recursive name algorithm.
For an algorithm to be a recursive algorithm, there are three laws,
If these three rules are fulfilled by an algorithm, then it can be called a recursive algorithm.
Insertion sort is a sorting technique that separates the input list into sorted and unsorted sub-lists. After separating the input list into two, as mentioned, it inserts one element at a time on the proper spot in the sorted sub-list from the unsorted one. After each iteration, one new element is added to the sorted sub-list, and one is removed from the unsorted one. In the end, the required sorted List is the sorted sub-list.
Selection sort is a sorting technique that separates the data into sorted and unsorted sub-lists. Then, the minimum element, or the smallest element from the unsorted List, is selected and placed in the sorted sub-list. The loop works until all the elements from the unsorted sub-list are shifted to the sorted sub-list giving us the final sorted List.
The space complexity of both the insertion sort and selection sort is O(1). This is because both sorting methods do not require any additional or minimal data storage. Only a single list element must be sorted.
The definition I am getting in my mind is, "The tree traversal is the process of visiting all the nodes of a tree". A tree can be traversed in three ways as
Inorder Traversal algorithm, steps can be given as:
Preorder Traversal algorithm steps can be given as follows:
Postorder Traversal algorithm steps can be given as follows:
A staple in DSA interview questions, be prepared to answer this one.
Sure, Some of the algorithms using tree traversal which I can recall at this moment are:
This question is a regular feature in Algorithm interview questions, be ready to tackle it.
The algorithm to insert a node in a binary search tree can be explained in 3 steps.
This is the Binary search tree, as per my knowledge.
Okay, so the Heap sort is a comparison-based sorting algorithm similar to the selection sort. This algorithm separates its input into two regions: one as sorted and another one as unsorted as the first step. Then, it successively removes the items from the unsorted part by taking the largest element from it and putting it into the sorted region one by one.
The main advantage of the heap sort algorithm is that it does not waste time scanning the unsorted part back to back multiple times as done in the selection sort. Instead, heap sort keeps the unsorted region in a heap data structure to identify the largest element in each step more rapidly. The steps of the heap sort algorithm can be explained as follows:
And this is all about the heap sort algorithm.
A skip list is a method for data structuring where it allows the algorithm to search, insert or delete the elements in a symbol table or dictionary.
In a skip list, elements are represented by nodes. The search function returns the content of the value related to the key. We can insert a new value in a key using the "insert" function and delete one using "delete". This is all I understand about the skip list.
To know if a linked list has a loop, I would use a two-pointer approach. It is because if we maintain two pointers and increase one pointer after processing 2 nodes and another after processing every node, we will encounter a situation where both the pointers will be pointing to the same node. The only reason for this is that the linked List has a loop.
Okay. I think the best solution is to use a min heap for building a min heap of the first k elements. For each element after the kth element, we would compare it with the root of the min heap. If the element is greater, it will be the root. Otherwise, it will be ignored. At the end of the List, we will have the largest element at the root of the min heap as the kth largest element.
Okay, so we have two integers, x and n. I will be writing the program in python.
def power(x, n) pow = 1 for i in range(n) pow = pow * x return pow #driver code if __name__ == ‘__main__’: x = 7 n = 2 #Function call print(power(x, n))
We can find the missing number in such an array by monitoring the elements of the array. The code for this will be
def missing_no(arr, N) #list of zeroes temp = [0] * (N+1) for i in range(0, N): Temp[arr[i] - 1] = 1 for i in range(0, N+1): if(temp[i] == 0): and = i+1 print(ans) #driver code if __name__ = ‘__main__’: arr = [7, 8, 10, 11] N = len(arr) #function call misssing_no(arr, N)
Okay, so a postfix expression is made up of operators and operands. The operator comes after the operand. The correct postfix phrase is 23+, which means 2+3.
This is a frequently asked question in DS algo interview questions.
I would say that queue is a type of data structure or, should say, an abstract type of data structure that specifies a linear or an ordered list. A queue uses a First In, First Out (FIFO) operation or rule to access its elements. In a queue, insert operations can be performed only at one end, called REAR, and delete operations can be performed only at the other end, called FRONT.
Dequeue is a double-ended queue where the elements can be inserted or deleted at both ends, Front or Rear. All the other properties of a dequeue are similar to a queue, including the First In, First Out (FIFO) rule to access the elements.
Okay, first, heap and Stack are both used as a part of memory, mainly in Java. Some of the advantages of the heap over Stack are:
PUSH and POP are acronyms for operations Pushing and Popping on a Stack, respectively. These operations are the ways data is stored and retrieved from the Stack.
PUSH is used to add an element to a stack, and POP is used to remove an element from the Stack.
PUSH takes two arguments, the name of the Stack to add the data item to and the value of the entry to be added. POP only requires the name of the Stack.
When the Stack is filled, the PUSH command, when issued, gives a stack overflow error, which means that the Stack cannot accommodate any more elements. In POP, a stack underflow error is thrown if the Stack is empty.
I think a single algorithm cannot be considered best as each algorithm is designed in a way to solve a problem in a certain situation. However, I have found QuickSort to be the fastest, having the best performance for most problem statements or inputs for this case.
There are certain advantages of Quicksort over other sorting algorithms.
There are many applications of graph data structure. Some of which I am able to recall are:
Okay, as per my knowledge, we have
Sure.
Expect to come across this popular question in Data structure interview questions.
Dynamic memory stores simple structured data types at runtime. It has the ability to combine the allocated structured blocks separately to form composite structures that expand and contract as needed. This helps to manage the data of data blocks of arbitrary size in arbitrary order. This is how dynamic memory allocation helps in managing data.
Some operations which we can perform on the queue are:
These are the few functions we perform on queues that I can recall right now.
A must-know for anyone heading into an Algorithm interview, this question is frequently asked in Algorithm interview questions.
Okay. For this, we first require two linked lists.
For example, if the first List is 2→4→6 and the second is 1→5→7→9→11, the first List should become 2→1→4→5→6→7 and the second List should become empty.
This is what we are aiming to achieve with the program. All the nodes of the second List should only be inserted when there are positions available.
Okay, so to do this, we would run a loop while there are available positions in the first loop. Then, we would insert nodes of the second List by changing the pointers. The code for this can be given as
Code:
class Node(object): def __init__(self, data:int): self.data = data self.next = None class LinkedList(object): def __init__(self): self.head = None def push(self, new_data:int): new_node = Node(new_data) new_node.next = self.head # Moving the head to point the new node # new node self.head = new_node # Function to print linked List from head def printList(self): temp = self.head while temp != None: print(temp.data) temp = temp.next # Main function that inserts nodes of linked List an into b at # alternate positions. Since head of first List never changes # but head of second List might change, we need single # pointer for first List and double pointer for second List. def merge(self, a, b): a_curr = a.head b_curr = b.head # swap their positions until one is empty while a_curr != None and b_curr != None: # Save next pointers a_next = a_curr.next b_next = b_curr.next # make b_curr as next of a_curr change next pointer # of b_curr b_curr.next = a_next # change next pointer of a_curr a_curr.next = b_curr # update current pointers for next iteration a_curr = a_next b_curr = b_next b.head = b_curr # Driver code list1 = LinkedList() list2 = LinkedList() # Creating the Linked lists # 1. list1.push(6) list1.push(4) list1.push(2) # 2. for i in range(1, 5, 7, 9, 11): list2.push(i) print("First Linked List:") list1.printList() print("Second Linked List:") list2.printList() # Merging the linked lists list1.merge(a = list1, b = list2) print("Modified first linked list:") list1.printList() print("Modified second linked list:") list2.printList()
Output :
First Linked List: 2 4 6; Second Linked List: 1 5 7 9 11; Modified First Linked List:2 1 4 5 6 7; Modified Second Linked List: 9 11
The code to implement the bubble sort algorithm will have 3 steps
Code:
def bubbleSort(arr): n = len(arr) # optimize code, so if the array is already sorted, it # doesn't need to go through the entire process swapped = False # Traverse through all array elements for i in range(n-1): # range(n) also work but outer loop will # repeat one time more than needed. # Last i elements are already in place for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] if not swapped: # if we haven't needed to make a single swap, we # can just exit the main loop. return # Driver code to test above arr = [74, 24, 35, 12, 32, 11, 90] bubbleSort(arr) print("Sorted array is:") for i in range(len(arr)): print("% d" % arr[i], end=" ")
Output:
Sorted array is: 11 12 24 32 35 74 90
Okay. In insertion sort, we assume that the first element in the array is to be sorted. The second element is stored separately in the key. This sorts the first two elements. We can then take the third element and make a comparison with the ones on its left. This process will go on until a point where we sort the array.
Code:
def insertionSort(arr): if (n := len(arr)) <= 1: return for i in range(1, n): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j >=0 and key < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key #sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)
Okay. Inheritance is the procedure in which one class inherits the attributes and methods of another class. The class that inherits the properties of another class is called the child class, and the class whose properties are being inherited is called the parent class. Another interesting thing about inheritance is that the child class can have its own properties and methods along with the ones inherited from the parent class.
Code:
class Person(object): # Constructor def __init__(self, name, id): self.name = name self.id = id # To check if this person is an employee def Display(self): print(self.name, self.id) class Child(Parent): # Constructor def __init__(self): self.value = "Inside Child" # Child's show method def show(self): print(self.value) # Driver code emp = Person("Satyam", 102) # An Object of Person emp.Display()
It's no surprise that this one pops up often in DSA interview questions.
Okay, So overloading is when a class has 2 or more methods with the same name. Then they are called overloaded methods.
Code:
def product(a, b): p = a * b print(p) # Second product method takes three argument and print their # product def product(a, b, c): p = a * b*c print(p) # Uncommenting the below line shows an error product(4, 5) # This line will call the second product method product(4, 5, 5) Overriding is when a superclass method is also implemented in the child class.
Code:
class Parent(): # Constructor def __init__(self): self.value = "Inside Parent" # Parent's show method def show(self): print(self.value) # Defining child class class Child(Parent): # Constructor def __init__(self): self.value = "Inside Child" # Child's show method def show(self): print(self.value) # Driver's code obj1 = Parent() obj2 = Child() obj1.show() obj2.show()
The method I would follow to write the program is that first find the reverse of the input string and then compare the two; if they are the same, then it is a palindrome; otherwise, not.
Code:
def isPalindrome(s): return s == s[::-1] # Driver code s = "malayalam" ans = isPalindrome(s) if ans: print("Yes") else: print("No")
For removing all occurrences of a given character from the input string, I would use the built-in string method "replace" to replace the character with another, including symbols and spaces.
Code:
# initializing string test_str = "CheeseoverCheese" # initializing removal character rem_char = "e" # printing original string print(" The original string is: " + str(test_str)) # Using translate() # Deleting all occurrences of character res = test_str.translate(None, rem_char) # printing result print(" quote The string after character deletion: " + str(res))
Output:
The original string is : CheeseoverCheese The string after character deletion : ChsovrChs
Okay, so to find the middle element of a linked list, I would first traverse the linked List using 2 pointers. Then, move one pointer by one and another by two. When the fast pointer reaches the end, the slow one will reach the middle.
Code:
class Node: # Function to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Function to get the middle of # the linked List def printMiddle(self): slow_ptr = self.head fast_ptr = self.head if self.head is not None: while(fast_ptr is not None and fast_ptr.next is not None): fast_ptr = fast_ptr.next.next slow_ptr = slow_ptr.next print("The middle element is: ", slow_ptr.data) # Driver code list1 = LinkedList() list1.push(5) list1.push(4) list1.push(2) list1.push(3) list1.push(1) list1.printMiddle()
Output:
The middle element is: 2
A common question in DS interview questions, don't miss this one.
This problem statement of deleting a node in the linked List can be solved using
The iterative method is as follows:
To delete a node from the linked List, we need to follow three steps;
The code for solving this problem can be:
Code:
Class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None # Insert new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Given a reference to the head of a list and a key, # delete the first occurrence of key in linked List def deleteNode(self, key): # head node temp = self.head # If head node is the last node if (temp is not None): if (temp.data == key): self.head = temp.next temp = None return # If there are more nodes after the head node # Search for the key to be deleted, keep track of the # previous node as we need to change 'prev.next' while(temp is not None): if temp.data == key: break prev = temp temp = temp.next # if key was not present in linked List if(temp == None): return # Unlink the node from linked List prev.next = temp.next temp = None # print the Linked List def printList(self): temp = self.head while(temp): print (" %d" %(temp.data)), temp = temp.next # Driver program list = LinkedList() list.push(9) list.push(1) list.push(4) list.push(6) print ("Created Linked List: ") list.printList() list.deleteNode(1) print (" Linked List after Deletion of 1:") list.printList()
Output:
Created Linked List: 6 4 1 9; Linked List after deleting the node with value as 1: 6 4 9
An algorithm is a set of rules to obtain the expected output from the given input. It defines a set of rules or steps specifying the calculations, data processing, and automated reasoning, which is reusable multiple times for either one or more than one problem statement. We can also say that an algorithm is a method for calculating a function that can be represented in a finite amount of space and time.
We need algorithms in programming during analysis or development as algorithms boost the effectiveness of some existing methods. Comparing an algorithm's performance to other approaches using time and space complexity concepts is easier. Using algorithms in our work or programs provides us with a detailed description of the criteria and goals of the problems, so we are moving forward in our project systematically. Algorithms bring well-defined outputs, finiteness to our program and an unambiguous approach toward the problem statement. Along with all these, the cost of design is also optimized and reduced many times if proper algorithms are used.
To compare two algorithms solving the same problem statement, we check the complexity of both algorithms, and the one with lesser complexity is the better among the two. Complexity is the technique used to categorize the efficiency of algorithms. We have two types of complexity; one is time complexity, and another one is space complexity.
The complexity of time checks the running time of a program as a function of the size of the input—the lesser time, the better the algorithm.
The complexity of space checks the algorithms on the basis of the space they are consuming on the computer storage to perform the task. The lesser the space used, the better the algorithm.
The best case and the worst case scenarios are the asymptotic analysis of an algorithm's performance analysis. The best-case scenario can be defined as the data arrangement or data situation in which the algorithm performs the best, and the worst-case scenario, on the other hand, is the situation or arrangement of the data in which the algorithm performs the worst. For example, the best-case scenario for a general binary search problem can be the time complexity of O(1), and the worst case can be O(n^2).
This is a frequently asked question in Algorithm interview questions.
Big O notation is an asymptotic notation to denote or define an upper bound for an algorithm by bounding the function from above. It represents the time and space complexity and is useful when we just have an upper constraint on an algorithm's time complexity.
Similar to the Big O notation, we have Big theta notation. It is also an asymptotic notation defining the exact asymptotic behavior. The theta notation binds the functions from above and below to define behavior. Dropping the low-order terms and ignoring leading constants is a convenient approach to getting the theta notation for a problem.
Sure,
Let the two numbers be a and b,
We need to use the XOR function or the bitwise function as in Java to swap these, and this can be done in three steps;
This way, the values of a and b are swapped using XOR without using the third variable.
Divide and conquer is an algorithm paradigm set up so that it can handle a large amount of data, split it into smaller chunks, and determine the solution to the problem for each smaller chunk of the data. The algorithm paradigm has three parts - Divide, Conquer and Combine. These can be defined as three steps in which the paradigm processes the input data,
A greedy algorithm is a method that aims to choose the best possible decision at each step, eventually resulting in a globally optimal solution. The greedy algorithm, in simple words, chooses the best option available at a time regardless of consequences. The main goal of this algorithm is to find the best optimal solution for the complete problem and not just the subproblems. The greedy algorithm is used in a bunch of algorithms to find the solution, and some of them can be listed as the Fractional Knapsack problem or Dijkstra's algorithm.
Sure, searching algorithms are used for searching for an element or an item from a data structure or a list of elements/items. There are 2 categories based on the type of search method, i.e., Sequential Search and Interval Search. Sequential search performs the search consecutively along the data. In contrast, Interval search performs the search by splitting the data set into two equal parts each time.
The linear search algorithm is used to search for an element in a list of elements. In linear search, the algorithm traverses the List of elements from the beginning to the end and inspects the properties of all the elements noticed along the way. The algorithm follows the following steps:
Expect to come across this popular question in DSA interview questions.
Depth-first search is a search algorithm mainly used in trees and graphs. As the name suggests, this algorithm first visits nodes in depth before searching along the same level. To explain the processing of the algorithm, I would say,
The algorithm starts at the root node and checks each branch as far as possible before backtracking to check the other branches. When a dead end occurs in any iteration, the algorithm traverses backward. For remembering the next vertex to start the search, it uses Stack. The output of the DFS algorithm is a spanning tree.
We use Stack to implement the DFS algorithm. Following are the steps to implement it.
Okay, so we need to add a node in the middle of a sorted linked list. I am assuming that the linked List is sorted in ascending order. Now, adding a node in the middle of this linked List sorted in ascending order can be done in the following steps;
Dynamic programming is basically a recursion optimization. We can use it to optimize any recursive solution which involves repeated calls for the same input.
In dynamic programming, the goal is to save the results of the subproblems, so we need not recalculate them. Using dynamic programming to solve a problem also reduces the time complexity making the algorithm more efficient.
Swapping two numbers without using the third number is a small 3-step algorithm. It can be done if we store the sum of numbers in one number and then subtract the sum from another. For example,
If a and b are two numbers as
a = 2 and b = 3
Then we can swap these two numbers getting the output as
a = 3 and b = 2
By following the steps,
We have a = 2 and b = 3,
Then the first step is to add the two numbers and store the value in variable a,
a = a + b ; this would give us a = 5
The second step is to subtract a and b and store the value in variable b,
b = a - b; which will be 5 - 2 = 3
The third or final step is to now subtract a and b and store the value in a,
a = a - b; giving us 5 - 3 = 2
In the end, we now have a = 2 and b = 3, as required.
The algorithm to reverse a string gives the output by reversing the input string. For example, let the input string be "details", then the output should be "selected". The pseudocode of the algorithm can be given as this:
A hash table, as per my knowledge, is a data structure for storing values to keys of arbitrary type. The hash table has an index into an array using the hash function. These indexes are used to store the elements in the hash table. We assign each possible element to the bucket using the hash function. We can assign multiple keys to a single bucket so that all the key-value pairs are stored in the form of lists within their buckets. In simple words, the hash table contains lists mapped to strings. For each word, we add to the List at a key, or we create a new list if needed and add the word to it. This is all I know about hash tables as of now.
A must-know for anyone heading into a DS interview, this question is frequently asked in Data structure questions.
Okay, so we can use the hash table to find all anagrams in a dictionary. For this, we have to group all the words containing the same set of letters. If we map the words to strings representing their sorted letters, we can group words into lists by using the sorted letters as the key.
The pseudocode for this would be:
FUNCTION find_anagrams(words)
word_group = HashTable<String, List> FOR word in words word_group.get_or_default(sort(word),[]).push(word) END FOR anagrams = List FOR key, value IN word_group anagrams.push(value) END FOR RETURN anagrams
It's no surprise that this one pops up often in Algorithm interview questions.
Inserting a node in the binary search tree is a small three-step process. The first step is to check if the node which we are inserting with the root node is smaller or greater than the root node.
Further steps of the algorithm would be:
Okay, so counting the leaf nodes in a binary tree is also a three-step process,
"No. of lead nodes = no. of leaf nodes in left subtree + no. of leaf nodes in right subtree"
Encryption means transforming readable text into a secret code format known as "Ciphertext". This technique of encrypting a text uses a string of bits known as "keys" to convert the text into a secret code. The larger the key, the more possibility of potential patterns for producing the ciphertext. Most of the algorithms use fixed blocks of input with lengths ranging from 64 to 128 bits, while others use the stream technique. The three popular cryptographic algorithms are -
A common question in Data structure interview questions for freshers, don't miss this one.
The merge sort algorithm is a comparison-based sorting algorithm. In the algorithm, the order of equal elements in the input and output is the same. The merge sort works in the following way;
The time complexity of the mergesort is O(nlog(n)), where n is the size of the input list, and the space complexity is linear, O(n).
Quicksort is also a sorting algorithm. It is quicker than the merge sort and heapsort sorting algorithms. The quick sort algorithm is based on the divide and conquer algorithmic paradigm and operates by picking a 'pivot' element from the input array and separating the other elements into two subarrays based on whether they are greater or less than the pivot. Because of this, it is also known as the partition exchange sort. Due to its recursive nature, Quicksort must be written in such a way that it can be called for a range within a bigger array, even if the end purpose is to sort the complete array.
The following are the steps in the quicksort sorting algorithm.
Bubble sort is again a sorting algorithm, also known as sinking sort. In bubble sort, the algorithm iterates through a list, comparing neighboring elements and swapping them if they are out of order. The List is then sent through the iterations multiple times until there are no swaps done and the input list is sorted. The bubble sort algorithm can be explained using an example.
Let us assume an array (7 5 12 3 4 9). The process of the bubble sort algorithm to sort this array in ascending order can be explained as follows.
First Pass:
Second Pass:
Third Pass:
At the end of the third pass, the input list is sorted in ascending order. This is all I know about the bubble sort.
To find the maximum subarray sum for a given array, we can use Kadane's algorithm. It searches the given array from left to right, computes the largest sum at position n in the nth step, and stores this sum in a variable. The algorithm further calculates the subarray sum and keeps storing the biggest sum in the variable. In the end, the value of the variable will be the desired maximum subarray sum.
The pseudo-code for this can be
Dijkstra's algorithm is used to find the shortest path between a given node in a graph to any other node in the graph. It is a five-step algorithm to calculate the distance between 2 nodes in a graph and might also be used to depict road networks.
No, we cannot use the binary search algorithm for linked lists. The reason for this is that in the linked List, random access is not allowed. We cannot reach the middle term or element of the linked list in constant or O(1) time. Thus, making the use of binary search algorithms on a linked list impossible.
One of the most frequently posed sorting interview questions, be ready for it.
A recursive algorithm approaches a difficult problem by breaking it down into smaller subproblems until the problem is small enough to be solved quickly. A recursive algorithm involves a function that calls itself, which is why the recursive name algorithm.
For an algorithm to be a recursive algorithm, there are three laws,
If these three rules are fulfilled by an algorithm, then it can be called a recursive algorithm.
Insertion sort is a sorting technique that separates the input list into sorted and unsorted sub-lists. After separating the input list into two, as mentioned, it inserts one element at a time on the proper spot in the sorted sub-list from the unsorted one. After each iteration, one new element is added to the sorted sub-list, and one is removed from the unsorted one. In the end, the required sorted List is the sorted sub-list.
Selection sort is a sorting technique that separates the data into sorted and unsorted sub-lists. Then, the minimum element, or the smallest element from the unsorted List, is selected and placed in the sorted sub-list. The loop works until all the elements from the unsorted sub-list are shifted to the sorted sub-list giving us the final sorted List.
The space complexity of both the insertion sort and selection sort is O(1). This is because both sorting methods do not require any additional or minimal data storage. Only a single list element must be sorted.
The definition I am getting in my mind is, "The tree traversal is the process of visiting all the nodes of a tree". A tree can be traversed in three ways as
Inorder Traversal algorithm, steps can be given as:
Preorder Traversal algorithm steps can be given as follows:
Postorder Traversal algorithm steps can be given as follows:
A staple in DSA interview questions, be prepared to answer this one.
Sure, Some of the algorithms using tree traversal which I can recall at this moment are:
This question is a regular feature in Algorithm interview questions, be ready to tackle it.
The algorithm to insert a node in a binary search tree can be explained in 3 steps.
This is the Binary search tree, as per my knowledge.
Okay, so the Heap sort is a comparison-based sorting algorithm similar to the selection sort. This algorithm separates its input into two regions: one as sorted and another one as unsorted as the first step. Then, it successively removes the items from the unsorted part by taking the largest element from it and putting it into the sorted region one by one.
The main advantage of the heap sort algorithm is that it does not waste time scanning the unsorted part back to back multiple times as done in the selection sort. Instead, heap sort keeps the unsorted region in a heap data structure to identify the largest element in each step more rapidly. The steps of the heap sort algorithm can be explained as follows:
And this is all about the heap sort algorithm.
A skip list is a method for data structuring where it allows the algorithm to search, insert or delete the elements in a symbol table or dictionary.
In a skip list, elements are represented by nodes. The search function returns the content of the value related to the key. We can insert a new value in a key using the "insert" function and delete one using "delete". This is all I understand about the skip list.
To know if a linked list has a loop, I would use a two-pointer approach. It is because if we maintain two pointers and increase one pointer after processing 2 nodes and another after processing every node, we will encounter a situation where both the pointers will be pointing to the same node. The only reason for this is that the linked List has a loop.
Okay. I think the best solution is to use a min heap for building a min heap of the first k elements. For each element after the kth element, we would compare it with the root of the min heap. If the element is greater, it will be the root. Otherwise, it will be ignored. At the end of the List, we will have the largest element at the root of the min heap as the kth largest element.
Okay, so we have two integers, x and n. I will be writing the program in python.
def power(x, n) pow = 1 for i in range(n) pow = pow * x return pow #driver code if __name__ == ‘__main__’: x = 7 n = 2 #Function call print(power(x, n))
We can find the missing number in such an array by monitoring the elements of the array. The code for this will be
def missing_no(arr, N) #list of zeroes temp = [0] * (N+1) for i in range(0, N): Temp[arr[i] - 1] = 1 for i in range(0, N+1): if(temp[i] == 0): and = i+1 print(ans) #driver code if __name__ = ‘__main__’: arr = [7, 8, 10, 11] N = len(arr) #function call misssing_no(arr, N)
Okay, so a postfix expression is made up of operators and operands. The operator comes after the operand. The correct postfix phrase is 23+, which means 2+3.
This is a frequently asked question in DS algo interview questions.
I would say that queue is a type of data structure or, should say, an abstract type of data structure that specifies a linear or an ordered list. A queue uses a First In, First Out (FIFO) operation or rule to access its elements. In a queue, insert operations can be performed only at one end, called REAR, and delete operations can be performed only at the other end, called FRONT.
Dequeue is a double-ended queue where the elements can be inserted or deleted at both ends, Front or Rear. All the other properties of a dequeue are similar to a queue, including the First In, First Out (FIFO) rule to access the elements.
Okay, first, heap and Stack are both used as a part of memory, mainly in Java. Some of the advantages of the heap over Stack are:
PUSH and POP are acronyms for operations Pushing and Popping on a Stack, respectively. These operations are the ways data is stored and retrieved from the Stack.
PUSH is used to add an element to a stack, and POP is used to remove an element from the Stack.
PUSH takes two arguments, the name of the Stack to add the data item to and the value of the entry to be added. POP only requires the name of the Stack.
When the Stack is filled, the PUSH command, when issued, gives a stack overflow error, which means that the Stack cannot accommodate any more elements. In POP, a stack underflow error is thrown if the Stack is empty.
I think a single algorithm cannot be considered best as each algorithm is designed in a way to solve a problem in a certain situation. However, I have found QuickSort to be the fastest, having the best performance for most problem statements or inputs for this case.
There are certain advantages of Quicksort over other sorting algorithms.
There are many applications of graph data structure. Some of which I am able to recall are:
Okay, as per my knowledge, we have
Sure.
Expect to come across this popular question in Data structure interview questions.
Dynamic memory stores simple structured data types at runtime. It has the ability to combine the allocated structured blocks separately to form composite structures that expand and contract as needed. This helps to manage the data of data blocks of arbitrary size in arbitrary order. This is how dynamic memory allocation helps in managing data.
Some operations which we can perform on the queue are:
These are the few functions we perform on queues that I can recall right now.
A must-know for anyone heading into an Algorithm interview, this question is frequently asked in Algorithm interview questions.
Okay. For this, we first require two linked lists.
For example, if the first List is 2→4→6 and the second is 1→5→7→9→11, the first List should become 2→1→4→5→6→7 and the second List should become empty.
This is what we are aiming to achieve with the program. All the nodes of the second List should only be inserted when there are positions available.
Okay, so to do this, we would run a loop while there are available positions in the first loop. Then, we would insert nodes of the second List by changing the pointers. The code for this can be given as
Code:
class Node(object): def __init__(self, data:int): self.data = data self.next = None class LinkedList(object): def __init__(self): self.head = None def push(self, new_data:int): new_node = Node(new_data) new_node.next = self.head # Moving the head to point the new node # new node self.head = new_node # Function to print linked List from head def printList(self): temp = self.head while temp != None: print(temp.data) temp = temp.next # Main function that inserts nodes of linked List an into b at # alternate positions. Since head of first List never changes # but head of second List might change, we need single # pointer for first List and double pointer for second List. def merge(self, a, b): a_curr = a.head b_curr = b.head # swap their positions until one is empty while a_curr != None and b_curr != None: # Save next pointers a_next = a_curr.next b_next = b_curr.next # make b_curr as next of a_curr change next pointer # of b_curr b_curr.next = a_next # change next pointer of a_curr a_curr.next = b_curr # update current pointers for next iteration a_curr = a_next b_curr = b_next b.head = b_curr # Driver code list1 = LinkedList() list2 = LinkedList() # Creating the Linked lists # 1. list1.push(6) list1.push(4) list1.push(2) # 2. for i in range(1, 5, 7, 9, 11): list2.push(i) print("First Linked List:") list1.printList() print("Second Linked List:") list2.printList() # Merging the linked lists list1.merge(a = list1, b = list2) print("Modified first linked list:") list1.printList() print("Modified second linked list:") list2.printList()
Output :
First Linked List: 2 4 6; Second Linked List: 1 5 7 9 11; Modified First Linked List:2 1 4 5 6 7; Modified Second Linked List: 9 11
The code to implement the bubble sort algorithm will have 3 steps
Code:
def bubbleSort(arr): n = len(arr) # optimize code, so if the array is already sorted, it # doesn't need to go through the entire process swapped = False # Traverse through all array elements for i in range(n-1): # range(n) also work but outer loop will # repeat one time more than needed. # Last i elements are already in place for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] if not swapped: # if we haven't needed to make a single swap, we # can just exit the main loop. return # Driver code to test above arr = [74, 24, 35, 12, 32, 11, 90] bubbleSort(arr) print("Sorted array is:") for i in range(len(arr)): print("% d" % arr[i], end=" ")
Output:
Sorted array is: 11 12 24 32 35 74 90
Okay. In insertion sort, we assume that the first element in the array is to be sorted. The second element is stored separately in the key. This sorts the first two elements. We can then take the third element and make a comparison with the ones on its left. This process will go on until a point where we sort the array.
Code:
def insertionSort(arr): if (n := len(arr)) <= 1: return for i in range(1, n): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j >=0 and key < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key #sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)
Okay. Inheritance is the procedure in which one class inherits the attributes and methods of another class. The class that inherits the properties of another class is called the child class, and the class whose properties are being inherited is called the parent class. Another interesting thing about inheritance is that the child class can have its own properties and methods along with the ones inherited from the parent class.
Code:
class Person(object): # Constructor def __init__(self, name, id): self.name = name self.id = id # To check if this person is an employee def Display(self): print(self.name, self.id) class Child(Parent): # Constructor def __init__(self): self.value = "Inside Child" # Child's show method def show(self): print(self.value) # Driver code emp = Person("Satyam", 102) # An Object of Person emp.Display()
It's no surprise that this one pops up often in DSA interview questions.
Okay, So overloading is when a class has 2 or more methods with the same name. Then they are called overloaded methods.
Code:
def product(a, b): p = a * b print(p) # Second product method takes three argument and print their # product def product(a, b, c): p = a * b*c print(p) # Uncommenting the below line shows an error product(4, 5) # This line will call the second product method product(4, 5, 5) Overriding is when a superclass method is also implemented in the child class.
Code:
class Parent(): # Constructor def __init__(self): self.value = "Inside Parent" # Parent's show method def show(self): print(self.value) # Defining child class class Child(Parent): # Constructor def __init__(self): self.value = "Inside Child" # Child's show method def show(self): print(self.value) # Driver's code obj1 = Parent() obj2 = Child() obj1.show()