What the Daily WTF?

What if you decided to implement binary trees using N-ary trees, as someone above suggested? Do you have to change your sum algorithm because of that?

Depending on your algorithm, maybe. Take your earlier sum algorithm:

```
def sum(root):
if !root: return 0
return root.nodeValue + sum(root.firstChild) + sum(root.nextSibling)
Sorry, but that ain't gonna work on an N-ary tree.

jape

Because those are the directions you were given. Duh.

Yeah.... where?

Sorry, but that ain't gonna work on an N-ary tree.

So, what if I just implement a binary tree whose initializer constructs a N-ary tree node that happens to always have 2 nodes, and I define get/set leftChild to be equivalent to this.firstChild and get/set rightChild to be equivalent to this.firstChild.nextSibling (or this.childN(N = 2)).

dkf

What if you decided to implement binary trees using N-ary trees, as someone above suggested?

That'd be a hypothetical question, yes?

LurkerAbove

It's interesting to me that

def sum(root):
    # Base cases be damned.
    return sum(root.left) + sum(root.right)

, which, we are told, someone who would not come up with this would not be able to say he knows 'programming', five hours later becomes:

def sum(root):
  if !root: return 0
  return root.nodeValue + sum(root.firstChild) + sum(root.nextSibling)

So someone who 'knows programming' spends 2 minutes on a problem and gets it wrong. Perhaps that was the kind of 'programmer' the interviewer was trying to eliminate.

Groaner

Now, you would except the questions to be asked are regarding this
position, but in this and many others, you'd be wrong. In this
particular case the test was to write a binary tree.

"Sure, it's been a while, but I think I remember all the details. You're going to need a Node class and a Tree class. Is there a legitimate business need that warrants implementing a custom container in lieu of using the proven, tested and optimized implementations provided by the framework/a library/etc.? One thing I've learned is that brand new code always has bugs, and it's best to use a proven implementation before rolling your own."

Trees might be theoretically nicer than arrays, but arrays have this tricky habit of working better in practice (due to better memory locality and so better use of the facilities of real hardware).

What's the rule of thumb these days - still ~16 elements before trees start to become the more performant choice?

What? Do people even fail to realize that big O notation is useful for deciding when to use data structures and algorithms, not about how to implement them?

If they don't know that binary trees generally offer logaritmic access then they're garbage programmers. We're not even entering technical details here. We're not talking about the "wouldn't know how to write a binary tree" programmers (which already sounds ridiculous to me, do these people understand other basic concepts such as recursion?). We're talking about the "would incorrectly use a HashMap instead of Vector/Array" variety.

You are absolutely correct in an academic sense, but we're talking about web development. That means dealing with network latency and spinning disks, which have response times in the milliseconds and beyond. They're your true bottleneck. The microseconds saved by picking an algorithm of lesser complexity are likely never going to be noticed. When the application's load scales to the point that it makes a difference is the time to address that problem.

Hash maps are the answer.

For an extremely large class of problems (well, it's more of a complement class) hashing is just fine. As long as you avoid the rabbit hole of perfect hashing, which is theoretically wonderful but utterly impractical.

And even if there are lots of collisions, if the hash buckets are implemented as balanced binary trees, you get logarithmic complexity as your worst case.

Can't you really come up with something like this in 2 minutes? Can you believe someone who would not come up with this would be able to say he knows 'programming'? Recursion?

I would prefer to provide a table with a self-referencing foreign key and have them build a query with a recursive CTE to list parent rows and their children in depth order. That shows that they understand recursion, and that they know SQL better than about 19 out of 20 people.

@blakeyrat said:

jape:
Binary trees are as much as programming basics as a linked list is.

Only for C and C++ programmers. The rest of the world has moved on past those shitty languages, and implementation details like this no longer matter.

It's not even a problem in C++ with std::map. The fact that some people think C is superior in spite of that frightens me.

Ok, good luck with that on an interview. Especially when the interviewer is the "dickhead" that gets the problems solved instead of just randomly typing on the keyboard something that resembles code.

Which problems are solved by reimplementing containers?

Related: http://blog.codinghorror.com/why-cant-programmers-program/ (also using Discourse by the way).

Invoking Atwood around here isn't exactly a great source of credibility. However, even a blind squirrel is correct twice a day. Implementing FizzBuzz is going to be a lot faster than implementing a binary search tree (particularly in a language without garbage collection). That allows for more time in the interview for discussing more important topics.

@boomzilla said:

Actually, the job wanted someone with experience in something that is one of the places that requires lots of optimization:

Experience with SQL

But that doesn't have terribly much to do with traditional data structure / algorithm type analysis.

It's there, but the connection is tenuous. Table scans are linear complexity. Index seeks are logarithmic. The Cartesian product of two tables is quadratic. Rather than ask about the algorithmic complexity of a query plan, I'd rather ask candidates what sort of indexing strategy they would use given a schema and reporting requirements. Nineteen out of twenty of them will still have no idea what to do.

HardwareGeek

I don't get it.

Another JDGI.

redwizard

@blakeyrat said:

The point is, the job position is specifically oriented around UI and web services...

As described, yes.

Be aware that half the job descriptions out there are either severely lacking, ridiculously laden with "requirements" that would leave you perpetually in school just to keep the certifications current (I'm talking to you, HR dimwits), plain wrong*, or have a host of other WTFery I can't list off the top of my head.

@presidentsdaughter said:

Next time you're conducting a technical interview, stick with the position description

As mentioned above, this is a challenge for many organizations. Beware those groups.

Sorry to say this, but while that other guy might be an asshole, you just proved to them you would be useless in a team lead position.

That's assuming the interviewer was professional in his demeanor, which I doubt based on what's written here. We weren't there, so cannot assume how the interview was being conducted. I have seen interviewers get condescending with interviewees and this smacks of that kind of attitude. It is a rare breed who can keep their cool and respond with something creative, or nothing. More often the interviewee eventually lashes back, grows fearful, may even break down and cry or just go apathetic to the whole thing. In ALL cases, that interviewee should run from that job. The only thing I would have recommended @Eldelshell do in this situation is what @DrPepper already covered:

@DrPepper said:

"After learning about this position and this company during this interview, I've decided that this company would not be a good fit for me. I'm more interested in doing XXX and I'm looking for those opportunities"

It's an opportunity to throw their own job description back at them and be perfectly polite and professional about it.

@Yamikuronue said:

I routinely see people having no idea what takes so long in their code The ability to figure out what the fuck you're asking the machine to DO and why it takes a long time is way more useful and also way more rare than being able to rattle off HTTP actions or status codes or what have you that's readily available on google.

...and managers who understand this, who recognize in you this ability and allow you to get on with it are worth their weight in gold. Those are the jobs you run TO.
///////////////////
*Seen in a job ad in the fall of 1997: REQUIREMENT: 5 years experience in Windows 95.

redwizard

As for @jape vs. @blakeyrat (star attraction)...and a few other combos above...

-Breaks out popcorn and soda...-

ben_lubar

breaks out pizza

redwizard

@Arantor said:

Needs more @blakeyraNt

FTFY

Arantor

Well, there's that but in terms of what I was getting at - battle of egos - @blakeyrat definitely should have been part of that. A warrior competing in a duel by using blakeyrants is always worth watching but of course there's more to it than simply the weapon in battle.

redwizard

Right below the "*Seen in a job ad in the fall of 1997: REQUIREMENT: 5 years experience in Windows 95."

WTF is all that extra stuff added in after that line? OMG!

DISSSSSCOOOOUUUURRRRRSSSSSSSEEEEEEE!!!!!!!!!!!!!!!!!!!!!!!!!!!!

/Shakes Fist/

ben_lubar

I don't see anything added.

HardwareGeek

I see a bunch of slashes on the line above, but nothing below.

redwizard

It's gone. Killing and reloading the browser cleaned it up. Guess it's just Discourse and me in the Twilight Zone.

Trying to add the word 'me' as an edit to fix my grammar yields this informative message from Discourse, preventing me from fixing my post:

Body is too similar to what you recently posted.

Arantor

Twilight Zone?

http://www.youtube.com/watch?v=LfHPbxawzUI

HardwareGeek

@redwizard said:

Trying to add the word 'me' as an edit

No repro, sort of. It's B*****med-up, but not that way.

It will allow me to make a one-letter edit. But if I decide I don't like the change, and do another one-letter edit to go back to the way it was, then I get the "Body too similar." I can do a different one-letter edit, but I can never return the text to what it was in any previous submission.

Has it always behaved this way? I haven't tried undoing an edit before, that I can recall.

redwizard

@HardwareGeek said:

It will allow me to make a one-letter edit. But if I decide I don't like the change, and do another one-letter edit to go back to the way it was, then I get the "Body too similar." I can do a different one-letter edit, but I can never return the text to what it was in any previous submission.

Exactly what I ran into. First edit I messed up, then I tried to edit correctly and it won't let me. So you did repro. I was just too lazy to type up the details on my Droid at the time.

redwizard

Good idea, awful execution. :-/

dkf

@Groaner said:

What's the rule of thumb these days - still ~16 elements before trees start to become the more performant choice?

Still depends mostly on whether you've got memory locality, and what else you're using memory for. Benchmarks may measure one thing, but keeping things compact so that more cache space is available for other things is still a benefit.

Bah! Pesky global resource constraints!

In terms of hashing, if you've got non-malicious keys then you're better off rebuilding the hash table to be larger when the size of a chain gets too large. (There appears to be a lot of folklore surrounding exactly what to do about this, and the literature isn't nearly as systematic as it likes to think; cryptographic hashes — a totally different thing — are much better studied.) That keeps maximum chain lengths below about 10 (and average chain lengths quite a bit lower).

Assuming you use the right rebuild factors, but that's on a par with saying that you assume that the tree is balanced. ;)

PJH

@Intercourse said:

"You will not believe the bullet we dodged by not hiring this prick I just finished interviewing."?

http://what.thedailywtf.com/t/testing-a-juniors-mettle-part-2/3663

@EvanED said:

it could be handled but no one actually checks for malloc returning NULL so you'll just get a segfault anyway

LOLWUT? You don't check for NULL on malloc()s? Where do you work so I can avoid it...

That said, one company ours acquired had software that did(n't) do exactly that. Restarting the program on a SIGSEGV was their preferred way of handling out of memory exceptions. I had words when I noticed they were doing that...

PleegWat

We come pretty close - the malloc() wrapper detects NULL and goes on to call exit(EXIT_MEM). Or something along those lines.

dkf

@PJH said:

LOLWUT? You don't check for NULL on malloc()s? Where do you work so I can avoid it...

That's an interesting case, as you can recover in several different way. For failed large allocations, you can usually die pretty gracefully (Don't have a spare 2GB of memory? Oh well.) Sometimes you can even recover (e.g., keeping the image data compressed in memory). If a small allocation fails, you're doomed as you're not even certain to be able to allocate enough memory to print a message saying what exactly went wrong (one has to keep the message in memory so one can write() it immediately).

PJH

Most of the code I've written simply drops what it was trying to do, attempts to log the failure and carries on.

That said, the code I write tries not to be degenerative enough to be in the position that it runs out memory to begin with.

I've no idea, yet, what my aforementioned software was doing to reach that stage...

abarker

Yeah.... where?

IN THE DAMN OP!

Evo

IN THE DAMN OP!

Actually, it never says it should be a member function. This would be fine (untested, but POC):

int sum(const Tree& tree) {
   int left = tree.hasLeft() ? sum(tree.getLeft()) : 0;
   int right = tree.hasRight() ? sum(tree.getRight()) : 0;
   return left + right;
}

... Bring on the flamewars:

Using ternary operator - I actually prefer it here.
Avoiding the use of pointers.
The lack of distinction between a tree and a node (would be prettier, but meh).
Not making this the beautiful oneliner:

int sum(const Tree& tree) { return tree.hasLeft() && tree.hasRight() ? sum(tree.getLeft()) + sum(tree.getRight()) : tree.hasLeft() ? sum(tree.getLeft()) : tree.hasRight() ? sum(tree.getRight() : 0; }

Of which I'm not even sure I got it right...

dkf

@Evo said:

Not making this the beautiful oneliner:

You're making things harder by not using pointers.

int sum(const Tree *tree) {
    return tree==NULL ? 0 : tree->val() + sum(tree->left()) + sum(tree->right());
}

cvi

You're making things harder by not using pointers.

<sarcasm>You can have the best of both worlds:</sarcasm>

int sum( const Tree& tree ) {
    return &tree == NULL ? 0 : tree.val() + sum(*tree.left()) + sum(*tree.right());
}

Filed under: Don't do this. For real.

Groaner

@cvi said:

Filed under: Don't do this. For real.

Null references. Twisted!

Eldelshell

Many of you are saying "if you're a senior and don't know how to write a BST you should be punished".

But you know what, that's why I went to college and that's why I studied that in college. What is a degree in CS worth then?

The same thing with certifications. I have the SCJD (yes, way when Java 1.4 and J2EE were a thing) and I'm still asked the difference between HashMap and Hashtable. So there, another good money wasted for nothing.

Eldelshell

@blakeyrat said:

Oh yah, that's obscure as shit. I don't think I've ever, EVER, seen HTTP PATCH used.

Yes, that's the typical question you're asked in REST interview questions to also make the interviewer feel superior because PATCH is not used anywhere right now (some mf will go and implement it in jQuery after reading this post).

The idea of PATCH is to be faster than PUT. If you send a PUT you have to include the whole resource. With PATCH you only send the fraction of elements you want to modify.

@FrostCat said:

There's also HEAD and maybe a couple even more obscure ones.

HEAD is not that "obscure" and can be quite useful. For example, to test for session status. But yes, it's not widely used.

ben_lubar

With PATCH you only send the fraction of elements you want to modify.

Did someone say "race conditions"?

Eldelshell

@ben_lubar said:

Did someone say "race conditions"?

Well, I was being didactically simplistic here. The reality is that PATCH is much harder to implement since you also have to send what data to replace or the correct hash in the header (called ETag)

abarker

Even then, there could still be opportunities for race conditions. I would bet that is part of why it isn't implemented much

dkf

Even then, there could still be opportunities for race conditions. I would bet that is part of why it isn't implemented much

The lack of a standard content type for describing what to change is a bigger issue. No point in saying that you want to apply a delta if you can't say how to do it.

boomzilla

Tree walking with recursion; automatic F. Unless you like to facilitate stack overflows, you perform tree walking with iteration and maintaining back state on a stack. Ofcourse, it's not a one-liner that way. But a solid algorithm implementation very rarely is.

Or you could use a language that doesn't suck so much. Either way.

EDIT: meh...and this is why I shouldn't try to write snark early on a Monday morning before caffeine and with an allergy attack...

boomzilla

@Groaner said:

It's there, but the connection is tenuous. Table scans are linear complexity. Index seeks are logarithmic. The Cartesian product of two tables is quadratic. Rather than ask about the algorithmic complexity of a query plan, I'd rather ask candidates what sort of indexing strategy they would use given a schema and reporting requirements. Nineteen out of twenty of them will still have no idea what to do.

Yes, agree completely. And if they didn't mention profiling queries, they automatically fail.

dkf

Tree walking with recursion; automatic F. Unless you like to facilitate stack overflows, you perform tree walking with iteration and maintaining back state on a stack. Ofcourse, it's not a one-liner that way. But a solid algorithm implementation very rarely is.

Assuming you've got a balanced binary tree, and your stack can hold 100 entries (very modest!) then you can cope with 1267650600228229401496703205375 (= 2¹⁰⁰-1) items in the tree. You will have memory problems long before you run out of stack space.

JazzyJosh

Force the tree to be unbalanced (Really? Listen, can we move on?)

ArrayList<Object> binaryTree = new ArrayList<Object>();

Easy.

Also this is where we learn that Discourse refuses to parse after a < instead of changing it to & lt; which I also have to space out because escaping is broken.

Arantor

Yes, this we knew. It's so helpful that it allows this - as opposed to doing it as standard then only unescaping the entities that make known legal tags.

JazzyJosh

s/we/I/

Arantor

@JazzyJosh said:

s/we/I/

No, no, this is hardly a new thing. The only surprise is that you hadn't been bitten by it before since Discourse has done this since the start.

JazzyJosh

Correct.

FrostCat

You've certainly used other types of trees. Even the DOM is a tree. People not realizing that scares me.

Fair enough. Web work isn't my primary stuff, though, so the kind of data I work with is usually organized more like datasets; I actually didn't think of the DOM when I wrote that.

Ragnax

@Arantor said:

Yes, this we knew. It's so helpful that it allows this - as opposed to doing it as standard then only unescaping the entities that make known legal tags.

It shouldn't attempt to parse inside code regions

<div>like this</div>

The real issue ofcourse being that Markdown without GitHub style fenced code blocks is a complete DICK for rendering code blocks. And this on a forum dedicated to WTFs in programming, ofcourse... (Hey Discourse guy; see the problem there?)

PleegWat

One or more of the following may be true:

Any piece of software exposed to this community will prove to be TRWTF
All forum software is TRWTF

dkf

The real issue ofcourse being that Markdown without GitHub style fenced code blocks is a complete DICK for rendering code blocks.

The real issue is that Discourse doesn't really parse anything. It's just a toxic hellstew of regular expressions.

HardwareGeek

The real issue is ~~that~~ Discourse ~~doesn't really parse anything~~. It's just a toxic hellstew ~~of regular expressions~~.

FTFY

Ragnax

The real issue is that Discourse doesn't really parse anything. It's just a toxic hellstew of regular expressions.

@HardwareGeek said:

FTFY

Touché!

[EDIT]
And for added irony; Discourse completely shat over the nested quote for whatever reason, so I had to edit to compromise.

Go Discourse! [/sarcasm]

HardwareGeek