Data structures and algorithms problems in C++ using STL

 
The Standard Template Library (STL) is a library for the C++ programming language. The STL provides many useful algorithms and containers. The Containers are objects that store data. We have taken help of following containers to solve mentioned problems –

vector, list, queue, priority_queue, stack, set, map, multimap, unordered_set, unordered_multiset, unordered_map, unordered_multimap
 

We have avoided using STL algorithms as main purpose of these problems are to improve your coding skills and using in-built algorithms will do no good.. Nevertheless, we have still used following common algorithms at many places –

minmaxswapsortnext_permutationbinary_searchrotatereverse

 

Priority Queue (Heap) –

 

Graphs –

 

Array –

  • Rearrange the array with alternate high and low elements
  • Find pair with given sum in the array
  • Shuffle a given array of elements (Fisher–Yates shuffle)
  • Find equilibrium index of an array
  • Find majority element in an array (Boyer–Moore majority vote algorithm)
  • Find sub-array with 0 sum
  • Find maximum length sub-array having given sum
  • Find maximum length sub-array having equal number of 0’s and 1’s
  • Find all distinct combinations of given length
  • Find all distinct combinations of given length – Part 2
  • Find all distinct combinations of given length with repetition allowed
  • Merging Overlapping Intervals
  • Find minimum platforms needed in the station so to avoid any delay in arrival of any train
  • Longest Increasing Subsequence
  • Iterative Implementation of Quicksort
  • Custom Sort | Sort elements by their frequency and Index
  • Custom Sort | Sort elements of the array by order of elements defined by the second array
  • Find Triplet with given sum in an array
  • 4 sum problem | Quadruplets with given sum
  • Binary Search
  • Find the peak element in an array
  • Activity Selection Problem
  • Job Sequencing Problem with Deadlines
  • Maximum Product Subset Problem
  • Find pairs with given difference k in the array | Constant space solution
  • Find pairs with given difference k in the array
  • Quickselect Algorithm
  • Check if subarray with 0 sum is exists or not
  • 4 sum problem | Quadruplets with given sum
  • Print all distinct Subsets of a given Set
  • K-Partition Problem | Printing all Partitions
  • 3 Partition Problem
  • 3-partition problem extended | Print all partitions
  • Find Frequency of each element in a sorted array containing duplicates
  • Replace each element of the array by its corresponding rank in the array
  • Group elements of an array based on their first occurrence
  • Find all Symmetric Pairs in an Array of Pairs
  • Find count of distinct elements in every sub-array of size k
  • Print all sub-arrays of an array having distinct elements
  • Find ways to calculate a target from elements of specified array
  • Find Minimum Index of Repeating Element in an Array
  • Check if an Array is Formed by Consecutive Integers
  • Find two non-overlapping pairs having same sum in an array
  • Find two numbers with maximum sum formed by array digits
  • Count the distinct absolute values in the sorted array
  • Find subarrays with given sum in an array
  • Find the surpasser count for each element of an array
  • Find maximum absolute difference between sum of two non-overlapping sub-arrays
  • Print all combination of numbers from 1 to n having sum n
  • Find Index of Maximum Occurring Element with Equal Probability
  •  

    Matrix –

     

    Strings –

  • Check if given string is a rotated palindrome or not
  • Check if repeated subsequence is present in the string or not
  • Check if strings can be derived from each other by circularly rotating them
  • Determine if two strings are anagram or not
  • Find all binary strings that can be formed from given wildcard pattern
  • Find all interleavings of given strings
  • Isomorphic Strings
  • Find all possible palindromic substrings in a string
  • Find all possible combinations of words formed from mobile keypad
  • Find all combinations by replacing given digits with characters of the corresponding list
  • Find all words from given list that follows same order of characters as given pattern
  • Find first k non-repeating characters in a string in single traversal
  • Group anagrams together from given list of words
  • Reverse text without reversing the individual words
  • Validate an IP address
  • Find the longest substring of given string containing k distinct characters
  • Find all palindromic permutations of a string
  • Find all substrings of a string that are permutation of a given string
  • Longest substring of given string containing distinct characters
  • Find all Permutations of a given string
  • Find all lexicographically next permutations of a string sorted in ascending order
  • Find Lexicographically minimal string rotation
  • Find all N-digit binary numbers with k-bits set where k ranges from 1 to N
  • Generate binary numbers between 1 to N
  • Calculate rank of given string among all its lexicographically sorted permutations
  • Shortest Superstring Problem
  • Check if given string is interleaving of two other given strings
  • Iterative Approach to find Permutations of a String in C++ and Java
  • std::next_permutation | Overview & Implementation in C++
  • std::prev_permutation | Overview & Implementation in C++
  • Implementation of KMP Algorithm in C, C++ and Java
  • Construct the longest palindrome by shuffling or deleting characters from a string
  • Determine if characters of a String follows a specified order or not
  • Determine if a pattern matches with a string or not
  •  

    Binary Tree –

  • Check if two binary trees are identical or not | Iterative & Recursive
  • Calculate height of binary tree | Iterative & Recursive
  • Delete given Binary Tree | Iterative & Recursive
  • Level Order Traversal of Binary Tree
  • Spiral Order Traversal of Binary Tree
  • Reverse Level Order Traversal of Binary Tree
  • Print all nodes of a given binary tree in specific order
  • Print left view of binary tree
  • Print Bottom View of Binary Tree
  • Print Top View of Binary Tree
  • Find next node in same level for given node in a binary tree
  • Check if given binary tree is complete binary tree or not
  • Determine if given binary tree is a subtree of another binary tree or not
  • Postorder Tree Traversal | Iterative & Recursive
  • Preorder Tree Traversal | Iterative & Recursive
  • Inorder Tree Traversal | Iterative & Recursive
  • Find ancestors of given node in a Binary Tree
  • Find Vertical Sum in a given Binary Tree
  • Print nodes in vertical order of a given Binary Tree (Vertical Traversal)
  • Find the diagonal sum of given binary tree
  • Print Diagonal Traversal of Binary Tree
  • Print corner nodes of every level in binary tree
  • Print Right View of a Binary Tree
  • Find maximum width of given binary tree
  • Build Binary Tree from given Parent array
  • Find a pair with given sum in a BST
  • Construct a Binary Tree from Ancestor Matrix
  • Print leaf to root path for every leaf node in a binary tree
  •  

    Dynamic Programming –

  • Introduction to Dynamic Programming
  • Longest Common Subsequence | Introduction & LCS Length
  • Longest Common Subsequence | Finding all LCS
  • Longest Common Subsequence of K-sequences
  • Longest Palindromic Subsequence using Dynamic Programming
  • Longest Repeated Subsequence problem
  • Shortest Common Supersequence | Introduction & SCS Length
  • Find longest sequence formed by adjacent numbers in the matrix
  • Count number of paths in a matrix with given cost to reach destination cell
  • 0-1 Knapsack problem
  • Subset sum problem
  • Minimum Sum Partition problem
  • Coin Change Problem (Total number of ways to get the denomination of coins)
  • Find optimal cost to construct Binary Search Tree
  • Maximum Length Snake Sequence
  • Check if given string is interleaving of two other given strings
  • Find ways to calculate a target from elements of specified array
  •  

    Linked List –

     

    Miscellaneous –

     
     

    Thank you for being with us. 🙂

     


    Leave a Reply

    avatar
      Subscribe  
    newest oldest most voted
    Notify of
    bogomipz
    Guest

    I’ve spent the last hour browsing and I would like to say this is a great resource for coding problems. I like that the methodology for solving them is discussed for each posting.

    Michael
    Guest

    amazing work!

    TartanLlama
    Guest

    This is a pretty impressively large collection of algorithms, but I’m curious how you envisage them being used in an interview setting. I give quite a lot of interviews and I’d never dream of giving most of these as on-the-spot implementation problems.

    Matt Robinson
    Guest

    I watched a google mock interview one time.
    The interviewer gave the problem and had the interviewee start working on a solution.
    Generally, they would work towards the “obvious” solution (often the first solution shown in the links above). You cant expect everyone to come up with the “best” solution right away. The interviewer then tried to coax the problem solver into finding a better solution with questions such as “what if we can only go over the list once? How can we use the number of occurences to help us? (you get the idea, depends on the problem).”

    The optimal solution for many of these are quite clever and very hard to think of. But it gives a good idea of how the interviewee thinks. Also, if you choose a relatively simple problem, if they can at least come up with the “obvious” solution.

    Anshul
    Guest

    I have been using your website for quite a while and I find it to be absolutely great in DS and Algo preparation for technical interviews. The explanation and the solution TechieDelight provides on most questions is probably the best available online, much better than every other website. Thank you and your team for helping me in my preparation.

    Jerick
    Guest

    It’s a gift from the CS gods to professors: Here’s several years worth of homework assignments.

    AlgoLover
    Guest

    A really cool algorithmic problem I’ve been obsessed with lately is stable sorting in O(n log n) time and O(1) extra space. It’s possible (Trabb Pardo 1977, Katajainen and Pasanen, Huang and Langston, etc.) but all known algorithms are very complicated. As far as I understand now, there seems to be a “wall” at sqrt(n) extra space. If we have that much, it’s not too hard to write a stable mergesort or quicksort with the right time complexity. But if we are restricted to O(1) or O(log n) space, the algorithms become much more involved, using a sqrt(n) buffer inside the array to encode information about the rest. There are working implementations on GitHub (GrailSort and WikiSort), both are over 500 lines.

    Here’s a couple innocent-looking special cases that are still surprisingly hard:

    1) Given an array [a1, a2, …, an, b1, b2, …, bn], rearrange it into [a1, b1, a2, b2, …, an, bn] using O(n) time and O(1) extra space.

    2) Given an array of zeroes and ones, sort it stably using O(n) time and O(1) extra space.

    I’d be very interested to hear about any advances in this area.

    faragon
    Guest

    Very useful work! I would love to see it implemented in many other languages. Any takers? 🙂

    Pii
    Guest

    I love STL 🙂

    Jes
    Guest

    This is really nice, I’m gonna start doing some of them, thanks!

    Smith
    Guest

    Well done!!