18 ms·
Data structures and algorithms problems in C++ using STL
- dmitrygr 10y agoWebsite is unusable on mobile. Text falls off right side, horizontal scrolling disabled. How is this still a thing?
- a_t48 10y agoThought 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 10y agoI was thinking the same, but don't agree on the latter: using the STL makes code quite compact and easier to follow.
- roel_v 10y 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 10y agoIs there something similar that's language agnostic or in Python?
- uuuuuuuuuuuu 10y agoSure there is, but I doubt you'll be able to get the same performance as C++ without doing heavy optimization.
- hellofunk 10y agoI 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.
- pjmlp 10y agoWell there is one of the best books on the subject. "Introduction to Algorithms" https://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen-ebook/dp/B007CNRCAO/ref=mt_kindle?_encoding=UTF8&me= https://www.amazon.com/Introduction-Algorithms-Thomas-H-Corm...
- mtdewcmu 10y 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.
- gjm11 10y agoThis looks like it: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.471.4772 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.471.... I don't see any links to it from any of Skiena's or the publisher's webpages, so it's not clear how legitimate it is. Incidentally, I wouldn't really suggest Skiena as an alternative to Cormen et al; they're extremely different in style and content, and in situations where you need one of them the other probably won't help you. I recommend getting both. (For more verbosity on this, see my review of the first edition of Skiena's book at https://www.mccaughan.org.uk/g/books/alg-design.html https://www.mccaughan.org.uk/g/books/alg-design.html .)
- HugoDaniel 10y agoIt 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 10y agoAppears 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 10y agoIt compiles with -std=c++11, graph one fails with 03 on WSL at least
- castratikron 10y agoI see "nullptr" in a few examples, which is C++11.
- lorenzhs 10y agoYeah but it should work in C++03 if you just '#define nullptr NULL'. Not saying it's good practice but C++11 usage is very light.
- pjmlp 10y agoIf 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.
- askee 10y agoThe 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 10y agoIt 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.
- lorenzhs 10y agoBut 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).
- asafira 10y agovery cool! I stand corrected, I didn't think of this when I considered it. Sorry for the mix-up
- bogomipz 10y agoIts O(n logk) then? It maintain a heap I'm guessing?
- lorenzhs 10y agoNo, as per my previous comment, it t does not use a heap. It's like quicksort, but only doing one of the recursive calls: - choose a pivot p randomly from the elements - partition into elements <= p and > p. This takes time O(n). - if the number of elements <= p is at most k (the rank of the element we want), do a recursive call on these elements. Otherwise recurse on the other elements (those >p). Because a random pivot splits the elements well enough most of the time, this has an expected running time of O(n): 1 + ½ + ¼ + ⅛ + … < 2 in the best case, and similar constants if the partitioning is a little worse. But in the worst case, when the pivot is the smallest/largest element in each iteration, it's O(n²). That's where the fanciness of introselect comes in: if quickselect doesn't converge, it switches to an algorithm with worst-case O(n) time, which is slower in most cases but saves the day when quickselect has trouble.
- thealistra 10y agoIt 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 10y agoBut 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 10y agoSince 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.
- lorenzhs 10y agoThat seems entirely unrelated to tail call optimisation though? For once, "return foo(bar, baz)" isn't returning a named value, it's returning an rvalue. Secondly, return value optimisation doesn't optimise away the stack frame. Thirdly, the standard isn't as strict as you make it sound: compilers may elide the copy if they can, but if they cannot they have to move, never copy.
- cousin_it 10y agoA 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 10y agoInteresting 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).
- gpderetta 10y agoa) 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).
- cousin_it 10y agoOn one hand, amelius is right, there are already simple fast stable sorts using O(sqrt(n)) extra space and that should be okay for all practical purposes. (Though they aren't very well known, and inventing one will take you a week or two.) Allocating 30K elements to help sort a billion elements is no big deal, you don't need to squeeze further. My interest is more academic, how come the known O(1) solutions are so complex compared to O(sqrt(n)) and can they be simplified.
- coldcode 10y agoFunny 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.
- deleted 10y ago[deleted]
- anilshanbhag 10y agoJust 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 10y agoit is clearly O(klogn). We are popping k times from a heap of size n.
- skdotdan 10y agoI'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?
- partycoder 10y agoMost 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 10y agoD?
- pjmlp 10y agoC#, Java, Swift, Rust, D probably.
- agentgt 10y agoSome 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.html https://realworldocaml.org/v1/en/html/first-class-modules.ht...
- kevincox 10y agoCall 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.
- bogomipz 10y agoI'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.
- partycoder 10y agoThanks for sharing this. I was looking into http://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/ 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 10y agoDoes 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 10y agohttps://visualgo.net https://visualgo.net
- sn9 10y agoThere's a great course on Coursera that uses Java by Bob Sedgewick.
- faragon 10y agoVery useful work! I would love to see it implemented in many other languages. Any takers? :-)
- geokon 10y agoIs there an offline/e-book version?