Fuck You, I Quit - Hiring Is Broken (article)

[blakeyrat]

@fbmac I don't know what in the post you quoted makes you think the job market in Seattle is bad...

For the record, I get maybe 3-4 "hey this job would be perfect for you!"-type emails a week, unsolicited (well, other than me having a LinkedIn account.) I average probably 1-2 interviews a month, because a lot of those unsolicited jobs are ones I don't want. (I have a lot of web analytics on my resume, so I get hit-up by recruiters who want a Omniture expert or a Python programmer. Because somehow Python of all languages got associated with "big data" analysis...)

But I'm mostly-happily employed right now. If I weren't, I don't think I'd have much trouble finding work.

[theBread]

@blakeyrat SciPy and NumPy are things now, and there's been a few python podcasts I've listened to that talk about big data and python. Maybe there's a new industry shift towards Python?

[blakeyrat]

@theBread See, strangely, I'd assume Java would be the best language for "big data":

1. It's the "default" language for HADOOP and a bunch of Apache "big data" tools
2. It has relatively-native support for arbitrary precision number types
3. It runs everywhere

It's also an application where Java's huge weaknesses (the shitty JRE, lack of UI libraries that don't suck, etc.) don't really do any harm.

[dkf]

@theBread said in Fuck You, I Quit - Hiring Is Broken (article):

NumPy

Be very careful with NumPy; a lot of programmers are writing code for it and publishing that code without saying explicitly that it is a requirement, yet quite a few standard distributions of Python don't include it in the process by default. Mysterious breakage ensues.

A colleague of mine describes such programmers as NumPtys.

[Yamikuronue]

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

HADOOP

HADOOP is so last year. Heil Hydra!

[blakeyrat]

@Yamikuronue That still appears to be Java, so it doesn't change my point.

I'm disappointed by the quality of their logo:

Where's the sprinting lion/leopard man/woman with sneakers? Feh. This looks like an actual designer might have actually touched it at some point.

[Ascendant]

@WPT

Oh yeah same as here. You become a reserve after you have finished your 2 years time in the barracks.

[Dreikin]

@Yamikuronue said in Fuck You, I Quit - Hiring Is Broken (article):

Heil Hydra!

(think "Squirrel!")

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

I'm disappointed by the quality of their logo

Indeed. It obviously should've been

Oh shi-

[dse]

@theBread said in Fuck You, I Quit - Hiring Is Broken (article):

@blakeyrat SciPy and NumPy are things now, and there's been a few python podcasts I've listened to that talk about big data and python. Maybe there's a new industry shift towards Python?

One only needs to use Java, then Python. And it is not just that Java is crap, Python is beautiful. When in need, just use Cython with a touch of C or C++, and you are golden.

[dkf]

@dse said in Fuck You, I Quit - Hiring Is Broken (article):

And it is not just that Java is crap, Python is beautiful.

Python's nice enough if you're not writing classes. The shine comes off a bit once you write classes of any sophistication. (OTOH, in Java you're always writing classes, whether you want to or not…)

[asdf]

@theBread said in Fuck You, I Quit - Hiring Is Broken (article):

Maybe there's a new industry shift towards Python?

Depends on the field. Python is definitely very popular in the machine learning community, for example.

[dse]

@dkf said in Fuck You, I Quit - Hiring Is Broken (article):

classes of any sophistication.

I hope you do not mean multiple inheritance. which has an odd implementation in Python and is ugly anyways.
I write classes when there is a need (most of the time actually), if all you need is a function you do not have to hide the fact like in Java. Modules are much better for a collection of small functions, in a nice namespace.

The only design pattern I miss in Python is Mixins. I used multiple inheritance for it and later realized how ugly Super gets.

[dkf]

@dse said in Fuck You, I Quit - Hiring Is Broken (article):

I hope you do not mean multiple inheritance.

It wasn't what was was thinking of specifically, but if the shoe fits…

[Adynathos]

@dkf said in Fuck You, I Quit - Hiring Is Broken (article):

Be very careful with NumPy; a lot of programmers are writing code for it and publishing that code without saying explicitly that it is a requirement, yet quite a few standard distributions of Python don't include it in the process by default. Mysterious breakage ensues.

I would say it is the opposite - if you do numerical tasks on Python, always install Numpy.
If there is a Python program that does some numerical calculations and it does NOT use Numpy, it is very suspicious.
Do they use some awfully slow in-house numeric implementation? Do they use a different library which will ensure the outputs of their code needs to be painfully converted?

[asdf]

@dse said in Fuck You, I Quit - Hiring Is Broken (article):

I hope you do not mean multiple inheritance. which has an odd implementation in Python and is ugly anyways.

TIL Python allows multiple inheritance.

[dkf]

@Adynathos said in Fuck You, I Quit - Hiring Is Broken (article):

I would say it is the opposite - if you do numerical tasks on Python, always install Numpy.

Blame the distribution vendors.

[Adynathos]

@dkf Where is that a problem? You can usually pip install numpy.

[blakeyrat]

@dkf Yeah it's great. Until you need something from a library, and then you realize there is no standard library there's just a conglomeration of shit, half of which is broken in Python 2, the other half of which is broken in Python 3, and 90% of which is broken in both.

[asdf]

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

and then you realize there is no standard library

That's bullshit.

[Adynathos]

@blakeyrat Depends what your project is. I find Python very suitable for quick prototyping, scientific and numerical problems where you need to change the program often, as a replacement for shell scripts.
Generally for small programs which you want to write quickly.
For bigger projects I would prefer something statically typed.

[asdf]

@asdf

The funniest part is, Python is probably the language with the largest standard library out there:

The Python Standard Library — Python 3.5.9 documentation

That's a pretty fucking huge, I'd say.

[AyGeePlus]

@dse said in Fuck You, I Quit - Hiring Is Broken (article):

When in need, just use Cython with a touch of C or C++, and you are golden.

The strangest thing is libraries tend to be written in pure python (for PyPy use) or python and C++, forbidding alternative interpreters without recompiling all your libraries which is a giant pain.

It's my least favorite thing about the python parallelism ecosystem.

I might be leaving python for Julia, we'll see.

[blakeyrat]

@asdf In .net there's a working SOAP client in the standard framework.

In Python, there's no working SOAP client anywhere in the anything. But there's like 6 non-working ones that you have to go through one by one and implement and try out before you realize they don't fucking work.

And it doesn't count if your library is big simply because it contains:

• urllib
• urllib2: the sequel
• oops-we-fucked-something-up-urllib3
• urllib4: the quest for peace

etc.

[asdf]

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

In Python, there's no working SOAP client anywhere in the anything.

That's because SOAP is bullshit. I get that this doesn't help you if you have to work with it, but that protocol should die in a fire.

Apart from a SOAP client, what is missing from the Python standard library that you'd expect in a standard library? It even has shit like WAV file support built-in. And a fucking IMAP client.

And, yes, the history of urllib is a sad one, but I bet that parts of the .NET standard library have evolved similarly over the years.

[blakeyrat]

@asdf said in Fuck You, I Quit - Hiring Is Broken (article):

That's because SOAP is bullshit. I get that this doesn't help you if you have to work with it, but that protocol should die in a fire.

Wow. You mention a dumb excuse, then in the very next sentence you explain why your excuse is dumb. That's a time saver. Maybe next time, not post at all?

[asdf]

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

You mention a dumb excuse, then in the very next sentence you explain why your excuse is dumb.

Maybe, just maybe, the first two sentences weren't meant as an excuse and were not entirely serious.

@blakeyrat said in Fuck You, I Quit - Hiring Is Broken (article):

Maybe next time, not post at all?

Nah, if you're allowed to post BS and bad excuses, then so am I.

[lucas1]

@dkf

A colleague of mine describes such programmers as NumPtys.

I was chatting to a someone on another forum "Numpy doesn't work on Windows".

I fire up cmder, create and activate a new virtualenv in python (yes I still use 2.7) and type pip install numpy ... installation works fine.

Apparently they didn't bother installing c++ compiler on his machine

[cabrito]

@lucas1 you don't even need a compiler nowadays; in Windows and Mac 'pip install numpy' will pull a .whl , which includes all necessary binaries.

[dse]

@cabrito said in Fuck You, I Quit - Hiring Is Broken (article):

@lucas1 you don't even need a compiler nowadays; in Windows and Mac 'pip install numpy' will pull a .whl , which includes all necessary binaries.

Plus, on Windows just install Anaconda it comes prepackaged with the essential libraries; that of course includes Numpy and SciPy. In Windows you also get the nice shortcuts in the start menu to run Spyder, ...

[cabrito]

@dse +1 to Anaconda. Scientist in not CS (physics, chem, biology, etc ...) loves this python distro with a wide number of scientific software ready to use

[dse]

@cabrito said in Fuck You, I Quit - Hiring Is Broken (article):

@dse +1 to Anaconda. Scientist in not CS (physics, chem, biology, etc ...) loves this python distro with a wide number of scientific software ready to use

@cabrito So do data scientists (used to be called statistician) and anyone who has pipelines of data to process (Scikits, Pandas, ...). Python is perfect for glue and pipeline.

[lucas1]

@dse I am wary of installing 3rd party distributions of python, I've had problems with active python before.

[dse]

Julie Bort  /  Oct 16, 2016  /  Enterprise, Tech, Careers

Google's nit-picky interview process is a huge turnoff for some experienced coders

In one important way, Google may have shot itself in the foot: its legendary difficult interview process.

[dkf]

@lucas1 said in Fuck You, I Quit - Hiring Is Broken (article):

I am wary of installing 3rd party distributions of python

The biggest thing to be wary of is having multiple distributions of python on a system, as python's remarkably good at getting itself into a mess when you do that. This is why I don't like python from an engineering perspective. I also don't like some language features very much.

[CrazyEyes]

@The_Quiet_One It happened to me once, and in the exact same period of months, actually. I was laid off in January and didn't end up successfully getting hired until April. To be fair, I should have gotten hired sooner, but screwed it up entirely of my own accord (let's just say I should have drank more water, and my to-be-employer was a software team working under an energy company, so they inherited power plant level safety regulations). Also, I only had 6 months of experience at the time, so that probably didn't help with my other offers.

But even between those, I frequently felt like I interviewed extremely well, and then didn't get the job. Honestly that's the thing that really annoys me the most. I can take straight-up being told that I'm not going to get the job, but when I interview very well and then they just select another candidate with no explanation, it's the worst. Once, I did a live coding exercise that took about 45 minutes, and had 5 problems. When I showed them my third solution, the dev lead there said "I think we've seen enough -- you're the first person we've interviewed in 3 years to provide a good solution to the third problem." It was implementing my own string-to-integer conversion function. Afterward, the dev lead was all warm smiles and the executive/manager (who you'd think is normally a people-person) just had a face chiseled out of stone, was completely unreadable. I felt sure that I would get the job after that, but nope, nothing.

I'm fairly confident that what usually happens is they just interview a guy who has a year more experience than you and then they hire him just to be "on the safe side," even though that thinking is frequently highly flawed. I hate interviews, most of all because the interviewers are always way worse at communicating than you'd think for people whose job it is to, you know, communicate.

[Maciejasjmj]

@CrazyEyes said in Fuck You, I Quit - Hiring Is Broken (article):

let's just say I should have drank more water, and my to-be-employer was a software team working under an energy company, so they inherited power plant level safety regulations

No, let's not just say that. Have you been showing up hungover? Have you dehydrated yourself to the point of exhaustion? Have you been moonlighting as a neutron moderator in a nuclear reactor?

[Rudolf Polzer]

@Yamikuronue This is one of my favorite interviewing laws:

Whenever a candidate says they're going to implement a breadth-first search (BFS), the probability that they're actually going to implement a depth-first search (DFS) is exactly 100%.

(Which in many cases doesn't make the solution any less correct)

Now, for reference, here's a mostly working (untested, just proven correct) recursive implementation of BFS:

bfs' :: (Node -> Set Node) -> Set Node -> Set Node -> [Set Node]
bfs' getNext visited current = (current : bfs' getNext visited' next)
  where
    visited' = visited `union` current
    next = foldr (union . getNext) empty current `difference` visited'

(Adding the case of current being empty, and fixing the typos, is left as an exercise for the reader)

[Adynathos]

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

Now, for reference, here's a mostly working (untested, just proven correct) recursive implementation of BFS:

I even once did a Haskell project, but your code is extremely unreadable :(

[Rudolf Polzer]

Yes, but I can't read other people's Haskell either.

In my specific sample above, the main understanding issue is that this isn't the "usual" BFS one might expect - e.g. it doesn't use a queue. And it doesn't operate node by node, but rather "layer by layer": in each recursion step it outputs all nodes reachable with a shortest path length of 0, then 1, then 2, then 3, ... (thus all those set operations). For trolling purposes, I evaded the typical queue a BFS would use.

Also, I had to use sets to not cause a worse than logarithmic (I know, fixable by using another Set implementation than Data.Set) complexity degradation. And to avoid having to decide on a specific representation of the graph, I just pass a function that from a node gives you the next nodes (which e.g. could be a map lookup).

Here's actually working code:

module Main where

import qualified Data.Set as S

bfs :: Ord a => (a -> S.Set a) -> S.Set a -> [S.Set a]
bfs getNext = bfs' getNext S.empty

bfs' :: Ord a => (a -> S.Set a) -> S.Set a -> S.Set a -> [S.Set a]
bfs' getNext visited current
    | S.null current = []
    | otherwise      = (current : bfs' getNext visited' next)
  where
    visited' = visited `S.union` current
    next = S.foldr (S.union . getNext) S.empty current `S.difference` visited'

graph :: Int -> S.Set Int
graph 0 = S.fromList [1, 2]
graph 1 = S.fromList [0, 3]
graph 2 = S.fromList [3]
graph 3 = S.fromList [4]
graph 4 = S.empty

main = print . bfs graph $ S.singleton 0

[Dreikin]

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

@Yamikuronue This is one of my favorite interviewing laws:

Whenever a candidate says they're going to implement a breadth-first search (BFS), the probability that they're actually going to implement a depth-first search (DFS) is exactly 100%.

(Which in many cases doesn't make the solution any less correct)

Now, for reference, here's a mostly working (untested, just proven correct) recursive implementation of BFS:

bfs' :: (Node -> Set Node) -> Set Node -> Set Node -> [Set Node]
bfs' getNext visited current = (current : bfs' getNext visited' next)
  where
    visited' = visited `union` current
    next = foldr (union . getNext) empty current `difference` visited'

(Adding the case of current being empty, and fixing the typos, is left as an exercise for the reader)

Oookay…

@Adynathos said in Fuck You, I Quit - Hiring Is Broken (article):

I even once did a Haskell project, but your code is extremely unreadable

Yeah.

Let's start by adding some syntax highlighting:

bfs' :: (Node -> Set Node) -> Set Node -> Set Node -> [Set Node]
bfs' getNext visited current = (current : bfs' getNext visited' next)
  where
    visited' = visited `union` current
    next = foldr (union . getNext) empty current `difference` visited'

...okay, so that doesn't appear to work. I know highlight.js supports Haskell, so ?

Anyway. Let's try some initial translations:

What objects do we have?

Types:

Basic types:

• Set: Actually a sort of tree underneath, which is how it makes sense in this context since the abstract idea of a set wouldn't need a breadth-first search. Consequently, from here on I will translate this as tree.
• Node: Presumably, a node in a tree.
• [...]: A list.

Composite types:

• (Node -> Set Node): A function that takes a Node and returns a tree of Nodes.
• [Set Node]: A list of node trees.

Operators and other special tokens/symbols:

• .: Indicates function composition - i.e., f(x) . g(y) becomes f(g(y)).
• ``: Two backticks with a word in between them mean that a function is being called in infix position.
• where: Appears to mean that the following lines/statements/whatever within this token's scope define things for use by the preceding statement/expression.

Functions:

• bfs': (why is it primed?) takes the function getNext and the two trees (visited and current) and returns a list of trees of Nodes.
• getNext: Something that takes a node and returns a tree of nodes. Presumably with only one node in it. The parameter side of whatever is passed into bfs'.
• union: takes the union of two collections - i.e., union A B means everything in A and everything in B.
• difference: takes the difference of two collections - i.e., difference A B means everything in A that's not in B.
• foldr: A generic function that takes, in order:
  • (a -> b -> b): a function that takes two values (of types a and b) and produces a value of type b.
  • B: an initialized accumulator of type b.
  • A: a collection of elements, each of type a.
    foldr takes an element from the right of A, uses (a -> b -> b) to combine it with the accumulator B, and repeats until done with the collection.
• (union . getNext): takes a node, turns it into a node tree, and then gets the union of that tree and another tree.

Other objects:

• visited: A tree of Nodes. Presumably starts out empty.
• current: A tree of Nodes. Presumably starts out at the root of the tree we're interested in searching.
• visited': A tree of Nodes. The new visited tree in the recursion.
• next: A tree of Nodes. The new current tree in the recursion.

---

Uh, does this actually work? From what I can tell next never has any contents, and after the initial call visited is always the complete tree. That is,

bfs' getNext empty full

calls

bfs' getNext full empty

because

• nextVisited = visited ∪ current = everything,
• current \ nextVisited = current \ (visited ∪ current) = current \ everything = nothing

Whoops, messed up the evaluation sequence. Doesn't matter though - see below.

[Dreikin]

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

Here's actually working code:

module Main where

import qualified Data.Set as S

bfs :: Ord a => (a -> S.Set a) -> S.Set a -> [S.Set a]
bfs getNext = bfs' getNext S.empty

bfs' :: Ord a => (a -> S.Set a) -> S.Set a -> S.Set a -> [S.Set a]
bfs' getNext visited current
    | S.null current = []
    | otherwise      = (current : bfs' getNext visited' next)
  where
    visited' = visited `S.union` current
    next = S.foldr (S.union . getNext) S.empty current `S.difference` visited'

graph :: Int -> S.Set Int
graph 0 = S.fromList [1, 2]
graph 1 = S.fromList [0, 3]
graph 2 = S.fromList [3]
graph 3 = S.fromList [4]
graph 4 = S.empty

main = print . bfs graph $ S.singleton 0

Oh, I see.

why would you make trees like that? Is that normal for Haskell?

[The_Quiet_One]

@CrazyEyes said:

Also, I only had 6 months of experience at the time, so that probably didn't help with my other offers.

Experience goes a long way in your job prospects. If your first job only lasted 6 months, it could raise some red flags. Whether or not that's a fair judgement is another story, however. I'd hope they at least gave you a chance to explain your situation, assuming you simply got laid off under circumstances beyond your control.

@CrazyEyes said:

I'm fairly confident that what usually happens is they just interview a guy who has a year more experience than you and then they hire him just to be "on the safe side," even though that thinking is frequently highly flawed. I hate interviews, most of all because the interviewers are always way worse at communicating than you'd think for people whose job it is to, you know, communicate.

It is flawed, to be sure. Now, from the employer's perspective, there's a lot at stake, since whoever they hire comes with the cost of training them (taking other employees' time), and if things don't work out, it's usually a few months before you can really come to that conclusion, since any hiccups could be anything from a rookie mistake to just a fluke, so you need to identify a pattern of failure to make that call. By then, you've wasted a few months. So, you've got to weigh your options. Some employers weigh heavily on the experience, while others think the ability to communicate well and have a well-rounded personality trumps everything else. Still others seem to think anyone with a pulse and a resume that says they did a bunch of cool things warrants an automatic hire, and I can tell you those guys are greatly underestimating how many people blatantly lie on their history, and chances are you'd end up working with a bunch of asshats who did just that.

In my experience, I've interviewed people who say they had 10 years of experience get pwned by someone fresh out of college. I've had people who had amazing expertise but didn't make the cut because they were extremely condescending and arrogant, which wouldn't play well with our other colleagues, plus with there being a chance of occasional contacts with customers for really technical issues, we couldn't afford that kind of liability.

[Dreikin]

@Dreikin said in Fuck You, I Quit - Hiring Is Broken (article):

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

Here's actually working code:

module Main where

import qualified Data.Set as S

bfs :: Ord a => (a -> S.Set a) -> S.Set a -> [S.Set a]
bfs getNext = bfs' getNext S.empty

bfs' :: Ord a => (a -> S.Set a) -> S.Set a -> S.Set a -> [S.Set a]
bfs' getNext visited current
    | S.null current = []
    | otherwise      = (current : bfs' getNext visited' next)
  where
    visited' = visited `S.union` current
    next = S.foldr (S.union . getNext) S.empty current `S.difference` visited'

graph :: Int -> S.Set Int
graph 0 = S.fromList [1, 2]
graph 1 = S.fromList [0, 3]
graph 2 = S.fromList [3]
graph 3 = S.fromList [4]
graph 4 = S.empty

main = print . bfs graph $ S.singleton 0

Oh, I see.

why would you make trees like that? Is that normal for Haskell?

New version of analysis!

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

@Yamikuronue This is one of my favorite interviewing laws:

Whenever a candidate says they're going to implement a breadth-first search (BFS), the probability that they're actually going to implement a depth-first search (DFS) is exactly 100%.

(Which in many cases doesn't make the solution any less correct)

Now, for reference, here's a mostly working (untested, just proven correct) recursive implementation of BFS:

bfs' :: (Node -> Set Node) -> Set Node -> Set Node -> [Set Node]
bfs' getNext visited current = (current : bfs' getNext visited' next)
  where
    visited' = visited `union` current
    next = foldr (union . getNext) empty current `difference` visited'

(Adding the case of current being empty, and fixing the typos, is left as an exercise for the reader)

Oookay…

@Adynathos said in Fuck You, I Quit - Hiring Is Broken (article):

I even once did a Haskell project, but your code is extremely unreadable

Yeah.

Let's start by adding some syntax highlighting:

bfs' :: (Node -> Set Node) -> Set Node -> Set Node -> [Set Node]
bfs' getNext visited current = (current : bfs' getNext visited' next)
  where
    visited' = visited `union` current
    next = foldr (union . getNext) empty current `difference` visited'

...okay, so that doesn't appear to work. I know highlight.js supports Haskell, so ?

Anyway. Let's try some initial translations:

Clarifying code from here:

module Main where

import qualified Data.Set as S

bfs :: Ord a => (a -> S.Set a) -> S.Set a -> [S.Set a]
bfs getNext = bfs' getNext S.empty

bfs' :: Ord a => (a -> S.Set a) -> S.Set a -> S.Set a -> [S.Set a]
bfs' getNext visited current
    | S.null current = []
    | otherwise      = (current : bfs' getNext visited' next)
  where
    visited' = visited `S.union` current
    next = S.foldr (S.union . getNext) S.empty current `S.difference` visited'

graph :: Int -> S.Set Int
graph 0 = S.fromList [1, 2]
graph 1 = S.fromList [0, 3]
graph 2 = S.fromList [3]
graph 3 = S.fromList [4]
graph 4 = S.empty

main = print . bfs graph $ S.singleton 0

What objects do we have?

Types:

Basic types:

• Set: A set of items.
• Node: A node in the graph. In context, an integer as a node ID.
• [...]: A list.

Composite types:

• (Node -> Set Node): A function that takes a Node and returns a set of Nodes.
• [Set Node]: A list of node sets.

Operators and other special tokens/symbols:

• .: Indicates function composition - i.e., f(x, y) . g(z) becomes f(g(z), y).
• ``: Two backticks with a word in between them mean that a function is being called in infix position.
• where: Appears to mean that the following lines/statements/whatever within this token's scope define things for use by the preceding statement/expression.

Functions:

• bfs': Takes the function getNext and the two node sets visited and current and recursively returns a list of node sets.
• getNext: A function that maps a Node to the Set of its neighboring Nodes. The first parameter of bfs'.
• union: The union of two sets - i.e., union A B means everything in A and everything in B.
• difference: The relative complement of two sets - i.e., difference A B means everything in A that's not in B.
• foldr: A generic function that takes, in order:
  • (a -> b -> b): a function that takes two values (of types a and b) and produces a value of type b.
  • B: an initialized accumulator of type b.
  • A: a collection of elements, each of type a.
    foldr takes an element from the right of A, uses (a -> b -> b) to combine it with the accumulator B, and repeats until done with the collection.
• (union . getNext): takes a node, returns its child nodes, and then gets the union of that set and the accumulator.

Other objects:

• visited: A set of Nodes. Presumably starts out empty.
• current: A set of Nodes. Presumably starts out as the root set of the graph we're interested in searching.
• visited': A tree of Nodes. The new visited set in the recursion.
• next: A tree of Nodes. The new current set in the recursion.

Important new objects:

• graph: A function representing a graph by mapping each Node to the Set of its neighboring Nodes.

Analysis

Graphs and searching

The crux of the in this one appears to be the structure and method of interaction with the graph being searched, as well as what "search" means. Let's start with the second part:

What does it mean to search?

In this case, it means "build a list in the order you'd like to check things". You may note that this does not fit the common definition of search, and you would be correct. This appears to simply take a particular graph structure and transform it into a struct you would then execute a linear search on. The actual search is something you would do on the result of this function.

What is the graph structure?

The graph is defined via a function, which is itself a switch-case statement. The switch is the Node passed into the function, which then returns a set of neighboring nodes from the matching case. To wit, this:

graph :: Int -> S.Set Int
graph 0 = S.fromList [1, 2]
graph 1 = S.fromList [0, 3]
graph 2 = S.fromList [3]
graph 3 = S.fromList [4]
graph 4 = S.empty

describes a directed graph looking like:

0 ◄─► 1 ─► 3 ─► 4
│          ▲
└───► 2 ───┘

as a static/pre-defined structure.

How is the graph used?

The graph is used like so:

neighbors = graph node

where node is the node you want the neigbors of, and neighbors is the Set of all the nodes 1 level downstream from the current node.

Top-level explanation of bfs'

The first call of bfs' in our example will look like:

retval = bfs' graph empty 0

And it will result in the following actions:

Creating visited'

The first internal variable, visited', is created in this line:

visited' = visited `union` current

This updates the visited list for the next call so that it includes the set of all nodes currently being examined. For our first node, this means the initially empty set now contains 0.

Creating next

The other internal variable, next, is created in this line:

next = foldr (union . getNext) empty current `difference` visited'

A lot of stuff is happening hear, so lets break it down into pieces.

Reduce

The first piece we'll look at is this one:

(union . getNext)

This piece creates a composite function out of union and getNext (which is actually graph in our example). The result, in this case and context would look like this in more familiar notation: union(graph(x), y).

Fold

The next piece we'll look at is foldr. This is explained above, so I won't go into that, but we'll look at how it's being used instead:

foldr (union . getNext) empty current

Here foldr is being passed union(graph(x), y) as the reducer, empty as the initialized accumulator (an empty set) x, and current as the Set from which each y is taken in turn. Because the function being used is foldr, the elements are notionally taken in right-to-left order. In context, however, this matters not a whit.

So, for our example of current being 0, this means it works like so:

• Grab an element from current (0)
• Get graph(0) ({1, 2})
• Get {} ∪ {1, 2} ({1, 2})
• No more elements in current, so done.

The result of this is a set containing the neighbors of each element in the nodes currently being examined, which we'll call neighbors in the next section.

Filter

The final piece in the creation of next is

foldr (union . getNext) empty current `difference` visited'

which we'll abbreviate to

neighbors `difference` visited'

This is fairly simple, and results in removing all the nodes we've already visited from the new neighbors set, resulting in the next set of unvisited nodes for bfs' to be applied to.

Creating the return list

Finally, we come to the meat of the function

current : bfs' getNext visited' next

This is responsible for creating and returning the list (recursively) and has two major parts:

Creating the list

This list is created quite simply by concatenating together the set of things we just looked at (0) and the result of applying bfs' to all the neighbors we haven't looked at yet ({1, 2}) via the : operator.

Recursing to find the rest of the list

Because this is recursive, 1 and 2 are then added to the list as a set, followed by the set of all their neighbors not yet visited, followed by the set of all their neighbors' neighbors not yet visited, etc. until we finally have a list looking like this:

[{0}, {1,2}, {3), {4}]

Which is the value returned by bfs', and which can be used for a breadth-first search of the graph by checking each item in turn.

[Tsaukpaetra]

@CrazyEyes Welcome to the forums!

[Tsaukpaetra]

@Rudolf-Polzer Also, Welcome to the forums!

[dkf]

@Rudolf-Polzer said in Fuck You, I Quit - Hiring Is Broken (article):

Whenever a candidate says they're going to implement a breadth-first search (BFS), the probability that they're actually going to implement a depth-first search (DFS) is exactly 100%.

Just ask them what the difference is between the two. Anything that says something like “one uses a stack of nodes to process, the other a queue” is correct.

[Yamikuronue]

@dkf said in Fuck You, I Quit - Hiring Is Broken (article):

Anything that says something like “one uses a stack of nodes to process, the other a queue” is correct.

Why would the answer not be "one of them searches every node at the current level before going deeper, while the other goes as far down as possible before backtracking to search adjacent nodes"?

[dkf]

@Yamikuronue said in Fuck You, I Quit - Hiring Is Broken (article):

Why would the answer not be "one of them searches every node at the current level before going deeper, while the other goes as far down as possible before backtracking to search adjacent nodes"?

That's also correct. And equivalent. ;)

[Yamikuronue]

@dkf One is a description of how to implement the algorithm, while the other shows understanding of what it's doing. Your answer sounds like something my classmates would have memorized by rote to pass the exam XD

[dkf]

@Yamikuronue My description emphasises the similarity in the algorithms, the other emphasises the difference. The key is that if you think about the differences first, you implement DFS using a recursive algorithm and then think “oh shit” when trying to implement BFS.