I always like to ask this question:
Given a set of N numbers, how would you find the duplicates?
What I'm fishing for is: Do they grasp the difference between O(N^2) vs O(NlogN).
As they answer, if they need it, I'll provide a few hints to guide them along.
If they suggest a double-for loop O(N^2), I'll inquire if there is a more efficient approach. Or how long they think it would take to run with 10,000,000 numbers.
If they suggest sorting O(NlogN) followed by comparing adjacent values O(N), well that's good enough.
The ones who ask:
- Are these floating-point or integer numbers?
- How wide (8/16/32/64-bit) are these integers?
- How large is the set?
- Or who suggest an array of counters (for small-width integers).
- Or who suggest O(N^2) for very small set sizes.
Those I really want to keep!
But it can be hard to think of all the details under stress & time-pressure.
Look, nobody knows everything. Most people can be taught. But when an individual lacks the fundamentals, really basic algorithmic complexity theory, it's going to be an uphill battle.
(And yes, I've had many coworkers straight out of Dilbert who didn't understand what O(N^2) meant and didn't want to learn! Somehow they always got fast-tracked into management...)
Amended to add:
You seem to be quite a fan of the big-Oh :) - eljenso
I needed something simple/elementary/basic that's common to all structured programming courses of study. We're talking Freshman/Sophomore level here. When you get to the more advanced stuff, people go off in different directions and subfields. It's harder to reliably test.
At the same time, I needed something that would clearly be neglected in those "Learn C++ in 30 days" community-college type classes.
Out here in the Real World, I've seen things you would not believe!
- One fellow coder took down the
production server with an
inappropriate cartesian join. Even
after I explained O(N^2) vs
O(NlogN), and how to use GROUP-BY & HAVING clauses to achieve
O(NlogN), he still couldn't wrap his mind around it. He insisted it
was impossible to solve right up
until I sent him the code. (All 5 lines of it!)
- Another fellow thought int * foo() { int a; return & a } was an appropriate mechanism for memory allocation. Sadly, he was not the worst member of that particular team. Another programmer, who couldn't manage to grasp a for loop, took top (bottom) honors there.
- At yet another job I was criticized for breaking my code into small methods/functions. Apparently, when my boss wrote code, she just used one big function. Self taught, of course. Same lady eventually arranged for my termination so she could take over and do the coding "correctly". God help them!
- Yet another coder, sadly one of the better members on this particular team, wrote a threading library I needed to use. I asked him where the mutexes where. He said "I tried it without mutexes and it works, so we're not using them". I got hauled out on the carpet for rewriting his code. But that seemed the best course of action to take.
Seriously, I can't make this stuff up.
While I'm amending... Two other suggestions:
(1) Give them some simple code and ask them to explain what happens to the stack as the routines execute. Code should involve malloc or new, data on stack (including pointers), manipulation of said data, a function or method call, etc. Keep it short.
(2) Give them a simple problem, such as write code for some basic complex number math (add, subtract, multiple, square root, etc). Point out to them up front how to do the math. (Especially for square root.) Complex number math knowledge is not what you're testing.
See if they come up with an Object-Oriented (OO) solution or a functional decomposition approach.
Some folks do write functional code in C++. That will get ugly & painful real fast!