melreams.com

Nerrrrd

Link of the day

Today’s link is a companion to my earlier post with resume advice. After resumes come interviews, and in those you’ve got to ask your interviewer a few questions. When you’re just starting out it’s really hard to know what’s okay to ask or what you would even want to ask. Fortunately Jen Hamilton compiled a fantastic list of questions to ask interviewers from various sources (they’re linked at the bottom) and her own interests and experiences.

A couple of questions I’d like to highlight are these ones:

Flex time/core hours? Is variability tolerated or is everyone expected to be on the same schedule?

Is it possible to work from home, say, 1 or 2 days a week? Does anyone do this?

Just because a lot of companies that hire developers work normal 9-5 hours doesn’t mean they all do. I’ve heard enough horror stories to strongly recommend asking exactly when you are expected to be in the office/available online and whether it’s going to be a big deal to work from home to let the field tech in to fix your internet connection.

Hiring funnels are a thing

Unrelated image from pexels.com to make this post look nicer in social media shares.
Unrelated image from pexels.com to make this post look nicer in social media shares.

Recently I went to a Victoria BC Startups meetup about diversity and inclusion in recruitment called Lever talks Diversity and Inclusion in Recruitment. What I learned the most about was how hiring funnels work.

I first learned about the concept of funnels from sales funnels, where you start at the top with lots of people who are simply aware your product/service exists, and work your way down through getting them interested in your product to making a decision about whether to buy to eventually making a sale, with fewer people at every level. That’s normal for sales (and for any other funnel, like hiring), not everyone who is aware of your product is going to want it. Many of them may not even have a problem your product solves. Some people go with competitors, some people just keep doing what they’re already doing, some people are ready to buy but at the last minute they lose their budget or their boss decides to change direction, all sorts of things happen. Because of that, you need a lot of potentials at the top of the funnel to make sure anyone makes it all the way down to the bottom.

Sounds a bit like hiring, doesn’t it? ;) The big difference with hiring is that you either need to get people into the top of the funnel before you have an open position for them or you need to fill that funnel up extraordinarily quickly once you do have that open position.

The big thing I learned about that is that lots of people don’t think exactly like me. I’m sure that’s all kinds of helpful :)

More precisely, what I learned is that it’s normal to start talking with people before you actually have a job to fill and that doesn’t make you a time-wasting jerk as long as you’re honest about not having an open position right then.

The reason I had so much trouble with that idea was because I don’t usually bother talking to other companies until I’m Capital D Done with my current company and am actively interested in a new job. Since I thought that way I assumed everyone else did too, and because of that I figured talking with potential hires about a job that didn’t exist yet would be a mean-spirited waste of their time. I mean, they could have been talking with someone else about a job that actually existed and started making real progress toward their goal of finding a new job instead of wasting time on maybes with me. I’m not saying it was perfectly rational to be that worried about wasting people’s time, just that it was a thing I worried about.

But apparently it’s also normal for people to start talking to other companies well before they reach the Capital D Done stage, which makes it not a jerk move to talk with them about a job that doesn’t exist yet – as long as you’re clear about the job not existing yet, of course. I’m harping on that point because I feel very strongly about not jerking people around and because that’s the big thing that makes talking with people without having a job opening to interview them for work for me – I have to know I’m not jerking them around or I just feel weird about the whole thing.

Honestly, it’s probably smarter to start looking around before you desperately need a change, but the flip side of my not wanting to waste candidates’ time is that I don’t want to waste hiring managers’ time either. I assumed they only started talking with people because they had a job they needed to fill, which would make it a waste of their time to talk with them before I was sure I wanted to leave my current job.

I never really thought about how much time it takes to fill a hiring funnel (have you ever tried to hire an experienced developer in Victoria? It’s hard!), so I never realized how useful it actually is for hiring managers to have some people already in the funnel. If you have that then when it’s time to hire you don’t have to start from scratch, you can interview people who you’ve already talked to, who you already think could be a fit, who are already interested in your company. That sounds pretty great if you’re looking to hire, which makes it not at all a jerk move to talk to hiring managers before you’re sure you want to change jobs – again, as long as you’re honest.

In short, the moral of the story is that not everyone thinks the exact same way you do and that as long as you’re honest about what you have to offer you’re not being a jerk :)

How does binary search work, anyway?

Unrelated photo by Matthew Weibe to make this post look nice in social media shares.
Unrelated photo by Matthew Weibe to make this post look nice in social media shares.

Or, yet another blog post idea I stole from that article about programming interview concepts. You can find the rest of those posts under the how does it work? tag.

Binary search is an extremely simple idea that’s useful for much more than finding an element in a sorted array. The way binary search works is you compare the item you want to find with the item in the middle of the array, then whichever “side” of the midpoint of the array your element falls on, you compare it to the midpoint of that half until you find the item you want.

According to wikipedia a binary search makes at worst O(log2n) comparisons, which is pretty great when you have a large array. Because the search halves the search space each iteration, the maximum number of iterations you’ll need is the number of times you can divide your array in half. For an array of 100 items, you should only need 7 searches, and for an array of 200 items, you only need 8, and for 1000 items, only 10 searches. See how slowly the number of searches grows as the array gets a lot larger? That’s just cool!

Also cool: you can use that concept for more than just finding stuff in arrays. Back in college they taught us to narrow down where a bug in your code is using a binary search. Basically, comment out half of your code and see if the bug still happens. If it doesn’t, uncomment half of the commented half. If it does, comment out another half of the uncommented half. It always felt weird to do that, like I should’ve just been able to see the problem by reading the code, but it worked. If you’re new or just totally stumped, give it a try.

Of course, binary search isn’t the only way to find things. Hash maps can be even faster, but all they can tell you is whether your target item exists or not. If you want to return the next largest or smallest item in the event that you don’t find an exact match, hash maps are no help at all. There are binary search trees too (which I’ll go into more detail on in a future post), but ironically even though they’re named binary search trees, binary searching an array is usually faster. The problem with binary trees is it’s hard to keep them perfectly balanced, so you might have more “halves” on one side than the other which messes with your search efficiency. What binary trees are good for is quick updates – it can be a real hassle to add or remove an item from an array, trees are much easier to work with. There’s also plain old linear search, where you start at one end of your array and look at every item until you find the one you want. If you’re not going to search your array enough times for it to be worth sorting it, linear search is good enough.

That kind of tradeoff can actually make algorithm questions interesting. I still don’t care even a little bit whether you looked up how to reverse a binary tree before the interview, but I care a lot if you think to ask if you’re going to search that array enough times to recoup the cost of sorting it. Programmers, myself included, can be terrible about overengineering to solve problems that don’t actually exist. But more on that in another post!

How does big O notation work, anyway?

Unrelated image from pexels.com to make this post look nicer in social media shares.
Unrelated image from pexels.com to make this post look nicer in social media shares.

You didn’t think I was going to stop beating that programming interview concepts post into the ground, did you? Unlike some of the other concepts, big O notation is something you actually need to understand to write good code. Even better, you don’t need to know the term big O notation to have a conversation about the underlying concept.

Big O notation, also known as the order of a function, is a way of describing how much worse a function performs when you give it more input. If you’re sorting a small enough list, for example, it really doesn’t matter how efficient your algorithm is. If your list is a million items long, then the efficiency of your algorithm suddenly matters a whole lot.

The specifics aren’t necessarily that interesting, but let’s run through them quickly. Some functions, like figuring out whether a number is even or odd, are constant, or O(1). No matter how big a number you give that function, it’s going to take about the same amount of time to figure out whether it’s even. Functions that take longer in direct proportion to the size of the input, like finding an item in an unsorted list are called O(n) – the order is the same as the size of the input. Inefficient sort algorithms like insertion sort or bubble sort get much worse, O(n²). A bad sort has to compare each item in the list to every item in the list, which means that performance gets worse much faster than the input size increases. An extremely inefficient algorithm could even be O(n!), for example brute-forcing the travelling salesman problem.

In other words, nested loops are really, really bad :)

Understanding just how much worse an inefficient algorithm performs is a really important part of being able to make reasonable tradeoffs in your code. If your input is large enough, creating a binary tree out of it may be worth the extra memory usage for the improvement in time to find any given item. Assuming the computer will just magically handle it is not good enough when you may have to process hundreds of thousands of items or more.

As an interview question, I actually like big O notation – as long as you don’t insist on using those exact words to describe it. There’s no reason you need to use comp sci jargon to talk about which function of two examples would perform better with a massive amount of data to work on. It’s also something you can have an actual conversation about. Sometimes an inefficient algorithm is your only option, sometimes it can be avoided by using a different data structure, sometimes you can avoid the issue entirely by finding a different way to meet the user’s needs. That much more interesting to talk about than whether your candidate thought to look up how a breadth first search works :)

What should you ask in an interview: culture edition

Unrelated image from pexels.com to make this post look nicer in social media shares.
Unrelated image from pexels.com to make this post look nicer in social media shares.

Last time I talked about what technical questions you should ask in an interview, which is important but culture fit is at least as important. We’ve all heard of The No Asshole Rule, right? I firmly believe there is no such thing as an asshole so brilliant they’re worth working with, so for me culture fit trumps technical skill as long as all the candidates are halfway competent.

So what should you ask in interview to gauge culture fit?

First of all, the way many people talk about culture fit is completely and utterly wrong. Culture fit is not even slightly about figuring out if someone is cool enough to work with you. It is NOT about looking for a brogrammer who will play foosball and drink heavily with your team. It’s also not about finding someone who enjoys the same nerdy TV shows, books, games (video, card, or board), comics, etc as you do.

To quote Donna Choi’s Medium post about how they make hiring decisions at stackoverflow:

Be careful with “Cultural Fit”. This is often a catch-all for a vague sense of “would not fit in”, which can come to mean “is like me”. If you feel someone is a good or bad cultural fit, you must explain what you mean.
Valid “Cultural Fit” things: self-motivated, passionate, gets stuff done, cares about open source / giving back to the community, likes “default open”, hates office politics / meetings, pragmatic attitude towards tools / best practices, etc.
Invalid “Cultural Fit” things: obvious stuff like race, gender, sexual orientation, religion but also softer things like age, personality or hobbies (does not have to like Magic the Gathering to be a good dev). Assume that your bias is to hire people you “like” and be very careful of that.”

Another way to put it is how Johanna Rothman describes culture:

It’s about what you can and cannot say in the organization, how people treat each other, and what we reward.

Culture fit is about values, not about hobbies. A workplace run by grownups does not care even slightly about how “cool” you are or whether you’d be fun to hang out with. They care that you all have compatible views of the world. For example, some companies are very cautious and have very rigid procedures for deploying to production. Others do their best but ultimately feel that rolling back a bad release is not the end of the world. Commitment to work/life balance is another example of culture fit: is the company standard that nobody works overtime unless production is on fire, or are occasional spikes in hours to be expected? Priorities are also part of cultural fit: does the feature need to be perfect or just good enough? Are you planning to grow the company quickly and then sell it off, or are you planning to work here for the next ten years?

Rand Fishkin from Moz has a great definition of what culture fit actually is:

  1. Shared beliefs – the things that you collectively hold to be true about the world (e.g. good people tend to have traits like X, the right way to treat others is Y, what’s appropriate/inappropriate at work is Z).
  2. Shared priorities – what matters in terms of big, overarching things like work/life balance, short vs. long term commitment, how decision are made, etc.
  3. Stylistic cohesion – some people don’t work well together, others find themselves able and inspired to do more when surrounded by a certain type. Cohesion isn’t about finding lots of people who are the same, but about making sure there’s no one on the team that detracts from others and that many get more enjoyment and progress from the diverse perspectives their co-workers bring.

Now that we know what culture fit actually is, how do we figure out whether a candidate will fit?

First of all you need to know what your company’s culture actually is. Without some sort of solid definition, you’re stuck stumbling around asking largely random questions and hiring someone you “have a good feeling about,” which usually comes from them being like you. This is how you end up with a total lack of diversity and bad hires because you don’t actually know what you’re looking for.

Once you know what your culture actually is, it becomes a lot simpler to ask questions about it. If part of your culture is that everybody gets their say when a decision is made, ask your candidate how they think decisions should be made. If part of your culture is that when things go wrong you fix it first, try to keep it from happening again second, and look for someone to blame never, then ask your candidate how they think problems should be handled. If it’s important that your people get enough downtime, ask a team lead/manager candidate how they make sure their team gets enough downtime and how they handle it if upper management suddenly drops a new requirement on them. If you often have to meet rigid deadlines, ask how much flexibility they need.

Like I said in my post about technical interviewing, you are allowed to straight up ask about culture! Just make sure you’re actually asking about culture and not about whether you’d enjoy hanging out with the candidate.

For more example questions, I recommend looking at lists of questions for candidates to ask their interviewers. There’s some good stuff in this list and there are plenty more of them out there. Not all of those questions still make sense if you turn them around to ask a candidate, but you can steal a good chunk of them :)

Sadly, that’s the simple part of interviewing for culture fit. Another really important part is asshole detection, which can be a lot harder. Good culture fit questions will definitely detect at least some assholes, but people can be jerks in very subtle ways. I mean, nobody is going to tell their interviewer that they don’t listen to new ideas, but there is no shortage of people who will do things their way and only their way. People can also quietly wreck your company’s reputation by being enough of a jerk outside of work, in case you weren’t already paranoid about making a bad hire.

Normally I don’t recommend trying to trick your candidate because I think it’s a dick move, but I’ve heard it can be really useful to take a candidate out to lunch or for an after work drink and see how they behave outside of work. You would think people would stay on their best behaviour when they haven’t even started the job yet, but something about being outside the office seems to help people forget they’re still being interviewed. To be fair, I wouldn’t want to work somewhere I couldn’t be myself, so as tricks go I don’t think that one is that bad.

Readers, do you have any tips on catching jerks who are smart enough not to be obvious about it?

What should you ask in an interview?

In a few of my how does it work? posts I’ve mentioned that asking about a particular data structure or algorithm is a boring interview question that doesn’t tell you much of anything about whether your candidate can code.

First of all, the reason I think asking someone to implement a data structure or an algorithm is boring is because all you learn by doing that is whether or not your candidate looked it up beforehand. Not even that, necessarily. Interviews are pretty stressful and plenty of people’s minds go blank when they’re stressed. I once choked on a question about the servlet lifecycle and it’s not like I don’t know how servlets work. If a question might tell you one thing and might tell you nothing, I don’t think it’s a good use of the limited amount of time you have in an interview.

Unrelated image from pexels.com to make this post look nicer in social media shares.
Unrelated image from pexels.com to make this post look nicer in social media shares.

I hate ridiculous brainteasers for the same reason – they’re just so binary.  Either your candidate gets the right answer or they don’t, which may or may not tell you anything because a stressful situation where you’re really scared of looking stupid is basically the worst possible environment to solve puzzles in.

Given all that, it seems fair to ask “Well what on earth should I ask in an interview?”

My take on it is that we’re overcomplicating the question. Which is kind of an occupational hazard, so don’t feel too bad about it :) Basically, if you want to know if someone can program, ask them about programming! Just straight up ask them how they would solve a problem.

One of my many pet peeves are wildly improbable scenarios questions like how many piano tuners are there in New York? Google, that’s how many. If you want to know how someone approaches a problem, just give them a programming problem. I really think it’s just weird to dance around the subject you really want to know about. You are allowed to straight up ask people about programming! It’s not as if programming problems are thin on the ground either (hey, what do you do all day again?), although it does take some work to find a problem that doesn’t require twenty minutes of backstory to explain why the problem is a problem. And if you’re asking improbable scenario questions because you want to see how a person thinks about a problem without them jumping directly into code, I think you’re depriving yourself of useful information. If somebody jumps directly into coding without thinking the problem through, I want to know that!

The kind of questions I think are interesting are realistic-ish (obviously you need something relatively simple if you want to ask more than two questions before you run out of time) scenarios like “given a system like x, how would you add feature y?” and “how does your solution change when you discover that the system is actually more like q than like x?” or “what would you do if production went down or was painfully slow?” or “given this description of a weird bug, what would you do to track it down and solve it?”

While every interviewing method has flaws, I like the idea of giving someone a take home project that either takes under two hours or that you pay them for, then talking about the choices they made in the interview. If you want to know if someone can code, just ask them to write some code! But for the love of god don’t ask them to do it on a whiteboard, that’s ridiculous. Coding on a whiteboard in no way resembles what a programmer does all day, even if your candidate is good at it it’s simply irrelevant to the job you’re trying to fill.

The downsides to take home projects are that they’re very biased in favour of people who have the free time outside of work to do them and that like everything else, it’s very very easy to do them badly. I’m willing to spend an hour or two on a take home project, but any more than that and I expect to get paid for my time.  That’s coming from someone who has no children, no pets, no elderly or sick relatives to look after, and practically no chores to do, too. For people who do have responsibilities, asking them to spend n hours of their scant free time on you is a big deal and you need to keep that in mind when you design your take home project.

Which is the other potential problem with take home projects: they need to actually take the amount of time you say they will. Yes, that means you need to have someone at the level you’re trying to hire for solve it first. I would say solve it yourself, but if you’ve been programming for ten years and you’re trying to fill a junior position, you need an actual junior to make sure what you’re asking for is reasonable.

That said, even the worst take home project is much more realistic than the ridiculous idea of asking people to take a short contract with you to see how they actually work with everyone in the office. There is basically zero chance anyone with any responsibilities is going to think “Sure, I’ll definitely quit my stable full-time permanent job to take a two week contract with some yahoo who might hire me if they decide they like me. What could go wrong?” That said, if you’re looking for people you can exploit, by all means keep hiring that way.

On a more cheerful note, a really good idea that came from a discussion on slack is having the candidate read some code and explain what it does. Most professional programming involves way more reading code and making sure you understand it, so much so that it seems like a really good idea to test people on that directly.

In general, ask stuff that directly relates to the job you’re asking someone to do. If you really do want them doing algorithm design then fine, ask them about algorithms. If you’re doing web apps, ask them about the frameworks you use or about general web concepts like concurrency, multi-threading, sessions, basic security, etc. If you do consulting, lean a little harder on scenarios where the candidate needs to ask questions to figure out what the client really needs, which is usually not what they asked for.

What do you think, readers? Do you have any favourite interview questions?

How does quicksort work, anyway?

Unrelated image from pexels.com to make this post look nicer in social media shares.
Unrelated image from pexels.com to make this post look nicer in social media shares.

Why yes, I am going to keep mining that article about stuff you should know for programming interviews for blog post ideas :) While I don’t think that a lot of the common interview concepts from that article are actually worthwhile to ask about in an interview, I do think they’re interesting bits of nerd trivia and going in depth into how stuff works shows that nothing the computer does is magic.

Sort algorithms in particular are a weird interview question because you should basically never implement one at work. There are always edge cases, but in general if you actually write a sort function you have done something bad and you should feel bad. The correct way to implement a sort function is to import a library and go on with your day.

That said, sort algorithms are interesting in their own right. They’re one of those things that seem incredibly simple and boring until you start thinking about how you would tell a computer how to sort things. There are also way more sort algorithms than you might think, all with their own pros and cons.

Quick sort uses a divide and conquer strategy – instead of sorting the entire array you give it, it picks a pivot point (different implementations do this in different ways, one of the simplest methods is just to take the middle element of your array), rearrange the elements of your array so that everything less than the pivot is on the left and everything greater is on the right. Then you break the array into halves and recursively search each one until everything in the array is in order. There’s a really helpful gif at the top of the wikipedia article about quicksort that explains it better.

Because quick sort rearranges the array elements by swapping them, it requires very little memory, which was a big deal when it was invented by Tony Hoare in 1959. To this day it’s one of the fastest sorting algorithms, provided you do a good job of picking your pivot point. If you do a bad job of that things go off the rails, particularly if your array is mostly sorted already. In that case quick sort can (if you don’t check for a sorted or mostly sorted array) effectively unsort and resort your array which is pretty slow, surprisingly enough.

Another efficient (in this case it’s a technical term for sort algorithms that are efficient enough to actually use) sort algorithm is merge sort. Merge sort is even older than quick sort, it was invented in 1945 by John von Neumann. Like quick sort, it uses a divide and conquer strategy, the difference is that merge sort divides the array into the smallest pieces it can, then merges those pieces into two element arrays, then merges those into four element arrays and so on until it produces a completely sorted array. As usual, wikipedia has a gif that explains it visually.

Merge sort requires much more memory than quick sort does because of the way it creates new arrays while it’s sorting. This can be an issue if you’re sorting especially large arrays, although I’m sure more advanced algorithms based on merge sort can do some sort of trickery to mitigate that :) On the upside, it’s a stable sort – if you have two objects in the array with the same sort order, they’ll stay in that order – unlike quick sort. It’s also good at handling slow sequential media like tape drives and handling linked lists, which quick sort is slow at and heap sort can’t handle at all.

Heap sort, the last sort algorithm I want to talk about today, is an interesting one. Unlike quick sort and merge sort, heap sort puts all the elements of the array into a heap first, then uses that to sort the array.

Quick digression from sorting: a heap is a partially ordered tree structure. In a heap, the child nodes are always less than (in a min heap, or always larger in a max heap) the parent node, but siblings aren’t in any particular order relative to each other. The root node is always the largest or smallest element in the heap, and if you remove it the heap rebalances itself so the next largest or smallest element becomes the new root.

Back to heap sort: once you have a heap it’s very simple, you just take the root, add it to your array, let the heap rebalance itself, take the new root, and so on until your heap is empty.

In comparison with other sorts, heap sort is a little slower than quick sort on average but has better worst case performance. Merge sort has similar time bounds (average, best case, and worst case time it takes to sort an array), but takes up more memory because a heap sort can be done in place. On the other hand, merge sort is stabl, parallelizes well, and works on datasets too large to fit into memory at once, which neither quick sort not heap sort can do.

One last piece of trivia: the Timsort algorithm, implemented in 2002 by Tim Peters, is based on merge sort and insertion sort (a very simple sort algorithm) and is the standard sort function in Python and Java.

There’s a huge amount of detail I skipped over, I recommend poking around wikipedia if you’re interested in more detail about the many, many, many ways you can sort a list. Just don’t ask about them in interviews, because all you’ll learn by doing that is whether your interviewee looked them up beforehand :)

How does a breadth-first search work, anyway?

In a recent post I mentioned having read an article about passing programming interviews that said it was important to be able to write a breadth-first search and to understand how hash maps work. I covered hash maps last time, so this time let’s talk about breadth-first searches.

The first question is what on earth is a breadth first search? It’s a way of searching a tree structure. in a breadth-first search, you look at all the nodes at a particular ‘level’ of the tree before looking at anything in the next level. Another way you can do it is depth-first, where you follow each node’s children down and down until you run out of children, then go back up to the next child node you haven’t already visited and follow it’s children down until you run out again, and so on until you’ve visited all the nodes in the tree.

This is definitely a case where a picture is worth 1000 words. Here’s the order you visit nodes in a breadth-first search:

By Alexander Drichel - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3786735
Order nodes are visited in a breadth-first search. By Alexander DrichelOwn work, CC BY 3.0

and here’s the order in a depth first search:

Order nodes are visited in a depth first search. By Alexander Drichel - Own work, CC BY-SA 3.0
Order nodes are visited in a depth-first search. By Alexander DrichelOwn work, CC BY-SA 3.0

Great, what’s a breadth-first search for? According to wikipedia it’s good for a bunch of problems in graph theory that I totally don’t understand, and some more understandable stuff like finding the shortest path between two nodes in a tree and serializing a binary tree in such a way that you can easily deserialize it.

So how do you do a breadth-first search anyway?

bijulsoni has graciously provided an example in their article Introduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA on Code Project. If you’re interested, that code is provided under The Code Project Open License (CPOL) 1.02, which basically states that you can do whatever you like with the code but don’t come crying to them if it doesn’t work.

Here’s a breadth-first search:

 
public void breadthFirstSearch() { 
    //BFS uses Queue data structure 
    Queue q=new LinkedList(); 
    q.add(this.rootNode); 
    printNode(this.rootNode); 
    rootNode.visited=true; 
    while(!q.isEmpty()) { 
        Node n=(Node)q.remove(); 
        Node child=null; 
        while((child=getUnvisitedChildNode(n))!=null) { 
            child.visited=true; 
            printNode(child); 
            q.add(child); 
        } 
    } 
    //Clear visited property of nodes 
    clearNodes(); 
} 

and to compare, here’s how a depth-first search works:

public void depthFirstSearch() {
    //DFS uses Stack data structure
    Stack s=new Stack();
    s.push(this.rootNode);
    rootNode.visited=true;
    printNode(rootNode);
    while(!s.isEmpty()) {
        Node n=(Node)s.peek();
        Node child=getUnvisitedChildNode(n);
        if(child!=null) {
            child.visited=true;
            printNode(child);
            s.push(child);
        } else {
            s.pop();
        }
    }
    //Clear visited property of nodes
    clearNodes();
}

The complete, runnable code can be downloaded from the article linked above if you’d like to run it yourself. getUnvisitedChildNode() does what you would expect, so I left it out to save space. What I find really interested about the breadth-first and depth-first algorithms is that they’re practically identical except for the different data structures used to hold the nodes we’re working on. The simple change from a queue (where you add items to the end and remove items from the head) to a stack (where you both add and remove items from the end) is all it takes to change a breadth-first search to a depth-first search.

Now we all know how a breadth-first search (and a depth-first search as a bonus) works. You can safely forget the details, secure in the knowledge you can look it up if you need to :)

How does a hash map work, anyway?

I was reading this article about programming interviews a little while ago and one of the things they mentioned was that “A startlingly high percentage of interview questions reduce to breadth-first search or the use of a hash table to count uniques. You need to be able to write a BFS cold, and you need to understand how a hash table is implemented.” I saw that and started thinking wait a minute, how is a hash table implemented? I’m sure we covered that in college, but that was quite a while ago and I’ve forgotten a lot of stuff.

Unrelated photo from pexels.com
Unrelated photo from pexels.com

Quick note: Hash tables are also known as hash maps, dictionaries, associative arrays and probably more. I usually call them hash maps because that’s what they’re called in java.

For data structures, hash maps are really kind of cool. Under the hood, the data is actually stored in an array of linked lists. The interesting part is how the hash map decides where to put new elements. In a hash map, each array index is a bucket to put elements in, not the location of a single element. It uses a hash function (according to wikipedia, “any function that can be used to map data of arbitrary size to data of fixed size”, basically you give it an object and it gives you a number in a certain range) to decide which bucket to put any given item in. Hash % array length = array index to add item to. If there’s already an item in that bucket, it walks down the linked list to the last item and adds the new item to it. Because there can be multiple items in each “bucket,” the hash map creates an entry element that contains both the key and the value so it can find the right value for a given key when you ask for an element back.

Dividing the whole collection of keys and values into buckets is how hash maps work so quickly. If you had to search the whole list of keys each time it would much longer to get an element back from the hash map, but because of the bucketing system you only have to look at the elements in one bucket. It’s also very fast to add elements because you don’t need to worry about resorting the list, you just find the right bucket and add your new element to the end of the list.

There is a complication, though: the more items in each bucket the longer it takes to find an item. If your “buckets” fill up, you’ll need to expand the hash map by making a longer array and recalculating which bucket to put each and every item into. That can be a pretty bad performance hit if you have enough items in your hash map already. You also don’t necessarily want to avoid that problem by using a very large array, that just eats up memory for no good reason if you have so many buckets that you never end up putting anything in most of them.

Because of the bucketing system, hash maps are a great way to count uniques – being able to quickly find the right bucket and look through only a few items means you can add items or see whether the hash map already contains the item you want to add. On the other hand, hash maps aren’t very useful if you care about the order of your items or if you’re just going to process all of them in a loop. Getting a list of every element in a hash map involves walking each linked list in each bucket, which can take some time (and memory!) if you have enough items. If you’re going to process everything in your collection, skip the overhead of a hash map and just use an array list or linked list.

Okay, so given all of those implementation details, why are hash maps interesting to ask about in an interview? While it’s generally a good idea to understand data structures because they’re so core to what we do as programmers, I’m suspicious they get asked about in interviews because those interviewers were asked about them. Unless you’re interviewing a recent grad and want to make sure they paid attention in class, I’m not convinced that you really learn anything interesting about someone’s ability to code by asking for more details than what a hash map is good for and when you should use one. I mean, it’s been years since I forgot how a hash map actually works and I manage to write code that does what I meant most of the time :)

The interviewer is on your side

I’ve been thinking about interviews lately since I know a number of recent grads who are looking for work (ping me if you’re looking to hire a junior dev). Interviews can be really intimidating, especially when you’re trying to find your first development job. They still make me nervous and I’ve been at this programming thing for ten years.

photo of the skyline of a large city under an overcast sky
Unrelated photo from pexels.com

I’ve only participated in a couple of interviews from the employer side of the table and I’ve never run one myself, but I’m going to tell you what I learned anyway :)

One thing that you might not know is that interviewers don’t always get their other tasks cut back very much to make up for the time they spend interviewing. Don’t take that the wrong way, that doesn’t mean they hate doing interviews and want you to fail, it means they want to do the fewest interviews they can get away with and then stop.

Seriously, for the interviewer the ideal outcome of an interview is that the candidate is great, they can tell HR to send them an offer, and they can stop interviewing. Programmers don’t like getting interrupted anyway, and an interview and debrief with the other interviewers and then typing up notes for HR is a big chunk of your day.

The interviewer really and truly wants you to be great. It’s the most convenient way the interview can possibly go for them, and it really is awkward for everyone when an interview doesn’t go well. Nobody wants to watch someone crash and burn in an interview. Obviously that sucks a lot more for the interviewee, but it’s not really a great time for the interviewer/s either. Even if you’re not amazing, nobody wants to watch you fail.

Because the interviewer wants to stop interviewing, they’re looking for reasons to hire you, not reasons to turn you down. Nobody wants to make a bad hire, but ideally we can just make a good one and call it a day.

Another thing you should know is that culture fit, particularly if you’re interviewing at a startup, is extremely important. When the entire dev team is four people, the next hire makes a much bigger difference than it does on a team of twenty. On the one hand, that can make you nervous, but on the other hand, there’s nothing you can do about whether you’re a fit, so there’s really no point worrying about it. I know, I know, that doesn’t really work on me either. Do as I say and not as I do and all that :) You wouldn’t want to be on a team you don’t get along with anyway, so the best thing you can do is let your interviewers know who you are.

Something that took me quite a while to learn is that you are interviewing the company just as much as they are inte rviewing you. You’re not the only one who gets to make a decision here, the company you’re interviewing with needs to impress you too. I personally recommend asking about things like work life balance, whether they believe in crunch time, what their expectations for a new dev are, how they handle it when something goes wrong, exactly what time you’re expected to be in the office (startups are often flexible on this, but it’s good to know how flexible they are. Some offices also start at unusual times to stay in sync with head offices in other timezones), what the interviewer’s favourite thing about working for that company is, etc, etc. There are plenty of lists of standard questions to ask employers in an interview, take a look at a couple for inspiration and ask about the stuff that matters to you.

Employers really do like it when you ask questions, it shows that you care about which company you work for and aren’t just desperately trying to find anything that pays. Much like in dating, desperation is just not attractive. Employers like to feel special too :)

The one thing I really want everyone to take away from this blog post is that if the company is worth working for, the interviewer is on your side. They want you to be great so they can hire you and go back to work :)