Data structures and algorithms problems in C++ using STL

http://www.techiedelight.com/data-structures-and-algorithms-interview-questions-stl/

by coder007 • 9 years ago

227 76 9 years ago

techiedelight.com

dmitrygr2• 9 years ago

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

wazanator• 9 years ago

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

dmitrygr2• 9 years ago

No I do not. Code is fine. Comments in code are cut off mid word. PixelXL. Chrome.

a_t48• 9 years ago

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.

stabbles• 9 years ago

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

roel_v• 9 years ago

"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.

D3lt4• 9 years ago

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

uuuuuuuuuuuu• 9 years ago

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

hellofunk• 9 years ago

I don't think the question had anything to do with speed.

To answer the question, there are many general books on algorithm design that would be appropriate for any language.

pjmlp3• 9 years ago

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

"Introduction to Algorithms"

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

mtdewcmu2• 9 years ago

"The Algorithm Design Manual", by Steven Skiena, is very readable and it's generously free to download. I was going to post the link, but I couldn't unmangle it from Google. It's easy to find.

bogomipz7• 9 years ago

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.

HugoDaniel• 9 years ago

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 ?

lorenzhs8• 9 years ago

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.

divbit• 9 years ago

It compiles with -std=c++11, graph one fails with 03 on WSL at least

pjmlp3• 9 years ago

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• 9 years ago

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.

askee• 9 years ago

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.

asafira2• 9 years ago

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.

lorenzhs8• 9 years ago

But std::distance(first, last) is how n is defined.

std::nth_element is typically implemented using a fancy version of quickselect called introselect. You can imagine quickselect as a version of quicksort where the recursive call is only executed on the side which contains the element. Introselect adds some fanciness to ensure worst-case linear running time if quickselect takes too long (bad pivot selection).

bogomipz7• 9 years ago

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

thealistra• 9 years ago

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

lorenzhs8• 9 years ago

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 :)

sqeaky• 9 years ago

Since C++11 elision of copies of named local lvalues being returned is mandatory. In practice this was elided by older smart compilers and new compilers elide a whole more when returning.

cousin_it7• 9 years ago

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.

amelius• 9 years ago

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).

gpderetta2• 9 years ago

a) allocating the extra space might be expensive.

and most importantly:

b) you might not have extra space. For example, if you are implementing an out of core sort (i.e. sorting huge on-disk datasets), you want to maximize the size of the chunk you will sort in memory and do not want to waste any memory for the temporary storage. (this is related to locality of reference of course, you can a make similar argument for out-of-cache sorting).

coderfreak333• 9 years ago

The both problems that you mentioned are quite similar, IMO

cousin_it7• 9 years ago

The first has a simple solution if you know some university-level math. The second has no simple solution AFAIK.

throwaput3• 9 years ago

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?

throwaput3• 9 years ago

Even for power of two it's not correct, forget my statement about cycles.

davidtgoldblatt• 9 years ago

I think you're on the right track (i.e. viewing it as a permutation, and looking at the cycle decomposition of that permutation).

Try indexing from 0 instead of 1 if you're not. Then the cycle containing 1 will start with (1, 2, 4, 8, ...). What happens when it wraps around?

pklausler• 9 years ago

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

cousin_it7• 9 years ago

See openasocket's question and mkingston's answer in another subthread.

pierrebai• 9 years ago

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.)

cousin_it7• 9 years ago

When people talk about these things, they usually assume something like the transdichotomous model (machine word size is unknown, n fits in a machine word, arithmetic on machine words is O(1)). It gives the right complexities for everyday algorithms.

coldcode• 9 years ago

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.

anilshanbhag• 9 years ago

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• 9 years ago

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

skdotdan• 9 years ago

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?

partycoder2• 9 years ago

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.

adrianN• 9 years ago

pjmlp3• 9 years ago

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

agentgt• 9 years ago

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

kevincox• 9 years ago

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.

bogomipz7• 9 years ago

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• 9 years ago

I suppose you meant geeksforgeeks.org

bogomipz7• 9 years ago

Indeed, yes, sorry.

partycoder2• 9 years ago

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.

whytaka• 9 years ago

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• 9 years ago

https://visualgo.net

sn9• 9 years ago

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

faragon• 9 years ago

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

geokon• 9 years ago

Is there an offline/e-book version?

Data structures and algorithms problems in C++ using STL

Related Stories