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 –

**min, max, swap, sort, next_permutation, binary_search, rotate, reverse**

#### Heap (Priority Queue) –

#### Graphs –

#### Array –

#### Matrix –

#### Strings –

#### Binary Tree –

#### Dynamic Programming –

#### Miscellaneous –

**Thank you for being with us. 🙂**

## Leave a Reply

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.

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.

amazing work!

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

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.

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.

I love STL 🙂

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

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