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

 

Heap (Priority Queue) –

 

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 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
  •  

    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
  •  

    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
  •  

    Dynamic Programming –

     

    Miscellaneous –




     
     

    Thank you for being with us. 🙂

     




    Leave a Reply

    Notify of
    avatar
    Sort by:   newest | oldest | most voted
    bogomipz
    Guest
    bogomipz

    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.

    AlgoLover
    Guest
    AlgoLover

    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.

    Michael
    Guest
    Michael

    amazing work!

    Jerick
    Guest
    Jerick

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

    TartanLlama
    Guest
    TartanLlama

    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
    Matt Robinson

    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.

    Pii
    Guest

    I love STL 🙂

    faragon
    Guest
    faragon

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

    wpDiscuz