what is problem solving in data structure

EnjoyMathematics

Problem-Solving Approaches in Data Structures and Algorithms

This blog highlights some popular problem-solving strategies for solving problems in DSA. Learning to apply these strategies could be one of the best milestones for the learners in mastering data structure and algorithms.

An Incremental approach using Single and Nested loops

One of the simple ideas of our daily problem-solving activities is that we build the partial solution step by step using a loop. There is a different variation to it:

• Input-centric strategy: At each iteration step, we process one input and build the partial solution.
• Output-centric strategy: At each iteration step, we add one output to the solution and build the partial solution.
• Iterative improvement strategy: Here, we start with some easily available approximations of a solution and continuously improve upon it to reach the final solution.

Here are some approaches based on loop: Using a single loop and variables, Using nested loops and variables, Incrementing the loop by a constant (more than 1), Using the loop twice (Double traversal), Using a single loop and prefix array (or extra memory), etc.

Example problems:   Insertion Sort ,  Finding max and min in an array ,  Valid mountain array ,  Find equilibrium index of an array ,  Dutch national flag problem ,  Sort an array in a waveform .

Decrease and Conquer Approach

This strategy is based on finding the solution to a given problem via its one sub-problem solution. Such an approach leads naturally to a recursive algorithm, which reduces the problem to a sequence of smaller input sizes. Until it becomes small enough to be solved, i.e., it reaches the recursion’s base case.

Example problems:   Euclid algorithm of finding GCD ,  Binary Search ,  Josephus problem

Problem-solving using Binary Search

When an array has some order property similar to the sorted array, we can use the binary search idea to solve several searching problems efficiently in O(logn) time complexity. For doing this, we need to modify the standard binary search algorithm based on the conditions given in the problem. The core idea is simple: calculate the mid-index and iterate over the left or right half of the array.

Example problems: Find Peak Element , Search a sorted 2D matrix , Find the square root of an integer , Search in Rotated Sorted Array

Divide and Conquer Approach

This strategy is about dividing a problem into  more than one subproblems,  solving each of them, and then, if necessary, combining their solutions to get a solution to the original problem. We solve many fundamental problems efficiently in computer science by using this strategy.

Example problems:   Merge Sort ,  Quick Sort ,  Median of two sorted arrays

Two Pointers Approach

The two-pointer approach helps us optimize time and space complexity in the case of many searching problems on arrays and linked lists. Here pointers can be pairs of array indices or pointer references to an object. This approach aims to simultaneously iterate over two different input parts to perform fewer operations. There are three variations of this approach:

Pointers are moving in the same direction with the same pace:   Merging two sorted arrays or linked lists, Finding the intersection of two arrays or linked lists , Checking an array is a subset of another array , etc.

Pointers are moving in the same direction at a different pace (Fast and slow pointers):   Partition process in the quick sort , Remove duplicates from the sorted array , Find the middle node in a linked list , Detect loop in a linked list , Move all zeroes to the end , Remove nth node from list end , etc.

Pointers are moving in the opposite direction:  Reversing an array, Check pair sum in an array , Finding triplet with zero-sum , Rainwater trapping problem , Container with most water , etc.

Sliding Window Approach

A sliding window concept is commonly used in solving array/string problems. Here, the window is a contiguous sequence of elements defined by the start and ends indices. We perform some operations on elements within the window and “slide” it in a forward direction by incrementing the left or right end.

This approach can be effective whenever the problem consists of tasks that must be performed on a contiguous block of a fixed or variable size. This could help us improve time complexity in so many problems by converting the nested loop solution into a single loop solution.

Example problems: Longest substring without repeating characters , Count distinct elements in every window , Max continuous series of 1s , Find max consecutive 1's in an array , etc.

Transform and Conquer Approach

This approach is based on transforming a coding problem into another coding problem with some particular property that makes the problem easier to solve. In other words, here we solve the problem is solved in two stages:

• Transformation stage: We transform the original problem into another easier problem to solve.
• Conquering stage: Now, we solve the transformed problem.

Example problems: Pre-sorting based algorithms (Finding the closest pair of points, checking whether all the elements in a given array are distinct, etc.)

Problem-solving using BFS and DFS Traversal

Most tree and graph problems can be solved using DFS and BFS traversal. If the problem is to search for something closer to the root (or source node), we can prefer BFS, and if we need to search for something in-depth, we can choose DFS.

Sometimes, we can use both BFS and DFS traversals when node order is not required. But in some cases, such things are not possible. We need to identify the use case of both traversals to solve the problems efficiently. For example, in binary tree problems:

• We use preorder traversal in a situation when we need to explore all the tree nodes before inspecting any leaves.
• Inorder traversal of BST generates the node's data in increasing order. So we can use inorder to solve several BST problems.
• We can use postorder traversal when we need to explore all the leaf nodes before inspecting any internal nodes.
• Sometimes, we need some specific information about some level. In this situation, BFS traversal helps us to find the output easily.

To solve tree and graph problems, sometimes we pass extra variables or pointers to the function parameters, use helper functions, use parent pointers, store some additional data inside the node, and use data structures like the stack, queue, and priority queue, etc.

Example problems: Find min depth of a binary tree , Merge two binary trees , Find the height of a binary tree , Find the absolute minimum difference in a BST , The kth largest element in a BST , Course scheduling problem , bipartite graph , Find the left view of a binary tree , etc.

Problem-solving using the Data Structures

The data structure is one of the powerful tools of problem-solving in algorithms. It helps us perform some of the critical operations efficiently and improves the time complexity of the solution. Here are some of the key insights:

• Many coding problems require an effcient way to perform the search, insert and delete operations. We can perform all these operations using the hash table in O(1) time average. It's a kind of time-memory tradeoff, where we use extra space to store elements in the hash table to improve performance.
• Sometimes we need to store data in the stack (LIFO order) or queue (FIFO order) to solve several coding problems. 
• Suppose there is a requirement to continuously insert or remove maximum or minimum element (Or element with min or max priority). In that case, we can use a heap (or priority queue) to solve the problem efficiently.
• Sometimes, we store data in Trie, AVL Tree, Segment Tree, etc., to perform some critical operations efficiently. 

Example problems: Next greater element , Valid Parentheses , Largest rectangle in a histogram , Sliding window maximum , kth smallest element in an array , Top k frequent elements , Longest common prefix , Range sum query , Longest consecutive sequence , Check equal array , LFU cache , LRU cache , Counting sort

Dynamic Programming

Dynamic programming is one of the most popular techniques for solving problems with overlapping or repeated subproblems. Here rather than solving overlapping subproblems repeatedly, we solve each smaller subproblems only once and store the results in memory. We can solve a lot of optimization and counting problems using the idea of dynamic programming.

Example problems: Finding nth Fibonacci,  Longest Common Subsequence ,  Climbing Stairs Problem ,  Maximum Subarray Sum ,  Minimum number of Jumps to reach End ,  Minimum Coin Change

Greedy Approach

This solves an optimization problem by expanding a partially constructed solution until a complete solution is reached. We take a greedy choice at each step and add it to the partially constructed solution. This idea produces the optimal global solution without violating the problem’s constraints.

• The greedy choice is the best alternative available at each step is made in the hope that a sequence of locally optimal choices will yield a (globally) optimal solution to the entire problem.
• This approach works in some cases but fails in others. Usually, it is not difficult to design a greedy algorithm itself, but a more difficult task is to prove that it produces an optimal solution.

Example problems: Fractional Knapsack, Dijkstra algorithm, The activity selection problem

Exhaustive Search

This strategy explores all possibilities of solutions until a solution to the problem is found. Therefore, problems are rarely offered to a person to solve the problem using this strategy.

The most important limitation of exhaustive search is its inefficiency. As a rule, the number of solution candidates that need to be processed grows at least exponentially with the problem size, making the approach inappropriate not only for a human but often for a computer as well.

But in some situations, there is a need to explore all possible solution spaces in a coding problem. For example: Find all permutations of a string , Print all subsets , etc.

Backtracking

Backtracking is an improvement over the approach of exhaustive search. It is a method for generating a solution by avoiding unnecessary possibilities of the solutions! The main idea is to build a solution one piece at a time and evaluate each partial solution as follows:

• If a partial solution can be developed further without violating the problem’s constraints, it is done by taking the first remaining valid option at the next stage. ( Think! )
• Suppose there is no valid option at the next stage, i.e., If there is a violation of the problem constraint, the algorithm backtracks to replace the partial solution’s previous stage with the following option for that stage. ( Think! )

In simple words, backtracking involves undoing several wrong choices — the smaller this number, the faster the algorithm finds a solution. In the worst-case scenario, a backtracking algorithm may end up generating all the solutions as an exhaustive search, but this rarely happens!

Example problems: N-queen problem , Find all k combinations , Combination sum , Sudoku solver , etc.

Problem-solving using Bit manipulation and Numbers theory

Some of the coding problems are, by default, mathematical, but sometimes we need to identify the hidden mathematical properties inside the problem. So the idea of number theory and bit manipulation is helpful in so many cases.

Sometimes understanding the bit pattern of the input and processing data at the bit level help us design an efficient solution. The best part is that the computer performs each bit-wise operation in constant time. Even sometimes, bit manipulation can reduce the requirement of extra loops and improve the performance by a considerable margin.

Example problems: Reverse bits , Add binary string , Check the power of two , Find the missing number , etc.

Hope you enjoyed the blog. Later we will write a separate blog on each problem-solving approach. Enjoy learning, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced courses and blogs.

OpenDSA Data Structures and Algorithms Modules Collection

Chapter 21 senior algorithms course.

Show Source |    | About    «   21. 1. Data and Algorithm Analysis   ::   Contents   ::   21. 3. Semester Overview   »

$(function () { var moduleName = "an-introduction-to-problem-solving"; var sections = ['investigation-and-argument', 'heuristics-for-problem-solving-"in-the-small"', 'problem-solving-"in-the-large"', 'pairs-problem-solving', 'errors-in-reasoning', 'references']; TimeMe.initialize({ idleTimeoutInSeconds: 10 }); sections.forEach(function (section, i) { TimeMe.trackTimeOnElement(section); }); var timeObj = {}; setInterval(function () { timeObj[moduleName.substring(0, 5)] = TimeMe.getTimeOnCurrentPageInSeconds().toFixed(2); sections.forEach(function (section, i) { timeObj[i + "-" + section.substring(0, 5)] = TimeMe.getTimeOnElementInSeconds(section).toFixed(2); }); for (var sec of sections) { } console.log(JSON.stringify(timeObj)) }, 2000); });

21. 2. An Introduction to Problem Solving ¶

21. 2.1. an introduction to problem solving ¶.

This document presents a brief overview of selected material from four textbooks (see [FL95, Lev94, WL99, Zei07] in the bibliography). Reading any of these books should help you to become a better problem solver.

To successfully solve any problem, the most important issue to get actively involved. Levine [Lev94] calls this “The Principle of Intimate Engagement”. Writers on problem solving often use terms like “roll up your sleeves” and “get your hands dirty”. It means actively engaging with the problem, and doing some work to get it done. For easier problems, you will “see” an answer fairly quickly once you actively engage, and the issue then is to work through to completion. For most problems, the ones matter most, you won’t “see” an answer right away. For these problems, you will have to use various strategies to come up with a potential solution for even getting started.

Problem solvers can be categorized as either “engagers” or “dismissers”. Engagers typically have a history of success with problem solving. Dismissers have a history of failure. Of course, you might be an engager for one type of problem, and a dismisser for another. Many students do significant problem solving for recreation—Sodoku puzzles, computer games with meaningful problem solving tasks, and all sorts of “puzzles”. They might spend hours engaged with “interesting” problems. Yet, these same students might dismiss math and analytical computer science problems due to a historical lack of success. If you have this problem, then to be successful in life you will need to find ways to get over what is obviously a mental block. You need to learn to transfer successful problem-solving strategies from one part of your life to other parts.

Levine uses examples of trying to repair a clothes dryer or a wobbly table. How to solve the problem might not be immediately obvious. The first step is to take the effort to look at the problem. In this example, it starts by opening the back of the dryer, or looking under the table. This initial investigation can often lead to a solution. It is a matter of adopting the mental attitude of being willing to take the risk and the effort. Then it is a matter of working with the problem for awhile to see what can be done. At that point, a possible solution path might open up. But nothing can be solved unless you are willing to take the time and make the effort. All of the heuristics for solving problems start with that.

Fogler and LeBlanc [FL95] discuss the differences between effective and ineffective problem solvers.

The most important factors that distinguish between ineffective and effective problem solvers are the attitudes with which they approach the problem, their aggressiveness in the problem-solving process, their concern for accuracy, and the solution procedures they use. For example, effective problem solvers believe that problems can be solved through the use of heuristics and careful persistent analysis, while ineffective problem solvers think, “You either know it or you don’t”. Effective problem solvers become very active in the problem-solving process: They draw figures, make sketches, and ask questions of themselves and others. Ineffective problem solvers don’t seem to understand the level of personal effort needed to solve the problem. Effective problem solvers take great care to understand all the facts and relationships accurately. Ineffective problem solvers make judgments without checking for accuracy… By approaching a situation using the characteristic attitudes and actions of an effective problem solver, you will be well on your way to finding the real problem and generating an outstanding solution.

21. 2.1.1. Investigation and Argument ¶

Problem solving has two parts [Zei07]: the investigation and the argument. Students are too used to seeing only the argument in their textbooks and lectures. Unfortunately, to be successful in school (and in life after school), one needs to be good at both, and to understand the differences between these two phases of the process. To solve the problem, you must investigate successfully. Then, to give the answer to your client (solution on homework or exam, or report to boss), you need to be able to make the argument in a way that gets the solution across clearly and succinctly. The argument phase involves good technical writing skills—the ability to make a clear, logical argument. Understanding standard proof techniques can help you. The three most-used proof techniques are deduction (direct proof), contradiction, and induction.

21. 2.1.2. Heuristics for Problem Solving “In the Small” ¶

Write it down After motivation and mental attitude, the most important limitation on your ability to solve problems is biological: While you have lots of storage capacity, your “working memory” is tiny. For active manipulation, you can only store \(7\pm 2\) pieces of information. You can’t change this biological fact. All you can do is take advantage of your environment to get around it. That means, you must put things into your environment to manipulate them. Most often, that translates to writing things down, and doing it in a way that lets you manipulate aspects of the problem (correct representation).

Look for special features Examples include cryptogram addition problems. You might recognize that something on one end must be a 1, in other circumstances one of the numbers must be a zero. Consider the following cryptogram puzzle where you must replace the letters with numbers to make a legal addition problem. In this case, we should recognize two special features: (1) The leading digit of the answer must be a one, and (2) One of the right most digits must be a zero. Recognizing these special features puts us well on the way to solving the full problem.

Go to the extremes Study boundary conditions of the problem. For lots of problems, it helps to start with the small cases, which are one form of boundary condition.

Simplify A version of going to extremes is to simplify the problem. This might give a partial solution that can be extended to the original problem.

Penultimate step What precondition must take place before the final solution step is possible? If you recognize this, then getting to the penultimate step leads to the final solution, and solving the penultimate problem might be easier. Towers of Hanoi gives an excellent example of finding a solution from looking at the penultimate step.

Lateral thinking Be careful about being lead into a blind alley. Using an inappropriate problem-solving strategy might blind you to the solution.

Get your hands dirty Sometimes you need to just “play around” with the problem to get some initial insight. For example, when trying to see the closed form solution to a summation, its often a good place to start writing the first few sums down.

Wishful thinking A version of simplifying the problem. Sometimes you can transform the problem into something easy, or see how to get the start position to something that you could “wish” was the solution. That might be a smaller step to the actual solution.

Symmetry Look for symmetries in the problem. They might give clues to the solution.

21. 2.1.3. Problem Solving “In the Large” ¶

There are lots of standard techniques for solving larger and messier “real-world” problems (the type of problems often encountered by engineers in their professional lives). Fogler and LeBlanc [FL95] discuss such techniques in detail. Here is a brief outline of an overall process for disciplined problem solving of “real world” problems.

Problem Definition The client for a problem will often not state it in the correct way. Your first step toward solution is often to define the “real” problem that needs to be solved. It might not be obvious what this is. To get at the “real” problem, you will need to begin by studying it, collecting information about it, and talking to people familiar with the problem. You might consider restating the problem in a number of ways. Define the desired state. Then make restatements of the current problem formulation that can trigger new insights. Consider looking at the problem statement by making the opposite statement. Alternatively, perhaps we can change the surrounding situation such that the current problem can be “made OK” rather than solved directly.

Generate solutions Once you have settled on a problem statement, you need to generate and analyze a range of possible solutions. Blockbusting and brainstorming techniques can generate a list of possible solutions to study.

Decide the Course of Action There are a number of standard techniques for select from a given list of potential actions (e.g., situation analysis, Pareto analysis, K.T. Problem analysis, decision analysis).

Implement the Solution Getting approval may be the necessary first step to implementation. Once that is taken care of, again there are a number of standard techniques for planning implementations (e.g., Gannt charts, critical path analysis).

Evaluation Evaluation should be built into all phases of the problem solving process.

21. 2.1.4. Pairs Problem Solving ¶

Whimbey & Lochhead [WL99] discuss a technique for pair problem solving that separates the pair into a solver and a listener. The listener plays an active role, being responsible for keeping the problem solver on track and requiring the problem solver to vocalize their process. The listener is actively checking for errors by the problem solver. See the handout for more details on this.

21. 2.1.5. Errors in Reasoning ¶

Again from Whimbey & Lochhead [WL99] comes a description of how people go wrong in problem solving. Specifically related to homework and tests, typical problems stem from failing to read the problem carefully. Thus, students will often fail to use all relevant facts, or plain mis-interpret the problem. Other typical mistakes come from failing to be systematic, or worse yet being just plain careless. All of this indicates that many of the points lost by students on tests and homeworks are not caused by “not knowing the material”, but rather are caused by not executing problem solving effectively. Those are points that don’t need to be lost.

Comprehension in reading is a major factor to success. Proper comprehension of technical material requires careful reading, and often re-reading. There is no such thing as speed reading with comprehension. The mythology of the speed reading advocates, such as “read in thought groups”, “skim for concepts”, and “don’t re-read”, are all ineffective.

21. 2.1.6. References ¶

[FL95] H. Scott Fogler and Steven E. LeBlanc. Strategies for Creative Problem Solving. Prentice Hall, 1995.

[Lev94] Marvin Levine. Effective Problem Solving. Prentice Hall, second edition, 1994.

[WL99] Arthur Whimbey and Jack Lochhead. Problem Solving & Comprehension. Lawrence Erlbaum Associates, sixth edition, 1999.

[Zei07] Paul Zeitz. The Art and Craft of Problem Solving. John Wiley & Sons, second edition, 2007.

Contact Us | | Privacy | | License    «   21. 1. Data and Algorithm Analysis   ::   Contents   ::   21. 3. Semester Overview   »

Contact Us | | Report a bug

DSA Tutorial

Linked lists, stacks & queues, hash tables, shortest path, minimum spanning tree, maximum flow, time complexity, dsa reference, dsa examples, learn data structures and algorithms.

Data Structures and Algorithms (DSA) is a fundamental part of Computer Science that teaches you how to think and solve complex problems systematically.

Using the right data structure and algorithm makes your program run faster, especially when working with lots of data.

Knowing DSA can help you perform better in job interviews and land great jobs in tech companies.

This Tutorial

This tutorial is made to help you learn Data Structures and Algorithms (DSA) fast and easy.

Animations, like the one below, are used to explain ideas along the way.

Delay: {{ delay }}

{{ resultText }}: {{ currVal }}

First, you will learn the fundamentals of DSA: understanding different data structures, basic algorithm concepts, and how they are used in programming.

Then, you will learn more about complex data structures like trees and graphs, study advanced sorting and searching algorithms, explore concepts like time complexity, and more.

This tutorial will give you a solid foundation in Data Structures and Algorithms, an essential skill for any software developer.

Try it Yourself Examples in Every Chapter

In every chapter, you can edit the examples online, and click on a button to view the result.

The code examples in this tutorial are written in Python, C, and Java. You can see this by clicking the "Run Example" button.

Advertisement

What You Should Already Know

Although Data Structures and Algorithms is actually not specific to any programming language, you should have a basic understanding of programming in one of these common programming languages:

DSA History

The word 'algorithm' comes from 'al-Khwarizmi', named after a Persian scholar who lived around year 800.

The concept of algorithmic problem-solving can be traced back to ancient times, long before the invention of computers.

The study of Data Structures and Algorithms really took off with the invention of computers in the 1940s, to efficiently manage and process data.

Today, DSA is a key part of Computer Science education and professional programming, helping us to create faster and more powerful software.

DSA Exercises

Test yourself with exercises.

What does DSA stand for?

Start the Exercise

Learn by taking a quiz! The quiz will give you a signal of how much you know about Data Structures and Algorithms.

Start DSA Quiz

My Learning

Track your progress with the free "My Learning" program here at W3Schools.

Log in to your account, and start earning points!

This is an optional feature. You can study at W3Schools without using My Learning.

Learn by Examples

Learn by examples! This tutorial supplements all explanations with clarifying examples.

See All DSA Examples

COLOR PICKER

Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail: [email protected]

Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail: [email protected]

Top Tutorials

Top references, top examples, get certified.

Contact Information

How to learn data structures and algorithms. 20 problem-solving techniques you must know.

• . December 28, 2020

This is the article I wish I had read when I started coding. Programming is about solving problems and here I will dive deep into 20 problem-solving techniques, with code samples, big O analysis, and challenges so that you can master them. In this article , I outlined a high-level strategy to prepare for your next coding interview as well as the top mistakes to avoid. Here, I will dive deep into 20 problem-solving techniques that you must know to excel at your next interview. They have helped me at work too and even given me ideas for a side project I am working on. Also, the last section includes a step-by-step guide to learn data structures and algorithms , with examples.

I have grouped these techniques in:

• Pointer based
• Recursion based

Sorting and searching

Extending basic data structures, miscellanea.

I will explain each of them, show how to apply them to coding problems, and leave you some exercises so that you can practice on your own.min

This list is part of the study notes that I took before I applied to Amazon. I hope they will be as useful to you as they have been to me.

For your convenience, I have copied here the problem statements, but I have left links to all of the exercises. You can copy-paste my solution and play around with it. I strongly recommend you code your solution and see if it passes the tests.

Some of the questions are better explained through an image or diagram. For these, I have left a comment asking you to open the link to get a graphical description of the problem.

Pointer based techniques

1. two pointers.

This technique is very useful on sorted arrays and arrays whose elements we want to group .

The idea is to use two (or more pointers) to split the array into different areas or groups based on some condition:

• Elements smaller than, equal to and greater than a certain value
• Elements whose sum is too small or too large

The following examples will help you understand this principle.

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.
• Input: numbers = [2,7,11,15], target = 9
• Output: [1,2]
• Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Since the array a is sorted, we know that:

• The largest sum is equal to the sum of the last 2 elements
• The smallest sum is equal to the sum of the first 2 elements
• For any index i in [0, a.size() – 1) => a[i + 1] >= a[i]

With this, we can design the following algorithm:

• We keep 2 pointers: l , starting at the first element of the array, and r starting at to the last.
• If the sum of a[l] + a[r] is smaller than our target, we increment l by one (to change the smallest operand in the addition for another one equal or larger than it at l+1 ); if it is larger than the target, we decrease r by one (to change our largest operand for another one equal or smaller at r-1 ).
• We do this until a[l] + a[r] equals our target or l and r point to the same element (since we cannot use the same element twice) or have crossed, indicating there is no solution.

Here is a simple C++ implementation:

The time complexity is O(N), since we may need to traverse the N elements of the array to find the solution.

The space complexity is O(1), since we only need two pointers, regardless of how many elements the array contains.

There are other ways of solving this problem (using a hash table, for example), but I have used it just as an illustration of the two pointer technique.

Here are two variations of this exercise: three sum and four sum . They can be solved similarly by reducing them to this very same problem.

This is a very common technique: transform a problem whose solution you don’t know to a problem that you can solve .

Remove duplicates from array

Given a sorted array, nums, remove the duplicates in-place such that each element appears only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

• Given nums = [1,1,2],
• Given nums = [0,0,1,1,1,2,2,3,3,4],

It doesn’t matter what values are set beyond the returned length.

The array is sorted and we want to move duplicates to the end of the array, which sounds a lot like grouping based on some condition . How would you solve this problem using two pointers?

• You will need one pointer to iterate through the array, i .
• And a second pointer, n , one to define the area that contains no duplicates: [0,n].

The logic is as follows. If the values of the elements at index i (except i = 0) and i-1 are:

• The same, we don’t do anything – this duplicate will be overwritten by the next unique element in a .
• Different: we add a[i] to the section of the array that contains no duplicates – delimited by n , and increment n by one.

This problem has linear time complexity and constant space complexity (it is usually the case for problems solved using this technique).

Sort colors

Given an array with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not supposed to use the library’s sort function for this problem.

• Input: [2,0,2,1,1,0]
• Output: [0,0,1,1,2,2]

The groups this time are:

• Smaller than 1
• Larger than 1

What we can achieve with 3 pointers.

This implementation is a bit tricky, so make sure you test it thoroughly.

Since need to traverse the array to sort it, the time complexity is O(N). The space complexity is O(1).

Just as a curiosity, this is an instance of the National Dutch flag problem described by Dijkstra.

Remove the n-th node from the end of a linked list

Given a Linked List and a number n, write a function that returns the value at the n-th node from the end of the Linked List.

This is one of the most common variations of the two-pointer technique: introducing an offset so that one of the pointers reaches a certain condition, the other one is in the position you are interested in.

In this case, if we move one of the pointers, f , n times and then start advancing both at the same time by one node, when f reaches the end of the list the other pointer, s , will point to the node right before the node we want to delete.

Make sure you define what n = 1 means (last element or the element before the last element?), and avoid off-by-one errors.

The time and space complexity are the same as the previous problems’.

2. Pointers moving at different speeds

Now, you will have two pointers moving at different speeds : at every iteration, one of the pointers will advance one node and the other will advance two nodes. We can use this variation to:

• Get to the middle element of a linked list
• Detect cycles in a linked list

As usual, it will become clearer once I present some examples.

Find the middle node of a linked list of unknown size

Given a non-empty, singly linked list with head node head, return a middle node of the list. If there are two middle nodes, return the second middle node.

• Input: [1,2,3,4,5]
• Output: Node 3 from this list

Solving this problem in 2 passes is easy: on the first pass we compute the size of the list, L , and on the second pass we only advance L/2 nodes to find the element at the middle of the list. This approach has linear complexity in time and constant in space.

How can we use 2 pointers to find the middle element in one single pass?

If one of the pointers, f , moves twice as fast as the other one s , when f reaches the end, s will be in the middle of the list.

Here’s my solution in C++. Make sure you take into account edge cases (empty list, lists of odd and even sizes, etc) when you test your code.

Detect cycle in a linked list

Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where the tail connects to. If pos is -1, then there is no cycle in the linked list.

• Input: head = [3,2,0,-4], pos = 1
• Output: true
• Explanation: There is a cycle in the linked list, where the tail connects to the second node.

The simplest solution is to add all the nodes to a hash set. When we traverse the list, if we get to a node that has already been added to the set, there is a cycle. If we get to the end of the list, there are no cycles.

This has a time complexity of O(L), being L the length of the list, and space complexity of O(L), since in the worst case – no cycles – we need to add all the elements of the list to the hash set.

Time complexity cannot be improved. However, space complexity can be reduced to O(1). Think for a minute how this can be achieved with two pointers moving at different speeds.

Let’s call these pointers fast and slow. For each node slow visits, fast will move two nodes forward. Why?

• If fast reaches the end of the list, the list does not contain any cycles.
• If there is a cycle, since fast moves twice as fast as slow, it is just a matter of time (iterations, to be more precise) that the fast node catches the slow one, pointing both to the same node, which indicates the existence of a cycle.

Now, let’s translate this solution into code:

Find the duplicate number

Given an array, nums, containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

• Input: [1,3,4,2,2]

This is the same problem/solution as the previous problems, for arrays instead of linked lists.

Here are more problems that can be solved using this technique:

• Detect if two linked lists have elements in common
• Happy numbers

3. Sliding Window

The sliding window technique eases the task of finding optimal chunks of contiguous data that meet a certain condition:

• Longest subarray that …
• Shortest substring containing …

You can think of it as another variation of the two pointer technique, where pointers are updated separately based on a certain condition. Below is the basic recipe for this type of problems, in pseudocode:

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

• Input: “abcabcbb”
• Explanation: The answer is “abc”, with the length of 3

Find the length of the longest substring without repeating characters sounds a lot like *finding optimal *chunks of contiguous data* that meet a certain condition.*

Based on the recipe I described above, you will need:

• Two pointers, l and r , to define our substring s .
• A variable, sol , to store the length of the longest substring we have seen so far.
• A way of keeping track of the characters that form s : a set, seen , will be perfect for this.

While iterating through the string:

• If the current character is in seen you have to increment l to start removing elements from the beginning of our s .
• Otherwise, add the character to seen , move r forward and update sol .

For more practice, you can try the following problems:

• Permutation of a string
• Max consecutive ones

There might be simpler solutions but focus on using this technique to get a better grasp of it.

Recursion based techniques

4. dynamic programming.

I already published an article on this topic that you can find here .

5. Backtracking

The idea behind backtracking is to explore all the potential solutions for a problem, in a smart way. It builds candidate solutions incrementally and as soon as it determines that a candidate solution is not viable, it backtracks to a previous state and tries the next candidate.

Backtracking problems present you with a list of choices. Should you:

• place this piece in this position ?
• add this number to the set?
• try this number in this position next?

After you have picked one of the options, it will get you a new list of choices, until you reach a state where there are no more choices: either you arrived at a solution or there is no solution.

Visually, you are moving from the root of a tree with every choice, until you get to a leaf. The basic high-level recipe (in pseudocode) for a backtracking algorithm is the following:

This can of course change depending on the problem:

• If you need all solutions, the helper function returns nothing (void) to avoid stopping when we find the first solution.
• To backtrack, you may have to bring your program to a previous state before you can move forward
• After you choose a child, you need to detect if the candidate solution is viable or not: the definition of viable depends on the problem

But the core idea is the same: examine, in a systematic way, all paths and backtrack as soon as the current path is no longer viable.

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

• Output: [ [“.Q..”, // Solution 1 “…Q”, “Q…”, “..Q.”], [“..Q.”, // Solution 2 “Q…”, “…Q”, “.Q..”] ]
• Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

This is a classic backtracking problem

• We need all solutions here, which is why the recursive function returns nothing as I explained in the introduction of this section.
• Do not worry too much about the isViableSolution function for now. Try to see the recipe I gave (slightly modified) you in action.

Letter combination

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent (check the link for diagram). Note that 1 does not map to any letters.

• Input: “23”
• Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

For every number in the input, you have several letters to choose from. If you can draw a tree (this is what I do) where the branches are born from the different choices you take, chances are that you can apply backtracking.

Note : Before you start solving any problem, try different approaches: dynamic programming, greedy algorithms, divide and conquer, a combination of algorithms and data structures, etc. Coding is the last step .

My solution, in C++:

Since I knew already the size of the solution, I initialize my candidate with that size and just modified the character at position idx . If the size is not known, this can be done instead:

Sudoku solver

Write a program to solve a Sudoku puzzle by filling the empty cells. Open the link to get a longer description, including an image of the puzzle.

In an interview, unless you have plenty of time, you will not need to implement isViableSolution , just to sketch it. I know a colleague who got this question in an on-site.

Even though the code is long, it is mostly because of isViableSolution . Otherwise, it is not very different from other backtracking problems.

• N queens II
• Generate parenthesis
• Palindromic partitioning
• Letter tile possibilities

I have created a generic separate section for:

• Combinations

Permutations

Because conceptually they are similar: take the elements of a container (array, string, etc) and create subsets from them according to some rule(s).

You will notice that most of these are backtracking problems or very similar.

Given a set of distinct integers, nums, return all possible subsets ( the power set ).

Note: The solution set must not contain duplicate subsets.

• Input: nums = [1,2,3]
• Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

For every index i , you need to generate two solutions:

• One that contains a[i]
• One that does not contain a[i]

Until you get to the end of the array.

Here’s a simple implementation of what we have discussed.

Subsets – containing duplicates

This is a variant of the previous problem. Try playing around with my code to see if you can change it to meet the new requirement. You have to change less than 5 lines.

Given a collection of distinct integers, return all possible permutations.

• Input: [1,2,3]
• Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Very similar to the previous problem, but this time we need to consider all the elements of the array in our candidates. The way we move them around is by swapping elements at different positions.

Permutations with repetitions

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

• Input: [1,1,2]
• Output: [[1,1,2], [1,2,1], [2,1,1] ]

We can apply here the same trick as before for combinations. If you could not come up with this “trick”, you can always use a set to store the solutions and then create and return an array from this set.

As you can see, there is no need to learn every single data structure and algorithm in the literature to solve a vast amount of problems. What is valuable, and can be trained, is the ability to systematically think through a problem and skills to turn your ideas into code .

For extra practice:

• Combination sum
• Another variation: Combination sum II
• Combination sum III

Sorting is not a problem-solving technique per see but as you have seen in the previous sections we have been able to solve many problems by either sorting the input or assuming it was sorted and then applying one of the other techniques.

When you are facing a new problem, ask yourself:

• Can I sort the input? . For example, sometimes you have to return indices, therefore sorting is not an option
• How would this problem change if the elements were sorted?
• How does sorting affect the overall complexity? . The best sorting algorithms have a complexity of O(n log n) – sorting integers can be done in O(n)

For instance, our first problem (Two sum) can be solved in linear time with the two-pointer technique because the input is sorted. However, if we have to sort, the complexity becomes O(n log n).

Here you have a couple of problems that can be easily solved after sorting the input.

Other solutions trade space for time, so it is worth considering them before you start writing any code.

Valid anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

• Input: s = “anagram”, t = “nagaram”
• Input: s = “rat”, t = “car”
• Output: false

By definition, two strings are anagrams if they contain the same characters in different order . Therefore, we can simply sort both strings and compare them. The overall time complexity is O(n log n).

Intersection of two arrays

Given two arrays, write a function to compute their intersection.

• Input: nums1 = [1,2,2,1], nums2 = [2,2]
• Output: [2,2]

You can solve this problem by sorting both arrays and using a two-pointer based approach. Give it a try before reading my solution.

Imagine we have the following arrays:

• A = [1,2,4,5]
• B = [2,3,5,7,9,11]

And two pointers, l for A and r for B, starting at index 0 in each array.

We need to increment l to see if A has a 2: B can’t contain a 1 to the right of r , because it is sorted.

In short, we compare both elements:

• If they are the same, we include them to the array representing the intersection of both arrays and advance both pointers
• If they are different, we move the pointer pointing to the smallest of the two elements.

The time complexity of this approach is O(n log n) – even though the two-pointer part is linear – and the space complexity is O(1) – not including the space needed to store the intersection, of course, in which case we could say it is O(min(length(A), length(B)).

• K closest points to origin . In another section, I will present a different solution, slightly faster.
• Largest number

8. Intervals

Most interval related problems I have seen boil down to:

• Modeling the interval as an array of two elements, a pair/tuple or a custom class (this is the cleanest option)
• Sorting the input
• Iterating through the sorted array and deciding what to do based on the starts/ends of the intervals

You can see this as yet another type of problem that can be simplified after sorting the input, which is why I have included it in this section.

I’m leaving here my solution to two exercises, based on what I have just described. Try them before reading my solutions.

Merge intervals

Given a collection of intervals, merge all overlapping intervals.

• Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
• Output: [[1,6],[8,10],[15,18]]
• Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Interval list intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order . Return the intersection of these two interval lists.

9. Variations on binary search

Binary search is a search algorithm that can be applied to sorted data structures (like arrays or binary search trees) with O(log n) time complexity and O(1) space complexity.

What you might not know is its implementation’s most common bug. Assuming we are performing a binary search in the elements whose range goes from [l,r], the element in the middle is usually computed as:

const int m = (l + r) / 2;

Can you spot the problem here?

This line can overflow. The safe way of computing this middle element is:

const int m = l + (r - l) / 2;

Here’s a basic implementation of binary search, using C++ templates. If you understand how it works and how to implement it correctly, you can solve many problems that just have a little tweak in the requirements or that are binary search problems in disguise.

Integer square root

Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

We need to find a number in the range [0, x], which is sorted. It sounds a lot like a binary search problem.

It is not critical to know this, but we can optimize a little:

• If x is 0 or 1, its square root is x . This lets us start testing numbers from 2.
• The upper bound of the range can be reduced to x/2, since (x/2)^2 = x^2/4 >= x => x >= 4, which is true for any integer in the range [2,…]

With this, we can search in [2, x/2] and speed things up a bit.

• Search insert position
• Random pick with weight
• Minimum in rotated sorted array
• Minimum in rotated sorted array 2

10. Breadth-First Search

This is one of the techniques you need to know to explore trees and graphs. Since many problems can be modeled as graphs, you must know this technique. To implement it, we just need to use a queue q and add to this same queue the children of the nodes we process from q .

At any given point in the iteration, BFS visits all the nodes at the same distance from the origin. This will become clearer after some of these examples.

Word ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of the shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list.
• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.
• beginWord = “hit”,
• endWord = “cog”,
• wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
• Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

I got asked this question during my on-site interview at Amazon. The idea is to model this problem using a graph:

• Nodes represent words
• Edges connect words that only differ by one letter

With this setup, this problem is equivalent to finding a path between two nodes in a graph, which BFS can solve. Since all edges have the same weight (1), we do not need Dijkstra or any other fancier algorithm.

After you visit the DFS section :

What would happen if we use DFS instead? Do you see any benefits/drawbacks?

Order level tree traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Open the link for a graphical description of the problem.

You only need to add here a little tweak to the standard BFS algorithm: you need to know how many elements in the queue you need to process for each level.

This is one approach that can be applied to many other problems.

Let me propose a different kind of challenge: building something, instead of solving abstract problems. I find it more fun and you can add them to your Github profile. Here are just two examples:

• Web crawler using BFS to explore all the links on a website.
• Minesweeper . You can even play a bit to get more familiar with it.

11. Depth-First Search

Similar to BFS in its purpose: explore trees and graphs. DFS is not guaranteed to find the shortest path between two points, but it will find any existing path.

It is usually shorter to implement than BFS. Some people find it easier. Others, because of the recursive calls, not so much. It is up to you. Just make sure you think about potential stack overflow issues if the size of the stack starts to get big.

Some problems are much easier to be solved with DFS/recursion, that it is worth practicing.

Number of islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

• Input: grid = [ [“1″,”1″,”1″,”1″,”0”], [“1″,”1″,”0″,”1″,”0”], [“1″,”1″,”0″,”0″,”0”], [“0″,”0″,”0″,”0″,”0”]]

I got this problem at my first phone interview at Amazon.

As soon as you see a matrix, think of a graph. This problem (and its variations) is very straightforward:

• Iterate through the matrix
• For every 1 you find, increase the counter and sink the island

To sink the island, you need to visit all the surrounding 1s in the matrix, which is equivalent to visit all the neighbors of that node and of all its neighbors , which sounds a lot like a recursive problem.

You can try to solve this using BFS too, but DFS is much shorter.

Symmetric tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Many tree-related problems have relatively straightforward recursive solutions. This problem could be solved using BFS but DFS makes it so much easier.

I will leave this one here as an exercise for you. Just use my solution in case you get stuck.

Take the same challenges and exercises I gave you for BFS and try to implement them using DFS instead. Also, for more practice, give a try to the following exercises:

• Validate BST

12. Topological sort

You can see this algorithm as an application of DFS. Its implementation just needs one minor change to the regular DFS: after processing all the children of a node, add this node to a stack.

It is that simple.

The best way to intuitively understand what this algorithm achieves is to imagine a bunch of tasks, some of which depend on others (task 1 cannot start until task 2 has finished). A topological sort will list all these tasks preserving this structure of dependencies.

Let’s solve a problem using this algorithm.

Course schedule II

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

• Input: 2, [[1,0]]
• Output: [0,1]
• Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
• Input: 4, [[1,0],[2,0],[3,1],[3,2]]
• Output: [0,1,2,3] or [0,2,1,3]
• Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

This is the classical topological sort problem. There are a bunch of courses to take and some depend on others. This can be modeled as a directed graph. A topological sort would return the ordering of courses you should take to finish all courses .

A prerequisite to applying topological sort is that the graph is directed and acyclic . From the problem description, we can see that the graph is directed. We can detect if it contains any cycles and compute a topological sort in the same pass.

A more indirect but still valid approach would be to first check whether it has cycles and only if there are no cycles, compute a topological sort.

Here you can find a few more problems to practice.

13. Dequeues

I have seen data structure mostly used as another way to implement the sliding window technique you read about earlier in this article. The only difference with a standard FIFO queue is that you can operate (insert and delete elements) on both ends of the queue.

That’s it. Simple.

Let’s see how such a minor change can simplify some kind of these problems.

Sliding window maximum

Given an array, nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

*Note: Open the link for a better understanding of the problem (there is an image). *

• Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
• Output: [3,3,5,5,6,7]

We will use the dequeue to store indices , not values. We need this to know what elements are still part of the sliding window. For every iteration, there are four things to do.

• Remove elements in the dequeue which are outside of the current sliding window (one per iteration)
• Remove all elements in the dequeue which are smaller than the current element we are at since they cannot represent the max of that sliding window
• Add the current element to the deque
• Once we have completed the first sliding window, we can start adding elements to our solution. By design, the element at the front of our dequeue will contain the maximum of the sliding window, which is what we are interested in.

This technique can be applied to find the minimum or other properties of a contiguous block of data in an array.

Design your own circular dequeue , to fully grasp the internals of this data structure.

The best way to think of a trie is as an extension of a tree, where you store characters that form words as you move through the different branches of the trie.

There are variants where you store suffixes instead of prefixes, where you use compression to reduce the size of the trie, etc. But at its basic, it is another type of tree.

They are used everywhere:

• Auto-complete
• Spell checkers
• Longest prefix/suffix matching

Implement a trie

Implement a trie with insert, search, and startsWith methods.

Here is a simple implementation (for an interview, of course) of a trie. Compared to a tree, you just:

• An extra boolean to indicate whether that node marks the end of a word
• A data structure to store pointers to the node’s children: a hash table, an array of characters, etc.

Word search II

Given a 2D board and a list of words from the dictionary, find all words on the board. Each word must be constructed from letters of adjacent cells, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

• Input: board = [ [‘o’,’a’,’a’,’n’], [‘e’,’t’,’a’,’e’], [‘i’,’h’,’k’,’r’], [‘i’,’f’,’l’,’v’] ] words = [“oath”,”pea”,”eat”,”rain”]
• Output: [“eat”,”oath”]

This might not be the simplest way of solving this problem, but it is a clear application of a trie.

At every step, you will have built some candidate string and need to check if it belongs to the dictionary. A hash set containing all the words in the dictionary would give a very good performance. Why bothering with a trie then? Because a trie can tell you whether that path is worth exploring or not, improving the efficiency of our solution.

In our previous example, imagine we form the string “oa”.

We can check if this prefix (potential word) exists in our trie. It exists since we have added the word “oath”. Now imagine we keep moving right through our board and form the string “oaa”.

In our trie, there are no words that contain the prefix “oaa”, so we can backtrack at this point.

With a hash set that contains all the words, you could not do this type of prefix matching, unless you create two different tables: one for prefixes and another one for words.

This is a complex problem because it combines different elements and it is not easy to implement, so do not get discouraged if it takes you a few tries (no pun intended) to get it right.

Design your own autocomplete !

15. Two instances of the same data structure

Some problems can be solved by using two different instances of the same data structure, so it is worth keeping it in mind when you get stuck in a problem. I have seen it mostly with:

Do not limit yourself to these.

Find median from a stream of data

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

For example,

• [2,3,4], the median is 3
• [2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) – Add an integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

In increasing order of difficulty:

• Implement a queue using two stacks
• Tree zigzag order traversal
• Media from data stream

16. Bit manipulation

This section deserves a separate article. Here I will list some basic tricks and common bit manipulation problems.

This is the most comprehensive site I have found on this topic. Use it as a reference.

Missing number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

• Input: [3,0,1]

This problem can be solved just by using the XOR operator:

• Any bit XORed with itself produces a 0 -> a ^ a = 0
• Any bit XORed with 0 produces the original bit -> a ^ 0 = a
• XOR is associative = a ^ (b ^ c) = (a ^ b ) ^ c

If we XOR all the numbers in the array (integers in the range [0,n]) with all the integers in [0 to n], the pairs will produce zeroes and the missing number will be XORed with 0 (resulting in itself), solving our problem.

Power of two

Given an integer, write a function to determine if it is a power of two.

I got this one in an interview.

Powers of two can be expressed in binary as a leading 1 and some 0s:

With this, it is simple to figure out if a number is a power of two or not. You can achieve fast if you know what the following line does (I am sure you can figure it out on your own):

x & (x-1)

This trick is worth knowing since it is used a lot.

Number of 1s

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

• Input: 00000000000000000000000000001011
• Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

This problem is very straightforward: iterate through all the bits in the input and count how many how of them are 1s.

Try to use the trick I showed you in the previous exercise to improve the performance of this algorithm (in the average case).

These are for you to practice the previous techniques:

• Single number
• Hamming distance

17. Top ‘K’ Elements

This is another very frequent type of problem. You are given a list of elements and have to return the top K, defining top as:

• The largest/smallest
• The closest/furthest to a point
• The most frequent in the list

I have seen some of the following (or some sort of variation) asked in interviews.

There is no single data structure that will always give the right solution, but the following elements are very useful:

• Priority queue
• Sorting (the input or as an intermediate step)

Priority queues usually provide a better complexity.

Top k frequent words

Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

• Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
• Output: [“i”, “love”]
• Explanation: “i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order.

Pretty straightforward: count how many times each word appears (using a hash table) and somehow return the k most common elements.

For this last part, you either:

• Put all the elements with its frequencies in an array and sort it
• Use a priority queue

It is worth knowing this second approach since it can be applied to other problems.

Here is a simple solution in C++ using a priority queue.

K closest points to origin

We have a list of points on the plane. Find the K closest points to the origin (0, 0). Here, the distance between two points on a plane is the Euclidean distance.

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

• Input: points = [[1,3],[-2,2]], K = 1
• Output: [[-2,2]]

The obvious solution is to compute the distance to every single point, add them to an array, sort and get the top k. This is fine, but it can be improved with a priority queue.

We use a max heap , where the root of the heap is the maximum element of the heap. Why the maximum? Our heap contains the K points closest to the origin and the root points to the element that is the furthest from the origin amongst all the other points. If we find a point closer to this one, it may still be further than the rest, but we need to drop our current top and add this new point to the heap.

18. K-way merge

These problems are common too. There is not a unique approach to all of them, but if you know how to solve the problem of merging 2 lists, you can solve the problem of merging K lists to a bunch of instances of the simpler problem. As I mentioned, this is a very powerful approach that you should always keep in mind.

Merge 2 sorted lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4

We solve this problem with the same Two pointer technique we saw at the beginning of this article. In this case, we traverse linked lists instead of arrays, but the same ideas apply.

Merge k sorted lists

Given an array of linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked-lists into one sort linked-list and return it.

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

This is the general version of the previous problem. As I said, you can reduce this problem to many instances of the previous problem by merging lists 2 at a time. However, here I will present a more efficient solution.

Now, instead of two sorted lists, we have K. We need to create a list from picking the next minimum element of all the lists. Since they are sorted, it will be the first element of one of these lists. Luckily, there is a data structure that returns its minimum element in O(1) and has an insertion complexity of O(log K): a priority queue.

For every list, we add to the priority queue a pair containing:

• The head of that list
• An index to remember to which list that element belongs

After we pop an element, we add its value to our solution and add to the priority queue the new head of that list (the pair stores the value and the index of the list).

With this information, try to solve the problem. You will learn much more from it than from reading my solution without trying first.

19. Rolling hash

Rabin Karp is a great example of how to design a simple and efficient algorithm using intelligently a rolling hash function. It can be used to find a string s in a text t .

The basic ideas that you need to remember to be able to reconstruct this algorithm are the following:

• This is an improvement over the brute force method, where you compare s and every candidate substring, c , which is inefficient.
• If two strings are the same, they will produce the same hash.
• The inverse is not true: two different strings may produce the same hash.
• Using a rolling hash function we can compute the hash of a new string in O(1)

If we put all this together, we will efficiently compute hashes and only compare c and s when they have the same hash, reducing the number of comparisons and thus the average complexity of our algorithm (worst case, we need to compare all substrings and are back to the brute force method).

Find string in text

Return the index of the first occurrence of needle in a haystack, or -1 if the needle is not part of the haystack.

• Input: haystack = “hello”, needle = “ll”
• Input: haystack = “aaaaa”, needle = “bba”

Based on the above paragraphs, try to code the Rabin-Karp algorithm on your own to solve this problem.

20. How to learn new algorithms and data structures

As I have already mentioned here and in other articles, do not try to memorize things. It is counterproductive. You will end up mixing concepts, giving the right solution to the wrong problem, and forgetting what you have memorized. This is why you need to understand the algorithms . If you understand the basic data structures and can turn your ideas into code, you can also code these algorithms.

The best way to learn them is how I showed you when I described the Rabin-Karp algorithm:

1. Understand what problem this algorithm or data structure is trying to solve : Here, learning where other alternatives fall short is helpful. 2. Break it down to the key elements or steps that define the algorithm . Understand them individually and how they connect. From this, code the algorithm .

Example 1: Binary search

• Binary search is an improvement over a linear search for sorted arrays . It reduces the size of the array in half at every step, achieving a complexity of O(logN) instead of N.
• Two points: a)Since the array is sorted, comparing our target to the middle element of the array lets us discard half of the array at every step (the half containing elements that are too large or too small compared to the target . b)If the pointers cross, this is l > r , there is no solution. 3.

Example 2: Quad-tree

I wanted to show you how this breakdown process can be applied to a much more complex data structure. It is very unlikely that you will need to know about quad-trees for an interview. I just read about them once and found them so interesting that I decided to implement them.

What is a quad-tree?

From Wikipedia:

A quadtree is a tree data structure in which each internal node has exactly four children . Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions …

What problem is it trying to solve?

Now that we know the formal definition, I think it is easier to get an intuitive idea of what quadtrees can do from one of its applications.

Imagine we are trying to model a physical system made of a bunch of particles, each having a certain mass. Every particle attracts every other particle in the system. If we have N particles, at every step of our simulation, the number of interactions we need to process grows as N^2. This will be extremely slow for large values of N.

Since the attraction between two particles decays with the square of the distance, we can neglect the contribution of particles that are far. How do we know which particles are far without iterating through all the particles (the problem we are trying to avoid in the first place)? Here is where quadtrees come in handy.

Using quadtrees, we can efficiently query all the particles in a certain region. The lookup takes O(logN) time, making our overall time for every step O(n log n) since we have to do this for N particles.

Notice how at this point we do not care so much about the implementation. This is more of a high-level understanding of the data structure and to get an idea of where it can be useful .

In the next section, we will get into more detail.

What are the key elements of a quad-tree?

Let’s go back to the definition:

A quadtree is a tree data structure in which each internal node has exactly four children .

• They decompose space into adaptable cells
• Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits
• The tree directory follows the spatial decomposition of the quadtree.

So, our quadtree class is not very different from any other tree that you may have encountered (including the trie I presented earlier). Each node will contain:

• An integer representing its maximum capacity
• A boolean indicating whether it is a leaf or not (which means, the node has been divided because it reached its maximum capacity)
• Pointers to it 4 children
• An array of containing the points included in that node

Knowing what problem a data structure is trying to solve and breaking it down to its basic elements makes it much easier to implement it and especially to remember what the data structure is about and when it can be used . All you have to “memorize” is its definitions and properties – which are easier to remember if you think about what it is trying to solve.

Putting it all together

You can try to implement it in your favorite language here .

If you want to learn more about this data structure, I recommend these two to see a quadtree in action.

Nice to know

Here is a list of other topics that are good to know and I have not explicitly mentioned in the article. You don’t need to learn them all in one sitting.

• Disjoin sets . Very handy to solve many problems and easy to implement using arrays or tree-like structures.
• Shortest path algorithms . Dijktra’s algorithm , and at least knowing that there is a “heuristically-optimized version” A* . Also Bellman-Ford and Floyd-Warshall .
• Minimum spanning trees . What they are and how to compute them. These two are the most common algorithms: Kruskal’s (essentially, sorting edges and computing connected components, which can easily be done using disjoint sets) and Prim’s (very similar to Dijkstra’s shortest path algorithm).
• Balanced trees. There are many types, but knowing red-black trees is enough.

Conclusions

I have presented a list of 20 techniques that you will make your next interview a breeze. You will be using some of them at work too, or they might inspire you for side projects.

The point is not to learn every single data structure or algorithm in a book. As you can see, most of them are either basic techniques or small tweaks on basic data structures you already knew. I want to show you that you can achieve a lot with what you already know.

PS: I hope you found this useful. If so, like and share this article and follow me on Twitter .

Leave a Reply Cancel reply

You must be logged in to post a comment.

How to ace coding interviews. The ultimate guide.

What is the difference between a junior and a senior software developer, related posts.

The Ultimate Guide to Crypto Tokens

Coding Challenges: How to Solve Them

UTXO and Account-Based Blockchains

How to Become a Certified Kubernetes Application Developer

Data Structures

Arrays - ds easy problem solving (basic) max score: 10 success rate: 93.07%, 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.00%, left rotation easy problem solving (basic) max score: 20 success rate: 91.43%, sparse arrays medium problem solving (basic) max score: 25 success rate: 97.28%, array manipulation hard problem solving (intermediate) max score: 60 success rate: 61.63%, 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.30%, 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

• Table of Contents
• Course Home
• 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 C++ ¶

By Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College

• 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. Reviewing Basic C++
• 1.8. Getting Started with Data
• 1.9.1. Numeric Data
• 1.9.2. Boolean Data
• 1.9.3. Character Data
• 1.9.4. Pointers
• 1.10.1. Arrays
• 1.10.2. Vectors
• 1.10.3. Strings
• 1.10.4. Hash Tables
• 1.10.5. Unordered Sets
• 1.11.1. Parameter Passing: by Value versus by Reference
• 1.11.2. Arrays as Parameters in Functions
• 1.11.3. Function Overloading
• 1.12.1. A Fraction Class
• 1.12.2. Abstraction and Encapsulation
• 1.12.3. Polymorphism
• 1.12.4. Self Check
• 1.13.1. Logic Gates and Circuits
• 1.13.2. Building Circuits
• 1.14.1. Introduction to Turtles
• 1.14.2. Turtle & TurtleScreen
• 1.14.3. Geometry, Shapes, and Stamps
• 1.14.4. Advanced Features
• 1.15. Summary
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 1.18. Glossary
• 1.19. Matching
• 2.1. Objectives
• 2.2.1. Some Needed Math Notation
• 2.2.2. Applying the Math Notation
• 2.3. Big-O Notation
• 2.4.1. Solution 1: Checking Off
• 2.4.2. Solution 2: Sort and Compare
• 2.4.3. Solution 3: Brute Force
• 2.4.4. Solution 4: Count and Compare
• 2.5. Performance of C++ Data Collections
• 2.6. Analysis of Array and Vector Operators
• 2.7. Analysis of String Operators
• 2.8. Analysis of Hash Tables
• 2.9. Summary
• 2.10. Self Check
• 2.11. Discussion Questions
• 2.12. Programming Exercises
• 2.13. Glossary
• 2.14. Matching
• 3.1. Objectives
• 3.2. What Are Linear Structures?
• 3.3. What is a Stack?
• 3.4. The Stack Abstract Data Type
• 3.5. Using a Stack in C++
• 3.6. Simple Balanced Parentheses
• 3.7. Balanced Symbols - A General Case
• 3.8. Converting Decimal Numbers to Binary Numbers
• 3.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 3.9.2. General Infix-to-Postfix Conversion
• 3.9.3. Postfix Evaluation
• 3.10. What Is a Queue?
• 3.11. The Queue Abstract Data Type
• 3.12. Using a Queue in C++
• 3.13. Simulation: Hot Potato
• 3.14.1. Main Simulation Steps
• 3.14.2. C++ Implementation
• 3.14.3. Discussion
• 3.15. What Is a Deque?
• 3.16. The Deque Abstract Data Type
• 3.17. Using a Deque in C++
• 3.18. Palindrome-Checker
• 3.19. Summary
• 3.20. Discussion Questions
• 3.21. Programming Exercises
• 3.22. Glossary
• 3.23. Matching
• 4.1. Objectives
• 4.2. What Are Linked Structures?
• 4.3. Implementing an Unordered Linked List
• 4.4. The Node Class
• 4.5. The Unordered Linked List Class
• 4.6.1. Analysis of Linked Lists
• 4.7.1. Forward lists
• 4.7.2. Lists
• 4.8. Summary
• 4.9. Discussion Questions
• 4.10. Programming Exercises
• 4.11. Glossary
• 4.12. Matching
• 5.1. Objectives
• 5.2. What Is Recursion?
• 5.3. Calculating the Sum of a Vector 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. Self-check
• 5.15. Discussion Questions
• 5.16. Programming Exercises
• 5.17. Glossary
• 5.18. Matching
• 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. Self Check
• 6.7. Summary
• 6.8. Discussion Questions
• 6.9. Programming Exercises
• 6.10. Glossary
• 6.11. Matching
• 7.1. Objectives
• 7.2. Sorting
• 7.3. The Bubble Sort
• 7.4. The Selection Sort
• 7.5. The Insertion Sort
• 7.6. The Shell Sort
• 7.7. The Merge Sort
• 7.8. The Quick Sort
• 7.9. Self Check
• 7.10. Summary
• 7.11. Discussion Questions
• 7.12. Programming Exercises
• 7.13. Glossary
• 7.14. Matching
• 8.1. Objectives
• 8.2. Examples of Trees
• 8.3. Vocabulary and Definitions
• 8.4. Nodes and References
• 8.5. Parse Tree
• 8.6. Tree Traversals
• 8.7. Priority Queues with Binary Heaps
• 8.8. Priority Queues with Binary Heaps Example
• 8.9. Binary Heap Operations
• 8.10.1. The Structure Property
• 8.10.2. The Heap Order Property
• 8.10.3. Heap Operations
• 8.11. Binary Search Trees
• 8.12. Search Tree Operations
• 8.13. Search Tree Implementation
• 8.14. Search Tree Analysis
• 8.15. Balanced Binary Search Trees
• 8.16. AVL Tree Performance
• 8.17. AVL Tree Implementation
• 8.18. Summary of Map ADT Implementations
• 8.19. Summary
• 8.20. Discussion Questions
• 8.21. Programming Exercises
• 8.22. Glossary
• 8.23. Matching
• 9.1. Objectives
• 9.2. Vocabulary and Definitions
• 9.3. The Graph Abstract Data Type
• 9.4. An Adjacency Matrix
• 9.5. An Adjacency List
• 9.6. Implementation
• 9.7. The Word Ladder Problem
• 9.8. Building the Word Ladder Graph
• 9.9. Implementing Breadth First Search
• 9.10. Breadth First Search Analysis
• 9.11. The Knight’s Tour Problem
• 9.12. Building the Knight’s Tour Graph
• 9.13. Implementing Knight’s Tour
• 9.14. Knight’s Tour Analysis
• 9.15. General Depth First Search
• 9.16. Depth First Search Analysis
• 9.17. Topological Sorting
• 9.18. Strongly Connected Components
• 9.19. Shortest Path Problems
• 9.20. Dijkstra’s Algorithm
• 9.21. Analysis of Dijkstra’s Algorithm
• 9.22. Prim’s Spanning Tree Algorithm
• 9.23. Summary
• 9.24. Discussion Questions
• 9.25. Programming Exercises
• 9.26. Glossary
• 9.27. Matching

Acknowledgements ¶

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

Indices and tables ¶

Module Index

Search Page

• Table of Contents
• Scratch ActiveCode
• Navigation Help
• Help for Instructors
• About Runestone
• Report A Problem
• 1. Introduction
• 2. Analysis
• 3. Basic Data Structures
• 4. Recursion
• 5. Sorting and Searching
• 6. Trees and Tree Algorithms
• 7. Graphs and Graph Algorithms

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College (as remixed by Jeffrey Elkner)

• 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. Objectives
• 2.2. What Is Algorithm Analysis?
• 2.3. Big-O Notation
• 2.4.1. Solution 1: Checking Off
• 2.4.2. Solution 2: Sort and Compare
• 2.4.3. Solution 3: Brute Force
• 2.4.4. Solution 4: Count and Compare
• 2.5. Performance of Python Data Structures
• 2.7. Dictionaries
• 2.8. Summary
• 2.9. Key Terms
• 2.10. Discussion Questions
• 2.11. Programming Exercises
• 3.1. Objectives
• 3.2. What Are Linear Structures?
• 3.3. What is a Stack?
• 3.4. The Stack Abstract Data Type
• 3.5. Implementing a Stack in Python
• 3.6. Simple Balanced Parentheses
• 3.7. Balanced Symbols (A General Case)
• 3.8. Converting Decimal Numbers to Binary Numbers
• 3.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 3.9.2. General Infix-to-Postfix Conversion
• 3.9.3. Postfix Evaluation
• 3.10. What Is a Queue?
• 3.11. The Queue Abstract Data Type
• 3.12. Implementing a Queue in Python
• 3.13. Simulation: Hot Potato
• 3.14.1. Main Simulation Steps
• 3.14.2. Python Implementation
• 3.14.3. Discussion
• 3.15. What Is a Deque?
• 3.16. The Deque Abstract Data Type
• 3.17. Implementing a Deque in Python
• 3.18. Palindrome-Checker
• 3.19. Lists
• 3.20. The Unordered List Abstract Data Type
• 3.21.1. The Node Class
• 3.21.2. The Unordered List Class
• 3.22. The Ordered List Abstract Data Type
• 3.23.1. Analysis of Linked Lists
• 3.24. Summary
• 3.25. Key Terms
• 3.26. Discussion Questions
• 3.27. Programming Exercises
• 4.1. Objectives
• 4.2. What Is Recursion?
• 4.3. Calculating the Sum of a List of Numbers
• 4.4. The Three Laws of Recursion
• 4.5. Converting an Integer to a String in Any Base
• 4.6. Stack Frames: Implementing Recursion
• 4.7. Introduction: Visualizing Recursion
• 4.8. Sierpinski Triangle
• 4.9. Complex Recursive Problems
• 4.10. Tower of Hanoi
• 4.11. Exploring a Maze
• 4.12. Dynamic Programming
• 4.13. Summary
• 4.14. Key Terms
• 4.15. Discussion Questions
• 4.16. Glossary
• 4.17. Programming Exercises
• 5.1. Objectives
• 5.2. Searching
• 5.3.1. Analysis of Sequential Search
• 5.4.1. Analysis of Binary Search
• 5.5.1. Hash Functions
• 5.5.2. Collision Resolution
• 5.5.3. Implementing the Map Abstract Data Type
• 5.5.4. Analysis of Hashing
• 5.6. Sorting
• 5.7. The Bubble Sort
• 5.8. The Selection Sort
• 5.9. The Insertion Sort
• 5.10. The Shell Sort
• 5.11. The Merge Sort
• 5.12. The Quick Sort
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Programming Exercises
• 6.1. Objectives
• 6.2. Examples of Trees
• 6.3. Vocabulary and Definitions
• 6.4. List of Lists Representation
• 6.5. Nodes and References
• 6.6. Parse Tree
• 6.7. Tree Traversals
• 6.8. Priority Queues with Binary Heaps
• 6.9. Binary Heap Operations
• 6.10.1. The Structure Property
• 6.10.2. The Heap Order Property
• 6.10.3. Heap Operations
• 6.11. Binary Search Trees
• 6.12. Search Tree Operations
• 6.13. Search Tree Implementation
• 6.14. Search Tree Analysis
• 6.15. Balanced Binary Search Trees
• 6.16. AVL Tree Performance
• 6.17. AVL Tree Implementation
• 6.18. Summary of Map ADT Implementations
• 6.19. Summary
• 6.20. Key Terms
• 6.21. Discussion Questions
• 6.22. Programming Exercises
• 7.1. Objectives
• 7.2. Vocabulary and Definitions
• 7.3. The Graph Abstract Data Type
• 7.4. An Adjacency Matrix
• 7.5. An Adjacency List
• 7.6. Implementation
• 7.7. The Word Ladder Problem
• 7.8. Building the Word Ladder Graph
• 7.9. Implementing Breadth First Search
• 7.10. Breadth First Search Analysis
• 7.11. The Knight’s Tour Problem
• 7.12. Building the Knight’s Tour Graph
• 7.13. Implementing Knight’s Tour
• 7.14. Knight’s Tour Analysis
• 7.15. General Depth First Search
• 7.16. Depth First Search Analysis
• 7.17. Topological Sorting
• 7.18. Strongly Connected Components
• 7.19. Shortest Path Problems
• 7.20. Dijkstra’s Algorithm
• 7.21. Analysis of Dijkstra’s Algorithm
• 7.22. Prim’s Spanning Tree Algorithm
• 7.23. Summary
• 7.24. Key Terms
• 7.25. Discussion Questions
• 7.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 ¶

• Module Index
• Search Page

5 Structured Thinking Techniques for Data Scientists

Try 1 of these 5 structured thinking techniques as you wrestle with your next data science project.

Structured thinking is a framework for solving unstructured problems — which covers just about all data science problems. Using a structured approach to solve problems not only only helps solve problems faster but also helps identify the parts of the problem that may need some extra attention. 

Think of structured thinking like the map of a city you’re visiting for the first time.Without a map, you’ll probably find it difficult to reach your destination. Even if you did eventually reach your destination, it’ll probably take you at least double the time.

What Is Structured Thinking?

Here’s where the analogy breaks down: Structured thinking is a framework and not a fixed mindset; you can modify these techniques based on the problem you’re trying to solve.  Let’s look at five structured thinking techniques to use in your next data science project .

• Six Step Problem Solving Model
• Eight Disciplines of Problem Solving
• The Drill Down Technique
• The Cynefin Framework
• The 5 Whys Technique

More From Sara A. Metwalli 3 Reasons Data Scientists Need Linear Algebra

1. Six Step Problem Solving Model

This technique is the simplest and easiest to use. As the name suggests, this technique uses six steps to solve a problem, which are:

Have a clear and concise problem definition.

Study the roots of the problem.

Brainstorm possible solutions to the problem.

Examine the possible solution and choose the best one.

Implement the solution effectively.

Evaluate the results.

This model follows the mindset of continuous development and improvement. So, on step six, if your results didn’t turn out the way you wanted, go back to step four and choose another solution (or to step one and try to define the problem differently).

My favorite part about this simple technique is how easy it is to alter based on the specific problem you’re attempting to solve. 

We’ve Got Your Data Science Professionalization Right Here 4 Types of Projects You Need in Your Data Science Portfolio

2. Eight Disciplines of Problem Solving

The eight disciplines of problem solving offers a practical plan to solve a problem using an eight-step process. You can think of this technique as an extended, more-detailed version of the six step problem-solving model.

Each of the eight disciplines in this process should move you a step closer to finding the optimal solution to your problem. So, after you’ve got the prerequisites of your problem, you can follow  disciplines D1-D8.

D1 : Put together your team. Having a team with the skills to solve the project can make moving forward much easier.

D2 : Define the problem. Describe the problem using quantifiable terms: the who, what, where, when, why and how.

D3 : Develop a working plan.

D4 : Determine and identify root causes. Identify the root causes of the problem using cause and effect diagrams to map causes against their effects.

D5 : Choose and verify permanent corrections. Based on the root causes, assess the work plan you developed earlier and edit as needed.

D6 : Implement the corrected action plan.

D7 : Assess your results.

D8 : Congratulate your team. After the end of a project, it’s essential to take a step back and appreciate the work you’ve all done before jumping into a new project.

3. The Drill Down Technique

The drill down technique is more suitable for large, complex problems with multiple collaborators. The whole purpose of using this technique is to break down a problem to its roots to make finding solutions that much easier. To use the drill down technique, you first need to create a table. The first column of the table will contain the outlined definition of the problem, followed by a second column containing the factors causing this problem. Finally, the third column will contain the cause of the second column's contents, and you’ll continue to drill down on each column until you reach the root of the problem.

Once you reach the root causes of the symptoms, you can begin developing solutions for the bigger problem.

On That Note . . . 4 Essential Skills Every Data Scientist Needs

4. The Cynefin Framework

The Cynefin framework, like the rest of the techniques, works by breaking down a problem into its root causes to reach an efficient solution. We consider the Cynefin framework a higher-level approach because it requires you to place your problem into one of five contexts.

• Obvious Contexts. In this context, your options are clear, and the cause-and-effect relationships are apparent and easy to point out.
• Complicated Contexts. In this context, the problem might have several correct solutions. In this case, a clear relationship between cause and effect may exist, but it’s not equally apparent to everyone.
• Complex Contexts. If it’s impossible to find a direct answer to your problem, then you’re looking at a complex context. Complex contexts are problems that have unpredictable answers. The best approach here is to follow a trial and error approach.
• Chaotic Contexts. In this context, there is no apparent relationship between cause and effect and our main goal is to establish a correlation between the causes and effects.
• Disorder. The final context is disorder, the most difficult of the contexts to categorize. The only way to diagnose disorder is to eliminate the other contexts and gather further information.

Get the Job You Want. We Can Help. Apply for Data Science Jobs on Built In

5. The 5 Whys Technique

Our final technique is the 5 Whys or, as I like to call it, the curious child approach. I think this is the most well-known and natural approach to problem solving.

This technique follows the simple approach of asking “why” five times — like a child would. First, you start with the main problem and ask why it occurred. Then you keep asking why until you reach the root cause of said problem. (Fair warning, you may need to ask more than five whys to find your answer.)

Recent Data Modeling Articles

Get full access to Introduction to Python Programming and Data Structures, 3rd Edition by Pearson and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

Introduction to Python Programming and Data Structures, 3rd Edition by Pearson

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Book description

Introduction to Python Programming and Data Structures focuses on the fundamentals first to help learners learn problem solving and programming in a broad context. It introduces basic programming concepts and techniques on selections, loops, and functions, before writing custom classes. Step-by-step coverage demonstrates the use of Python to solve problems. Exercises and problems with varying levels of difficulty cover interesting application areas. The best way to learn programming is by practicing, and this introduction offers many opportunities to practice creating efficient, elegant code.

The 3rd Edition has new data structures topics and UpToDate content, examples and exercises that keep pace with recent trends.

Table of contents

• About Pearson
• Brief Contents
• 1.1 Introduction
• 1.2 What Is a Computer?
• 1.3 Programming Languages
• 1.4 Operating Systems
• 1.5 The History of Python
• 1.6 Getting Started with Python
• 1.7 Programming Style and Documentation
• 1.8 Programming Errors
• 1.9 Getting Started with Graphics Programming
• 2.1 Introduction
• 2.2 Writing a Simple Program
• 2.3 Reading Input from the Console
• 2.4 Identifiers
• 2.5 Variables, Assignment Statements, and Expressions
• 2.6 Simultaneous Assignments
• 2.7 Named Constants
• 2.8 Numeric Data Types and Operators
• 2.9 Case Study: Minimum Number of Changes
• 2.10 Evaluating Expressions and Operator Precedence
• 2.11 Augmented Assignment Operators
• 2.12 Type Conversions and Rounding
• 2.13 Case Study: Displaying the Current Time
• 2.14 Software Development Process
• 2.15 Case Study: Computing Distances
• 3.1 Introduction
• 3.2 Boolean Types, Values, and Expressions
• 3.3 Generating Random Numbers
• 3.4 if Statements
• 3.5 Two-Way if-else Statements
• 3.6 Nested if and Multi-Way if-elif-else Statements
• 3.7 Common Errors in Selection Statements
• 3.8 Case Study: Computing Body Mass Index
• 3.9 Case Study: Computing Taxes
• 3.10 Logical Operators
• 3.11 Case Study: Determining Leap Years
• 3.12 Case Study: Lottery
• 3.13 Conditional Expressions
• 3.14 Python 3.10 match-case Statements
• 3.15 Operator Precedence and Associativity
• 3.16 Detecting the Location of an Object
• 4.1 Introduction
• 4.2 Common Python Functions
• 4.3 Strings and Characters
• 4.4 Case Study: Revising the Lottery Program Using Strings
• 4.5 Introduction to Objects and Methods
• 4.6 String Methods
• 4.7 Case Studies
• 4.8 Formatting Numbers and Strings
• 4.9 Drawing Various Shapes
• 4.10 Drawing with Colors and Fonts
• 5.1 Introduction
• 5.2 The while Loop
• 5.3 Case Study: Guessing Numbers
• 5.4 Loop Design Strategies
• 5.5 Controlling a Loop with User Confirmation and Sentinel Value
• 5.6 The for Loop
• 5.7 Nested Loops
• 5.8 Minimizing Numerical Errors
• 5.9 Case Studies
• 5.10 Keywords break and continue
• 5.11 Case Study: Checking Palindromes
• 5.12 Case Study: Displaying Prime Numbers
• 5.13 Case Study: Random Walk
• 6.1 Introduction
• 6.2 Defining a Function
• 6.3 Calling a Function
• 6.4 Functions with/without Return Values
• 6.5 Positional and Keyword Arguments
• 6.6 Passing Arguments by Reference Values
• 6.7 Modularizing Code
• 6.8 The Scope of Variables
• 6.9 Default Arguments
• 6.10 Returning Multiple Values
• 6.11 Case Study: Generating Random ASCII Characters
• 6.12 Case Study: Converting Hexadecimals to Decimals
• 6.13 Function Abstraction and Stepwise Refinement
• 6.14 Case Study: Reusable Graphics Functions
• 7.1 Introduction
• 7.2 List Basics
• 7.3 Case Study: Analyzing Numbers
• 7.4 Case Study: Deck of Cards
• 7.5 Copying Lists
• 7.6 Passing Lists to Functions
• 7.7 Returning a List from a Function
• 7.8 Case Study: Counting the Occurrences of Each Letter
• 7.9 Searching Lists
• 7.10 Sorting Lists
• 8.1 Introduction
• 8.2 Processing Two-Dimensional Lists
• 8.3 Passing Two-Dimensional Lists to Functions
• 8.4 Problem: Grading a Multiple-Choice Test
• 8.5 Problem: Finding the Closest Pair
• 8.6 Problem: Sudoku
• 8.7 Multidimensional Lists
• 9.1 Introduction
• 9.2 Defining Classes for Objects
• 9.3 UML Class Diagrams
• 9.4 Using Classes from the Python Library: the datetime Class
• 9.5 Immutable Objects vs. Mutable Objects
• 9.6 Hiding Data Fields
• 9.7 Class Abstraction and Encapsulation
• 9.8 Object-Oriented Thinking
• 9.9 Operator Overloading and Special Methods
• 9.10 Case Study: The Rational Class
• 10.1 Introduction
• 10.2 Getting Started with Tkinter
• 10.3 Processing Events
• 10.4 The Widget Classes
• 10.5 Canvas
• 10.6 The Geometry Managers
• 10.7 Case Study: Loan Calculator
• 10.8 Case Study: Sudoku GUI
• 10.9 Displaying Images
• 10.10 Case Study: Deck of Cards GUI
• 11.1 Introduction
• 11.2 Combo Boxes
• 11.4 Pop-up Menus
• 11.5 Mouse, Key Events, and Bindings
• 11.6 Case Study: Finding the Closest Pair
• 11.7 Animations
• 11.8 Case Study: Bouncing Balls
• 11.9 Scrollbars
• 11.10 Standard Dialog Boxes
• 12.1 Introduction
• 12.2 Superclasses and Subclasses
• 12.3 Overriding Methods
• 12.4 The object Class
• 12.5 Polymorphism and Dynamic Binding
• 12.6 The isinstance Function
• 12.7 Case Study: A Reusable Clock
• 12.8 Class Relationships
• 12.9 Case Study: Designing the Course Class
• 12.10 Case Study: Designing a Class for Stacks
• 12.11 Case Study: The FigureCanvas Class
• 13.1 Introduction
• 13.2 Text Input and Output
• 13.3 File Dialogs
• 13.4 Case Study: Counting Each Letter in a File
• 13.5 Retrieving Data from the Web
• 13.6 Exception Handling
• 13.7 Raising Exceptions
• 13.8 Processing Exceptions Using Exception Objects
• 13.9 Defining Custom Exception Classes
• 13.10 Case Study: Web Crawler
• 13.11 Binary IO Using Pickling
• 13.12 Case Study: Address Book
• 14.1 Introduction
• 14.2 Tuples
• 14.4 Comparing the Performance of Sets and Lists
• 14.5 Case Study: Counting Keywords
• 14.6 Dictionaries
• 14.7 Case Study: Occurrences of Words
• 15.1 Introduction
• 15.2 Case Study: Computing Factorials
• 15.3 Case Study: Computing Fibonacci Numbers
• 15.4 Problem Solving Using Recursion
• 15.5 Recursive Helper Functions
• 15.6 Case Study: Finding the Directory Size
• 15.7 Case Study: Tower of Hanoi
• 15.8 Case Study: Fractals
• 15.9 Case Study: Eight Queens
• 15.10 Recursion vs. Iteration
• 15.11 Tail Recursion
• 16.1 Introduction
• 16.2 Measuring Algorithm Efficiency Using Big O Notation
• 16.3 Examples: Determining Big O
• 16.4 Analyzing Algorithm Time Complexity
• 16.5 Finding Fibonacci Numbers Using Dynamic Programming
• 16.6 Finding Greatest Common Divisors Using Euclid’s Algorithm
• 16.7 Efficient Algorithms for Finding Prime Numbers
• 16.8 Finding Closest Pair of Points Using Divide-and-Conquer
• 16.9 Solving the Eight Queen Problem Using Backtracking
• 16.10 Computational Geometry: Finding a Convex Hull
• 16.11 String Matching
• 17.1 Introduction
• 17.2 Insertion Sort
• 17.3 Bubble Sort
• 17.4 Merge Sort
• 17.5 Quick Sort
• 17.6 Heap Sort
• 17.7 Bucket Sort and Radix Sort
• 18.1 Introduction
• 18.2 Linked Lists
• 18.3 The LinkedList Class
• 18.4 Implementing LinkedList
• 18.5 List vs. Linked List
• 18.6 Variations of Linked Lists
• 18.7 Iterators
• 18.8 Generators
• 18.9 Stacks
• 18.10 Queues
• 18.11 Priority Queues
• 18.12 Case Study: Evaluating Expressions
• 19.1 Introduction
• 19.2 Binary Search Trees Basics
• 19.3 Representing Binary Search Trees
• 19.4 Searching for an Element in BST
• 19.5 Inserting an Element into a BST
• 19.6 Tree Traversal
• 19.7 The BST Class
• 19.8 Deleting Elements in a BST
• 19.9 Tree Visualization
• 19.10 Case Study: Data Compression
• 20.1 Introduction
• 20.2 Rebalancing Trees
• 20.3 Designing Classes for AVL Trees
• 20.4 Overriding the insert Method
• 20.5 Implementing Rotations
• 20.6 Implementing the delete Method
• 20.7 The AVLTree Class
• 20.8 Testing the AVLTree Class
• 20.9 Maximum Height of an AVL Tree
• 21.1 Introduction
• 21.2 What Is Hashing?
• 21.3 Hash Functions and Hash Codes
• 21.4 Handling Collisions Using Open Addressing
• 21.5 Handling Collisions Using Separate Chaining
• 21.6 Load Factor and Rehashing
• 21.7 Implementing a Map Using Hashing
• 21.8 Implementing a Set Using Hashing
• 22.1 Introduction
• 22.2 Basic Graph Terminologies
• 22.3 Representing Graphs
• 22.4 Modeling Graphs
• 22.5 Graph Visualization
• 22.6 Graph Traversals
• 22.7 Depth-First Search (DFS)
• 22.8 Case Study: The Connected Circles Problem
• 22.9 Breadth-First Search (BFS)
• 22.10 Case Study: The Nine Tail Problem
• 23.1 Introduction
• 23.2 Representing Weighted Graphs
• 23.3 The WeightedGraph Class
• 23.4 Minimum Spanning
• 23.5 Finding Shortest Paths
• 23.6 Case Study: The Weighted Nine Tail Problem
• Appendix A: Python Keywords
• Appendix B: The ASCII Character Set
• Appendix C: Number Systems
• Appendix D: Command Line Arguments
• Appendix E: Regular Expressions
• Appendix F: Bitwise Operations
• Appendix G: The Big-O, Big-Omega, and Big-Theta Notations
• Appendix H: Operator Precedence Chart
• Symbol Index

Product information

• Title: Introduction to Python Programming and Data Structures, 3rd Edition by Pearson
• Author(s): Liang
• Release date: December 2023
• Publisher(s): Pearson India
• ISBN: 9789357055857

You might also like

Head first python, 3rd edition.

by Paul Barry

What will you learn from this book? Want to learn the Python language without slogging your …

Learn Python the Hard Way: A Deceptively Simple Introduction to the Terrifyingly Beautiful World of Computers and Data Science, 5th Edition

by Zed A. Shaw

You Will Learn Python! Zed Shaw has created the world's most reliable system for learning Python. …

A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

by Jay Wengrow

p>If you thought data structures and algorithms were all just theory, you're missing out on what …

Python Crash Course, 2nd Edition

by Eric Matthes

This is the second edition of the best selling Python book in the world. Python Crash …

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

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

Array Without Last Element | Programming Tutorials | Lab

Labby - Jul 13

Build a Compiler in C language

Bek Brace - Jul 16

Exploring Transformer Networks: Revolutionizing Deep Learning

Monish Kumar - Jul 12

Supercharging Developer Productivity: Claude Project

Wilfried PETIT - Aug 3

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

• Quality Improvement
• Talk To Minitab

The Basics of Structured Problem-Solving Methodologies: DMAIC & 8D

Topics: Minitab Engage

When it comes to solving a problem, organizations want to get to the root cause of the problem, as quickly as possible. They also want to ensure that they find the most effective solution to that problem, make sure the solution is implemented fully, and is sustained into the future so that the problem no longer occurs. The best way to do this is by implementing structured problem-solving. In this blog post, we’ll briefly cover structured problem-solving and the best improvement methodologies to achieve operational excellence. Before we dive into ways Minitab can help, let’s first cover the basics of problem-solving.

WHAT IS STRUCTURED PROBLEM-SOLVING?

Structured problem-solving is a disciplined approach that breaks down the problem-solving process into discrete steps with clear objectives. This method enables you to tackle complex problems, while ensuring you’re resolving the right ones. It also ensures that you fully understand those problems, you've considered the reasonable solutions, and are effectively implementing and sustaining them.

WHAT IS A STRUCTURED PROBLEM-SOLVING METHODOLOGY?

A structured problem-solving methodology is a technique that consists of a series of phases that a project must pass through before it gets completed. The goal of a methodology is to highlight the intention behind solving a particular problem and offers a strategic way to resolve it. WHAT ARE THE BEST PROBLEM-SOLVING METHODOLOGIES?

That depends on the problem you’re trying to solve for your improvement initiative. The structure and discipline of completing all the steps in each methodology is more important than the specific methodology chosen. To help you easily visualize these methodologies, we’ve created the Periodic Table of Problem-Solving Methodologies. Now let’s cover two important methodologies for successful process improvement and problem prevention: DMAIC and 8D .

8D is known as the Eight Disciplines of problem-solving. It consists of eight steps to solve difficult, recurring, or critical problems. The methodology consists of problem-solving tools to help you identify, correct, and eliminate the source of problems within your organization. If the problem you’re trying to solve is complex and needs to be resolved quickly, 8D might be the right methodology to implement for your organization. Each methodology could be supported with a project template, where its roadmap corresponds to the set of phases in that methodology. It is a best practice to complete each step of a given methodology, before moving on to the next one.

MINITAB ENGAGE, YOUR SOLUTION TO EFFECTIVE PROBLEM-SOLVING

Minitab Engage TM was built to help organizations drive innovation and improvement initiatives. What makes our solution unique is that it combines structured problem-solving methodologies with tools and dashboards to help you plan, execute, and measure your innovation initiatives! There are many problem-solving methodologies and tools to help you get started. We have the ultimate end-to-end improvement solution to help you reach innovation success.

Ready to explore structured problem-solving?

Download our free eBook to discover the top methodologies and tools to help you accelerate your innovation programs.

See how our experts can train your company to better understand and utilize data. Find out more about our Training Services today!

You Might Also Like

• Trust Center

© 2023 Minitab, LLC. All Rights Reserved.

• Terms of Use
• Privacy Policy
• Cookies Settings

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

Top 100 Data Structure and Algorithms DSA Interview Questions Topic-wise

DSA has been one of the most popular go-to topics for any interview, be it college placements, software developer roles, or any other technical roles for freshers and experienced to land a decent job. If you are among them, you already know that it is not easy to find the best DSA interview questions among the vast pool of available problems. So here we are, with the Top 100 most asked DSA interview questions to help you sail through your technical rounds.

Top 100 Data Structure and Algorithms (DSA) Interview Questions Topic-wise

Table of Content

DSA Interview Questions on Array

Dsa interview questions on matrix, dsa interview questions on string, dsa interview questions on linked list, dsa interview questions on stack & queue, dsa interview questions on tree, dsa interview questions on heap, dsa interview questions on graph, dsa interview questions on dynamic programming, dsa interview questions on bit manipulations.

In this Top 100 DSA interview questions, we have segregated the problems based on the Data structure or algorithm used to solve them . Without further delay, let us begin your interview preparations:

• Check if pair with the given Sum exists in Array
• Best Time to Buy and Sell Stock
• Find duplicates
• Product of Array Except Self
• Maximum Subarray
• Maximum Product Subarray
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• Container With Most Water
• Find the Factorial of a large number
• Trapping Rain Water
• Chocolate Distribution Problem
• Insert Interval
• Merge Intervals
• Non-overlapping Intervals
• Set Matrix Zeroes
• Spiral Matrix
• Program to find the transpose of a matrix
• Word Search
• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Smallest window in a String containing all characters of other String
• Check whether two Strings are anagram of each other
• print all anagrams together
• Check if given Parentheses expression is balanced or not
• Sentence Palindrome
• Longest Palindromic Substring
• Palindromic Substrings
• Longest Common Prefix
• Reverse a Linked List
• Detect Cycle in a Linked List
• Merge Two Sorted Lists
• Merge K Sorted Lists
• Remove Nth Node From End Of List
• Reorder List
• Add 1 to a number represented as linked list
• Find the middle of a given linked list
• Delete last occurrence of an item from linked list
• Convert Infix expression to Postfix expression
• Next Greater Element
• Delete middle element of a stack
• Check mirror in n-ary tree
• The Celebrity Problem
• Length of the longest valid substring
• Print Right View of a Binary Tree
• Find the first circular tour that visits all petrol pumps
• Maximum Depth of Binary Tree
• Check if two trees have same structure
• Invert/Flip Binary Tree
• Binary Tree Maximum Path Sum
• Binary Tree Level Order Traversal
• Serialize and Deserialize Binary Tree
• Subtree of Another Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of BST
• Implement Trie (Prefix Tree)
• Add and Search Word
• Top K Frequent Elements
• Find Median from Data Stream
• Largest triplet product in a stream
• Connect n ropes with minimum cost
• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Number of Islands
• Longest Consecutive Sequence
• Snake and Ladder Problem
• Detect Cycle in a Directed Graph
• Bridges in a graph
• Check whether a given graph is Bipartite or not
• Find size of the largest region in Boolean Matrix
• Flood fill Algorithm
• Strongly Connected Components
• Topological Sorting
• Count ways to reach the n’th stair
• Coin Change
• 0/1 Knapsack Problem
• Longest Increasing Subsequence
• Longest Common Subsequence
• Word Break Problem
• Dice Throw 
• Egg Dropping Puzzle
• Matrix Chain Multiplication
• Combination Sum
• Subset Sum Problem
• Find maximum possible stolen value from houses
• Count Possible Decodings of a given Digit Sequence
• Unique paths in a Grid with Obstacles
• Cutting a Rod
• Maximum Product Cutting
• Count number of ways to cover a distance
• Number of 1 Bits
• Counting Bits
• Missing Number
• Reverse Bits
• Find XOR of all subsets of a set

Related posts:

• Commonly Asked Data Structure Interview Questions
• Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, …

Some other important Tutorials:

• System Design Tutorial
• Software Development Roadmap
• Roadmap to become a Product Manager

Please Login to comment...

Similar reads.

• Interview Questions
• interview-preparation
• interview-questions

Improve your Coding Skills with Practice

What kind of Experience do you want to share?