Data Structures & Algorithms Interview Q/A that can land you into your dream job

Being ‘Tech-savvy’ was something that just sounded cool once, but now has become the need of the hour. This environment now claims giant leaps in the development of technology, and to cater to this need, mastery of Data Structures & Algorithms becomes highly significant. Leading companies such as Amazon, Flipkart, Google, and Facebook need software developers skilled in efficient coding and that’s where Algorithms take command. With e-commerce picking up pace, the roles of software developers skilled in programming increase manifold.

 

Six-figure salary packages await those with proficiency in this skill. However, this reward comes by bagging the job which a large number of aspirants aim for and to emerge better than the best while at the interview their questions need to be understood with proper clarity.

 

With eyes on the coveted job position, backing yourself up with the plethora of possible questions becomes vital. And stocking up this armory can be done with the guidance of our book, HR Interview Questions You’ll Most Likely Be sked, which can prepare you out for the pathway to success with over 200 well researched questions for guidance!

 

Here are the Top 20 Data Structures & Algorithms Interview Questions from the book for your reference:

 

 

1) What are the different types of Data Structures?

Data Structures can be categorized in many ways, though broadly, they can be categorized as Linear and Non-linear data structures.

Linear data structures are those that are sequential, like lists, arrays, stacks and queues. They are stored and can be accessed sequentially.

Non-Linear data structures are objects or information that is not stored in an order. Graphs and trees are best example of non-linear data structures. While sequential data is easier to manage, non-linear data is not so easy. But many real-time solutions require non-linear data structures to be implemented such as hierarchical data, geographical positioning and games.

 

 

2) What is an iterator?

An iterator is a variable or object used to traverse through a list or an array. While some programming languages such as Java contain an iterator object, in other languages, a pointer is used instead. An iterator has 2 basic functions – to reference an element of the array at the given position and to move to the next position as required by the program.

Iterators can be implicit or explicit. Implicit iterators are when the program traverses the array for each element in the array without worrying about the index or position. Explicit iterator uses the position or index of the array to point to a particular element and has to be directed to the next element.

 

 

3) Write the basic algorithm to implement the push function for a stack.

 

The Push operation is used to insert an element on to the top of a stack. To insert an element into a stack, first the current last position has to be checked for overflow. If the maximum size allowed for the stack has run out, you have to exit the program. If otherwise, find the last element’s address and increment the pointer to move to the next position and insert the element there. Now this position will be considered as the top of the stack. To insert the next element or for the next push, the same steps are repeated.

 

 

4) Explain three practical applications of Stacks in software.

Stacks are extensively used for memory management. If you take most of the programming languages and platforms, memory management depends on stacks. That’s one reason you may have come across Stack Overflow error in Java and C. Most of the programs use stacks for managing the function call, parameters and other programming requirements. If your program requires some kind of backtracking to be done, you can implement stacks for the same. The undo / redo option available in MS Office is one example for stack implementation. Syntax parsing and expression evaluation also uses the stack implementation. Even compilers use the stack implementation to parse the code. The concept of stack is so basic and simple that it is used in many places in real-time implementation of various software and business logics.

 

 

5) Explain how to implement a queue using an array.

Every queue has a head and a tail. The head is the first element of the queue from where elements have to be popped out. Tail is the last element of the queue where elements can be pushed We can easily implement a queue using an array. In an empty queue, the head and tail will be the same element. As new elements are inserted into the queue, the tail is pushed to the next space available, to store more values and to denote the last element. As elements are popped out, the head is pushed to the next address to denote that the first element is released and the next element is the current first element.

 

 

6) List out the disadvantages of linked lists.

While Linked lists allow dynamic implementation of arrays, they also come with many disadvantages. One main disadvantage is that linked lists take up additional memory since it stores the address to the next node or the pointer to the next node. Another issue with a linked list is that, none of the elements can be randomly accessed. It has to be sequentially accessed by traversing through each node to get the address of the next node. When it comes to singly linked list, there’s no way you can move to the previous node or element.

 

 

7) What are the common uses of hash tables?

Hash tables store data in key-value pairs and are indexed. Indexing makes searches faster and hence, hash tables are used when there’s a large volume of key-value pairs to be stored which has to be easier to search. Hash tables also lets you work around the four basic functions of collections – put, which works with a set of key, value pair and get, contains and remove that works with a key. Caching is a common usage that implements hash tables in the real time. Sometimes hash tables also let you store relational data without disturbing the original objects.

 

 

8) What are the problems with hash tables?

Even though hash tables are considered good for implementing caching, hash tables take a lot of time performing the hash functions. Since the data stored in the slots are distributed randomly in the memory, it takes up more time in allocation and seeking information. First the index has to be searched for the next address and then the data in the address is accessed. Hash functions are quite complex and prone to errors. Since there are many hash functions used along with each hash table, it can be quite difficult to manage the hash functions. Moreover, a poorly written hash function can result in unwarranted collisions which affect the program performance adversely.

 

 

9) Explain a Spanning Tree.

A spanning tree is related to a network graph where every node appears at least once in the tree. Even though the minimum spanning tree or MST does not assure the shortest distance between 2 nodes, it assures that the total weight of the tree remains minimal. It is organized such that the total weight between the nodes remains minimal throughout the tree. A spanning tree, especially the MST can be used to implement the best network graph for a computer network, telecommunications, transportation and electrical grids.

 

 

10) How do you find the height of a node in a tree?

The height of a node in a tree is the length of the longest path from it to its outermost leaf. To find the height x of a node in the tree t, a recursive function height is used which finds the distance from x to its last leaf in the subtree and 1 is added to it. So it is height (x) = 1 + height(x, t). If x is a leaf, then its height is 0. Otherwise, for each node in tree t that comes after x, a counter is incremented which counts the height till x becomes the leaf.

 

 

11) Explain the Bit Vector representation of sets.

Sometimes the information required to be stored is only like a flag value or bit values 0 or 1, like the Boolean true or false. In such cases, a BitArray or Bit Vector representation is used which requires very little storage compared to any other data type. If the requirement is for a set that contains information on whether the particular student is above 18 years or not, a bit array representation will be the better choice. A bit array with values {0, 0, 1, 0, 1, 0, 0} means that out of 7 students, the 1st record corresponds to a student who is not yet 18 years old. The second student is also aged less than 18 years. The 3rd and 5th students are 18 or above and the rest of them are less than 18 years old.

 

 

12) What do you mean by cost of a graph?

The cost of a graph determines the cost involved in terms of the distance travelled or time taken to traverse through the graph Depth First or Breadth First. When a vertex is connected to another through an edge, the path will carry a cost for traversal which can be measured in terms of speed, distance, time or any other ‘weight’ as relevant to the graph representation. For example, when you have a network of computers, the time for response might be the weight or the amount of information transferred can be another weightage. But in the case of a location map, the distance covered or the time taken to reach might be the weightage. The cost of a graph is basically that total weightage to traverse through the graph by DSF or BSF.

 

 

13) Explain Divide-and-Conquer Algorithm.

In the Divide and Conquer algorithm, the entire problem is divided into smaller, reusable processes or procedures. These procedures or smaller chunks of processes are repeatedly used to solve the problem. Finally, the processes and iterations are combined appropriately to arrive at the desired solution. Recursion and iterative function calling are the usual methods adopted in this algorithm. The search and sort algorithms are best examples of implementations of divide and conquer algorithms.

 

 

14) Explain the algorithm for generating a random password of fixed length.

 

• Create a function which generates the password. The function will take in the length of the password.
• Inside the function, declare and assign a string, say strChars, with all possible alpha-numeric characters that can be a part of the password. Typically password contains the alphabets in small and capital letters and all digits.
• Store the length of the string into another variable say lenStrChars
• Have another empty string variable strRandPWD to store the randomly created password
• Start a loop that runs through the length of password required (as passed to the function from main)
• Within the loop, take random characters from the string strChars (the string with all possible values) and push it into the desired password string strRandPWD. Take rand() % lenStrChars to make sure the array index stays below lenStrChars or the length of the string.
• Once out of the loop, return strRandPWD
• The main function will call this function with the number of digits’ password it wants to generate.

 

 

15) How do you check for stability in sorting algorithms?

Any sorting algorithm can be made stable by making sure that the equal keys are coming in the same order as before sorting. While checking for the stability in the sorting algorithm being used, multiple conditions are checked that includes its keys before and after sorting. If you have a set of elements that are identical but appear more than once in a list, if their order is maintained after the sort is completed, it is said to be a stable sorting algorithm.

 

 

16) Explain the algorithm for binary search.

Binary search involves searching in a sorted array. The value to be searched is checked against the middle-most item of the array. If the middle element is equal to the search element, the element is found. Otherwise, if the element is less than the middle element, only the first half of the array is searched for. If the element is greater than the middle element, only the second half is searched. The steps are repeated until the entire array has been searched.

 

 

17) Explain why a Binary search is better than a Ternary search

A Binary search involves splitting the array into half and searching each half separately. A ternary search involves splitting the array into 3 parts and searching each separately. So when a binary search will involve 2 searches in each level, the ternary will involve 3 searches in each level. Technically, a binary search takes log2 (x) + O(1) comparisons to complete whereas a ternary search involves 2log3 (x) + O(1) comparisons. This means that a ternary search will require more comparisons to search than a binary search and hence, binary search is a better option.

 

 

18) Explain Huffman Template Algorithm.

In Huffman coding, the frequencies are usually used as weights to encode the symbols or data. In Huffman Template Algorithm, we can use any weight or combination of weights that forms the basis of sorting. Weight can be cost, occurrence, or any other weight which can even be non-numerical. The only requirement is that the symbol needs to be weighted. Such implementations tend to solve some minimization problems that usually comes up during encoding.

 

 

19) What are the applications of Huffman Coding?

Huffman coding is used for coding and decoding information. Arithmetic coding is a standard implementation of Huffman coding. Arithmetic coding, in fact, is a better implementation since it includes alphabets and numbers for coding as against the binary coding implemented by Huffman coding. Huffman coding is used as a backend to widely used encoding methods. Multimedia codecs such as MP3s and JPEGs use Huffman coding along with other methods.

 

 

20) How will you search in an almost sorted array?

When we need to search in an almost sorted array, it means that the array is more or less sorted, except for a few elements here and there. So we can start searching for the key from the middle as usual. The only difference being, we search for the 3 middle numbers first and then decide on whether to continue with a binary search for left array or right array. The advantage of doing this is that, when we consider 3 elements in the middle, we get an idea of how well-sorted the array is. Sometimes the key to be searched is in the middle, or the very next elements before or after it, and the search ends with single pass. Otherwise, if the key is less than mid value, search the left subarray or else, search the right subarray with the same steps.

 

With a plethora of applications lying in front of the recruiters for any open position, standing out amongst the rest is the key to land into your dream job and that is where the need to refer to Interview Q/A books arise.

 

 

Get one step closer to your dream job!

 

Prepare for your programming interview with our book HR Interview Questions You’ll Most Likely Be Asked (Third Edition). This book has a comprehensive list of questions to help you crack your interview, no matter what field you’re applying to.