Blogs On Job Interview Questions

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.

Here’s a List of TOP 13 Data Structures & Algorithms Interview Questions that you will most likely be asked in your next Data Structures & Algorithms Interview. We cover a range of the most important Data Structures & Algorithms Topics with these 13 Questions. Topics covered in the Blog are:   Data Structures: Introduction to Data Structures Arrays Stacks Queues Lists Hash Data Structures Trees Sets Graphs Algorithms   Algorithms: General Concepts of Algorithms Sorting Algorithms Search Algorithms Huffman Coding       1) What are Data Structures? (Learn more: Introduction to Data Structures) Data Structures are a method of structured or organized data storage that is easier to manage. Data usually has 2 aspects – the definition and its implementation. Data structures make sure they keep both aspects separate. The definition is made available for different implementations for different programs or usages. A data structure, as the name suggests, stores the information in a structured way so that it can be easily created, viewed, and managed. This involves creating complex data types which are a combination of various basic data types. One example can be a customer data type which will have a CustomerId of type Integer, Customer Name of type String and Address of type String.     2) What is an Array? (Learn more: Arrays) An array is a set of values represented by a single variable. Arrays are usually stored sequentially which makes it possible to access each element by its index. An array will have a fixed number of elements that are accessible with their index. An array can store any type of data as allowed by the programming language or the platform used. You can have integer arrays or string arrays and even arrays of objects and structures. The maximum number of elements allowed in an array is mentioned in the array declaration so that the memory can be allocated together. This makes sure that the array elements are sequentially accessible using the index or pointer dynamically. In some languages like C, a string is represented by a character array.     Example:   int arr[5] = {2, 4, 6, 8, 10};   char alphabets[10] = {‘a’, ‘b’, ‘c’, ‘x’, ‘y’, ‘z’, ‘1’, ‘2’, ‘h’, ‘i’};   string names[3] = {“Smitha”, “Allen”, “Ritik”};       3) Why are stacks used to perform recursion? (Learn more: Stacks) A Recursive function will call itself repeatedly. It is important to know who called the function with what value so that accordingly it will return the value to the right caller. Stacks function in the concept of LIFO or Last In First Out. For the same reason, it will recognize the last caller of the function that called it and will return the corresponding value to it. Recursion usually functions by stacking the caller addresses in the order in which the function is called. Hence, it is important to use a separate stack every time the recursive function is called explicitly in the program. For example, if factorial(n) is a recursive function that is called twice in a program, for each call, a separate stack should be used. To be more specific, in the same program that calls factorial(x) and factorial(y), separate stacks should be used.     4) What are the basic features of a Queue? (Learn more: Queues) Queues implement data structures that follow the First-In-First-Out concept. What is inserted first comes out first. This means that the push operation happens at one end of the queue while the pop operation happens at the other end. Even though the queue and stack operations are similar, in contrast to a stack which is open only at one end, the queue is open at both ends.           5) What are the advantages of Linked Lists? (Learn more: Linked List) Linked lists are a sequence of nodes connected by a link to the next and or previous node. Linked lists are used to implement many real-time application requirements. One basic application of a linked list is to create arrays dynamically. Since the linked lists contain the memory address to the next node, it need not be sequentially allocated. Each node will contain the address to the next node using which you can move to the next node. Linked lists allow easier implementation of stacks and queues. You implement insert and delete operations easily with linked lists.     6) What is a hashing? (Learn more: Hash Data Structures) Hashing is converting a set of key-value pairs into indexed information or an array that is easier to handle and retrieve. The information is always stored in key-value pairs with an index supporting a faster search. The size of the hash table is used for hashing the index. Hashing is done by the method of the key % size where key is the key of a particular element in the key-value pair and the size is the size of the hash table. It is basically mapping where a particular item is stored in the hash table.     7) Explain the Tree data structure. (Learn more: Trees) A tree has a root element with 1 or 2 nodes attached to each node. It is a hierarchical data structure used to store information in an ordered way. A binary tree can have zero to a maximum of 2 child nodes. The uppermost element or node is called the root, and the lowermost element or node that has no child node is called a leaf node. The number of elements that connect a particular node from the root to that node determines the depth of a node. The height of a node is determined by the length of the node to its deepest leaf. A tree’s height is determined by the height of its root.     8) What is a set? (Learn more: Sets) A set is a collection of unique elements, related to each other in some way, which need not be in any order. You can consider it akin to football players of a team where none of the names are repeated and the names need not be stored in any order. But they are all related as players of the same team. We cannot add any other member or element in this set. A set of students who belong to a class is also another implementation. We cannot add another class student in one class set.     9) What is a Graph data structure? (Learn more: Graphs) A Graph data structure contains a set of arrays called vertices and a set of edges. Every edge will have 2 vertices that point to a location of the edge. Graphs are used to implement images or networks wherein the edges or elements are related to each other in some way or the other. Every graph will have edges, vertices, paths, and adjacency. A graph can be represented as a tree data structure. The Vertex is the node. The Edge determines the path or the order in which other nodes are linked in the tree. Adjacency determines the nodes directly linked to another node by a path. A Path is a series of edges to traverse to reach a particular node.     10) What do you mean by Algorithm? An algorithm is basically the step-by-step procedure involved in solving a computer problem. Once you have the login in place, clearly specified with the loops and ifs, you can easily implement it in any programming language. It is based on this algorithm that a more refined Flowchart is prepared which is used by the programmers to write it in a particular programming language. You can develop algorithms for the simplest processes to very complex procedures such as database programming. To understand an algorithm, it can be followed step by step simulating with possible values of input.     11) How do you classify sorting algorithms? (Learn more: sorting algorithms) Sorting algorithms can be broadly classified comparison-based & counting-based, and in-place & not-in-place algorithms. Most of the sorting algorithms are based on comparison. The basic idea is to compare 2 elements and swap them or rearrange them based on the particular type of algorithm used. Examples of comparison-based algorithms are bubble sort, heap sort, selection sort, quick sort etc. The counting-based algorithms like bucket sort and radix sort use the divide and rule algorithms to divide the entire collection and then sort the elements. The in-place algorithms are carried out without using any additional array or data structure. Examples of in-place algorithms are quick sort and heap sort. The not-in-place algorithms use an additional array or data structure for sorting. Examples of not-in-place algorithms are bucket sort and merge sort.     12) Explain the algorithm for linear search. (Learn more: Search Algorithm) (Learn more: Search Algorithm) The linear search is the simplest of all search algorithms. The entire array is searched from the very first element until the element is found or until the end of the array. The element is compared with all elements of the array until a match is found. Linear search can be done on a sorted or unsorted array.     13) What is Huffman Coding? (Learn more: Huffman Coding) Huffman coding uses prefixes or weights to assign a code to the data being transmitted. More frequent codes get less weight and the rarely transmitted codes get more weight. These codes are bit sequences assigned to the data, which makes it a unique stream of data that can be easily decoded by the receiver without any vagueness. The codes or bit strings are assigned based on their probability or occurrence in the stream. This involves building a Huffman tree from the given data and to traversing the tree to assign the bit streams to the data. Start Learning all the important concepts of Data Structures & Algorithms from an Interview Perspective with our Blog Series starting with Introduction to Data Structures. Here is a list of some more questions that could be asked in your interview or written exam. Can you implement a queue using a stack? How to implement a queue using an array? How do you delete an element from an array? Explain collision resolution What is the difference between Chaining and Open addressing? Why is quicksort is preferred for arrays and merge sort for the linked list? How to find the length of a linked list? How do you convert a binary tree into a doubly-linked list? How to check if the given tree is a binary heap? What do you mean by shuffling?     Get one step closer to your dream job!   Prepare for all aspects of your interview with our Job Interview Questions book series, which includes books like HR Interview Questions You’ll Most Likely Be Asked (Third Edition) and Innovative Interview Questions You’ll Most Likely Be Asked. These include a myriad of questions that are helpful in cracking any interview, no matter what field you are in.