data structure problem solving questions

Data Structures

Arrays - ds easy problem solving (basic) max score: 10 success rate: 93.04%, 2d array - ds easy problem solving (basic) max score: 15 success rate: 93.16%, dynamic array easy problem solving (basic) max score: 15 success rate: 87.02%, left rotation easy problem solving (basic) max score: 20 success rate: 91.46%, sparse arrays medium problem solving (basic) max score: 25 success rate: 97.29%, array manipulation hard problem solving (intermediate) max score: 60 success rate: 61.69%, print the elements of a linked list easy problem solving (basic) max score: 5 success rate: 97.15%, insert a node at the tail of a linked list easy problem solving (intermediate) max score: 5 success rate: 95.31%, insert a node at the head of a linked list easy problem solving (basic) max score: 5 success rate: 98.31%, insert a node at a specific position in a linked list easy problem solving (intermediate) max score: 5 success rate: 96.96%, cookie support is required to access hackerrank.

Seems like cookies are disabled on this browser, please enable them to open this website

DEV Community

Posted on Mar 23, 2019 • Updated on Jan 28, 2023

50+ Data Structure and Algorithms Problems from Coding Interviews

Disclosure: This post includes affiliate links; I may receive compensation if you purchase products or services from the different links provided in this article.

There are a lot of computer science graduates and programmers applying for programming, coding, and software development roles at startups like Uber and Netflix; big organizations like Amazon , Microsoft , and Google ; and service-based companies like Infosys or Luxsoft, but many of them have no idea of what kind of programming interview questions to expect when you're applying for a job with these companies.

In this article, I'll share some frequently asked programming interview questions from different Job interviews for programmers at different levels of experience,from people who have just graduated from college to programmers with one to two years of experience.

Coding interviews are comprised mainly of d ata structure and algorithm-based questions as well as some of the logical questions such as, How do you swap two integers without using a temporary variable?

I think it's helpful to divide coding interview questions into different topic areas.

The topic areas I've seen most often in interviews are array , linked list , string , binary tree , as well as questions from algorithms like string algorithm, sorting algorithms like quicksort or radix sort , and other miscellaneous ones), and that's what you will find in this article.

It's not guaranteed that you will be asked these coding or data structure and algorithmic questions, but they will give you enough of an idea of the kinds of questions you can expect in a real programming job interview.

Once you have gone through these questions, you should feel confident enough to attend any telephonic or face-to-face interviews.

Btw, there is no point in attempting these questions if you don't have sufficient knowledge of essential Data Structure and Algorithms or you have not touched them for ages.

In that case, you should take a good introductory course like Data Structures and Algorithms: Deep Dive Using Java to refresh your DS and algorithms skills.

Top 50 Algorithms and Coding Interview Questions

Without any further ado, here is my list of some of the most frequently asked coding interview questions from programming job interviews :

1. Array Coding Interview Questions

An array is the most fundamental data structure, which stores elements at a contiguous memory location. It is also one of the darling topics of interviewers and you will hear a lot of questions about an array in any coding interview , like reversing an array, sorting the array, or searching elements on the array.

The key benefit of an array data structure is that it offers fast O(1) search if you know the index, but adding and removing an element from an array is slow because you cannot change the size of the array once it's created.

In order to create a shorter or longer array, you need to create a new array and copy all elements from old to new.

The key to solving array-based questions is having a good knowledge of array data structure as well as basic programming constructors such as loop, recursion, and fundamental operators.

Here are some tips to solve array based coding problems:

• array index starts at zero
• You can use loops to iterate over array
• array elements are stored in contiguous memory location so you can also access them using pointer arithmetic
• Array provides O(1) performance for search using index
• Adding or removing elements are slower in array due to re-sizing

Here are some of the popular array-based coding interview questions for your practice:

• How do you find the missing number in a given integer array of 1 to 100 ? ( solution )
• How do you find the duplicate number on a given integer array? ( solution )
• How do you find the largest and smallest number in an unsorted integer array? ( solution )
• How do you find all pairs of an integer array whose sum is equal to a given number?( solution )
• How do you find duplicate numbers in an array if it contains multiple duplicates?( solution )
• How are duplicates removed from a given array in Java? ( solution )
• How is an integer array sorted in place using the quicksort algorithm? ( solution )
• How do you remove duplicates from an array in place? ( solution )
• How do you reverse an array in place in Java? ( solution )
• How are duplicates removed from an array without using any library? ( solution )

These questions will not only help you to develop your problem-solving skills but also improve your knowledge of the array data structure.

If you need more advanced questions based upon array then you can see also see The Coding Interview Bootcamp: Algorithms + Data Structures , a Bootcamp style course on algorithms, especially designed for interview preparation to get a job on technical giants like Google, Microsoft, Apple, Facebook, etc.

And, if you feel 10 is not enough questions and you need more practice, then you can also check out this list of 30 array questions .

2. Linked List Programming Interview Questions

A linked list is another common data structure that complements the array data structure. Similar to the array, it is also a linear data structure and stores elements in a linear fashion.

However, unlike the array, it doesn't store them in contiguous locations; instead, they are scattered everywhere in memory, which is connected to each other using nodes.

A linked list is nothing but a list of nodes where each node contains the value stored and the address of the next node.

Because of this structure, it's easy to add and remove elements in a linked list , as you just need to change the link instead of creating the array, but the search is difficult and often requires O(n) time to find an element in the singly linked list.

This article provides more information on the difference between an array and linked list data structures.

It also comes in varieties like a singly linked list, which allows you to traverse in one direction (forward or reverse); a doubly linked list , which allows you to traverse in both directions (forward and backward); and finally, the circular linked list, which forms a circle.

In order to solve linked list-based questions, a good knowledge of recursion is important, because a linked list is a recursive data structure .

If you take one node from a linked list, the remaining data structure is still a linked list, and because of that, many linked list problems have simpler recursive solutions than iterative ones.

Here are some of the most common and popular linked list interview questions and their solutions:

• How do you find the middle element of a singly linked list in one pass? ( solution )
• How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle? ( solution )
• How do you reverse a linked list? ( solution )
• How do you reverse a singly linked list without recursion? ( solution )
• How are duplicate nodes removed in an unsorted linked list? ( solution )
• How do you find the length of a singly linked list? ( solution )
• How do you find the third node from the end in a singly linked list? ( solution )
• How do you find the sum of two linked lists using Stack? ( solution )

These questions will help you to develop your problem-solving skills as well as improve your knowledge of the linked list data structure.

If you are having trouble solving these linked list coding questions then I suggest you refresh your data structure and algorithms skill by going through Data Structures and Algorithms: Deep Dive ** Using Java** course.

You can also check out this list of 30 linked list interview questions for more practice questions.

3. String Coding Interview Questions

Along with array and linked list data structures, a string is another popular topic on programming job interviews. I have never participated in a coding interview where no string-based questions were asked.

A good thing about the string is that if you know the array, you can solve string-based questions easily because strings are nothing but a character array .

So all the techniques you learn by solving array-based coding questions can be used to solve string programming questions as well.

Here is my list of frequently asked string coding questions from programming job interviews:

• How do you print duplicate characters from a string? ( solution )
• How do you check if two strings are anagrams of each other? ( solution )
• How do you print the first non-repeated character from a string? ( solution )
• How can a given string be reversed using recursion? ( solution )
• How do you check if a string contains only digits? ( solution )
• How are duplicate characters found in a string? ( solution )
• How do you count a number of vowels and consonants in a given string? ( solution )
• How do you count the occurrence of a given character in a string? ( solution )
• How do you find all permutations of a string? ( solution )
• How do you reverse words in a given sentence without using any library method? ( solution )
• How do you check if two strings are a rotation of each other? ( solution )
• How do you check if a given string is a palindrome? ( solution )

These questions help improve your knowledge of string as a data structure. If you can solve all these String questions without any help then you are in good shape.

For more advanced questions, I suggest you solve problems given in the Algorithm Design Manual by Steven Skiena , a book with the toughest algorithm questions.

If you need more practice, here is another list of 20 string coding questions .

4. Binary Tree Coding Interview Questions

So far, we have looked at only the linear data structure, but all information in the real world cannot be represented in a linear fashion, and that's where tree data structure helps.

The tree data structure is a data structure that allows you to store your data in a hierarchical fashion. Depending on how you store data, there are different types of trees, such as a binary tree , where each node has, at most, two child nodes.

Along with its close cousin binary search tree , it's also one of the most popular tree data structures. Therefore, you will find a lot of questions based on them, such as how to traverse them, count nodes, find depth, and check if they are balanced or not.

A key point to solving binary tree questions is a strong knowledge of theory, like what is the size or depth of the binary tree, what is a leaf, and what is a node, as well as an understanding of the popular traversing algorithms, like pre-, post-, and in-order traversal.

Here is a list of popular binary tree-based coding questions from software engineer or developer job interviews:

• How is a binary search tree implemented? ( solution )
• How do you perform preorder traversal in a given binary tree?( solution )
• How do you traverse a given binary tree in preorder without recursion?( solution )
• How do you perform an inorder traversal in a given binary tree?*( solution )
• How do you print all nodes of a given binary tree using inorder traversal without recursion? ( solution )
• How do you implement a postorder traversal algorithm? ( solution )
• How do you traverse a binary tree in postorder traversal without recursion?( solution )
• How are all leaves of a binary search tree printed?( solution )
• How do you count a number of leaf nodes in a given binary tree?( solution )
• How do you perform a binary search in a given array?( solution )

If you feel that your understanding of binary tree coding is inadequate and you can't solve these questions on your own, I suggest you go back and pick a good data structure and algorithm course like From 0 to 1: Data Structures & Algorithms in Java .

If you need some more recommendations, here is my list of useful data structure algorithm books and courses to start with.

5. Miscellaneous Coding Interview Questions

Apart from data structure-based questions, most of the programming job interviews also ask algorithms , software design , bit manipulation, and general logic-based questions, which I'll describe in this section.

It's important that you practice these concepts because sometimes they become tricky to solve in the actual interview. Having practiced them before not only makes you familiar with them but also gives you more confidence in explaining the solution to the interviewer.

• How is a bubble sort algorithm implemented? ( solution )
• How is an iterative quicksort algorithm implemented? ( solution )
• How do you implement an insertion sort algorithm? ( solution )
• How is a merge sort algorithm implemented? ( solution )
• How do you implement a bucket sort algorithm?( solution )
• How do you implement a counting sort algorithm?( solution )
• How is a radix sort algorithm implemented?( solution )
• How do you swap two numbers without using the third variable? ( solution )
• How do you check if two rectangles overlap with each other? ( solution )
• How do you design a vending machine? ( solution )

If you need more such coding questions you can take help from books like Cracking The Code Interview , by Gayle Laakmann McDowell which presents 189+ Programming questions and solution. A good book to prepare for programming job interviews in a short time.

By the way, the more questions you solve in practice, the better your preparation will be. So, if you think 50 is not enough and you need more, then check out these additional 50 programming questions for telephone interviews and these books and courses for more thorough preparation.

Now You're Ready for the Coding Interview

These are some of the most common questions outside of data structure and algorithms that help you to do really well in your interview.

I have also shared a lot of these questions on my blog , so if you are really interested, you can always go there and search for them.

These common coding, data structure, and algorithm questions are the ones you need to know to successfully interview with any company, big or small, for any level of programming job.

If you are looking for a programming or software development job, you can start your preparation with this list of coding questions.

This list provides good topics to prepare and also helps assess your preparation to find out your areas of strength and weakness.

Good knowledge of data structure and algorithms is important for success in coding interviews and that's where you should focus most of your attention.

Further Learning Data Structures and Algorithms: Deep Dive Using Java Master the Coding Interview: Data Structures + Algorithms by Andrei Negaoie Grokking the Coding Interview: Patterns for Coding Questions Algorithms and Data Structures - Part 1 and 2 10 Books to Prepare Technical Programming/Coding Job Interviews 10 Algorithm Books Every Programmer Should Read Top 5 Data Structure and Algorithm Books for Java Developers From 0 to 1: Data Structures & Algorithms in Java Data Structure and Algorithms Analysis --- Job Interview

Closing Notes

Thanks, You made it to the end of the article ... Good luck with your programming interview! It's certainly not going to be easy, but by following this roadmap and guide, you are one step closer to becoming a DevOps engineer .

If you like this article, then please share it with your friends and colleagues, and don't forget to follow javinpaul on Twitter!

P.S. --- If you need some FREE resources, you can check out this list of free data structure and algorithm courses to start your preparation.

Top comments (16).

Templates let you quickly answer FAQs or store snippets for re-use.

• Location Bengaluru, India
• Work Full Stack Developer at Hashnode
• Joined Mar 6, 2019

This article is like a Gold mine for me. Thanks a lot

• Joined Sep 16, 2018

Thanks Mohd Shad Mirza

• Location Perth, Western Australia
• Education Moscow Aviation Institute
• Work Founder at FullStack.Cafe
• Joined Jul 14, 2018

Thanks a lot for the article, it's very helpful! For more Data Structures and Coding Interview Questions check my blog posts on fullstack.cafe . Hope it will help anyone to crack your next coding interview!

• Location New Delhi
• Joined Feb 23, 2022

GOF Academy is one of the Best IIT, Neet Coaching Institute in Kalu Sarai, Live Coaching Classes For Neet Preparation. Enquire Now For Admission Fees gofacademy.in/iit-coaching-in-kalu...

Are you preparing for competitive exams like IIT, NEET, NTSE, Olympiads, KVPY, UPSC or JEE? You must be looking for best coaching institute in Delhi, which can guide you in your competitive exam preparation. Aspirant must opt for GOF Academy that serves as the best IIT Coaching institutes in Delhi providing one stop exam solutions with study material, test series, and lectures. Our highly experienced faculties put in great efforts to clear the concept in aspirant’s mind with their short tricks. With the utmost support of lecturers and state of the art educational infrastructures, we are able to provide high-quality engineering education. If you searching for coaching institute in Delhi for IIT-JEE, NEET and foundation course, Call at 8700484442 to book your slot. Admission open, Limited Seats. Visit gofacademy.in

• Location Mumbai
• Education CSE Undegrad Student at Mumbai University
• Joined Sep 14, 2020

Thanks a lot

• Joined Jun 9, 2021

Hello. How can I initialize objects like Arrays, List in a constructor?

• Location Pune
• Education BE IT, MBA Systems Mgmt.
• Work Technical Lead at BNT Soft Pvt Ltd.
• Joined Feb 22, 2020

Thanks for sharing.

• Email [email protected]
• Joined Jul 14, 2022

Thanks for your content!

• Email [email protected]
• Location India
• Education Sir Padampat Singhania University
• Work Student | Most of the time i am teacher to myself. ( A Strict one)
• Joined Oct 8, 2021

dev.to/ukantjadia/day-07-2doo

• Joined Jan 23, 2019

another awesome article :D

let me know what you think about this:

udemy.com/course/leetcode-in-pytho...

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink .

Hide child comments as well

For further actions, you may consider blocking this person and/or reporting abuse

AppSec: The Security Specialty That Rules Them All

Michael Levan - Aug 16

Hints: Provide hints after a certain number of wrong guesses, such as whether the number is even or odd.

Avinash Mathi - Aug 15

#53 — Get Desired Data Every N Rows And Combine Them Into One Row

Judith-Excel-Sharing - Aug 28

🛠️ Tooling Evolution: The 5 Most Innovative JavaScript Proposals for 2024

Dharmendra Kumar - Aug 27

We're a place where coders share, stay up-to-date and grow their careers.

Ace your Coding Interview

• DSA Problems
• Binary Tree
• Binary Search Tree
• Dynamic Programming
• Divide and Conquer
• Linked List
• Backtracking

Data Structures and Algorithms Problems

• TopClassic, TopLiked ↗ Easy
• TopLiked ↗ Medium
• TopLiked ↗ Easy
• TopClassic, TopLiked ↗ Medium
• ↗ Medium
• ↗ Hard
• ↗ Easy
• TopAlgo ↗ Easy
• TopClassic ↗ Medium
• TopAlgo, TopClassic, TopAlgo ↗ Easy
• TopLiked ↗ Hard
• TopClassic, TopLiked ↗ Hard
• TopClassic ↗ Hard
• TopClassic ↗ Easy
• TopAlgo ↗ Medium
• TopClassic Hard
• ↗ Beginner
• TopAlgo ↗ Hard
• TopLiked Medium
• TopClassic, TopLiked, TopDP ↗ Medium
• TopLiked, TopDP ↗ Hard
• TopClassic, TopLiked, TopDP ↗ Hard
• TopDP ↗ Medium
• TopAlgo Medium
• TopClassic Medium
• TopAlgo Hard

Rate this post

Average rating 4.88 /5. Vote count: 5929

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?

Thanks for reading.

To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and support our growth. Happy coding :)

Top 100+ Data Structure Interview Questions and Answers

Explore a comprehensive list of data structure interview questions, curated to enhance your understanding and prepare you for technical interviews.

I am looking to hire

I am looking for a job

Data Structure Interview Questions and Answers is an extensive collection of queries and solutions focused on the fundamental and advanced concepts of data structures. Data Structure Interview Questions and Answers cover arrays, linked lists, stacks, queues, trees, graphs, and hash tables, addressing their implementation, applications, and efficiency. Data Structure Interview Questions and Answers is a comprehensive guide for preparing for technical interviews, enhancing problem-solving skills, and understanding data structures' critical role in computer science.

Array Data Structure Interview Questions and Answers

Array Data Structure Interview Questions cover a range of inquiries and responses related to the array data structure, a fundamental component in the field of computer science and programming. Array Data Structure Interview Questions aim to equip candidates with the knowledge and understanding required to navigate through questions about arrays efficiently during technical interviews.

Write a program to find the sum of all elements in an array.

View Answer

Hide Answer

To find the sum of all elements in an array, iterate through each element, adding them to a cumulative sum variable initialized at zero.

How do you remove duplicates from an array without using any additional data structure?

To remove duplicates from an array without using any additional data structure, iterate through the array, comparing each element with the rest. Overwrite duplicates with the next unique element, adjusting the array's size accordingly.

Can you explain how to rotate an array to the left by 'n' positions?

Rotating an array to the left by 'n' positions involves shifting each element 'n' positions to the left, with the leftmost elements wrapping around to the right end of the array.

How do you find the maximum and minimum elements in an array?

To find the maximum and minimum element in an array, iterate through the array, comparing each element to the current maximum and minimum, updating these variables as necessary.

Write a function to merge two sorted arrays into a single sorted array.

Merging two sorted arrays into a single sorted array requires iterating through both arrays simultaneously, comparing elements, and adding the smaller element to a new array until all elements are merged.

How do you find the intersection of two arrays?

Finding the intersection of two arrays involves iterating through one array and checking if its elements appear in the second array, storing the matches in a new array.

Explain the algorithm to find the "Kth" largest element in an array.

The algorithm to find the "Kth" largest element in an array typically involves sorting the array and accessing the element at the position length minus 'k'.

How do you move all zeros in an array to the end, maintaining the order of other elements?

To move all zeros in an array to the end while maintaining the order of other elements, iterate through the array, shifting non-zero elements forward, and filling the end of the array with zeros.

Write an algorithm to check if an array contains a duplicate within 'k' distance from each other.

An algorithm to check if an array contains a duplicate within 'k' distance from each other involves iterating through the array and checking the elements within 'k' positions ahead for duplicates.

Your engineers should not be hiring. They should be coding.

Help your team focus on what they were hired for. Flexiple will manage your entire hiring process and scale your tech team.

How do you find the majority element in an array if it exists?

Finding the majority element in an array, if it exists, requires iterating through the array to count the occurrences of each element and determining if any count exceeds half the size of the array.

Write a program to perform a binary search on a sorted array.

Performing a binary search on a sorted array involves repeatedly dividing the search interval in half, comparing the target value to the middle element, and narrowing the search based on the comparison.

How do you find all pairs in an array that sum up to a specific number?

To find all pairs in an array that sum up to a specific number, iterate through the array, for each element, searching for a complementary element that equals the target sum minus the current element.

Can you explain how to cyclically rotate an array by one position?

Cyclically rotating an array by one position involves moving the last element of the array to the front, and shifting all other elements one position to the right.

How do you implement a two-dimensional array's diagonal traversal?

Implementing a two-dimensional array's diagonal traversal requires iterating over the array in a manner that increases the row index and decreases the column index simultaneously for one direction, or vice versa.

Write a method to shuffle an array randomly.

Shuffling an array randomly involves iterating through the array and swapping each element with another randomly selected element from the array.

How do you find the common elements in three sorted arrays?

Finding the common elements in three sorted arrays requires iterating through all three arrays simultaneously, advancing in each array based on the comparison of the current elements to find matches.

Explain the process to flatten a multi-dimensional array.

Flattening a multi-dimensional array involves recursively traversing each element, if the element is an array itself, further traversing its elements, and aggregating the leaf values into a new, single-dimensional array.

How do you implement an algorithm to find the next greater element for every element in an array?

Implementing an algorithm to find the next greater element for every element in an array involves iterating through the array and for each element, searching the subsequent elements for a larger value.

Write a program to find the longest consecutive sequence in an array.

Finding the longest consecutive sequence in an array requires sorting it and then iterating through it to find the longest sequence of consecutive numbers.

How do you compute the prefix sum array for a given array?

Computing the prefix sum array for a given array involves iterating through the original array and summing the elements from the start to the current index, storing each sum in a new array at the corresponding index.

Linked List Data Structure Interview Questions and Answers

Linked List Data Structure Interview Questions offer a guide to understanding and tackling various interview questions related to the linked list data structure. Linked List Data Structure Interview Questions delve into the intricacies of linked lists, exploring their operations, types, applications, and comparisons with other data structures.

Write a function to split a circular linked list into two equal parts.

A function splits a circular linked list into two equal parts by finding the middle of the list using a fast and slow pointer approach and then cutting the list into two halves. Adjust the next pointers of the two halves to make them separate circular linked lists.

How would you implement a function to check if a linked list is a palindrome?

Implementing a function to check if a linked list is a palindrome involves reversing the second half of the list and comparing it with the first half. If all elements match, the linked list is a palindrome.

Can you code an algorithm to remove all elements from a linked list of integers that have a specific value?

An algorithm removes all elements from a linked list of integers that have a specific value by iterating through the list, maintaining a previous pointer, and unlinking the nodes that match the value.

Write an algorithm to add two numbers represented by two linked lists.

An algorithm adds two numbers represented by two linked lists by traversing both lists simultaneously, summing the corresponding digits along with any carry, and forming a new linked list of the sum.

How do you rotate a linked list to the right by 'k' places?

To rotate a linked list to the right by 'k' places, find the length, mod it with 'k' to get the effective rotations, and change the next pointers accordingly after locating the new head and tail.

Implement a function to swap pairs of nodes in a linked list.

A function swaps pairs of nodes in a linked list by iterating through the list and swapping the next pointers of adjacent nodes.

Write a function to find the entry node of a cycle in a linked list.

A function finds the entry node of a cycle in a linked list using Floyd's Tortoise and Hare algorithm to first detect the cycle and then find the cycle's entry point by moving two pointers at different speeds.

How would you flatten a multilevel doubly linked list?

Flattening a multilevel doubly linked list involves recursively traversing the list and connecting child nodes in line with the main list, adjusting the previous and next pointers accordingly.

Can you code a method to partition a linked list around a value 'x', such that all nodes less than 'x' come before all nodes greater than or equal to 'x'?

A method partitions a linked list around a value 'x' by creating two separate lists: one for nodes less than 'x' and another for nodes greater than or equal to 'x', and then concatenating these two lists.

Implement a function to copy a linked list with a next and random pointer.

A function copies a linked list with a next and random pointer by creating a mapping from the original nodes to their copies and then iterating through the list to assign the next and random pointers of the copies.

Write an algorithm to find the node at which the intersection of two singly linked lists begins.

An algorithm finds the node at which the intersection of two singly linked lists begins by first calculating the length of both lists, aligning them at the same start point, and then iterating until the intersection node is found.

How do you find the sum of two linked lists using Stack?

Finding the sum of two linked lists using Stack involves pushing all elements of both lists into separate stacks, popping them to sum the digits with carry, and forming a new linked list with the sum from the carried-over digits.

Write a method to reverse nodes in a linked list in groups of size 'k'.

A method reverses nodes in a linked list in groups of size 'k' by iteratively picking 'k' nodes, reversing them, and then connecting the reversed group with the rest of the list.

Can you implement a doubly linked list's insertion sort?

Implementing a doubly linked list's insertion sort involves iterating through the list, comparing each node with its predecessors, and placing it in its correct position ensuring both next and previous pointers are correctly updated.

Write a function that moves the last element to the front in a given singly linked list.

A function moves the last element to the front in a given singly linked list by traversing to the end of the list, disconnecting the last node, and setting it as the new head.

How would you remove the nth node from the end of a linked list?

Removing the nth node from the end of a linked list requires traversing the list to find the length, calculating the position of the node from the beginning, and unlinking it from the list.

Implement a function to merge k sorted linked lists into one sorted linked list.

A function merges k sorted linked lists into one sorted linked list by using a min-heap to keep track of the smallest elements of each list and linking them together to form a single sorted list.

Write a program to delete a linked list.

A program deletes a linked list by iterating through the list and deleting each node until the entire list is deleted, finally setting the head pointer to null.

Can you code an efficient algorithm to check if a linked list has a loop? If so, remove the loop.

An efficient algorithm checks if a linked list has a loop by using Floyd's cycle detection algorithm and removes the loop by finding the junction point and setting the next of the loop node to null.

How do you implement a queue using two stacks, with costly enqueues?

Implementing a queue using two stacks with costly enqueues involves using one stack for enqueuing elements and another for dequeuing, moving elements from the enqueue stack to the dequeue stack when necessary to maintain the queue order.

Stack Data Structure Interview Questions and Answers

Stack Data Structure Interview Questions provide insights into the linear data structure that follows the Last In, First Out (LIFO) principle for managing elements. Stack Data Structure Interview Questions cover essential questions that explore the fundamental operations of a stack, such as pushing (adding) an element, popping (removing) an element, and peeking (viewing the top element without removing it) from the stack.

What is a stack, and where is it used?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Stack finds usage in scenarios like function calls, undo mechanisms in software, and for solving algorithmic problems such as syntax parsing and expression evaluation.

How do you implement a stack using arrays?

To implement a stack using arrays, maintain a pointer to the top element of the stack. For push operations, increase the pointer and insert the element at the new top position. For pop operations, return the element at the top position and decrease the pointer.

Can you write a function to push an element onto a stack?

A function to push an element onto a stack adds the element to the end of the stack and updates the top pointer to point to this new element.

How do you pop an element from a stack?

To pop an element from a stack, remove the element at the top of the stack and decrement the top pointer.

Write a method to check if a stack is empty.

A method to check if a stack is empty compares the top pointer with the initial state, indicating an empty stack if they match.

How can you implement a stack using a linked list?

To implement a stack using a linked list, insert and remove elements from the same end, typically the head of the list, ensuring LIFO order is maintained.

What is the time complexity of push and pop operations in a stack?

The time complexity of push and pop operations in a stack is O(1), as these operations only involve working with the top element.

Can you code a function to return the top element of a stack without popping it?

A function to return the top element of a stack retrieves the value at the top pointer without modifying the stack's structure.

How do you reverse a string using a stack?

To reverse a string using a stack, push each character of the string onto the stack and then pop them in sequence, which reverses the order of the characters.

Write a program to evaluate a postfix expression using a stack.

A program to evaluate a postfix expression uses a stack to sequentially push operands and pop them for evaluation when an operator is encountered, pushing back the result until the expression is fully evaluated.

How do you implement two stacks in one array efficiently?

To implement two stacks in one array efficiently, divide the array from both ends, with one stack growing from the start and the other from the end, maximizing space utilization.

Can you solve the balanced parentheses problem using a stack?

The balanced parentheses problem is solved using a stack by pushing open parentheses onto the stack and popping them when a matching closing parenthesis is encountered, checking for balance throughout.

How do you design a stack that supports getMin() operation in constant time?

Design a stack to support the getMin() operation in constant time by keeping an auxiliary stack that stores the minimum element at the top after each operation.

Write a function to sort a stack using only push and pop operations.

A function to sort a stack uses a temporary stack to hold elements while the original stack is manipulated with push and pop operations to arrange the elements in sorted order.

Can you code the Tower of Hanoi problem using stacks?

The Tower of Hanoi problem can be coded using stacks by representing each peg as a stack and moving disks according to the rules, utilizing recursive stack operations.

How do you implement a queue using stacks?

A queue can be implemented using two stacks by enqueuing in one stack and dequeuing by reversing the order into the second stack, ensuring FIFO order is maintained.

Write an algorithm to find the next greater element for every element in an array using a stack.

An algorithm to find the next greater element for every element in an array pushes array indices onto a stack and pops them when a greater element is found, associating the greater element with the popped indices.

How do you check for circular dependencies in a project using a stack?

Check for circular dependencies in a project using a stack by performing a depth-first search on the dependency graph, pushing nodes onto the stack as they are visited, and detecting cycles when a node is encountered that is already in the stack.

Can you design a stack with operations on the middle element like deleteMiddle()?

Design a stack with operations on the middle element by using a doubly linked list to enable efficient access and modification of the middle element, adjusting the middle pointer as elements are added or removed.

How do you find the largest rectangular area in a histogram using a stack?

To find the largest rectangular area in a histogram using a stack, push the indices of the bars onto the stack when the current bar is higher than the bar at the top stack index and calculate areas by popping when the current bar is lower, updating the maximum area accordingly.

Queue Data Structure Interview Questions and Answers

Queue Data Structure Interview Questions encompass a collection of inquiries and elucidations aimed at evaluating a candidate's understanding and proficiency with Queue, a linear data structure. Queue operates on a First In, First Out (FIFO) principle, where the element entered first is the one to be removed first.

What is a queue in data structures?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at one end, called the rear, and removed from the other end, called the front.

How do you implement a queue using arrays?

Implement a queue using arrays by maintaining two pointers for the front and rear positions. Increase the rear pointer when adding an element and increase the front pointer when removing an element.

Can you implement a circular queue in Java?

Implement a circular queue in Java by using an array and two pointers, front and rear. Wrap around the rear to the beginning of the array when it reaches the end to utilize empty spaces.

What is the difference between a stack and a queue?

The main difference between a stack and a queue is in their ordering principles: a stack operates on a Last-In-First-Out (LIFO) principle, while a queue uses a First-In-First-Out (FIFO) principle.

How do you reverse a queue using recursion?

Reverse a queue using recursion by dequeuing an element, recursively reversing the remaining queue, and then adding the dequeued element at the rear of the queue.

Write a program to implement a priority queue.

Implement a priority queue by using a heap data structure where elements are inserted based on their priority and the element with the highest priority is always removed first.

What is a dequeue, and how do you implement it?

A dequeue (double-ended queue) is a data structure that allows the insertion and removal of elements from both the front and rear ends. Implement it using a doubly linked list to efficiently manage elements from both ends.

How do you implement a queue using two stacks?

Implement a queue using two stacks by using one stack for enqueuing elements and the other stack for dequeuing. When dequeuing, if the dequeue stack is empty, transfer all elements from the enqueue stack to the dequeue stack.

Explain the concept of a blocking queue in multithreading.

A blocking queue in multithreading is a queue that blocks the dequeue operation until an element becomes available and blocks the enqueue operation if the queue reaches its capacity, ensuring thread safety.

Write an algorithm to generate binary numbers from 1 to N using a queue.

Generate binary numbers from 1 to N using a queue by enqueuing the initial binary number "1" and then repeatedly removing the front element, appending "0" and "1" to it, and enqueuing these new binary numbers until N numbers are generated.

How do you perform a level order traversal of a binary tree using a queue?

Perform a level order traversal of a binary tree using a queue by enqueueing the root, then repeatedly dequeuing an element, printing it, and enqueuing its left and right children until the queue is empty.

Can you design a queue such that getMinimum() function has a constant time complexity?

Design a queue with a constant time complexity for getMinimum() by using two auxiliary data structures: a primary queue for enqueue and dequeue operations and an auxiliary deque to maintain the minimum element.

Implement a function to check if a queue is palindrome.

Check if a queue is palindrome by using a stack to reverse half of the queue's elements, then comparing these elements with the second half of the queue as they are dequeued.

How do you find the circular tour that visits all petrol pumps using a queue?

Find the circular tour that visits all petrol pumps using a queue by enqueueing petrol pump positions and their petrol amounts, then check if a complete tour is possible by maintaining a running sum of petrol.

Write a program to sort a queue without using extra space.

Sort a queue without using extra space by repeatedly finding the minimum element in the queue, dequeuing, and enqueuing elements as needed until the queue is sorted.

How do you implement a queue using a single linked list?

Implement a queue using a singly linked list by maintaining two pointers, one for the front of the queue and one for the rear, allowing for efficient enqueue and dequeue operations.

Can you solve the 'truck tour' problem using queues?

Solve the 'truck tour' problem using queues by enqueueing all petrol pumps with their petrol and distance to the next pump, then calculating if a truck can complete the circuit by starting at different pumps.

Write a function that merges k sorted queues into one sorted queue.

Merge k sorted queues into one sorted queue by using a min-heap to efficiently find and remove the smallest element among the front elements of all queues until all queues are empty.

How do you implement a sliding window maximum algorithm using a dequeue?

Implement a sliding window maximum algorithm using a dequeue by maintaining a dequeue of indices for elements within the current window, ensuring the front of the dequeue always contains the index of the maximum element.

Design and implement a data structure for the Least Recently Used (LRU) cache using a queue.

Design an LRU cache using a queue by pairing each element with its last access time, and when the cache reaches its capacity, dequeuing the least recently used element before enqueuing a new element.

Tree Data Structure Interview Questions and Answers

Tree Data Structure Interview Questions explore the intricate details and complexities of tree data structures, which are fundamental components in the field of computer science and software engineering. Tree Data Structure Interview Questions address various questions about tree data structures, ranging from basic concepts to more advanced topics such as binary trees, binary search trees, AVL trees, and B-trees.

What is a tree data structure, and where is it used?

A tree data structure is a hierarchical model that consists of nodes with a parent-child relationship, used in databases, and file systems, and for efficient data searching and sorting.

How do you traverse a binary tree using in-order traversal?

Traverse a binary tree using in-order traversal by visiting the left subtree first, then the current node, and finally the right subtree to achieve a sorted sequence of elements for binary search trees.

Write a program to find the height of a binary tree.

Find the height of a binary tree by recursively calculating the maximum depth of the left and right subtrees and adding one to account for the root node.

Can you explain the difference between binary trees and binary search trees?

In the binary search trees, each node has a value greater than all values in its left subtree and less than all values in its right subtree, facilitating efficient search operations.

How do you implement a binary search tree insertion operation?

Implement a binary search tree insertion operation by comparing the new value with the current node's value and recursively inserting it into the left subtree if it's less, or the right subtree if it's greater, ensuring the binary search tree property is maintained.

Write a function to check if a binary tree is balanced.

Check if a binary tree is balanced by ensuring that the height difference between the left and right subtrees of every node is no more than one.

How can you convert a binary tree into a doubly linked list?

Convert a binary tree into a doubly linked list by performing an in-order traversal and adjusting pointers to link nodes in a way that they form a doubly linked list.

What is a binary heap, and how do you perform an insert operation?

A binary heap is a complete binary tree that maintains the heap property; perform an insert operation by adding the element at the bottom and rightmost position, then heapify up to maintain the heap structure.

Explain the process of deleting a node from a binary search tree.

Delete a node from a binary search tree by locating the node, then replacing it with its in-order predecessor (the maximum-value node in its left subtree) or in-order successor (the minimum-value node in its right subtree) if the node has two children, and adjusting pointers to maintain the binary search tree properties.

How do you find the lowest common ancestor of two nodes in a binary search tree?

Find the lowest common ancestor of two nodes in a binary search tree by traversing from the root and choosing the path based on the values of the nodes being compared until finding the node where one value is on one side and the other is on the opposite side.

Write a program to perform level-order traversal of a binary tree.

Perform level-order traversal of a binary tree by using a queue to hold nodes and their children as you traverse the tree, ensuring that nodes are visited level by level.

How do you serialize and deserialize a binary tree?

Serialize a binary tree by converting it into a string of node values separated by commas, including null values for empty nodes, and deserialize by reconstructing the tree from this string using a queue to maintain the order of nodes.

What are AVL trees, and how do you perform rotations to balance them?

AVL trees are self-balancing binary search trees that maintain a balance factor of -1, 0, or 1 for every node and perform rotations—single or double, left or right—to restore balance when inserting or deleting nodes.

Can you implement a trie (prefix tree) and its insert and search operations?

Implement a trie (prefix tree) by using a tree-like data structure where each node represents a character of a string, and insert and search operations traverse the tree based on the characters of the string being inserted or searched.

How do you find the maximum path sum in a binary tree?

Find the maximum path sum in a binary tree by calculating, for each node, the maximum path sum that includes the node and possibly one of its subtrees, and updating the global maximum based on these values.

Write a function to mirror a binary tree.

Mirror a binary tree by swapping the left and right children of every node in the tree, either recursively or iteratively, to create a mirror image.

What is a segment tree, and how do you build one?

A segment tree is a binary tree used for storing intervals or segments, built by recursively dividing the segment into two halves until reaching individual elements, and storing information like sums or minimums at each node.

How do you check if a binary tree is a valid binary search tree?

Check if a binary tree is a valid binary search tree by ensuring, through in-order traversal, that the values of nodes are in ascending order, indicating that each node adheres to the binary search tree property.

Explain the concept of a Fenwick tree, or binary indexed tree, and its use case.

A Fenwick tree, or binary indexed tree, is a data structure that provides efficient methods for calculating prefix sums in a list of numbers, used in scenarios requiring frequent updates and queries for cumulative sums.

Write a program to find the kth smallest element in a binary search tree.

Find the kth smallest element in a binary search tree by performing an in-order traversal and maintaining a count of visited nodes, stopping when the count reaches k to return the current node's value.

Binary Search Tree Data Structure Interview Questions and Answers

Binary Search Tree Data Structure Interview Questions is a guide that delves into the intricacies of Binary Search Trees (BST), a pivotal data structure in computer science. Binary Search Tree Data Structure Interview Questions cover questions ranging from basic concepts to more advanced operations and properties of Binary Search Trees.

What defines a binary search tree (BST)?

A binary search tree (BST) is defined as a binary tree where each node has a value greater than all values in its left subtree and less than or equal to all values in its right subtree.

How do you insert a value into a BST?

Insert a value into a BST by comparing it with the root, recursively inserting it into the left subtree if the value is less, or into the right subtree if it is greater, until finding a leaf position where the new value can be added as a child node.

Write a program to delete a node from a BST.

To delete a node from a BST, find the node, then if it has two children, find its in-order successor (the smallest node in the right subtree), swap values, and delete the successor node; if the node has one or no child, adjust pointers to bypass the deleted node.

How do you search for a value in a BST?

Search for a value in a BST by starting at the root and recursively searching the left or right subtree based on whether the value is less than or greater than the current node's value until finding the value or reaching a leaf node.

What is the inorder predecessor and successor in a BST?

The inorder predecessor in a BST is the largest value node in the left subtree of the given node, and the inorder successor is the smallest value node in the right subtree of the given node.

Can you explain how to find the minimum and maximum value in a BST?

Find the minimum value in a BST by traversing down the left subtree until reaching the last node. Similarly, find the maximum value by traversing down the right subtree until reaching the last node.

Write a function to check if a binary tree is a BST.

Check if a binary tree is a BST by verifying that for every node, all values in its left subtree are less, and in its right subtree are greater, using an in-order traversal to ensure the values are sorted.

How do you find the height of a BST?

Find the height of a BST by calculating the maximum depth from the root to the furthest leaf node, using a recursive function that returns the greater height of the left or right subtree plus one.

What are the advantages of using a BST over other data structures?

The advantages of using a BST include efficient search, insert, and delete operations due to the tree's structured organization, and facilitating binary search methods with an average time complexity of O(log n).

How do you find the kth smallest element in a BST?

Find the kth smallest element in a BST by performing an in-order traversal and maintaining a count of visited nodes until reaching the kth element.

Can you implement a function to convert a sorted array to a balanced BST?

Convert a sorted array to a balanced BST by selecting the middle element as the root, recursively doing the same for the left half and right half of the array to construct the left and right subtrees.

Explain the process of balancing a BST.

Balance a BST by rotating nodes to ensure that the difference in heights between the left and right subtrees of any node does not exceed one, using rotations to restructure the tree.

How do you count the number of nodes in a BST that fall within a given range?

Count the number of nodes in a BST that fall within a given range by traversing the tree and incrementing a counter for each node whose value lies within the range, using a recursive or iterative approach.

Write a program to check if two BSTs are identical.

Check if two BSTs are identical by comparing their structures and node values recursively, ensuring that for every node in one tree, there is a corresponding node with the same value in the other tree.

How can you merge two BSTs into a single BST?

Merge two BSTs into a single BST by performing an in-order traversal of both trees to create sorted arrays, merging these arrays into a single sorted array, and then constructing a balanced BST from the merged array.

What is the time complexity of inserting an element into a BST?

The time complexity of inserting an element into a BST is O(log n) on average, assuming the tree is balanced, but can degrade to O(n) if the tree becomes skewed.

How do you perform a level-order traversal on a BST?

Perform a level-order traversal on a BST by using a queue to keep track of nodes at each level, enqueueing the root, and then continuously removing a node from the queue, visiting it, and enqueuing its left and right children until the queue is empty.

Can you explain the concept of a self-balancing BST and give examples?

A self-balancing BST is a binary search tree that automatically maintains its balance to ensure operations remain efficient. Examples include AVL trees and Red-Black trees, which use rotations to maintain a balanced height.

Write a function to determine if a BST is balanced.

Determine if a BST is balanced by ensuring that for every node, the height difference between the left and right subtrees is no more than one, using a recursive function that checks the balance of each subtree.

How do you efficiently find the lowest common ancestor (LCA) of two nodes in a BST?

Find the lowest common ancestor of two nodes in a BST by starting from the root and moving toward the left or right child depending on the nodes’ values until finding a node where one node is on one side and the other node is on the opposite side, indicating the LCA.

Graph Data Structure Interview Questions and Answers

Graph Data Structure Interview Questions cover a range of topics essential for understanding and implementing graphs, a fundamental data structure in computer science. Graph Data Structure Interview Questions dive into the properties, types, and algorithms associated with graphs.

What is a graph data structure, and what are its types?

A graph data structure consists of a set of vertices (nodes) connected by edges (links), and its types include undirected graphs, directed graphs, weighted graphs, and unweighted graphs.

How do you represent graphs in computer memory?

Represent graphs in computer memory using adjacency lists, which list all nodes connected to each node, or adjacency matrices, a 2D array where matrix[i][j] indicates the presence or absence of an edge between i and j.

Write a program to implement graph traversal using BFS.

Implement graph traversal using BFS (Breadth-First Search) by starting at a chosen node, exploring all its neighbors at the current depth level before moving on to the nodes at the next depth level, using a queue to manage the order of exploration.

Can you implement DFS for a graph represented using an adjacency list?

Implement DFS (Depth-First Search) for a graph using an adjacency list by starting at a selected node, recursively exploring each branch before backtracking, and using a stack (explicit or via recursion) to keep track of the vertices.

What is the difference between a tree and a graph?

The difference between a tree and a graph is that a tree is a special form of a graph that is connected and acyclic, with a single path between any two vertices, whereas graphs can have cycles, and multiple paths between vertices, and may not be connected.

How do you detect a cycle in a directed graph?

Detect a cycle in a directed graph using Depth-First Search (DFS) by keeping track of visited vertices and the recursion stack. A cycle exists if a vertex is reached that is already in the recursion stack.

Write an algorithm to find the shortest path between two vertices in a graph.

Find the shortest path between two vertices in a graph using Dijkstra's algorithm, which progressively extends the shortest path from the starting vertex to all other vertices by exploring the nearest unvisited vertex.

What is a weighted graph, and how do you represent it?

A weighted graph is a graph where each edge has a numerical value (weight) associated with it, representing costs like distance or time. Represent it using adjacency lists with weights or adjacency matrices where the elements are weights instead of booleans.

Can you explain the Dijkstra algorithm for finding the shortest path?

The Dijkstra algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights by using a priority queue to select the closest unvisited vertex and updating the paths to its neighbors if shorter paths are found.

How do you implement a graph using adjacency matrices?

Implement a graph using adjacency matrices by creating a 2D array where the element at row i and column j indicates whether an edge exists between vertex i and vertex j, with the value representing the edge weight in weighted graphs.

Write a function to check if a graph is bipartite.

Check if a graph is bipartite by attempting to color each vertex using two colors in such a way that no two adjacent vertices share the same color, using BFS or DFS to propagate the coloring.

What is a spanning tree, and what is a minimum spanning tree?

A spanning tree is a subset of a graph that includes all the vertices connected by the minimum number of edges required to maintain connectivity. A minimum spanning tree is a spanning tree with the least total edge weight.

Can you implement Kruskal’s algorithm to find a minimum spanning tree?

Implement Kruskal’s algorithm to find a minimum spanning tree by sorting all edges in non-decreasing order of their weight and adding them to the spanning tree one by one, ensuring that no cycles are formed, using a disjoint-set data structure to efficiently check for cycles.

How do you find strongly connected components in a graph?

Find strongly connected components in a graph using Kosaraju’s algorithm or Tarjan's algorithm, which involves DFS traversals to explore the connectivity and structure of the graph.

Write a program to perform topological sorting in a DAG (Directed Acyclic Graph).

Perform topological sorting in a DAG by using DFS to recursively visit nodes, pushing a node onto a stack only after all its dependent nodes have been visited, thereby ensuring that nodes are processed in dependency order.

What is the Bellman-Ford Algorithm, and how does it differ from Dijkstra's?

The Bellman-Ford Algorithm calculates the shortest paths from a single source vertex to all other vertices in a weighted graph, including those with negative weights, unlike Dijkstra's, which requires non-negative edge weights.

How do you find all pairs' shortest paths in a graph?

Find all pairs shortest path in a graph using the Floyd-Warshall algorithm, which iteratively updates distances between pairs of vertices through an intermediate vertex, considering all vertices as intermediate points.

Write an algorithm to detect negative cycles in a graph.

Detect negative cycles in a graph using the Bellman-Ford algorithm by performing one extra iteration after finding the shortest paths. If any distance is updated in this extra iteration, a negative cycle exists.

Can you explain the Floyd-Warshall algorithm and its use case?

The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in a graph, handling negative weights. It iteratively improves the path lengths between every pair using each vertex as an intermediate point.

How do you implement Prim's algorithm for finding a minimum spanning tree?

Implement Prim's algorithm for finding a minimum spanning tree by starting from an arbitrary vertex and growing the spanning tree one edge at a time, choosing the smallest edge connecting the tree to a vertex not yet in the tree, and using a priority queue to select the smallest edge efficiently.

Trie Data Structure Interview Questions and Answers

Trie data structure is a specialized tree used to store associative data structures. Trie Data Structure Interview Questions cover the fundamental aspects, applications, and operations related to the trie data structure, providing clear and concise answers to common interview questions.

What is a Trie, and what are its applications?

A Trie is a tree-like data structure that stores a dynamic set of strings, where the keys are usually characters. Its applications include autocomplete, spell-checking, IP routing, and pattern matching.

How do you insert a word into a Trie? Provide a code example.

Insert a word into a Trie by creating nodes for each character of the word if they do not already exist, marking the last node as the end of the word.

Can you explain how to search for a word in a Trie?

Search for a word in a Trie by traversing the Trie from the root, following the nodes corresponding to each character of the word. The search is successful if it reaches a node that marks the end of the word.

Write a function to delete a word from a Trie.

To delete a word from a Trie, recursively remove nodes from the end if they do not lead to any other words, ensuring not to disrupt other words in the Trie.

How do you implement auto-suggestions based on a prefix search in a Trie?

Implement auto-suggestions by performing a prefix search to find the node corresponding to the last character of the prefix, then recursively find all words that branch from that node, collecting suggestions.

What is the time complexity of inserting and searching for a word in a Trie?

The time complexity of inserting and searching for a word in a Trie is O(m), where m is the length of the word. This efficiency is due to the direct path followed for each character in the word.

How do you count the number of words in a Trie?

Count the number of words in a Trie by performing a depth-first search (DFS) and counting nodes that mark the end of a word, ensuring to traverse each possible path in the Trie.

Can you design a Trie to support wildcard searches?

Design a Trie to support wildcard searches by modifying the search function to allow a special wildcard character to match any character at a certain position, recursively searching all possible paths when a wildcard is encountered.

How do you store and retrieve a large dictionary efficiently using a Trie?

Store and retrieve a large dictionary efficiently using a Trie by utilizing the structure's ability to share prefixes, significantly reducing memory usage compared to storing each word independently, and allowing for quick lookups.

Write a program to find the longest common prefix among a set of strings using a Trie.

Find the longest common prefix among a set of strings by inserting all the strings into a Trie and then traversing the Trie from the root until reaching a node that has more than one child or is the end of a word, concatenating the characters traversed.

Ideal structure for a 60‑min interview with a software engineer

Get 15 handpicked jobs in your inbox each Wednesday

Build your dream team

1-stop solution to hire developers for full-time or contract roles.

Find your dream job

Handpicked opportunities with top companies for full-time and contract jobs.

Interview Resources

Want to upskill further through more interview questions and resources? Check out our collection of resources curated just for you.

Find Your Dream Job

Discover exciting roles at fast growing startups, tailored to your unique profile. Get started with Flexiple now!

• Elasticsearch
• Google Cloud
• React Native
• Ruby on Rails

EnjoyMathematics

Steps of Problem Solving in Data Structures and Algorithms

Every solution starts with a strategy, and an algorithm is a strategy for solving a coding problem. So, we must learn to design an efficient algorithm and translate this 'algorithm' into the correct code to get the job done.

But there are many coding problems available in data structures and algorithms, and most of the time, these problems are new to us. So as programmers, we need to develop ourselves as confident problem-solvers who are not intimidated by the difficulty of the given problem. 

Our long-term goal should be simple: Learn to design correct and efficient code within a given time. As we practice more and more, we will gain experience in problem-solving, and our work will become easier. Here are some essential skills that we should practice for every DSA problem:

• Developing an approach to understanding the problem
• Thinking of a correct basic solution
• Designing step-by-step pseudocode solutions
• Analyzing the efficiency of a solution
• Optimizing the solution further
• Transforming pseudocode into correct code

Now, the critical question would be: Is there a well-defined, guided strategy to approach and solve a coding problem? If yes, then what are the critical steps? Let's think and explore!

Step 1: Understanding the problem

Solving a problem requires a clear understanding of the problem. Unfortunately, sometimes we read only the first few lines and assume the rest of the problem or ignore this step because we have seen something similar in the past. We should view these as unfair practices and develop a clear approach to understanding problems.

During problem-solving, every small detail can help us design an efficient solution. Sometimes, a small change in the question can alter the solution approach. Taking extra time to understand the problem will give us more confidence later on. The fact is, we never want to realize halfway through that we misunderstood the problem.

It doesn't matter if we have encountered a question before or not; we should read the question several times. So, take a paper and write down everything while going through the problem. Exploring some examples will also help us clarify how many cases our algorithm can handle and the possible input-output patterns. We should also explore scenarios for large input, edge cases, and invalid input.

Sometimes, it is common for problem descriptions to suffer from these types of deficiencies:

• The problem description may rely on undefined assumptions
• The problem description may be ambiguous or incomplete
• The problem description may have various contradictions.

These deficiencies may be due to the abstract explanation of the problem description in our natural languages. So, it is our responsibility to identify such deficiencies and work with the interviewer or problem provider to clarify them. We should start by seeking answers to the following questions:

• What are the inputs and outputs?
• What type of data is available?
• What is the size or scale of the input?
• How is the data stored? What is the data structure?
• Are there any special conditions or orders in the data?
• What rules exist for working with the data?

Step 2: Thinking of a correct basic solution

The best approach would be to think of a correct solution that comes immediately to our mind. It does not matter even if it is an inefficient approach. Having a correct and inefficient answer is much better than an incorrect solution or significant delay in finding the solution. This could help us in so many ways:

• Help us to build good confidence or motivation at the start.
• Provide an excellent point to start a conversation with the interviewer.
• Sometimes, it provides a hint to improve efficiency by reducing some loops, removing some intermediate steps, or performing some operations efficiently.

Here are some examples of brute force patterns: three nested loops, two nested loops, solution using extra memory, solution using sorting, double traversal in the binary tree, considering all sub-arrays or substrings, exhaustive search, etc.

After thinking and communicating the brute force idea, the interviewer may ask for its time and space complexity. We need to work on paper, analyze each critical operation, and write it in the form of Big-O notation. Clear conceptual idea of time and space complexity analysis is essential at this stage.

Step 3: Designing efficient solution with pseudocode

This is a stage to use the best experience of DSA problem-solving and apply various problem-solving strategies . One practical truth is: moving from a basic algorithm to the most efficient algorithm is a little difficult in a single step. Each time, we need to optimize the previous algorithm and stop when there is no further optimization possible. Revisiting the problem description and looking for some additional information can help a lot in further optimization. For example:

• If the input array is sorted or nearly sorted, we can apply optimized algorithms such as a single loop, two-pointer approach, or binary search.
• If we need to find a subarray of size k, we can use the sliding window technique, which involves maintaining a window of size k over the array and sliding it over the elements to find the desired subarray.
• When searching is a critical operation, we can use optimized search algorithms or data structures like binary search, BST, or hash table.
• For optimization problems, we can consider divide and conquer, dynamic programming, or greedy algorithm approaches.
• If we need to find a solution with a given constraint, we can use backtracking.
• When working with string data, direct address tables, hash tables, or trie data structures can be useful.
• To frequently access and process max or min elements, we can use a priority queue or heap data structure.
• For dictionary operations such as insert, search, and delete, we can use hash tables or BST.
• If we need to perform both dictionary and priority queue operations, a BST may be useful.
• For range query operations such as range max, range min, or range sum, we can use data structures like segment trees or Fenwick trees.
• To process binary tree data level by level, BFS or level-order traversal can be used.

The idea would be simple: we should learn the use case of efficient problem-solving patterns on various data structures. Continuously thinking, analyzing, and looking for a better solution is the core idea. 

Here are some best examples of problems where several levels of optimisations are feasible. Practicing such types of coding questions helps a lot in building confidence.

Find equilibrium index of an array

• Using nested loops: Time = O(n²), Memory = O(1)
• Using prefix sum array: Time = O(n), Memory = O(n)
• Using single scan: Time = O(n), Memory = O(1)

Trapping rain water

• Using Dynamic Programming: Time = O(n), Memory = O(n)
• Using Stack: Time = O(n), Memory = O(n)
• Using two pointers: Time = O(n), Memory = O(1)

Check for pair with a given sum

• Using sorting and binary search: Time = O(nlogn), Memory = O(1)
• Using sorting and Two Pointers: Time = O(nlogn), Memory = O(1)
• Using a Hash Table: Time = O(n), Memory = O(n)

Find the majority element in an array

• Using two nested loops: Time = O(n²), Memory = O(1)
• Using Sorting: Time = O(nlogn), Memory = O(1)
• Using the divide and conquer: Time = O(nlogn), Memory = O(logn)
• Using Bit Manipulation: Time = O(n), Memory = O(1)
• Using Randomisation: Time = O(nlogn), Memory = O(1) Note: If value of n is very large.
• Boyer-Moore Voting Algorithm: Time = O(n), Memory = O(1)

Maximum Subarray Sum

• Using three nested loops: Time = O(n^3), Memory = O(1)
• Using two nested loops: Time = O(n^2), Memory = O(1)
• Using divide and conquer: Time = O(nlogn), Memory = O(logn)
• Using dynamic programming: Time = O(n), Memory = O(n)
• Kadane algorithm: Time = O(n), Memory = O(1)

Before you jump into the end-to-end code implementation, it’s good practice to write pseudocode on paper. It would be helpful in defining code structure and critical operations. Some programmers skip this step, but writing the final code becomes easier when we have well-designed pseudocode.

Step 4: Transforming pseudocode into a clean, correct, and optimized code

Finally, we need to replace each line of pseudocode with actual code in our favorite programming languages like C++, Java, Python, C#, JavaScript, etc. Never forget to test actual code with sample test data and check if the actual output is equal to the expected output. When writing code in your interviews, discuss sample data or test cases with the interviewer.

Simplifying and optimizing the code may require a few iterations of observation. We need to ask these questions once we are done writing the code: 

• Does this code run for every possible input, including the edge cases?
• Can we optimize the code further? Can we remove some variables or loop or some extra space?
• Are we repeating some steps a lot? Can we define it separately using another function?
• Is the code readable or written with a good coding style?

Enjoy learning, Enjoy coding, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced courses and blogs.

• Data Science
• Trending Now
• Data Structures
• System Design
• Foundational Courses
• Practice Problem
• Machine Learning
• Data Science Using Python
• Web Development
• Web Browser
• Design Patterns
• Software Development
• Product Management
• Programming

Top 50 Data Structures MCQs with Answers

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Insertion Sort

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)

log(2*n) -1

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node Q from the list?

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?

Consider the following conditions:

 (a)The solution must be feasible, i.e. it must satisfy all the supply and demand constraints. 

(b)The number of positive allocations must be equal to m1n21, where m is the number of rows and n is the number of columns. 

(c)All the positive allocations must be in independent positions. 

The initial solution of a transportation problem is said to be non-degenerate basic feasible solution if it satisfies: Codes:

(a) and (b) only

(a) and (c) only

(b) and (c) only

(a), (b) and (c)

• In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
• In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
• Both of the above
• None of the above
• Managing function calls
• The stock span problem
• Arithmetic expression evaluation
• All of the above

Question 10

There are 50 questions to complete.

Explore Insights, Tips and Articles with HeyCoach Blogs

HeyCoach's easy-to-follow blogs, packed with tips and tricks to help you excel in the tech industry.

Top 50 DSA Practice Problems to Sharpen Your Skills

Mastering Data Structures and Algorithms (DSA) is crucial for every software developer, not just for cracking coding interviews but also for solving real-world problems efficiently. Practicing DSA problems regularly enhances problem-solving skills and prepares you for various scenarios. This article presents the top 50 DSA practice problems that cover a broad spectrum of essential data structures and algorithms. These problems are tailored to improve your analytical thinking and provide a deep understanding of fundamental concepts. Let’s dive into these challenges to boost your skills in DSA.

1. Find the Maximum Subarray Sum (Kadane’s Algorithm)

Given an array of integers, find the contiguous subarray with the maximum sum.

2. Two Sum Problem

Find two numbers in a given array that add up to a specific target number.

3. Merge Two Sorted Arrays

Given two sorted arrays, merge them into a single sorted array.

4. Rotate Array

Rotate an array to the right by a given number of steps.

5. Find the Duplicate Number in an Array

Identify the duplicate number in an array containing multiple elements where one number is repeated.

6. Find the Missing Number in an Array

Given an array of integers containing numbers from 1 to n, find the one missing number.

7. Longest Palindromic Substring

Find the longest substring in a given string that reads the same forwards and backwards.

8. Reverse a String

Reverse a given string using iterative and recursive methods.

9. Check if Two Strings are Anagrams

Determine if two strings are anagrams of each other by checking character frequencies.

10. Valid Parentheses Checker

Check if a given string containing only parentheses is valid by ensuring proper opening and closing.

11. Binary Tree Inorder Traversal

Implement an inorder traversal of a binary tree both recursively and iteratively.

12. Find the Lowest Common Ancestor in a Binary Search Tree

Given a binary search tree and two nodes, find their lowest common ancestor.

13. Binary Tree Level Order Traversal

Traverse a binary tree level by level from top to bottom.

14. Depth-First Search (DFS) on a Graph

Implement DFS to explore all nodes in a graph.

15. Breadth-First Search (BFS) on a Graph

Use BFS to traverse a graph starting from a specific node.

16. Find the Shortest Path in a Binary Maze

Determine the shortest path in a binary maze from a starting point to an endpoint using BFS.

17. Detect a Cycle in a Directed Graph (Kahn’s Algorithm)

Use Kahn’s Algorithm to detect cycles in a directed graph.

18. Longest Increasing Subsequence

Find the longest increasing subsequence in a given array of integers.

19. 0/1 Knapsack Problem

Solve the classic 0/1 knapsack problem using dynamic programming.

20. Fibonacci Sequence using Dynamic Programming

Implement the Fibonacci sequence calculation using dynamic programming for efficiency.

21. Minimum Coin Change Problem

Find the minimum number of coins required to make a given amount using a set of denominations.

22. Edit Distance Between Two Strings

Calculate the minimum number of edits (insertions, deletions, or substitutions) required to transform one string into another.

23. Reverse a Linked List

Reverse a singly linked list using iterative and recursive methods.

24. Detect a Cycle in a Linked List (Floyd’s Cycle Detection Algorithm)

Identify if a linked list has a cycle using the Tortoise and Hare method.

25. Merge Two Sorted Linked Lists

Merge two sorted linked lists into one sorted linked list.

26. Find the Intersection Point of Two Linked Lists

Find the node where two singly linked lists intersect.

27. Find the Middle of a Linked List

Locate the middle node of a linked list in one pass using the slow and fast pointer technique.

28. Implement a Stack using Queues

Use two queues to implement a stack data structure.

29. Implement a Queue using Stacks

Use two stacks to implement a queue data structure.

30. Design a Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

31. Find the Largest Rectangle in a Histogram

Given a histogram, find the largest rectangle that can be formed with consecutive bars.

32. Implement Binary Search

Implement binary search on a sorted array to find a target value.

33. Find a Peak Element in an Array

Identify a peak element in an array where the element is greater than its neighbors.

34. Implement Quick Sort

Sort an array using the quick sort algorithm.

35. Implement Merge Sort

Implement merge sort to sort an array efficiently.

36. Heap Sort Algorithm

Use heap data structure to sort an array using heap sort.

37. Find the Kth Largest Element in an Array

Find the kth largest element in an unsorted array using a heap.

38. Solve the N-Queens Problem

Place N queens on an N×N chessboard such that no two queens threaten each other.

39. Sudoku Solver using Backtracking

Solve a Sudoku puzzle using backtracking.

40. Generate Valid Parentheses Combinations

Generate all combinations of well-formed parentheses given a number of pairs.

41. Find All Permutations of a String

Generate all possible permutations of a given string.

42. Combination Sum Problem

Find all unique combinations in a set of candidate numbers where the chosen numbers sum to a target.

43. Word Search in a 2D Grid

Given a 2D grid of letters, check if a given word exists in the grid.

44. Topological Sort in a Directed Graph

Perform a topological sort on a directed acyclic graph (DAG).

45. Find the Diameter of a Binary Tree

Calculate the longest path between any two nodes in a binary tree.

46. Check if a Binary Tree is a Valid Binary Search Tree

Verify if a binary tree meets the conditions of a binary search tree (BST).

47. Convert Sorted Array to Binary Search Tree

Convert a sorted array into a balanced binary search tree.

48. Design a LRU Cache

Implement an LRU (Least Recently Used) cache data structure with O(1) operations.

49. Find the Median of Two Sorted Arrays

Find the median value of two sorted arrays combined.

50. Longest Common Subsequence

Find the longest subsequence common to two given strings.

Solving these DSA problems will make you prepared for interviews and will also help in improving your coding skills. The goals of some of the problems are as follows, every problem is a chance to develop problem-solving skills and learn more about various sorts of data structures and algorithms. Solving the following DSA practice problems are significant as they prepare a candidate to solve similar problems without stress.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Java remains one of the most popular languages around the world, especially in financial fields. Companies like Goldman Sachs, eBay, Google , and Microsoft all hire Java developers.

Today, we’ll help you prepare for your next job interview at these and other popular companies by reviewing 50 of the most common Java data structure interview questions and answers.

By the end, you’ll have all the experience you need to answer the data structure questions that make up the bulk of most interviews.

Here’s what we’ll look at today:

• Array Data Structure Questions

Linked List Data Structure Questions

String data structure questions.

Stack and Queue Data Structure Questions

Tree Data Structure Questions

What to learn next

Answer any Java interview problem by learning the patterns behind common questions.

Solution and Explanation :

Time Complexity : O ( n + m ) O(n + m) O ( n + m ) where n and m are the sizes of arr1 and arr2 .

In the solution above, we start by creating a new empty array of the size equal to the combined size of both input arrays.

Starting from the index 0 individually compare the elements at corresponding indexes of both arrays.

Place the element with a lower value in the resultant array, and increment the index of the array where you find the smallest element.

Keep repeating this until you hit the end of one array. Move the elements of the other array into the resultantArray as it is.

7. Find Two Numbers that Add up to n

Create a method int[] findSum(int[] arr, int n) that takes an integer array arr and returns an array of the two integer elements that add up to integer n .

If there are multiple, return only one. If there is no such pair, return the original array.

Time Complexity : O ( n l o g n ) O(nlogn) O ( n l o g n )

The best way to solve this is by first sorting the array.

Here, we use QuickSort to sort the array first. Then using two variables, one starting from the first index of the array and the second from size−1 index of the array.

If the sum of the elements on these indexes of the array is smaller than the given value n , then increment index from the start else decrement index from the end until the given value n is equal to the sum.

Store the elements on these indexes in the result array and return it.

8. Find Minimum Value in Array

Create a method int findMinimum(int[] arr) that takes an array and returns the smallest element within the array.

Time Complexity : O ( n ) O(n) O ( n )

Start with the first element, which is 9 in this example, and save it in minimum as the smallest value.

Then, iterate over the rest of the array and compare the minimum to each element.

If any element is smaller than the minimum , then set minimum to that element. By the end of the array, the number stored in the minimum will be the smallest integer in the whole array.

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

9. Rearrange Positive & Negative Values

Create the method void reArrange(int[] arr) that takes an integer array and returns the same array sorted with all negative integers to the left of the middle element and all positive integers to the right.

In this solution, we rearrange the elements within the array rather than create a new array. To do this, we keep two variables i and j . Both of them are 0 initially.

i iterates over the array while j keeps track of the position where the next encountered negative number will be placed.

When we come across a negative number, the values at i and j indexes are swapped, and j is incremented. This continues until the end of the array is reached.

10. Right Rotate the Array by One Index

Create the method void rotateArray(int[] arr) which takes an array of integers and rotates the position of each element one to the right. The right-most element will rotate to become the left-most element.

To rotate the array towards the right, we have to move the array elements towards the right by one index.

This means every element stored at index i will be moved to i + 1 position.

However, if we start shifting elements from the first element of the array, then the element at last index arr[arr.length - 1] is overwritten.

We fix this by saving the last element of the array in the variable lastElement .

Then we start shifting elements from index i - 1 to i , where the initial value of i will be arr.length - 1 , and we will keep shifting the elements until i is greater than 0 .

When the loop ends, we store the value of lastElement in arr[0] .

11. Difference between Arrays and Linked Lists

What is the difference between Arrays and Linked Lists?

12. Singly Linked List

What makes Singly Linked Lists unique?

13. Mystery Code

What does the following fragment of code do?

14. Circular Linked List

What is a circular linked list?

15. Linked List Storage

Are elements in a linked list stored consecutively in memory?

Answer any Java interview problem by learning the patterns behind common questions

16. Insertion in a Singly Linked List (insert at End)

Create the method void insertAtEnd(T data) that will take a generic type T value called data and insert that value at the end of a linked list.

Solution and Explanation

If the list is empty, the situation is exactly like insertion at the head.

Otherwise, we can use a loop to reach the tail of the list and set our new node as the nextNode of the last node.

17. Search in a Singly Linked List

Create the function searchNode (T data) that takes a generic type T value and searches the elements of our Singly Linked List for a node that matches T .

If it is within the linked list, return true . If value T is not in in the linked list, return false

In this function, we traverse through the list and check whether the currentNode’s value of data matches the searched value data .

If it does, we will return True . Otherwise, we will return False .

18. Return the Nth node from End

Create the method Object nthElementFromEnd(SinglyLinkedList<T> list, int n) that takes a linked list and returns the n th element from the end of the linked list.

In the above solution, we first use the getter function list.getSize() to access the length of the list. Then we find the node which is at x position from the start using the equation:

P o s i t i o n = s i z e − n + 1 Position = size - n + 1 P os i t i o n = s i ze − n + 1

19. Reverse a Linked List

Create the method public static <T> void reverse(SinglyLinkedList<T> list) that will take a linked list as input and reverse its contents such that the final element from the input linked list is the first element of the output linked list.

The loop that iterates through the list is the key to this solution. For any current node, its link with the previous node is reversed, and the variable next stores the next node in the list:

• Store the current node’s nextNode in next
• Set current node’s nextNode to previous (reversal)
• Make the current node the new previous so that it can be used for the next iteration
• Use next to move on to the next node

In the end, we simply point the head to the last node in our loop.

20. Find if Doubly Linked-list is a Palindrome

Create the method isPalindrome(DoublyLinkedList<T> list) that takes a doubly linked list and returns if the list is a palindrome (the same if written in reverse).

It will return true if the linked list is a palindrome, or false if it’s not.

We start by taking pointers to headNode and tailNode ( lines 3-4 ).

Next, we check for a corner-case, when the linked list is empty, an empty linked-list is a palindrome so we return true ( lines 5-7 ).

Then, we simply traverse the linked list from both ends simultaneously and see if the traversals result in the same sequence of values ( lines 8-14 ).

If that is not the case, the linked list is not a palindrome ( lines 9-11 ), otherwise, it is.

21. Creating a String Object

Do both of these statements create a string?

22. Storage of Strings

Where are strings stored in memory?

23. Advantage of Immutability

What is one advantage of the data type’s immutable property?

24. Mutable Strings in Java

Can you create a mutable string in Java? If so, how?

25. Equals Behavior

What is the difference between equals() method and == operator?

26. Reverse Words in a Sentence

Create an algorithm that takes a string of multiple words and returns the same string with the words in reversed order.

This works in two general steps.

First, we reverse all characters in the string such that the final character becomes the first.

The final word will now be first, however, the word itself will also be in reverse order.

Next, we traverse the reversed string and now reverse each word in place.

The characters of each word will then be in the correct order while the position of each word is still reversed from the originally passed string.

27. Find all Palindrome Substrings

Write an algorithm that takes a string and finds all non-single letter palindromes within the input string.

Time Complexity : O ( n 2 ) O(n^2) O ( n 2 )

For each letter in the input string, start expanding to the left and right while checking for even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist.

We expand one character to the left and right and compare them. If both of them are equal, we print out the palindrome substring.

28. Longest Substring with K Distinct Characters

Given an algorithm that takes a string and integer K and returns the length of the longest substring with no more than K distinct characters.

This problem follows the Sliding Window pattern.

We can use a HashMap to remember the frequency of each character we have processed.

• First, we will insert characters from the beginning of the string until we have K distinct characters in the HashMap.
• These characters will be our sliding window. We are asked to find the longest such window having no more than K distinct characters. We will remember the length of this window as the longest window so far.
• After this, we will keep adding one character in the sliding window (i.e., slide the window ahead).
• In each step, we will try to shrink the window from the beginning if the count of distinct characters in the HashMap is larger than K . We will shrink the window until we have no more than K distinct characters in the HashMap.
• While shrinking, we’ll decrement the character’s frequency going out of the window and remove it from the HashMap if its frequency becomes zero.
• At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.

29. Fruit Basket Problem

With a given array of characters where each character represents a fruit tree, place the maximum number of fruits in each of 2 baskets. The only restriction is that each basket can have only one type of fruit.

You can start with any tree, but you can’t skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

Write a function to return the maximum number of fruits in both the baskets.

This problem follows the Sliding Window pattern and is quite similar to the Longest Substring with K Distinct Characters.

In this problem, we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!).

This transforms the current problem into the Longest Substring with K Distinct Characters where K=2 .

30. Print All Combinations of Balanced Braces

Given n pairs of parentheses, print all combinations of parentheses for a balanced, symmetrical pattern.

Time Complexity : O ( 2 n ) O(2^n) O ( 2 n )

The key to this solution is a recursive approach. We’ll maintain counts of two variables left_braces and right_braces .

Each iteration, we’ll see if left_braces count is lower than n . If yes, we add to left_braces and recurse into the next step.

If right_braces is less than left_braces , we’ll add to right_braces and recurse.

We stop the recursion process when both left_braces and right_braces are equal to n .

• Implement Queue using Stacks
• How does dequeue work for Queue elements?
• Is a Queue Last in First Out (LIFO) or First in First Out (FIFO)?
• What is a postfix expression?
• Evaluate Stack prefix expressions
• Generate Binary Numbers from 1 to n using Queue
• Reverse the First K Elements of a Queue
• Sort the Values in a Stack
• Next Greater Element using Stack
• How does a Priority Queue differ from a regular Queue?
• Check if Two Binary Trees are Identical
• What is the difference between a serialized and deserialized Binary Tree?
• What types of solutions are suited for breadth-first search (BFS)?
• How does post-order traversal compare with preorder traversal?
• Nth Highest Number in Binary Search Tree (BST)
• Print all Leaf Nodes of a Binary Tree
• Find the Greatest Sum of a Path Beginning at the Root Node
• Check if Left and Right Subtrees are Identical
• Write an In-Order Iterator for a Binary Tree
• Reverse Level Order Traversal

Congratulations on finishing those 50 questions!

The best way to prepare for coding interviews is the practice you’re doing right now. Soon, you’ll know all the question types you could encounter at your next interview.

To help you prepare for interviews, Educative has created the course Grokking Coding Interview Patterns in Java .

You’ll learn the 24 patterns behind every coding interview question, so you can be prepared to answer any problem you might face using Java.

Simplify your coding interview prep today! Get a structured, pattern-based approach to solving any coding interview question, without having to drill endless practice problems.

Happy learning!

Continue reading about Data Structures and Interview Prep

• Top Data Structures and Algorithms every developer must know
• Crack the Top 40 Java Coding Interview Questions
• Cracking the top Amazon coding interview questions

Frequently Asked Questions

What are the Types of Data Structures in Java?

Some common types of data structures in Java: -Array -Linked List -Stack -Queue -Binary Tree -Binary Search Tree -Heap -Hashing -Graph

How to prepare for a DSA interview?

Data structures and algorithms (DSA) rely heavily on core programming concepts. It’s essential to have a strong base in basic coding to grasp them effectively. Start by practicing your code in a programming language that you’re comfortable with, and then steadily enhance your coding abilities.

How do I prepare for a data structure interview?

• Review key concepts: Focus on fundamental data structures (arrays, linked lists, stacks, queues, trees, graphs, hash tables).
• Practice coding: Solve problems on platforms like LeetCode, HackerRank, or CodeSignal.
• Understand algorithms: Study sorting, searching, and traversal algorithms and practice writing them from scratch.
• Mock interviews: Simulate real interview scenarios to improve problem-solving speed and communication.

Learn in-demand tech skills in half the time

Mock Interview

Skill Paths

Assessments

Learn to Code

Tech Interview Prep

Generative AI

Data Science

Machine Learning

GitHub Students Scholarship

Early Access Courses

For Individuals

Try for Free

Gift a Subscription

Become an Author

Become an Affiliate

Earn Referral Credits

Cheatsheets

Privacy Policy

Cookie Policy

Terms of Service

Business Terms of Service

Data Processing Agreement

Copyright © 2024 Educative, Inc. All rights reserved.

Top 100 Data Structures Interview Questions

Data Structures are a fundamental concept in computer science that deal with the organization and storage of data. They are crucial in the design and execution of efficient algorithms and can heavily impact the performance of software. In technical interviews, understanding data structures is often vital, as they lay the foundation for problem-solving and coding exercises. This blog post features a comprehensive set of interview questions and answers on various types of data structures, commonly used in programming, like linked lists , stacks , queues , trees , and graphs . Expect to challenge and deepen your knowledge and application of these important tools.

Arrays and Strings

Explain how you would reverse an array in place..

In-place reversal modifies the original array without extra space.

Here is a general-purpose implementation:

Code Example: Array Reversal

Here is the Python code:

What is the difference between an array and a linked list ?

Let me put the two fundamental type of lists, Arrays and Linked Lists , into perspective.

Key Distinctions

Data organization.

• Array : Employs sequential memory storage and each element has a unique index.
• Linked List : Elements are scattered in memory and accessed sequentially via references (pointers).

Memory Management

• Array : Typically requires a single, contiguous memory block.
• Linked List : Memory allocations are dynamic and non-contiguous.

Complexity Analysis

When to Use Each

Arrays are preferable when:

• There’s a need for direct or random access such as in lookup tables.
• The data will remain relatively unchanged, and performance in accessing elements takes precedence over frequent insertions or deletions.

Linked Lists are more suitable when:

• Frequent insertions and deletions are expected, especially in the middle.
• The exact size of the list isn’t known in advance, and you want the memory to be used flexibly.
• The primary operations are sequential, such as iteration from the beginning to the end.

Code Example: Array vs. Linked List

Linked list, how would you check for duplicates in an array without using extra space.

Checking for duplicates in an array without additional space is a common challenge with solutions using hash functions, sorting, and mathematical calculations.

Brute Force Method

The code checks for duplicates based on numerical repetition.

• Time Complexity : O ( n 2 ) O(n^2)
• Space Complexity : O ( 1 ) O(1)

Code Implementation

Sorting approach.

This method involves sorting the array using a comparison-based sorting algorithm like Quick Sort. If two adjacent elements are the same, then the array has duplicates.

• Time Complexity : Best/Worst: O ( n log ⁡ n ) O(n \log n)
• Space Complexity : O ( 1 ) O(1) or O ( n ) O(n) depending on sorting algorithm

Mathematical Approach

For this method, the sum of numbers in the array is calculated. Mathematically, if no duplicates are present, the sum of consecutive natural numbers can be calculated to compare against the actual sum.

If actual sum − sum of numbers in the array = 0 \text{actual sum} - \text{sum of numbers in the array} = 0 , there are no duplicates.

Can you explain how to perform a binary search on a sorted array?

Let’s look at the high-level strategy behind binary search and then walk through a step-by-step example .

Binary Search Strategy

• Divide & Conquer : Begin with the entire sorted array and refine the search range in each step.
• Comparison : Use the middle element to determine the next search range.
• Repetition : Continue dividing the array until the target is found or the search range is empty.

Step-by-Step Example

Let’s consider the following array with the target value of 17 :

Initial Pointers : We start with the whole array.

This identifies the Middle number as 12 .

Comparison : Since the Middle number is less than the target 17 , we can discard the left portion of the array.

Updated Pointers : We now have a reduced array to search.

Final Comparison : Since the Middle number is now the target, 17 , the search is successfully concluded.

How would you rotate a two-dimensional array by 90 degrees?

Rotating a 2D array by 9 0 ∘ 90^\circ can be visually understood as a transpose followed by a reversal of rows or columns.

Algorithm: Transpose and Reverse

• Transpose : Swap each element A [ i ] [ j ] A[i][j] with its counterpart A [ j ] [ i ] A[j][i]
• Reverse Rows (for 9 0 ∘ 90^\circ CW) or Columns (for 9 0 ∘ 90^\circ CCW)
• Time Complexity : Both steps run in O ( n 2 ) O(n^2) time.
• Space Complexity : Since we do an in-place rotation, it’s O ( 1 ) O(1) .

Code Example: Matrix Rotation

Describe an algorithm to compress a string such as “ aabbccc ” to “ a2b2c3 ”..

You can compress a string following the count of each character. For example, “ aabbccc ” becomes “ a2b2c3 ”.

The python code for this algorithm is:

Time Complexity

This algorithm has a time complexity of O ( n ) O(n) since it processes each character of the input string exactly once.

Space Complexity

The space complexity is O ( k ) O(k) , where k k is the length of the compressed string. This is because the output string is stored in memory.

What is an array slice and how is it implemented in programming languages?

Let’s look at what is an Array Slice and how it’s implemented in some programming languages.

What is an Array Slice?

An array slice is a view on an existing array that acts as a smaller array. The slice references a continuous section of the original array which allows for efficient data access and manipulation.

Array slices are commonly used in languages like Python , Rust , and Go .

Key Operations

• Read : Access elements in the slice.
• Write : Modify elements within the slice.
• Grow/Shrink : Resize the slice, often DWARF amortized.
• Iteration : Iterate over the elements in the slice.

Underlying Mechanism

A slice typically contains:

• A pointer to the start of the slice.
• The length of the slice (the number of elements in the slice).
• The capacity of the slice (the maximum number of elements that the slice can hold).

Benefit of Use

• No Copy Overhead : Slices don’t duplicate the underlying data; they’re just references. This makes them efficient and memory-friendly.
• Flexibility : Slices can adapt as the array changes in size.
• Safety : Languages like Rust use slices for enforcing safety measures, preventing out-of-bounds access and memory issues.

Popular Implementations

Python : Uses list slicing, with syntax like my_list[2:5] . This creates a new list.

Go Lang : Employs slices extensively and is perhaps the most slice-oriented language out there.

Rust : Similar to Go, it’s a language heavily focused on memory safety, and slices are fundamental in that regard.

Code Example: Array Slicing

Here is the Rust code:

And here is the Go code:

Can you discuss the time complexity of array insertion and deletion ?

Both array insertions and deletions have a time complexity of O ( n ) O(n) due to potential need for data re-arrangement.

Array Insertion

• Beginning : O ( n ) O(n) if array full; 1 1 for shifting.
• Middle : O ( n ) O(n) to make room and insert.
• End : O ( 1 ) O(1) on average for appending.

Array Deletion

• Beginning : O ( n ) O(n) due to re-arrangement often needed.
• Middle : O ( n ) O(n) as it involves shifting.
• End : O ( 1 ) O(1) for most cases, but O ( n ) O(n) when dynamic resizing is required.

What are some ways to merge two sorted arrays into one sorted array ?

Merging two sorted arrays into a new sorted array can be accomplished through a variety of well-established techniques.

Methods of Merging Sorted Arrays

Using Additional Space :

• Create a new array and add elements from both arrays using two pointers, then return the merged list.
• Time Complexity: O ( n + m ) O(n + m) - where n n and m m are the number of elements in each array. This approach is simple and intuitive.

Using a Min Heap :

• Select the smallest element from both arrays using a min-heap and insert it into the new array.
• Time Complexity: O ( ( n + m ) log ⁡ ( n + m ) ) O((n + m) \log (n + m))
• Space Complexity: O ( n + m ) O(n + m) - Heap might contain all the elements.
• This approach is useful when the arrays are too large to fit in memory.

In-Place Merge :

• Implement a merge similar to the one used in Merge Sort , directly within the input array.
• Time Complexity: O ( n ⋅ m ) O(n \cdot m) - where n n and m m are the number of elements in each array.
• In-Place Merging becomes inefficient as the number of insertions increases.

Using Binary Search :

• Keep dividing the larger array into two parts and using binary search to find the correct position for elements in the smaller array.
• Time Complexity: O ( m log ⁡ n ) O(m \log n)

Two-Pointer Technique :

• Initialize two pointers, one for each array, and compare them to determine the next element in the merged array.
• Time Complexity: O ( n + m ) O(n + m)

How do you find the kth largest element in an unsorted array ?

To find the k th k^{\text{th}} largest element in an unsorted array, you can leverage heaps or quicksort .

Quickselect Algorithm

Idea : Partition the array using a pivot (similar to quicksort) and divide into subarrays until the partitioning index is the k th k^{\text{th}} largest element.

Time Complexity :

• Worst-case: O ( n 2 ) O(n^2) - This occurs when we’re faced with the least optimized scenario, reducing n n by only one element for each stitch step.
• Average-case: O ( n ) O(n) - Average performance is fast, making the expected time complexity linear.

Code Example : Python

Heap Method

• Build a max-heap O ( n ) O(n) - This takes linear time, making O ( n ) + O ( k log ⁡ n ) = O ( n + k log ⁡ n ) O(n) + O(k \log n) = O(n + k \log n) .
• Extract the max element k k times (each time re-heapifying the remaining elements).

Code Example: Python

Linked lists, explain how a singly linked list differs from a doubly linked list ..

Singly linked lists and doubly linked lists differ in how they manage node-to-node relationships.

Singly Linked List : Each node points to the next node.

Doubly Linked List : Both previous and next nodes are pointed to.

Visual Representation

Singly linked list, doubly linked list.

Access Direction : Singly linked lists facilitate one-way traversal, while doubly linked lists support bi-directional traversal.

Head and Tail Movements : Singly linked lists only operate on the head, while doubly linked lists can manipulate the head and tail.

Backward Traversal Efficiency : Due to their structure, singly linked lists may be less efficient for backward traversal.

Memory Requirement : Doubly linked lists use more memory as each node carries an extra pointer.

Code Example: Singly Linked List

Here is the Java code:

Code Example: Doubly Linked List

How would you detect a cycle in a linked list .

Cycle detection in a linked list is a fundamental algorithm that uses pointers to identify if a linked list has a repeating sequence.

Floyd’s “Tortoise and Hare” Algorithm

Floyd’s algorithm utilizes two pointers:

• The “tortoise” moves one step each iteration.
• The “hare” moves two steps.

If the linked list does not have a cycle, the hare either reaches the end (or null) before the tortoise, or vice versa. However, if there is a cycle, the two pointers are guaranteed to meet inside the cycle.

Algorithm Steps

• Initialize both pointers to the start of the linked list.
• Move the tortoise one step and the hare two steps.
• If the tortoise reaches the hare (a collision point), return such a point.
• If either pointer reaches the end (null), conclude there is no cycle.

• Time Complexity : O ( n ) O(n) where n n is the number of nodes in the linked list, due to each pointer visiting each node only once.
• Space Complexity : O ( 1 ) O(1) as the algorithm uses only a constant amount of extra space.

Code Example: Floyd’s Cycle Detection

What are the major operations you can perform on a linked list , and their time complexities .

Let’s look at the major operations you can perform on a singly linked list and their associated time complexities:

Operations & Time Complexities

Access (read/write) o ( n ) o(n).

• Head : Constant time: O ( 1 ) O(1) .
• Tail : O ( n ) O(n) without a tail pointer, but constant with a tail pointer.
• Middle or k-th Element : n 2 \frac{n}{2} is around the middle node; getting k-th element requires O ( k ) O(k) .

Search O ( n ) O(n)

• Unordered : May require scanning the entire list. Worst case: O ( n ) O(n) .
• Ordered : You can stop as soon as the value exceeds what you’re looking for.

Insertion O ( 1 ) O(1) without tail pointer, O ( n ) O(n) with tail pointer

• Head : O ( 1 ) O(1)
• Tail : O ( 1 ) O(1) with a tail pointer, otherwise O ( n ) O(n) .
• Middle : O ( 1 ) O(1) with tail pointer and finding position in O ( 1 ) O(1) time; otherwise, it’s O ( n ) O(n) .

Deletion O ( 1 ) O(1) for Head and Tail, O ( n ) O(n) otherwise

• Tail : O ( n ) O(n) because you must find the node before the tail for pointer reversal with a single pass.
• Middle : O ( n ) O(n) since you need to find the node before the one to be deleted.

Length O ( n ) O(n)

• Naive : Requires a full traversal. Every addition or removal requires this traversal.
• Keep Count : Maintain a separate counter, updating it with each addition or removal.

Code Example: Singly Linked List Basic Operations

Can you describe an in-place algorithm to reverse a linked list .

In-Place Algorithms modify data structures with a constant amount of extra working space O ( 1 ) O(1) .

A Singly Linked List presents a straightforward example of an in-place data structure, well-suited for in-place reversal algorithms.

Reversing a Linked List: Core Concept

The reversal algorithm just needs to update each node’s next reference so that they point to the previous node. A few key steps achieve this:

• Initialize : Keep track of the three key nodes: previous , current , and next .
• Reverse Links : Update each node to instead point to the previous one in line.
• Move Pointers : Shift previous , current , and next nodes by one position for the next iteration.

This process proceeds iteratively until current reaches the end, i.e., NULL .

• Time Complexity : The algorithm exhibits a linear time complexity of O ( n ) O(n) as it visits each node once.
• Space Complexity : As the algorithm operates in-place, only a constant amount of extra space (for nodes pointers) is required: O ( 1 ) O(1) .

Code Example: In-Place List Reversal

Explain how you would find the middle element of a linked list in one pass..

Finding the middle element of a linked list is a common problem with several efficient approaches, such as the two-pointer (or “runner”) technique .

Two-Pointer Technique

Explanation.

The two-pointer technique uses two pointers, often named slow and fast , to traverse the list. While fast moves two positions at a time, slow trails behind, covering a single position per move. When fast reaches the end, slow will be standing on the middle element.

Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

The pointers will traverse as follows:

• (1) slow : 1; fast : 2
• (2) slow : 2; fast : 4
• (3) slow : 3; fast : 6
• (4) slow : 4; fast : end

At (4), the slow pointer has reached the middle point.

• Time Complexity : O ( N ) O(N) – For every N nodes, we check each node once.
• Space Complexity : O ( 1 ) O(1) – We only use pointers; no extra data structures are involved.

Code Example: Two-Pointer (Runner) technique

Here is the Python implementation:

Unlock interview insights

Get the inside track on what to expect in your next interview. Access a collection of high quality technical interview questions with detailed answers to help you prepare for your next coding interview.

Track progress

Simple interface helps to track your learning progress. Easily navigate through the wide range of questions and focus on key topics you need for your interview success.

Save countless hours searching for information on hundreds of low-quality sites designed to drive traffic and make money from advertising.

Land a six-figure job at one of the top tech companies

Stand out and get your dream job

© 2024 Devinterview.io

• Runestone in social media: Follow @iRunestone Our Facebook Page
• Table of Contents
• Assignments
• Peer Instruction (Instructor)
• Peer Instruction (Student)
• Change Course
• Instructor's Page
• Progress Page
• Edit Profile
• Change Password
• Scratch ActiveCode
• Scratch Activecode
• Instructors Guide
• About Runestone
• Report A Problem
• This Chapter
• 1. Introduction' data-toggle="tooltip" >

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.

• 1.1. Objectives
• 1.2. Getting Started
• 1.3. What Is Computer Science?
• 1.4. What Is Programming?
• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
• 1.7. Review of Basic Python
• 1.8.1. Built-in Atomic Data Types
• 1.8.2. Built-in Collection Data Types
• 1.9.1. String Formatting
• 1.10. Control Structures
• 1.11. Exception Handling
• 1.12. Defining Functions
• 1.13.1. A Fraction Class
• 1.13.2. Inheritance: Logic Gates and Circuits
• 1.14. Summary
• 1.15. Key Terms
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 2.1.1. A Basic implementation of the MSDie class
• 2.2. Making your Class Comparable
• 3.1. Objectives
• 3.2. What Is Algorithm Analysis?
• 3.3. Big-O Notation
• 3.4.1. Solution 1: Checking Off
• 3.4.2. Solution 2: Sort and Compare
• 3.4.3. Solution 3: Brute Force
• 3.4.4. Solution 4: Count and Compare
• 3.5. Performance of Python Data Structures
• 3.7. Dictionaries
• 3.8. Summary
• 3.9. Key Terms
• 3.10. Discussion Questions
• 3.11. Programming Exercises
• 4.1. Objectives
• 4.2. What Are Linear Structures?
• 4.3. What is a Stack?
• 4.4. The Stack Abstract Data Type
• 4.5. Implementing a Stack in Python
• 4.6. Simple Balanced Parentheses
• 4.7. Balanced Symbols (A General Case)
• 4.8. Converting Decimal Numbers to Binary Numbers
• 4.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 4.9.2. General Infix-to-Postfix Conversion
• 4.9.3. Postfix Evaluation
• 4.10. What Is a Queue?
• 4.11. The Queue Abstract Data Type
• 4.12. Implementing a Queue in Python
• 4.13. Simulation: Hot Potato
• 4.14.1. Main Simulation Steps
• 4.14.2. Python Implementation
• 4.14.3. Discussion
• 4.15. What Is a Deque?
• 4.16. The Deque Abstract Data Type
• 4.17. Implementing a Deque in Python
• 4.18. Palindrome-Checker
• 4.19. Lists
• 4.20. The Unordered List Abstract Data Type
• 4.21.1. The Node Class
• 4.21.2. The Unordered List Class
• 4.22. The Ordered List Abstract Data Type
• 4.23.1. Analysis of Linked Lists
• 4.24. Summary
• 4.25. Key Terms
• 4.26. Discussion Questions
• 4.27. Programming Exercises
• 5.1. Objectives
• 5.2. What Is Recursion?
• 5.3. Calculating the Sum of a List of Numbers
• 5.4. The Three Laws of Recursion
• 5.5. Converting an Integer to a String in Any Base
• 5.6. Stack Frames: Implementing Recursion
• 5.7. Introduction: Visualizing Recursion
• 5.8. Sierpinski Triangle
• 5.9. Complex Recursive Problems
• 5.10. Tower of Hanoi
• 5.11. Exploring a Maze
• 5.12. Dynamic Programming
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Glossary
• 5.17. Programming Exercises
• 6.1. Objectives
• 6.2. Searching
• 6.3.1. Analysis of Sequential Search
• 6.4.1. Analysis of Binary Search
• 6.5.1. Hash Functions
• 6.5.2. Collision Resolution
• 6.5.3. Implementing the Map Abstract Data Type
• 6.5.4. Analysis of Hashing
• 6.6. Sorting
• 6.7. The Bubble Sort
• 6.8. The Selection Sort
• 6.9. The Insertion Sort
• 6.10. The Shell Sort
• 6.11. The Merge Sort
• 6.12. The Quick Sort
• 6.13. Summary
• 6.14. Key Terms
• 6.15. Discussion Questions
• 6.16. Programming Exercises
• 7.1. Objectives
• 7.2. Examples of Trees
• 7.3. Vocabulary and Definitions
• 7.4. List of Lists Representation
• 7.5. Nodes and References
• 7.6. Parse Tree
• 7.7. Tree Traversals
• 7.8. Priority Queues with Binary Heaps
• 7.9. Binary Heap Operations
• 7.10.1. The Structure Property
• 7.10.2. The Heap Order Property
• 7.10.3. Heap Operations
• 7.11. Binary Search Trees
• 7.12. Search Tree Operations
• 7.13. Search Tree Implementation
• 7.14. Search Tree Analysis
• 7.15. Balanced Binary Search Trees
• 7.16. AVL Tree Performance
• 7.17. AVL Tree Implementation
• 7.18. Summary of Map ADT Implementations
• 7.19. Summary
• 7.20. Key Terms
• 7.21. Discussion Questions
• 7.22. Programming Exercises
• 8.1. Objectives
• 8.2. Vocabulary and Definitions
• 8.3. The Graph Abstract Data Type
• 8.4. An Adjacency Matrix
• 8.5. An Adjacency List
• 8.6. Implementation
• 8.7. The Word Ladder Problem
• 8.8. Building the Word Ladder Graph
• 8.9. Implementing Breadth First Search
• 8.10. Breadth First Search Analysis
• 8.11. The Knight’s Tour Problem
• 8.12. Building the Knight’s Tour Graph
• 8.13. Implementing Knight’s Tour
• 8.14. Knight’s Tour Analysis
• 8.15. General Depth First Search
• 8.16. Depth First Search Analysis
• 8.17. Topological Sorting
• 8.18. Strongly Connected Components
• 8.19. Shortest Path Problems
• 8.20. Dijkstra’s Algorithm
• 8.21. Analysis of Dijkstra’s Algorithm
• 8.22. Prim’s Spanning Tree Algorithm
• 8.23. Summary
• 8.24. Key Terms
• 8.25. Discussion Questions
• 8.26. Programming Exercises

Acknowledgements ¶

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables ¶

Search Page

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Data Structures 👩‍💻 Domain on HackerRank - Problems & Solutions 📑📘

anishLearnsToCode/hackerrank-data-structures

Folders and files.

Repository files navigation

Hackerrank data structures solutions.

This repository contains solutions to the Data Structures domain part of HackerRank. The Data Structures Domain Falls under a broader Problem Solving Skill Set in HackerRank which consists of both Data Structures and Algorithms .

The Data Structures Domain is further Divided into the following sub-domains. To Contribute have a look at Contributing.md and happy coding 😀 🐱‍💻.

Sub Domains & Problems (+Solutions) in the Data Structures Domain

⚡ Quick Links: Arrays | Linked Lists | Trees | Balanced Trees | Stacks | Queues | Heap | Disjoint Set | Multiple Choice | Trie | Advanced |

Linked Lists

Balanced Trees

Disjoint Set

Multiple Choice

• Python 8.1%

Practice These Data Structure Interview Questions (and Answers) to Ace Your Technical Interview

• Share article on Twitter
• Share article on Facebook
• Share article on LinkedIn

If you’re interviewing for a role that involves any type of coding — think Software Developer , Web Developer , Data Scientist , or Game Developer , then there’s a good chance you’ll be asked questions related to data structures . And even if you aren’t asked questions specific to this topic, learning data structures gives you a huge advantage during your technical interview .

One of the best ways to prepare for your technical interview and data structure interview questions is to set up a mock interview with a friend or relative and ask them to play the role of the interviewer. They can ask you questions from a list you generate and go in order or mix up the order to keep you on your toes. They can also ask follow-up questions that require you to explain your answers. And don’t hesitate to incorporate details from your past accomplishments and projects in your answers.

If you’re interviewing over Zoom , consider setting up your mock interview over Zoom too. If you’d rather practice solo, you can record yourself answering questions and then play the recording back to find the areas that you need to work on.

To help you prepare for your upcoming interview, here are 15 data structure questions that are worth reviewing before your actual interview.

Learn something new for free

• Intro to ChatGPT

1. What’s a Graph or Network Structure?

This is a node-and-edge-based structure that documents the relationships between items and is commonly used to model real-life networks such as street and social networks. A tree is one example of a specific type of graph.

2. Describe what an array is and how to access it.

An array refers to a collection that contains data of the same type that are stored within memory locations that are contiguous.

Arrays are the simplest type of data structure and provide fast read/access times because elements are stored together.

3. What’s the difference between linear and non-linear data structures?

A linear structure refers to the elements of your data that are organized in sequence. On the other hand, when your data is distributed non-sequentially, as in a tree, you would say it has a non-linear structure.

4. What’s a multi-dimensional array?

A multi-dimensional array is one that has data structures spanning multiple dimensions. The most common type of array is a two-dimensional array, also known as a matrix, which is essentially a collection of single-dimension arrays.

5. What’s referred to as a linked list?

Linked lists are another common type of data structure. They are a type of collection in which elements are distributed in memory, as opposed to stored contiguously as in an array. The elements are tied or linked by references to the locations of the other items: each item in the list stores the address in memory of the next item.

6. Would a linked list be described as linear or non-linear?

In a way, this could be a kind of trick question. A linked list could be considered non-linear because of how items are stored in memory. But, more generally, it’s classified as a linear or sequential data structure like stacks and queues.

7. What’s a doubly-linked list (DLL)?

A DLL is a more complicated kind of linked list where the node has a pair of references: an address to the following node in the sequence and an address to the previous node.

8. What is meant by a stack in programming?

This can be a tough data structure interview question because “stack” (as in tech stack ) can also mean different technologies within an environment. However, in the context of programming, a stack refers to a linear data structure that’s governed by the principle of last-in, first-out (LIFO).

9. What is meant by the term “queue”?

This is another question that could be confusing because it has different meanings depending on the context, but it’s important to always remember the interviewer is interested in what a term means within the programming field. In this context, “queue” refers to a linear data structure that, unlike stack, uses a first-in, first-out (FIFO) approach.

10. What makes a stack different from a queue?

This question is designed to see if you understand the concepts of FIFO and LIFO. With a stack, the most recently added item is the first one to go out. With a queue, the item that was added the first time is the first to go out.

11. What is Big “O” Notation?

Big “O” notation is a way of categorizing the worst-case performance of a given algorithm. It also denotes how an algorithm will generally perform as the input increases. Some of the classes of big “O” include constant time, log n time, and n or linear increase in time.

12. What does the term “hashmap” mean?

“Hashmap” refers to a data structure that uses a hash table , which is often also described as a dictionary. It’s a structure in which data or objects are mapped to a value using a hashing function. A hash table enables fast search, delete, and insertion speeds. It’s a structure that is often employed because of its speed attributes. It falls under the constant time class within big ‘O’ notation.

13. What is constant time complexity?

This question may or may not be a follow-up or precursor to one about hashmap. Constant time complexity refers to an algorithm that takes the same amount of time to run regardless of the scale of the input.

14. What is meant by the term “priority queue”?

“Priority queue” refers to an abstract data type that is similar to a normal queue, except it has a priority associated with its elements. Elements with a higher priority get processed before those with lower priority.

15. Can you store a duplicate key in hashmap?

No, you can’t store a duplicate key in hashmap. Any new additions to a hashmap that use an existing key will override the previous value associated with that key.

More technical interview prep

Need to brush up on any of these topics? You can get a refresher on lists, stacks, and queues and learn about how computer memory works through nodes and pointers in our Linear Data Structures course. Or you can dive into the fundamental data structures of computer science in our Introduction to Algorithms and Linear Data Structures in Swift .

If you’re looking for an advanced course, check out our Learn Complex Data Structures course that’ll get you ready to solve advanced algorithmic problems like path-finding and maintaining priority queues.

For more interview prep, give our complete guide to the technical interview a look, and our tips on answering behavioral interview questions are also good to review. Check out our advice on the whiteboard interview too. Our Career Center offers even more guidance and resources for interviewing, networking, and job-hunting.

If you’re searching for your next course to take, check out our catalog and sign up for a class today.

Related courses

Linear data structures, learn data structures and algorithms with python, introduction to non-linear data structures in swift, subscribe for news, tips, and more, related articles.

How To Write A Programmer Bio (With 6 Examples)

The simple formula will make writing a bio feel like no big deal.

What Is DevSecOps & How to Break Into It 

DevSecOps roles are ideal for career shifters. Here’s how to make yourself a great DevSecOps candidate.

How to Estimate the Amount of Time You Need for a Project 

How long is a piece of string? Estimating software engineering work is part science, part finger in the air — here’s some practical advice to get started.

4 In-Demand Cybersecurity Skills That Will Help Get You Hired

Seize the job opportunities in cybersecurity by learning these key technical skills.

Context Switching Is Killing Your Productivity — 6 Tips for Focus

Context switching doesn’t just affect your productivity, it causes stress and frustration too. Here are some ways to manage interruptions at work.

7 Small Wins To Celebrate On Your Journey To Becoming A Professional Developer

Having an end goal is important, but so is celebrating your progress. Here are some milestones to look forward to as you learn how to code.

8 Tips For Applying To Jobs In Tech If You’re Really Busy

Use these tips to help you apply to jobs ​​in tech when you don’t have a lot of time to dedicate to your search.

• Python Home
• ▼Python Exercises
• Exercises Home
• ▼Python Basic
• Basic - Part-I
• Basic - Part-II
• Python Programming Puzzles
• Mastering Python
• ▼Python Advanced
• Python Advanced Exercises
• ▼Python Control Flow
• Condition Statements and Loops
• ▼Python Data Types
• List Advanced
• Collections
• ▼Python Class
• ▼Python Concepts
• Python Unit test
• Python Exception Handling
• Python Object-Oriented Programming
• ▼Functional Programming
• Filter Function
• ▼Date and Time
• Pendulum Module
• ▼File Handling
• CSV Read, Write
• ▼Regular Expressions
• Regular Expression
• ▼Data Structures and Algorithms
• Search and Sorting
• Linked List
• Binary Search Tree
• Heap queue algorithm
• ▼Advanced Python Data Types
• Boolean Data Type
• None Data Type
• Bytes and Byte Arrays
• Memory Views exercises
• Frozenset Views exercises
• NamedTuple exercises
• OrderedDict exercises
• Counter exercises
• Ellipsis exercises
• ▼Concurrency and Threading
• Asynchronous
• ▼Python Modules
• Operating System Services
• SQLite Database
• ▼Miscellaneous
• Cyber Security
• Generators Yield
• ▼Python GUI Tkinter, PyQt
• Tkinter Home
• Tkinter Basic
• Tkinter Layout Management
• Tkinter Widgets
• Tkinter Dialogs and File Handling
• Tkinter Canvas and Graphics
• Tkinter Events and Event Handling
• Tkinter Custom Widgets and Themes
• Tkinter File Operations and Integration
• PyQt Widgets
• PyQt Connecting Signals to Slots
• PyQt Event Handling
• ▼Python NumPy
• Python NumPy Home
• ▼Python urllib3
• Python urllib3 Home
• ▼Python Metaprogramming
• Python Metaprogramming Home
• ▼Python GeoPy
• Python GeoPy Home
• ▼BeautifulSoup
• BeautifulSoup Home
• ▼Arrow Module
• ▼Python Pandas
• Python Pandas Home
• ▼Pandas and NumPy Exercises
• Pandas and NumPy Home
• ▼Python Machine Learning
• Machine Learning Home
• TensorFlow Basic
• ▼Python Web Scraping
• Web Scraping
• ▼Python Challenges
• Challenges-1
• ▼Python Mini Project
• Python Projects
• ▼Python Natural Language Toolkit
• Python NLTK
• ▼Python Project
• Novel Coronavirus (COVID-19)
• ..More to come..

Python: Data Structures - Exercises, Practice, Solution

Data structures: [7 exercises with solution].

[ An editor is available at the bottom of the page to write and execute the scripts. ]

1. Write a Python program to locate the left insertion point for a specified value in sorted order. Go to the editor Expected Output: 4 2 Click me to see the sample solution

2. Write a Python program to locate the right insertion point for a specified value in sorted order. Go to the editor Expected Output: 3 2 Click me to see the sample solution

3. Write a Python program to insert items into a list in sorted order. Go to the editor Expected Output: Original List: [25, 45, 36, 47, 69, 48, 68, 78, 14, 36] Sorted List: [14, 25, 36, 36, 45, 47, 48, 68, 69, 78] Click me to see the sample solution

4. Write a Python program to create a queue and display all the members and size of the queue. Go to the editor Expected Output: Members of the queue: 0 1 2 3 Size of the queue: 4 Click me to see the sample solution

5. Write a Python program to find whether a queue is empty or not. Go to the editor Expected Output: True False Click me to see the sample solution

6. Write a Python program to create a FIFO queue. Go to the editor Expected Output: 0 1 2 3 Click me to see the sample solution

7. Write a Python program to create a LIFO queue. Go to the editor Expected Output: 3 2 1 0 Click me to see the sample solution

Python Code Editor:

More to Come !

Do not submit any solution of the above exercises at here, if you want to contribute go to the appropriate exercise page.

Test your Python skills with w3resource's quiz

Follow us on Facebook and Twitter for latest update.

• Weekly Trends and Language Statistics

Data Structure Interview Questions and Answers in 2024

Data structures are a way of organizing and storing data in a computer’s memory to facilitate efficient processing and retrieval of information. They provide a way to organize and structure data to perform operations on the stored information effectively. Many algorithms are based on the efficient use of data structures. Data structure-related questions are an integral part of technical interviews because they assess a candidate’s problem-solving skills, critical thinking, coding proficiency, and understanding of core computer science concepts. Being able to navigate data structure interview questions effectively can significantly contribute to success in technical interviews.

‘ Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ‘ — Linus Torvalds.

Now, let’s explore the Data Structure Interview Questions in three sections- 

Data Structure Interview Questions for Freshers

Data structure interview questions for experienced, data structure coding interview questions, 1. what is a data structure what are the characteristics of data structures.

A data structure is a way of organizing, storing, and managing data to facilitate efficient data access and modification. It defines a set of operations that can be applied to the data, as well as the relationships between the elements. The choice of a particular data structure depends on the nature of the data and the operations that need to be performed.

Characteristics of data structures

• Organization : Data structures organize and structure data for efficient retrieval, insertion, deletion, and manipulation of elements.
• Access Methods : Data structures define methods for accessing and manipulating the stored data. These methods may include searching for specific elements, sorting, and traversing the data.
• Efficiency : Different data structures are designed to optimize specific types of operations. The choice of a data structure depends on the efficiency requirements of the algorithms.
• Memory Management : Data structures often involve memory management, determining how data is stored in computer memory and how memory is allocated and deallocated.

2. What are the two types of data structures? 

The two important types of data structures are linear and non-linear data structures.

• Linear Data Structures : Except for the first and last elements, linear data structures arrange elements in a sequential order, with each element having a distinct predecessor and successor. The elements form a linear sequence. Examples of linear data structures include linked lists, stacks, arrays, and queues.
• Non-linear Data Structures : In non-linear data structures, elements are not arranged in a sequential or linear order. Instead, elements can have relationships with multiple predecessors and successors, forming more complex structures. Common examples of non-linear data structures include: Trees, Graphs, Heaps, and Hash Tables.

3. Explain some common Data Structures.

• Arrays : An array is a collection of fixed-size elements, each identified by an index.
• Linked Lists : In linked lists, elements are stored in nodes. Each node points to the next node in a sequence, resulting in a linear chain.
• Stacks : A stack is a collection of elements with two primary operations: push and pop. Here, elements are added and removed from one end.
• Queues : A queue is a collection of elements with two primary operations, enqueue and dequeue, which add elements at one end (rear) and remove them from the other end (front).
• Trees : Trees are hierarchical structures with a root node and branches leading to leaf nodes. Trees can be classified into various types, such as binary trees, binary search trees, etc.
• Graphs : A graph is a collection of vertices or nodes connected by edges. Graphs can be directed or undirected, and they can contain weighted edges. They are used for representing relationships between entities.
• Heaps : Heaps are specialized tree-based structures. Heaps are commonly used in priority queues and heap sort algorithms.
• Hash Tables : Hash Tables store data in key-value pairs. A hash function maps keys to indices in an array.

4. Explain how an array differs from a linked list.

• An array is a data structure that contains a sequential collection of elements with the same data type. Each element in the array is identified by an index that indicates its position in the sequence. At the same time, a linked list is a data structure made up of nodes, each of which contains data and a reference to the next node in the sequence. The last node typically points to null, indicating the end of the list.
• Elements in an array are stored in contiguous memory locations, allowing direct access to any element using its index. Meanwhile, linked lists do not require contiguous memory locations. Each node can be located anywhere in memory, and they are linked together by pointers, allowing for dynamic memory allocation.
• Arrays have a fixed size, which means the number of elements is known at the time of declaration. Linked lists can easily grow and shrink in size by adding or removing nodes, making them more flexible in terms of size changes compared to arrays.

5. Define a linked list and its advantages over arrays.

A linked list is a linear data structure and consists of nodes. Each node points to the next node in a sequence, resulting in a linear chain.

Advantages of Linked Lists Over Arrays:

• One of the significant advantages of linked lists is their dynamic size. Unlike arrays, linked lists can add or remove nodes, making them more flexible in handling data.
• Linked lists do not require pre-allocation of space for a fixed number of elements, as is the case with arrays. This dynamic memory allocation makes linked lists suitable for situations where the exact size of the data structure is unknown or subject to change.
• Linked lists are particularly efficient for insertions and deletions at any position within the list. Inserting or deleting elements in between a linked list involves updating pointers.
• Linked lists do not suffer from the memory wastage that can occur in arrays due to pre-allocation. Memory is allocated on demand for each node in a linked list, minimizing unused space.

6. Describe the basic operations of a stack and a queue.

• Stack :  A stack is a data structure that follows the Last In, First Out (LIFO) principle. The basic operations of a stack include:
• Push – Adds an element to the top of the Stack.
• Pop – Removes an element from the top of the Stack.
• Peek – Returns the topmost element from the Stack.
• isEmpty – Checks if the Stack is empty.
• Queue : A queue is another data structure that follows the First In, First Out (FIFO) approach. The basic operations of a queue include:
• Enqueue – Adds an element to the rear end of the queue.
• Dequeue – Removes the element from the front of the queue.
• Front – Returns the element at the front of the queue.
• isEmpty – Checks if the queue is empty.

7. What is a Queue, and how is it different from a Stack?

A queue is a data structure that follows the First In, First Out (FIFO) principle. In a queue, elements are added at the rear (enqueue) and removed from the front (dequeue). Queues are often used in scenarios where the order of processing is important, such as in task scheduling, printing, or managing requests in a network.

On the other hand, a stack is a data structure that follows the Last In, Last Out (LIFO) approach. In a stack, elements are added and removed from the same end, typically called the “top.” The last element pushed onto the Stack is the first to be popped off. Stacks are commonly used in situations where the order of processing is based on the order of arrival, such as in function calls, expression evaluation, or undo mechanisms.

8. What is a stack data structure? What are the applications of Stack?

A stack is a data structure that follows the Last In, First Out (LIFO) principle, i.e., the last element added to the Stack is the first one to be removed. 

Applications

• Function Calls and Recursion : Stacks play a crucial role in managing function calls and recursion in programming languages.
• Expression Evaluation : Stacks are commonly used for the evaluation of expressions, especially in the context of arithmetic expressions. The stack data structure facilitates the processing of operands and operators, ensuring that the expression is evaluated according to the order of operations. 
• Backtracking Algorithms : Stacks are commonly used in backtracking algorithms to keep track of the current state and facilitate the process of exploration and backtracking. Backtracking algorithms often use recursion to explore different branches of the solution space. In this case, the call stack itself acts as the stack data structure.
• Memory Management : Stacks play a critical role in memory management, particularly in the context of managing function calls and local variables. It provides a simple and efficient way to allocate and deallocate memory in a structured manner, contributing to the overall memory management strategy in programming languages and runtime environments.

9. What is a binary tree data structure? Explain the properties of a binary tree.

A binary tree is a hierarchical tree data structure in which each node can have no more than two children, known as the left and right children. Edges connect nodes in a binary tree, and there is a unique starting node called the root. The node without any children is called a leaf. Operations such as searching, insertion, and deletion can be performed efficiently in binary trees, especially when the tree is balanced. 

Here are the key properties of a binary tree:

• Root :  A binary tree’s root is the node at the very top. It serves as the starting point for navigating the tree.
• Nodes :  Each element in a binary tree is called a node. Nodes may contain data and references to their left and right children.
• Edges :  The connections between nodes are called edges. In a binary tree, each node has at most two edges leading to its children.
• Parent :  A node in a binary tree is considered a parent if it has one or more children.
• Children :  The nodes directly below a parent are referred to as its children.
• Leaf Nodes :  Leaf nodes are nodes with no children. They are the terminal nodes at the bottom of the tree.
• Internal Nodes :  Internal nodes are nodes that have at least one child. These nodes are not leaves.
• Depth :  The depth of a node is the distance from the root to that node. The root has a depth of 0.

10. Define a graph and explain the differences between directed and undirected graphs.

A graph is a computational representation of a set of objects, known as vertices or nodes, connected by edges. Graphs are used to model relationships between entities. The two main components of a graph are:

• Vertices (Nodes) : These are the entities represented in the graph. Each vertex can have additional information associated with it, known as attributes.
• Edges : These are the connections between vertices. Edges represent relationships or interactions between the entities.

11. What are the differences between Directed and Undirected Graphs?

• Directed Graph/Digraph : In a directed graph, edges have a direction, i.e., they have an initial vertex and a terminal vertex. They are ordered.
• Undirected Graph : In an undirected graph, edges do not have a direction. The connections between vertices are symmetric, and the vertices are unordered.

Now, let’s go through some common Data Structure interview questions for Experienced Professionals.

1. What is a Deque?

A deque, or “double-ended queue,” is a data structure that allows the insertion and deletion of elements from both the front and back. This makes it versatile, as elements can be efficiently added or removed from either end.

The operations on a deque can be summarized as follows:

• EnqueueFront : Add an element to the front.
• EnqueueRear : Add an element to the rear.
• DequeueFront : Remove an element from the front.
• DequeueRear : Remove an element from the rear.

Deques are useful in situations where you need efficient insertion and deletion at both ends of the data structure. They can be employed in algorithms that require maintaining a sliding window of elements, palindrome checking, and other scenarios where elements need to be accessed from both ends.

2. What is BST? What are its applications?

A Binary Search Tree is a binary tree data structure where each node has at most two children, and for each node:

• All nodes in its left subtree have keys smaller than the nodes’.
• All nodes in its right subtree have keys greater than the nodes’.
• Both the left and right subtrees are also binary search trees.

This ordering property ensures that a binary search can be efficiently performed on the tree. 

Key operations on a binary search tree:

• Search : The search operation in a Binary Search Tree (BST) involves finding a specific key within the tree. Given a key, the search operation navigates the tree from the root, comparing the key with the current node’s key at each step. If the key matches the current node’s key, the search is successful, and the corresponding value is returned. If the key is smaller, the search continues in the left subtree; if it’s larger, the search continues in the right subtree. If the key is not found after reaching a node, the search operation returns a null indicating that the key is not present.
• Insertion : The insertion operation starts with a search for the key in the tree. If the key is not found (i.e., the search reaches a leaf node), a new node is created with the given key and value. The new node is then inserted at the appropriate position in the tree while maintaining the BST property. If the key already exists in the tree, the associated value is updated.
• Deletion : Deleting a node involves three cases:
• If the node to be deleted is a leaf (has no children), it can be removed directly.
• If the node has one child, the node is replaced by its child.
• If the node has two children, it is replaced by its in-order successor (or predecessor), and the in-order successor’s original position is adjusted.
• Traversal : Traversal in a Binary Search Tree (BST) involves visiting all the nodes of the tree in a specific order. The three common types of binary tree traversal are in-order, pre-order, and post-order. Each traversal method defines a different order in which the nodes are visited. 

Applications of Binary Search Trees

• Tables and Dictionaries: Binary Search Trees (BSTs) are widely used to implement tables and dictionaries, providing an efficient way to associate keys with values and allowing for quick retrieval, insertion, and deletion operations.
• Database Indexing: Binary search trees are used in databases to index and efficiently search for records.
• File System: File systems often use BSTs to maintain directory structures and quickly locate files.
• Network Routing Tables: In networking, BSTs can be employed to store routing information efficiently.

3. What are the ways to traverse a tree?

The three primary methods to traverse a tree are in-order, pre-order, and post-order traversal. 

• In-order traversal is a method of traversing a binary tree in which each node is visited in a specific order. The order of visiting nodes in an in-order traversal is left, node, right. This traversal produces the elements of a binary search tree (BST) in ascending order. In the context of a binary tree, “left” refers to the left subtree, “node” refers to the current node, and “right” refers to the right subtree.
• Pre-order traversal is a method of traversing a binary tree in a specific order: Node – Left – Right. In this traversal, each node is visited before its left and right subtrees. The process starts from the root node, and for each node, the node itself is visited first, followed by the traversal of its left subtree and then its right subtree.
• Post-order traversal is a method of traversing a binary tree in a specific order: Left – Right – Node. In this traversal, each node’s left and right subtrees are visited before the node itself. The process starts from the root node, and for each node, the left subtree is traversed first, followed by the traversal of the right subtree, and finally, the current node is visited.

4. Explain different types of queues

There are mainly four types of queues. They are

• Linear Queue : In a linear queue, elements are stored linearly or sequentially. The first element is added at one end (rear/enqueue), and elements are removed from the other end (front/dequeue). This is the most basic form of a queue.
• Circular Queue : A circular queue is an extension of a linear queue where the rear end is connected to the front end, forming a circular structure. This allows for efficient utilization of space and avoids the need to shift elements when the rear reaches the end of the queue. The circular queue is often implemented using an array or a linked list.
• Priority Queue : In a priority queue, elements are assigned priority values. Elements with higher priority are dequeued before elements with lower priority. Priority queues are used in scenarios where the priority of elements determines the order of processing.
• Double-Ended Queue (Deque) : A deque allows the insertion and deletion of elements from both ends (front and rear). It can be used as a queue, Stack, or a combination of both. Deques are more versatile than linear queues.

5. What are the representations of a graph data structure? What are the applications for graphs?

There are two main representations of graphs: the adjacency matrix and the adjacency list.

• An adjacency matrix is a 2D array (matrix) where each cell at position (a, b) represents whether there is an edge between vertex a and vertex b. If there is an edge, the cell contains a 1; otherwise, it contains a 0.
• An adjacency list is a collection of lists or arrays where each list represents the neighbors of a vertex. For each vertex v, the list contains all vertices adjacent to v.

Graphs are versatile data structures with a wide range of applications across various domains. Here are some common applications of graph data structures:

• Social Networks : Graphs model relationships between individuals in social networks. Nodes represent people, and edges represent connections or friendships. Algorithms on graphs can be used to analyze social network structures, find communities, and suggest connections.
• Routing and Networks : Graphs model the connections between routers or devices in computer networks. Algorithms like Dijkstra’s or Bellman-Ford can find the shortest path between two nodes. Graphs are also used to model and analyze transportation networks, such as roads and railways.
• Recommendation Systems : Graphs can represent user-item interactions. Recommendation algorithms analyze the graph to suggest items based on the preferences of similar users.
• Artificial Intelligence : Graphs are used in knowledge representation, with nodes as concepts and edges as relationships. Graph-based algorithms contribute to machine learning and pattern recognition tasks.

Learn More: Data Structure Learning Roadmap

6. What is the difference between BFS and DFS?

Breadth First Search (BFS) and Depth First Search (DFS) are two fundamental algorithms used to traverse and explore graphs or tree structures.

7. What are the different types of array data structures?

Arrays are data structures that store elements of the same type in contiguous memory locations. Here are some common types of array data structures:

• A one-dimensional array is a simple array that stores elements in a single line or row. Elements are accessed using a single index.

           Example:

           [3 1 7 9]

• A two-dimensional array is an array of arrays forming a matrix or table structure. Elements are accessed using two indices (row and column).

            Example:

            [[1 3 4 5]

            [2 4 5 6]]

• A multi-dimensional array is an array with more than two dimensions. Here, Elements are accessed using multiple indices.

           [[[1,2,3,4,5] 

           [6,7,8,9,1]]

           [[1,1,3,4,5]

           [6,7,1,0,2]]]

8. What are the different types of Linked List data structures?

Linked lists are linear data structures where elements are stored in nodes, and each node points to the next node in the sequence. Here are some common types of linked lists:

• Singly Linked List : Each node in a singly linked list contains data as well as a reference to the node following it in the sequence. The last node points to null, indicating the end of the list. Here, Traversal is only possible in one direction.

           0 -> 1 -> 2 -> 3 -> null

• Doubly Linked List: In a doubly linked list, each node contains data and references to both the next and the previous nodes in the sequence. Here, Traversal is in both forward and backward directions.

            null <- 0 <-> 1 <-> 2 <-> 3 -> null

• Circular Linked List: In a circular linked list, the last node points back to the first, forming a loop. This can be implemented using singly or doubly linked nodes.

            1 -> 2 -> 3 -> 1

• Doubly Circular Linked List: A Doubly Circular Linked List is a type of linked list in which each node contains data and two pointers. Similar to a doubly linked list, a doubly circular linked list has pointers to both the next and the previous nodes. However, in a circular linked list, the last node points back to the first node, creating a loop. In a doubly circular linked list, this Loop is formed in both directions.

            1 <-> 2 <-> 3 <-> 4 <-> 1

            ↑_______________________|

            In the example above, the arrows indicate the direction of the pointers. The last node points back to the first node, forming a circular structure in both directions.

9. What are infix and postfix expressions?

• Infix Expression – An infix expression refers to a standard mathematical expression in which operators are placed between operands. In an infix expression, the position of an operator in relation to its operands determines the order of operations, following the rules of precedence and associativity. In infix expressions, parentheses are often used to indicate the order of operations explicitly. The order of operations is as follows:
• Parentheses
• Multiplication and Division (from left to right)
• Addition and Subtraction (from left to right)

        Example:

        a + b * (c – d) / e

• Postfix Expression –  In data structures, a postfix expression is a way of representing mathematical expressions in which operators follow their operands. Postfix notation eliminates the need for parentheses to indicate operation order, as operator position determines operation sequence. In a postfix expression, operators are placed after their corresponding operands.

            a b c d – * e /

Related Learning: Data Structures in C

10. Explain the concept of hashing and hash functions.

Hashing is the process of using a hash function to convert arbitrary-sized data to fixed-size values (hash codes). A hash function is a mathematical function that takes an input and returns a fixed-size string of characters, which is typically a hash code. The resulting hash code is often used as an index to locate a data record in a hash table quickly. The output appears random and unique for different inputs, and even a small change in the input should produce a significantly different hash value. Hashing is commonly employed in various applications, such as hash tables, digital signatures, data integrity checks, and cryptographic applications. A hash table is a data structure that uses hash functions to map keys to indexes in an array. Each index in the array corresponds to a “bucket” where the associated value is stored. Hash tables provide fast average-case time complexity for basic operations like insertion, deletion, and lookup.

Now, let’s move ahead with some common coding data structure interview questions.

1. Given an array of integers, write a function to find the sum of all elements in Python.

#Function to find the sum of elements

def sum_func(array1):

    return sum(array1)

array1 = [1, 2, 3, 4, 5]

result = sum_func(array1)

print(f”The sum of elements in the array is: {result}”)

The sum of elements in the array is: 15

In this example, the function sum_func takes a list of integers as its parameter and uses the built-in sum_func function to calculate the sum of all elements in the array.

Related Learning: Data Structures in Python

2. Program to print the duplicate elements of an array.

#Initializing the array   

array = [1, 2, 3, 5, 9, 4, 5, 7, 6, 8, 0, 3, 0];   

print(“Duplicate elements in the array include: “); 

#Traversing through the elements using for Loop

for i in range(0, len(array)):  

    for j in range(i+1, len(array)):  

        if(array[i] == array[j]):  

            print(array[j]);  

   Duplicate elements in the array include: 

   3

   5

   0

3. Write a program to determine if two strings are anagrams

string1 = “Heart”;  

string2 = “Earth”;   

#Checking for the length of strings  

if(len(string1)!= len(string2)):  

    print (“The strings are not Anagram”);  

else:  

    #Using the lower() function to change the case of the string to lowercase

    string1 = string1.lower();  

    string2 = string2.lower();  

    #Sorting the strings  

    string1 = ”. join(sorted(string1));  

    string2 = ”. join(sorted(string2));  

    if (string1 == string2):  

        print (“The strings are Anagrams”);   

    else:  

        print (“The strings are not Anagrams”);  

The strings are Anagrams

4. Write a Program to count the number of vowels in a given string.

string = “Edureka”

# Function to count vowel

def vowels_count(string):

    temp = 0

    #All vowels 

    vowel = set(“aeiouAEIOU”)

    #For Loop to iterate through the string

    for element in string:

        if element in vowel:

            temp = temp + 1

    print(“Total number of vowels in the string:”, temp)

#Testing the Function 

vowels_count(string)

     Total number of vowels in the string: 4

5. Implement a stack using arrays.

class Stack:

    def __init__(self):

        self.items = []

    def is_empty(self):

        return len(self.items) == 0

    def push(self, item):

        self.items.append(item)

    def pop(self):

        if not self.is_empty():

            return self.items.pop()

        else:

            raise IndexError(“pop from an empty stack”)

    def peek(self):

            return self.items[-1]

            raise IndexError(“peek from an empty stack”)

    def size(self):

        return len(self.items)

#Calling the function

stack1 = Stack()

stack1.push(1)

stack1.push(2)

stack1.push(3)

#Printing results

print(“Stack:”, stack1.items)

print(“Pop:”, stack1.pop())

print(“Peek:”, stack1.peek())

print(“Size:”, stack1.size())

The above example shows the implementation of basic stack operations like push, pop, and peek, checking if the stack is empty and getting the size of the stack. 

  Stack: [1, 2, 3]

  Pop: 3

  Peek: 2

  Size: 2

6. Write a program to calculate the height of a binary tree.

class Node:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None

def tree_height(root):

    if root is None:

        return 0

    else:

        left_height = tree_height(root.left)

        right_height = tree_height(root.right)

        # Return the maximum height of the left and right subtrees, plus 1 for the current level.

        return max(left_height, right_height) + 1

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

tree_height = tree_height(root)

print(“Height of the binary tree:”, tree_height)

Height of the binary tree: 3

7. Implement a queue using an array.

class queue:

    # __init__ function

    def __init__(self, capacity):

        self.front = self.size = 0

        self.rear = capacity -1

        self.Q = [None]*capacity

        self.capacity = capacity

    # Checking if Queue is full

    def isfull(self):

        return self.size == self.capacity

    # Checking if Queue is empty

    def isempty(self):

        return self.size == 0

    # Function to add an element to the queue. 

    def enqueue(self, item):

        if self.isfull():

            print(“Full”)

            return

        self.rear = (self.rear + 1) % (self.capacity)

        self.Q[self.rear] = item

        self.size = self.size + 1

        print(“% s enqueued to queue” % str(item))

    # Function to remove an element from the queue. 

    def dequeue(self):

        if self.isempty():

            print(“Empty”)

        print(“% s dequeued from queue” % str(self.Q[self.front]))

        self.front = (self.front + 1) % (self.capacity)

        self.size = self.size -1

    # Function to get front of queue

    def queuefront(self):

            print(“Queue is empty”)

        print(“Front item is”, self.Q[self.front])

    # Function to get rear of the queue

    def queuerear(self):

        print(“Rear item is”, self.Q[self.rear])

# Adding elements to the queue

if __name__ == ‘__main__’:

    queue = queue(4)

    queue.enqueue(1)

    queue.enqueue(2)

    queue.enqueue(3)

    queue.enqueue(4)

    queue.dequeue()

    queue.queuefront()

    queue.queuerear()

      1 enqueued to queue

      2 enqueued to queue

      3 enqueued to queue

      4 enqueued to queue

      1 dequeued from queue

      Front item is 2

      Rear item is 4

In this example, the queue class represents a queue implemented using a circular array. The enqueue method adds an item to the rear end of the queue, the dequeue method removes and returns the item from the front end of the queue, and the peek method returns the item at the front without removing it. The queue keeps track of its front and rear indices to manage the circular nature of the array.

8. Write a Python program to reverse a linked list.

class node: 

    #Constructor 

    def __init__(self, data): 

        self.data = data 

        self.next_node = None

class linked_list: 

    # Initialize head 

    def __init__(self): 

        self.head_node = None

    # Function to reverse the linked list 

    def reverse_ll(self): 

        previous_node = None

        current_node = self.head_node

        while(current_node is not None): 

            next_node = current_node.next_node

            current_node.next_node = previous_node

            previous_node = current_node 

            current_node = next_node

        self.head_node = previous_node

    # Function to push a node 

    def push_node(self, new_data): 

        new_node = node(new_data) 

        new_node.next_node = self.head_node 

        self.head_node = new_node 

    # Printing the LinkedList 

    def print_ll(self): 

        count = self.head_node

        while(count): 

            print (count.data,end=” “) 

            count = count.next_node

# Testing the functions 

ll = linked_list() 

ll.push_node(2) 

ll.push_node(4) 

ll.push_node(1) 

ll.push_node(8) 

ll.push_node(3) 

print (“Linked List:”) 

ll.print_ll() 

ll.reverse_ll() 

print (“Reversed Linked List:”) 

   Linked List:

   3 8 1 4 2 

   Reversed Linked List

   2 4 1 8 3 

In the above example, the reverse_ll function takes the head node of the linked list as an input and reverses the links between nodes.

9. Write a Python Program to count the number of nodes in a complete Binary Tree.

class node:

    def __init__(self, data):

        self.left_node = None

        self.right_node = None

        self.data = data

# Function to get the total number of nodes in a complete binary tree

def totalnodes(root_node):

    if(root_node == None):

        return 0  

    # Find the left height and right height

    left_height = totalnodes(root_node.left_node)

    right_height = totalnodes(root_node.right_node)

    return 1 + left_height + right_height

# Function to create a new node

def newNode(data):

    Node = node(data)

    return Node

# Testing the function

root_node = newNode(1)

root_node.left_node = newNode(2)

root_node.right_node = newNode(3)

root_node.left_node.left_node = newNode(4)

root_node.left_node.right_node = newNode(5)

root_node.right_node.left_node = newNode(6)

print(“The total number of nodes in the tree is:”,totalnodes(root_node))

  The total number of nodes in the tree is: 6

10. Write a Python Program to find the length of the linked list:

        self.data = data  

        self.next_node = None  

class Linked_List:

    # Initializing head node

    # Function to push a node to the Linked List

    def push(self, new_data):

        new_node = node(new_data)

        new_node.next_node = self.head_node

        self.head_node = new_node

    # Function to count the number of nodes in the Linked List

    def nodeCount(self):

        count = self.head_node # Initialise count

        nodecount = 0 # Initialise nodecount

        while (count):

            nodecount += 1

        return nodecount

#Testing the function

    ll = Linked_List()

    ll.push(9)

    ll.push(4)

    ll.push(1)

    ll.push(0)

    ll.push(2)

    ll.push(8)

    print(“The total count of nodes in the linked list is :”, ll.nodeCount())

The total count of nodes in the linked list is: 6

This brings us to the end of the ‘Data Structure Interview Questions’ blog. This blog covers the most common data structure interview questions through three sections- Interview Questions for freshers, Interview Questions for Experienced, and coding questions. I hope you are clear with all the three sections. Make sure to go through this article before going for the next interview. All the best!

Have a query for us? Kindly let us know in the comments section, and we’ll get in touch with you.

Check out Edureka’s Python Developer Masters Program , crafted by industry experts through extensive research, facilitating expertise in Python and its libraries. This program will help you gain proficiency in Data Science, Machine Learning, Deep Learning, and Natural Language Processing through hands-on projects. This program offers a transformative opportunity to upskill, reshape your career, and access new opportunities. Enroll now to embark on your journey to success!

Recommended videos for you

Php & mysql : server-side scripting language for web development, implementing web services in java, introduction to java/j2ee & soa, nodejs – communication and round robin way, hibernate mapping on the fly, node js express: steps to create restful web app, create restful web application with node.js express, ms .net – an intellisense way of web development, microsoft .net framework : an intellisense way of web development, microsoft sharepoint-the ultimate enterprise collaboration platform, effective persistence using orm with hibernate, php and mysql : server side scripting for web development, building web application using spring framework, spring framework : introduction to spring web mvc & spring with bigdata, node js : steps to create restful web app, microsoft sharepoint 2013 : the ultimate enterprise collaboration platform, mastering regex in perl, portal development and text searching with hibernate, hibernate-the ultimate orm framework, responsive web app using cakephp, recommended blogs for you, how are bootstrap colors implemented, how to reverse a number in java, how to implement instanceof in java, what is the continue statement in java, how to set classpath in java, foreach loop in javascript: one stop solution for beginners, how to convert char to string in java, what is binary search in java how to implement it, all you need to know about javascript objects, bufferedreader in java : how to read text from input stream, how to install xampp server : the ultimate guide, how to implement nested class in java, immutable string in java: all you need to know, how to implement shallow copy and deep copy in java, how to implement a background image in html, how to implement intval in php, what is the concept of string pool in java, what is upcasting and downcasting in java, how to implement print_r in php, how to convert binary to decimal in java, join the discussion cancel reply, trending courses in programming & frameworks, full stack web development internship program.

• 29k Enrolled Learners
• Weekend/Weekday

Java Course Online

• 78k Enrolled Learners

Python Scripting Certification Training

• 14k Enrolled Learners

Flutter App Development Certification Course

• 13k Enrolled Learners

Mastering Java Programming and Microservices ...

• 1k Enrolled Learners

Spring Framework Certification Course

• 12k Enrolled Learners

Node.js Certification Training Course

• 10k Enrolled Learners

Advanced Java Certification Training

• 7k Enrolled Learners

PHP & MySQL with MVC Frameworks Certifica ...

• 5k Enrolled Learners

Data Structures and Algorithms using Java Int ...

• 31k Enrolled Learners

Browse Categories

Subscribe to our newsletter, and get personalized recommendations..

Already have an account? Sign in .

20,00,000 learners love us! Get personalised resources in your inbox.

At least 1 upper-case and 1 lower-case letter

Minimum 8 characters and Maximum 50 characters

We have recieved your contact details.

You will recieve an email from us shortly.

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

I have two variable to check the condition, the time complexity is more if I have declared those variable outside the loop

While solving the LeetCode "Longest Valid Parentheses" problem, I used two variables, canAdd and previousSum , to manage the addition of left parentheses to the stack. After moving the declaration of canAdd and previousSum outside the loop, the execution time increased by 1ms.

• data-structures
• time-complexity

• 3 And the question is ?.... 😉 –  Alexandre Vinçon Commented yesterday
• Why is this tagged with time-complexity ? Why do you mention time complexity in the title? Time complexity is not about a number of milliseconds (or whatever time unit), but about asymptotic behaviour. –  trincot Commented yesterday
• 3 Why should I not upload images of code/data/errors? –  DavidW Commented yesterday
• Don't worry about such trivial changes in execution time. –  Unmitigated Commented yesterday
• 1 You can see such minor changes even when you resubmit the same code. The time complexity is what that matters (the rate of growth when input size increases) - not the actual running time. The latter can vary from run to run. –  Thiyagu Commented yesterday

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer.

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged java data-structures time-complexity or ask your own question .

• The Overflow Blog
• The hidden cost of speed
• The creator of Jenkins discusses CI/CD and balancing business with open source
• Featured on Meta
• Announcing a change to the data-dump process
• Bringing clarity to status tag usage on meta sites
• What does a new user need in a homepage experience on Stack Overflow?
• Feedback requested: How do you use tag hover descriptions for curating and do...
• Staging Ground Reviewer Motivation

Hot Network Questions

• You find yourself locked in a room
• Is response variable/dependent variable data required for simr simulation?
• What should I do if my student has quarrel with my collaborator
• Microsoft SQL In-Memory OLTP in SQL Express 2019/2022
• Creating Layout of 2D Board game
• In roulette, is the frequency of getting long sequences of reds lower than that of shorter sequences?
• Why didn't Air Force Ones have camouflage?
• Pull up resistor question
• How do I safely download and run an older version of software for testing without interfering with the currently installed version?
• Clarification Regarding a Possible Typo in David J. Griffiths' Introduction to Electrodynamics
• What was the first "Star Trek" style teleporter in SF?
• Did Babylon 4 actually do anything in the first shadow war?
• Can Christian Saudi Nationals visit Mecca?
• What's the benefit or drawback of being Small?
• Current in a circuit is 50% lower than predicted by Kirchhoff's law
• Largest number possible with +, -, ÷
• Why is there so much salt in cheese?
• How do I learn more about rocketry?
• Sylvester primes
• Is there a way to do a PhD such that you get a broad view of a field or subfield as a whole?
• Does the USA plan to establish a military facility on Saint Martin's Island in the Bay of Bengal?
• What's the difference? lie down vs lie
• When can the cat and mouse meet?
• Short story about humanoid creatures living on ice, which can swim under the ice and eat the moss/plants that grow on the underside of the ice