data structures and algorithms problem solving

• 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

Data Structures

Arrays - ds easy problem solving (basic) max score: 10 success rate: 93.08%, 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: 86.99%, 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.61%, print the elements of a linked list easy problem solving (basic) max score: 5 success rate: 97.16%, 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.32%, 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

DSA Tutorial

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

Data Structures is about how data can be stored in different structures.

Algorithms is about how to solve different problems, often by searching through and manipulating data structures.

Theory about Data Structures and Algorithms (DSA) helps us to use large amounts of data to solve problems efficiently.

What are Data Structures?

A data structure is a way to store data.

We structure data in different ways depending on what data we have, and what we want to do with it.

First, let's consider an example without computers in mind, just to get the idea.

If we want to store data about people we are related to, we use a family tree as the data structure. We choose a family tree as the data structure because we have information about people we are related to and how they are related, and we want an overview so that we can easily find a specific family member, several generations back.

With such a family tree data structure visually in front of you, it is easy to see, for example, who my mother's mother is—it is 'Emma,' right? But without the links from child to parents that this data structure provides, it would be difficult to determine how the individuals are related.

Data structures give us the possibility to manage large amounts of data efficiently for uses such as large databases and internet indexing services.

Data structures are essential ingredients in creating fast and powerful algorithms. They help in managing and organizing data, reduce complexity, and increase efficiency.

In Computer Science there are two different kinds of data structures.

Primitive Data Structures are basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.

Abstract Data Structures are higher-level data structures that are built using primitive data types and provide more complex and specialized operations. Some common examples of abstract data structures include arrays, linked lists, stacks, queues, trees, and graphs.

What are Algorithms?

An algorithm is a set of step-by-step instructions to solve a given problem or achieve a specific goal.

A cooking recipe written on a piece of paper is an example of an algorithm, where the goal is to make a certain dinner. The steps needed to make a specific dinner are described exactly.

When we talk about algorithms in Computer Science, the step-by-step instructions are written in a programming language, and instead of food ingredients, an algorithm uses data structures.

Algorithms are fundamental to computer programming as they provide step-by-step instructions for executing tasks. An efficient algorithm can help us to find the solution we are looking for, and to transform a slow program into a faster one.

By studying algorithms, developers can write better programs.

Algorithm examples:

• Finding the fastest route in a GPS navigation system
• Navigating an airplane or a car (cruise control)
• Finding what users search for (search engine)
• Sorting, for example sorting movies by rating

The algorithms we will look at in this tutorial are designed to solve specific problems, and are often made to work on specific data structures. For example, the 'Bubble Sort' algorithm is designed to sort values, and is made to work on arrays.

Data Structures together with Algorithms

Data structures and algorithms (DSA) go hand in hand. A data structure is not worth much if you cannot search through it or manipulate it efficiently using algorithms, and the algorithms in this tutorial are not worth much without a data structure to work on.

DSA is about finding efficient ways to store and retrieve data, to perform operations on data, and to solve specific problems.

By understanding DSA, you can:

• Decide which data structure or algorithm is best for a given situation.
• Make programs that run faster or use less memory.
• Understand how to approach complex problems and solve them in a systematic way.

Where is Data Structures and Algorithms Needed?

Data Structures and Algorithms (DSA) are used in virtually every software system, from operating systems to web applications:

• For managing large amounts of data, such as in a social network or a search engine.
• For scheduling tasks, to decide which task a computer should do first.
• For planning routes, like in a GPS system to find the shortest path from A to B.
• For optimizing processes, such as arranging tasks so they can be completed as quickly as possible.
• For solving complex problems: From finding the best way to pack a truck to making a computer 'learn' from data.

DSA is fundamental in nearly every part of the software world:

• Operating Systems
• Database Systems
• Web Applications
• Machine Learning
• Video Games
• Cryptographic Systems
• Data Analysis
• Search Engines

Theory and Terminology

As we go along in this tutorial, new theoretical concepts and terminology (new words) will be needed so that we can better understand the data structures and algorithms we will be working on.

These new words and concepts will be introduced and explained properly when they are needed, but here is a list of some key terms, just to get an overview of what is coming:

Where to Start?

In this tutorial, you will first learn about a data structure with matching algorithms, before moving on to the next data structure.

Further into the tutorial the concepts become more complex, and it is therefore a good idea to learn DSA by doing the tutorial step-by-step from the start.

And as mentioned on the previous page, you should be comfortable in at least one of the most common programming languages, like for example JavaScript , C or Python , before doing this tutorial.

On the next page we will look at two different algorithms that prints out the first 100 Fibonacci numbers using only primitive data structures (two integer variables). One algorithm uses a loop, and one algorithm uses something called recursion.

Click the 'Next' button to continue.

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.

Learn Python practically and Get Certified .

Popular Tutorials

Popular examples, reference materials, learn python interactively, learn ds & algorithms.

A computer program is a collection of instructions to perform a specific task. For this, a computer program may need to store data, retrieve data, and perform computations on the data.

A data structure is a named location that can be used to store and organize data. And, an algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allow us to write efficient and optimized computer programs.

Our DSA tutorial will guide you to learn different types of data structures and algorithms and their implementations in Python, C, C++, and Java.

Do you want to learn DSA the right way? Enroll in our Interactive DSA Course for FREE.

• Introduction

Data Structures (I)

Data structures (ii), tree based dsa (i), tree based dsa (ii), graph based dsa.

• Sorting and Searching

Greedy Algorithms

• Dynamic Programming

Other Algorithms

• How to learn DSA?

DSA Introduction

• What is an algorithm?
• Data Structure and Types
• Why learn algorithms?
• Asymptotic Notations
• Master Theorem
• Divide and Conquer Algorithm
• Types of Queue
• Circular Queue
• Priority Queue
• Linked List
• Linked List Operations
• Types of Linked List
• Heap Data Structure
• Fibonacci Heap
• Decrease Key and Delete node from Fibonacci Heap
• Tree Data Structure
• Tree Traversal
• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
• Binary Search Tree
• Insertion into B-tree
• Deletion from B-tree
• Insertion on a B+ Tree
• Deletion from a B+ Tree
• Red Black Tree
• Insertion in Red Black Tree
• Deletion from Red Black Tree
• Graph Data Structure
• Spanning Tree
• Strongly Connected Components
• Adjacency Matrix
• Adjacency List
• DFS Algorithm
• Breadth-first Search
• Bellman Ford's Algorithm

Sorting and Searching Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Linear Search
• Binary Search
• Greedy Algorithm
• Ford-Fulkerson Algorithm
• Dijkstra's Algorithm
• Kruskal's Algorithm
• Prim's Algorithm
• Huffman Code
• Floyd Warshall Algorithm
• Longest Common Subsequence
• Backtracking Algorithm
• Rabin-Karp Algorithm

Why Learn DSA?

• Write optimized and scalable code - Once you have knowledge about different data structures and algorithms, you can determine which data structure and algorithm to choose in various conditions.
• Effective use of time and memory - Having knowledge about data structures and algorithms will help you write codes that run faster and require less storage.
• Better job opportunities - Data structures and algorithms questions are frequently asked in job interviews of various organizations including Google, Facebook, and so on.

How you can learn data structure and algorithms?

Interactive dsa course.

Want to learn DSA with Python by solving quizzes and challenges after learning each concept? Enroll in our DSA Interactive Course for FREE.

Learn DSA from Programiz

Programiz offers a complete series of easy to follow DSA tutorials along with suitable examples. These tutorials are targeted for absolute beginners who want to dive into the field of computer programming.

Learn DSA from Books

Learning from books is always a good practice. You will get the big picture of programming concepts in the book which you may not find elsewhere.

Here are some books we personally recommend.

• Introduction to Algorithms, Thomas H. Cormen - it is one of the best books in algorithms and covers a broad range of algorithms in-depth
• Algorithms, Robert Sedgewick - it is the leading textbook on algorithms and is widely used in colleges and universities
• The Art of Computer Programming, Donald E. Knuth - this book is considered best if you know the subject and are looking for deeper understanding

Learn DSA through visualization

Once you have some idea about data structure and algorithms, there is a great resource at Data Structure Visualizations that lets you learn through animation.

Ace your Coding Interview

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

Data Structures and Algorithms Problems

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

Rate this post

Average rating 4.88 /5. Vote count: 5923

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

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

Tell us how we can improve this post?

Thanks for reading.

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

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

Navigation Menu

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

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

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Several Coding Patterns for Solving Data Structures and Algorithms Problems during Interviews

Chanda-Abdul/Several-Coding-Patterns-for-Solving-Data-Structures-and-Algorithms-Problems-during-Interviews

Folders and files.

Repository files navigation

These are my notes in Javascript from a course that categorizes coding interview problems into a set of 16 patterns .

Additional Resources

Here are a few other resources that I found helpful when learning Data Structures and Algorithms using JavaScript

• Run JS - A JavaScript playground for your desktop
• Big O CheatSheet - Reference for Big-O complexities of common algorithms
• Blind 75 - For additional practice, the Blind75 list of interview questions is 🔥. I would approach the questions in this order or this order or create a custom Blind75 study plan
• Edabit is a great resource if you need additional Javascript practice before you start using leetcode .
• LeetCode of course 😋
• Pramp - for mock interviews
• FreeCodeCamp's Algorithms - Extra practice, esp. the Sort Algorithms section.
• Build 15 JavaScript Projects - Vanilla JavaScript Course - for extra Vanilla JavaScript/DOM Manipulation practice.

🌟 Challenge Questions

👩🏽‍🦯 questions from blind 75, 😐📖 questions tagged facebook/meta, 🌴 questions tagged amazon, 🔎 questions tagged google, pattern 1: sliding window.

In many problems dealing with an array (or a LinkedList ), we are asked to find or calculate something among all the contiguous subarrays (or sublists) of a given size. For example, take a look at this problem:

Given an array, find the average of all contiguous subarrays of size K in it.

Lets understand this problem with a real input:

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

A brute-force algorithm will calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by 5 to find the average.

The efficient way to solve this problem would be to visualize each contiguous subarray as a sliding window of 5 elements. This means that we will slide the window by one element when we move on to the next subarray. To reuse the sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find the sum and, as a result, the algorithm complexity will reduce to O(N) .

Pattern 2: Two Pointer

In problems where we deal with sorted arrays (or LinkedList s) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray. For example, take a look at the following problem:

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target .

To solve this problem, we can consider each element one by one (pointed out by the first pointer) and iterate through the remaining elements (pointed out by the second pointer) to find a pair with the given sum. The time complexity of this algorithm will be O(N^2) where n is the number of elements in the input array.

Given that the input array is sorted, an efficient way would be to start with one pointer in the beginning and another pointer at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do not, we will do one of two things:

• If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
• If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Pattern 3: Fast & Slow pointers

The Fast & Slow pointer approach, also known as the Hare & Tortoise algorithm , is a pointer algorithm that uses two pointers which move through the array (or sequence/ LinkedList ) at different speeds. This approach is quite useful when dealing with cyclic LinkedList s or arrays.

By moving at different speeds (say, in a cyclic LinkedList ), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

One of the famous problems solved using this technique was Finding a cycle in a LinkedList . Lets jump onto this problem to understand the Fast & Slow pattern.

Pattern 4: Merge Intervals

This pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.

Given two intervals ( a and b ), there will be six distinct ways the two intervals can relate to each other:

• a and b do not overlap
• a and b overlap, b ends after a
• a completely overlaps b
• a and b overlap, a ends after b
• b completly overlaps a

Pattern 5: Cyclic Sort

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. For example, take the following problem:

You are given an unsorted array containing numbers taken from the range 1 to n . The array can have duplicates, which means that some numbers will be missing. Find all the missing numbers.

To efficiently solve this problem, we can use the fact that the input array contains numbers in the range of 1 to n . For example, to efficiently sort the array, we can try placing each number in its correct place, i.e., placing 1 at index 0 , placing 2 at index 1 , and so on. Once we are done with the sorting, we can iterate the array to find all indices that are missing the correct numbers. These will be our required numbers.

Pattern 6: In-place Reversal of a LinkedList

In a lot of problems, we are asked to reverse the links between a set of nodes of a LinkedList . Often, the constraint is that we need to do this in-place , i.e., using the existing node objects and without using extra memory.

in-place Reversal of a LinkedList pattern describes an efficient way to solve the above problem.

Pattern 7: Tree Breadth First Search

This pattern is based on the Breadth First Search (BFS) technique to traverse a tree.

Any problem involving the traversal of a tree in a level-by-level order can be efficiently solved using this approach. We will use a Queue to keep track of all the nodes of a level before we jump onto the next level. This also means that the space complexity of the algorithm will be O(W) , where W is the maximum number of nodes on any level.

Pattern 8: Depth First Search (DFS)

This pattern is based on the Depth First Search (DFS) technique to traverse a tree.

We will be using recursion (or we can also use a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be O(H) , where H is the maximum height of the tree.

Pattern 9: Two Heaps

In many problems, where we are given a set of elements such that we can divide them into two parts. To solve the problem, we are interested in knowing the smallest element in one part and the biggest element in the other part. This pattern is an efficient approach to solve such problems.

This pattern uses two Heaps to solve these problems; A Min Heap to find the smallest element and a Max Heap to find the biggest element.

Pattern 10: Subsets

A huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements. This pattern describes an efficient Breadth First Search (BFS) approach to handle all these problems.

Pattern 11: Modified Binary Search

As we know, whenever we are given a sorted Array or LinkedList or Matrix , and we are asked to find a certain element, the best algorithm we can use is the Binary Search .

Pattern 12: Bitwise XOR

XOR is a logical bitwise operator that returns 0 (false) if both bits are the same and returns 1 (true) otherwise. In other words, it only returns 1 if exactly one bit is set to 1 out of the two bits in comparison.

Pattern 13: Top 'K' Elements

Any problem that asks us to find the top/smallest/frequent K elements among a given set falls under this pattern.

Pattern 14: K-way merge

This pattern helps us solve problems that involve a list of sorted arrays.

Whenever we are given K sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays. We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum. While inserting elements to the Min Heap we keep track of which array the element came from. We can, then, remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.

Pattern 15: 0/1 Knapsack (Dynamic Programming)

0/1 Knapsack pattern is based on the famous problem with the same name which is efficiently solved using Dynamic Programming (DP) .

In this pattern, we will go through a set of problems to develop an understanding of DP . We will always start with a brute-force recursive solution to see the overlapping subproblems, i.e., realizing that we are solving the same problems repeatedly.

After the recursive solution, we will modify our algorithm to apply advanced techniques of Memoization and Bottom-Up Dynamic Programming to develop a complete understanding of this pattern.

Pattern 16: 🔎 Topological Sort (Graph)

Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event B is dependent on event A , A comes before B in topological ordering.

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

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College

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

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

Acknowledgements ¶

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

Indices and tables ¶

Search Page

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

Exploits Ep - 1: From Prototype Pollution to a 100% Discount

Adnan Hashmi - Aug 3

How to Use the React Context API in Your Projects

Sudhanshu Gaikwad - Jul 27

Singleton and Unmodifiable Collections and Maps

Paul Ngugi - Jul 13

Declarando Variáveis de Controle de Laço Dentro do for

DevsJavaGirlsBR - Jul 13

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

EnjoyMathematics

Steps of Problem Solving in Data Structures and Algorithms

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

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

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

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

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

Step 1: Understanding the problem

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

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

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

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

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

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

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

Step 2: Thinking of a correct basic solution

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

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

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

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

Step 3: Designing efficient solution with pseudocode

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

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

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

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

Find equilibrium index of an array

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

Trapping rain water

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

Check for pair with a given sum

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

Find the majority element in an array

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

Maximum Subarray Sum

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

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

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

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

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

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

Enjoy learning, Enjoy coding, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced courses and blogs.

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

Welcome to the daily solving of our PROBLEM OF THE DAY with Karan Mashru We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Greedy but also build up problem-solving skills. You are given timings of n meetings in the form of (start[i], end[i]) where start[i]   is the start time of meeting i and end[i] is the finish time of meeting i. Return the maximum number of meetings that can be accommodated in a single meeting room, when only one meeting can be held in the meeting room at a particular time. 

Note: The start time of one chosen meeting can't be equal to the end time of the other chosen meeting.

Input: n = 6, start[] = [1, 3, 0, 5, 8, 5], end[] =  [2, 4, 6, 7, 9, 9] Output: 4 Explanation: Maximum four meetings can be held with given start and end timings. The meetings are - (1, 2), (3, 4), (5,7) and (8,9)  

Give the problem a try before going through the video. All the best!!! Problem Link: https://practice.geeksforgeeks.org/problems/n-meetings-in-one-room-1587115620/1