Data structures and algorithms problems in C++ using STL

[cousin_it]

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.

[pierrebai]

Nit-pick: I believe there are no sorting algorithm in O(1) space: just keeping the index of an element takes log2(N) space. Most algorithms hide this fact by assuming numbers have an infinite range. If you do, then you can use a single data for any algorithm, given a sufficiently clever encoding :) (Just use a number base-N and then you got as much easy-to-access, direct-addressable storage as you want per elements.)

[pklausler]

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

I'm missing something here. If the array's values truly are all in {0,1}, then all the zeroes are indistinguishable and you get stability for free (same for the ones).

  mysort all01list = let ones = sum all01list in replicate (length all01list - ones) 0 ++ replicate ones 1

[throwaput]

On the first glance the first problem seems quite impossible. For example, if n is power of two, then for each prime number < n there will be a cycle starting with that number. If n is not a power of two, I haven't yet seen any good explanation of cycles. Any hints? We can't use a or b in any way?

[amelius]

Interesting problems. But is there a practical reason why you'd want to put such stringent restriction on extra space? I mean, space is relatively cheap nowadays (except of course if locality of reference/cache size is an issue, where it translates back into time).

[coderfreak333]

The both problems that you mentioned are quite similar, IMO

[bogomipz]

I've spent the last hour browsing www.techiedelight.com 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.

I would be interested in hearing recommendations for other such sites that specifically discuss the methodology for approaching these problems.

Geeksforgeeks.com is another such resource for learning the approaches as well but I would be curious to hear any other suggestions as well.

[born2web]

I suppose you meant geeksforgeeks.org

[askee]

The k'th largest element in an array can also be found by the nth_element() algorithm already included in the STL. It has linear complexity as opposed to the O(n log k) and O(k log n) variants proposed here.

[asafira]

It is only linear in std::distance(first, last), so it very well might be (and likely is) nlogk .

Edit: see comment below for why it actually is O(n) and not O(n logk) as I had thought.

[bogomipz]

Is the nth_element() function an implementation of "quick select" then"

[a_t48]

Thought this was going to be "problems in STL data structures" not "solving problems using with STL". A better title might be "Solving algorithm problems in C++" as STL isn't really important to the solutions.

[roel_v]

"as STL isn't really important to the solutions."

Sure it is. It's as much as showcase of practical applications of the STL as it is of algorithms. Any algorithms book has implementations, the great thing about this site is that it shows you how to use the STL in real world applications.

[stabbles]

I was thinking the same, but don't agree on the latter: using the STL makes code quite compact and easier to follow.

[whytaka]

Does anyone know of a website that teaches you data structures and algorithms, preferably in C, in an interactive way? I've always found that's the best way for me to learn.

[witty_username]

https://visualgo.net

[sn9]

There's a great course on Coursera that uses Java by Bob Sedgewick.

[thealistra]

It claimed that recursive binary search has a space complexity of O(1) - it has O(log n) as the stack frames are your used memory

[lorenzhs]

But it can be implemented iteratively instead of recursively, so that there is only one stack frame. O(1) space for binary search is entirely possible. The link demonstrates both versions, the iterative one uses O(1) auxiliary space and the recursive implementation uses O(log n), unless the compiler uses tail call optimization :)

[coldcode]

Funny how I focused on "problems" and "using STL" when I read the headline the first time. I remember C++ fondly but only because my mind has now forgotten all the "fun" of debugging STL.

[partycoder]

Thanks for sharing this. I was looking into http://www.geeksforgeeks.org/top-10-algorithms-in-interview-... but it's not very idiomatic.

Then, make sure you use std::make_unique or std::make_shared rather than operator new if you are going for a C++ job.

[faragon]

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

[anilshanbhag]

Just looked at the kth largest algorithm and author claims max heap method is k log n ! His method is actually n log n. The min heap is n log k and the right way to do it.

[coder007]

it is clearly O(klogn). We are popping k times from a heap of size n.

[skdotdan]

I'm very used with this kind of stuff with C++.

Which modern language should I try if the first thing I miss in a language is the STL and the C-like syntax?

[kevincox]

Call me crazy but stick with c++.

It has a ton of warts and complexity but it also has the features you need. If you program in C++ you can have simple solutions 95% of the time and when the intrinsic complexity is higher the language has the tools to save the day. Many other languages will solve the simple parts slightly cleaner but the complexity explodes on the difficult bits.

However if you are looking for fun I really like Rust, it has a nice c++ feel without having to worry so much. Personally I still think it is a bit too new for "enterprise coding" but it is maturing nicely and learning it will really teach you a lot.

[agentgt]

Some what analogous: OCaml has Modules and Functors (not the normal FP functors but more like signature mappers).

OCaml I guess isn't that modern but they did just add First Class modules [1].

[1]: https://realworldocaml.org/v1/en/html/first-class-modules.ht...

[partycoder]

Most modern general purpose languages will provide you with equivalent functionality. But the C++ standard library and STL, not to mention Boost, has taken this very far.

[pjmlp]

C#, Java, Swift, Rust, D probably.

[adrianN]

D?

[D3lt4]

Is there something similar that's language agnostic or in Python?

[pjmlp]

Well there is one of the best books on the subject.

"Introduction to Algorithms"

https://www.amazon.com/Introduction-Algorithms-Thomas-H-Corm...

[bogomipz]

http://interactivepython.org/runestone/static/pythonds/index...

It's free. It doesn't have the formalism of CLRS which some might not like but its still a great practical resource if you want Python.

[uuuuuuuuuuuu]

Sure there is, but I doubt you'll be able to get the same performance as C++ without doing heavy optimization.

[geokon]

Is there an offline/e-book version?

[dmitrygr]

Website is unusable on mobile. Text falls off right side, horizontal scrolling disabled. How is this still a thing?

[wazanator]

Looks fine on my phone. Do you have desktop request on by accident?

[HugoDaniel]

It doesn't state what standard it is using. Is it with:

  C++98 or
  C++03 or
  C++11 or
  C++14 or
  C++11 or
  C++17 or
  C++20 ?

[lorenzhs]

Appears to be C++11, which is contained twice in your list. C++20 doesn't exist yet. C++17 isn't finished either.

It doesn't appear to use new language features, only some library things like std::unordered_map, from what I gathered in a quick look. Most things will probably work just fine with C++03.

[pjmlp]

If this would be in Python, for example, for starters we would need to know if it is 2 or 3 variant.

Then we would need to know which of the following versions is being used:

    Python 1.0 - January 1994
        Python 1.5 - December 31, 1997
        Python 1.6 - September 5, 2000
    Python 2.0 - October 16, 2000
        Python 2.1 - April 17, 2001
        Python 2.2 - December 21, 2001
        Python 2.3 - July 29, 2003
        Python 2.4 - November 30, 2004
        Python 2.5 - September 19, 2006
        Python 2.6 - October 1, 2008
        Python 2.7 - July 3, 2010
    Python 3.0 - December 3, 2008
        Python 3.1 - June 27, 2009
        Python 3.2 - February 20, 2011
        Python 3.3 - September 29, 2012
        Python 3.4 - March 16, 2014
        Python 3.5 - September 13, 2015
        Python 3.6 - December 23, 2016

And for extra fun we can also add PyPy, CPython, IronPython, MicroPython, .... into the mix.

I can gladly play this game with any other programming language.

Languages that people care about, get new versions all the time, and not all tooling implementations or developers catch up at the same time.

It is part of our job to deal with it.

[w8rbt]

Email the author and ask? After he tells you, then use -std=c++XX (or similar) on your favorite compiler and you'll be fine.