Khan Academy: Algorithms
khanacademy.org
khanacademy.org
Half way through writing a line of code they would pop up and tell me that my code couldn't execute, maybe I should add a semi colon. It's really distracting and of course code can't execute when you are in the middle of typing an if-statement. It is not helpful at all.
On top of that there's no "submit" button (because it is supposed to test continuously) so sometimes when I was done it wouldn't test the code and made it impossible to get a "completion" on parts.
Also in the first example it complained when I was using Math.round for the index calculation and only wanted to accept Math.floor. (although not applicable in this case, I think Math.floor is not the best choice since it won't behave like ints in negative cases)
I love algorithms, AND I think they are necessary in interviews, but I feel like the tech community has become ridiculous in how they interview for them lately.
Example problem: Given two words in a dictionary, transform one word into another, changing one character at a time, using only words in the dictionary.
A good interview would recognize most people have no clue how to solve this, give hints and still pass candidates who make a reasonable attempt but fail. Now it seems to be that most places will just fail you, if you don't know the most optimal answer and can't write it out without any syntax mistakes.
This is ridiculous, and I have experienced it and this attitude around major tech companies. What this has resulted in is Algorithm trivia. Your ability to succeed is your ability to memorize every algorithm question and approach in existence.
Please don't do this. The HN guidelines ask you to "resist commenting about being downvoted" because "it makes for boring reading and never does any good". It isn't that we don't understand how provocative it can be to have a comment downvoted for no apparent reason—we know the feeling all too well. Hence the word "resist".
Still, I agree that they're overused. The truth is, the vast majority of modern programming doesn't even involve intensive algorithm writing and is more focused on the design and construction of apps that are nothing more than CRUD operations and business logic.
There are software developers whose work actually requires no knowledge of algorithms, mathematics, or even CS besides their language, framework, and some architectural concepts.
On the other hand, there are "software developers" whose primary work is to develop algorithms and computational methods.
For historical reasons those roles are not always properly and clearly separated.
This can be one of the reasons why we have intimidating algorithmic interviews that are irrelevant to the actual work of the developers who are being interviewed.
Many good algorithms are quite counter-intuitive and non-obvious, so there is very little chance that you would come up with one yourself during the course of working on a problem. In practice, people who haven't spent enough time memorizing algorithms tend to choose the wrong path while solving real-world problems, as they can't even anticipate the direction in which the correct solution lies because, again, many good algorithms are non-obvious and can't be thought out on the spot.
What I'm looking for in asking somewhat algorithmic questions in an interview is the ability of the coder to reduce a problem to one which has probably already been solved. A separate but interesting problem is, given such a solution, how well can you implement it - but that's more of a fizzbuzz exercise in many cases.
(No algo) < (Blackbox algo) < (Whitebox algo)
To me this seems like a good one only because it gave me immediately some talking points to put on a whiteboard.
- Build graph with vertices being words and edges being all words differing by one character - search graph for shortest path between given two words
Implementation would be another matter as there are a number of complexity gotchas. This would be a job for hitting CLRS.
This seems like something most people could come up with to start as it seems pretty obvious but a single graph theory course I took some years ago must have biased me a bit.
I interviewed at an internet darling company. They had the main interviewer (who was a bit rude) and another shadow interviewer who takes notes on everything you do an say. All interviews are like this.
The coding gotchas quickly make you super nervous as everything you do and say is recorded. You have 15 minutes. Plus whiteboard is not an editor. I don't code linearly like writing a text book.
I have come to a realization that fresh out of university me performs better at interviews than 7 year experienced me.
Assuming the "first build a graph" approach is the most efficient one, it's definitely taking me longer than 15 minutes to get a reasonably efficient solution. Just for the graph-building part. I'm taking a two-step approach, first connect the matching words that differ in length by one, so filtering for (a == b[1:] or a == b[:-1]), assuming a is always the shorter word of the pair. Checking all words of length N vs length N+1 that way took a few minutes on my (not very powerful) netbook. Not entirely happy with it, but no way I could optimize that further in 15 minutes anyway (if there is an even better algorithm), and that part of the calculation is done.
edit: just thought of a better way
aa = sorted([words of length N])
bb = [words of length N+1]
# now make a sorted list of the longer words, truncated on either side,
# (paired with the original for retrieval later)
bb1 = sorted([(w[1:], w) for w in bb]
+ [(w[:-1], w) for w in bb])
# now we can do a merge operation on aa and bb1, and find
# the matches in O(len(aa)+len(bb1)) instead of O(len(aa)*len(bb))
#
# a merge operation that I can't be arsed to write out here, but I
# promise it'll involve some super clever usage of the itertools module
#
I would agree with that, you're contributing to a discussion to be sure, just the wrong one, I'd rather read about this somewhere else.
What's that supposed to mean? Search the dictionary for other words that contain the letters you want and put them into the source word, while also taking out unwanted letters from the source word?
I would also wager that whomever was asking that sort of question would probably be looking for some optimal form of the answer, and having never encountered it, oh well.
That said, most of the reason we teach sorting algorithms is to teach algorithms in general, and particularly the consequential lesson that "There are often many methods to doing something that work; these methods are often different in extraordinarily consequential ways; the right method for certain problems -- even ones which look trivial on the outside! --may require literally years of R&D to develop."
In that type of environment, you need to do a lot of thinking about basic algorithm science, including exploring the many types of sorting algos.
(Here's some code I'm working on right now in that vein, which helps to perform efficient percentile calculations in a smart contract https://github.com/drcode/ethereum-order-statistic-tree)
For instance, adding an index to a database table is something I regularly do for performance, and the reason is based on principles I learned in college. The runtime complexity of an indexed table is way better. Any monkey coder can add the index too, the difference is that I know what's going on under the hood (finding things in a ordered tree data structure are way faster than scanning through the whole table).
I was grumpy learning some things in college early on, and the more I advance my career, the more I appreciate the things I learned even if I don't code them up, or even use them, on a regular basis.
For straight up sorting, yes.
But, some other algorithms have exactly the same structure as sorting.
As a toy example, take the famous skyline problem. See https://briangordon.github.io/2014/08/the-skyline-problem.ht... for the details:
"You are given a set of n rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the x position of the left edge, the x position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night."
One approach to solving the problem is equivalent to merge sort: you write a merge function that merges two lists of in-order non-overlapping rectangles, and go from there.
A related problem (not the same problem, but amenable to the same sort of approaches), for example, comes up when displaying overlapping appointments in a calendar timeline view.
Not many out of the box libraries would have find N min out of a stream/iterator...draw the moving median, moving min/max and so on. You won't find a red/black tree with linked next nodes to do the task efficiently. So sometimes there is that.
I'm not sure if I've ever run into anyone who said "The things I learned in college have turned out to be pretty much worthless in my professional career. I wasted a lot of time learning irrelevant information." It's interesting that the majority of every CS education is always valuable, to every person, with no exceptions.
OTOH, I'm not sure full coursework is needed for that. Just make your way through Sedgwick's algorithms book in a month or two and you're in the top 1% probably.
When you study sorting you really do it because:
1) It's a simple, frequent and clear problem that everybody understands
2) People just need to think about it for a while to figure out a correct algorithm normally O(n^2) and think about optimizations from there (that will probably still make it O(n^2)).
3) You can study different techniques to solve that problem: like divide-and-conquer (mergesort), using a data structure (heapsort), divide-and-conquer+randomization (quicksort), not going for comparisons but using the structure of the data (radixsort).
4) You can learn to apply big-O notation for efficiency and compare different algorithms
5) You can study the limits of a problem (not an algorithm) like the omega(n log(n)) limit of comparison sorts and the omega(n) limit of sorting in general).
This also happens with the less clear but also rich problem of the Minimum Spanning Tree that has 2 famous algorithm (Prim and Kruskal) that can be implemented with different data structures having a great impact in efficiency.
So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them. Sorting is normally already implemented in the popular and not so popular programming languages libraries.
What I suspect generally that I cannot prove (yet): When teachers teach things that are easy to teach but not directly important to learn, students are distracted by the surface irrelevance.
Of course the underlying concepts and designs of sorting are important to understand. But, that the GP asked, "Do professional programmers actually think about this? Is this relevant?" means the curriculum has a problem. The problem is: students are asking meta-questions that should've been answered by the "why?" mentioned above.
In sum, I agree with the parent, especially with:
> So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them.
It's easy (possibly... lazy? Again, this is what I suspect that I cannot prove) for a CS department to declare "Students will learn [list of topics] by examining and implementing sorting algorithms."
By contrast, it's a hard to 1. interest students by presenting them with problems not fossilized exercises. 2. ensure to students' parents and taxpayers and employers that they know the "basics|fundamentals|theory"
So, in this case, programmers would use this stuff when a sort takes up too much time or too much RAM for what it's meant to do. Then you need to know what big-O is and how to fix it.
It seems a bit odd to spend all this time preparing for things that don't happen every day, but, really, that's what people pay the big bucks for: Someone who can smooth over life's little difficulties, at least in that specific realm.
http://www.joelonsoftware.com/articles/fog0000000319.html
Someone who hasn't thought about sorting algorithms is likely to implement a "Shlemiel the painter" solution without even realizing that their problem is fundamentally sorting related.
Software engineers (like engineers in other fields) are in the business of taking stuff made by scientists and building things out of it that businesses and consumers use (like spotify and bridges and dialysis machines). They wouldn't do much in the realm of specific algorithm design, it's mostly about research and system architecture.
I had always believed that I wouldn't need to know the CS theory because I was able to write code that worked and didn't find it too complicated. When I decided to become a developer I learned by launching a few websites, which performed horribly, but I didn't realize until I got a few users. It took me a while to even figure out what was wrong, but eventually I learned about Big-O and realized my algorithms were far from optimal. Started scrambling to teach myself all CS theory I could find online, just so I could build things properly. Then there is a phase where you are constantly worried there is something else from CS school you are missing which will cause your software to blow up, but eventually you get more confident (with shipped code/and a better understanding of CS theory).
So in the end, I think the CS theory in school saves you from a lot of head banging and ignorance after you graduate. However, you will probably do a lot of this in your undergrad, so I guess it all balances out in the end!
For example, I remember one developer (who know works at Amazon funny enough), who used dual for loops to iterate through data and find values in multiple places in our application. This caused a noticeable UI slow down. I ended up just loading this data in a Hashmap and it became instantaneous.
It then becomes a game of ensuring adequate access paths and the like and using a query analyzer to see if what you put in executes as you like. I am more than amazed at the tricks a good query engine can pull but readily take advice it offers when a new index/access path is required.
Since this covers the sorting the next issue is, making sure the project requests are asking for the right data. A lot of time we gain efficiency by analyzing what they want and making their request better fit that (see Bob, you really didn't need that million record request when all you wanted were this set here)
Skiena's Algorithm Design Manual is great for the former approach, and has a cookbook feel to it, since most of it is just an index of different algorithms to use for different situations.
Generally speaking though, I do think about Big-O notation when writing something that isn't trivial. If I do have to implement some particular known algorithm, then I typically look to the language itself for a solution. Failing that I look for a suitable library, and only after exhausting those potential solutions do I write my own.
The same goes for data-structures. For example, I might need a set of unique values, but, when I code, I would choose an enum-set or a hash-set based on what problem I'm solving.
Graph algorithms, and linear algebra complexities, on the other hand, I've had to worry about a bunch.
In my experience, "algorithms" denotes a higher level, more advanced course (OBSTs, flows, stable marriage, ILP/LP...)
Heap sort is O( n log(n) ) in all cases including worst, and quicksort is O( n^2 ) worst case. O( n log(n) ) is the Gleason bound, the fastest sort there can be on average from comparing pairs of keys so that in that sense heap sort is asymptotically the fastest possible. Dropping the technique of comparing pairs lets us consider radix sort which can be faster, still. The lecture does cover merge sort; good.
For graphs, the min cost network flow problem is linear programming, and it turns out that if the arc capacities are integers and start with a basic integer feasible solution, then the simplex algorithm maintains integer solutions and, if merely an optimal solution exists, will find an optimal integer solution.
It turns out that this fact is in practice one of the best tools for linear integer programming which generally is in NP-complete. This progress on integer programming is worth noting.
For cycling in the simplex algorithm for the min cost flow problem on networks, W. Cunningham, long at Waterloo, has a nice solution based on what he calls strongly feasible basic solutions.
For the simplex algorithm for the network flow problem, there are, compared with the simplex algorithm in general, some enormous simplifications -- e.g,. a feasible basis corresponds to a spanning tree of arcs -- and, thus, astoundingly high performance on astoundingly large problems -- this fact should be noted.
Maybe I missed it, but I didn't see trees mentioned. Both AVL trees and red-black trees are good examples, that is, balanced binary trees good for collection classes. And B-trees, multi-way branched balanced trees, long important on hard disk (and likely now on solid state disks) for database should also be mentioned.
Since need to teach heap sort, should also mention that the heap data structure is good for an easy implementation of fast priority queues, e.g., look at 1 billion numbers one at a time, in any order, and end up with the 100 largest, efficiently. Also there is a modification of the heap data structure that has good locality of reference when doing a lot of virtual memory paging.
And for hashing, the clean solution is
Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, Extendible hashing-a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344.
I'm not thrilled with recursion since in practice it can strain implementations of the call stack.
Course over. Hope you enjoyed it!
Honestly, how are you going to live life if any reminder of pop culture can distract you from a serious subject? And how are you going to interact with people if noticing such a thing (even if it's tremendously obvious) makes you feel the need to shout about it? Best to knock it on the head now.
Of course I don't really believe parent poster has that problem: it was making a little fun as mild chastisement for the terrible comment. I honestly think you could have interpreted it correctly if you hadn't been so quick to take offence.
This naturally seems to stem from their conscious efforts to promote a 'serious'/on-topic culture and humor's nature as being subjective and often hard to detect.