I don’t blog often. And I haven’t blogged about coding for a while; but I think I should. So here goes.
Having recently graduated from UCLA, I’m now trying to get a solid job at a solid company making some solid money. My skills primarily consist of writing code and running startups so that’s my target. Apart from the obvious choices (Google, Facebook, Microsoft, and so on), I’m also applying to a slew of startups around LA and the Bay Area. If you’re not familiar with the interview processes for tech companies, they go something like so: HR interview, phone tech interview 1, phone tech interview 2 … phone tech interview n, campus tech interview 1, campus tech interview 2 … campus tech interview n, offer or no offer.
Now I’m all up for hiring smart people that know how to get things done, but I really really loathe the technical interview. To explain why, let me cite an example from Cracking the Code Interview — the de facto bible of tech interviews.
2.2 Implement an algorithm to find the nth to last element of a singly linked list.
Easy, right? Well, not so fast, skipper. Here is the proposed solution (by an apparent Googler):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public static LinkedListNode nthToLast(LinkedListNode head, int n) { LinkedListNode p1 = head; LinkedListNode p2 = head; if (n <= 0) return null; // Move p2 n nodes into the list. Keep n1 in the same position. for (int i = 0; i < n – 1; i++) { if (p2 == null) { return null; // Error: list is too small. } p2 = p2.next; } if (p2 == null) { // Another error check. return null; } // Move them at the same pace. When p2 hits the end, // p1 will be at the right element. while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; } |
Feel free to scratch your head and go “what the hell” because I know I am. The above is considered a solution to Problem 2.2. First, let me mention what’s wrong with it:
- Using two pointers is dumb.
- It’s difficult to read. I needed 10 minutes to get my head around it when the function should be doing something trivial
- It’s simply bad design. More on this in a few.
Now let’s solve the problem like real software engineers, not hipster programmers that thrive on esoteric nonsense:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// this is how normal people find the length of a linked list public int getLength(Node head) { int length = 0; Node n = head; // iterate through the list while (n != null) { // yay more length ++length; // go forward! n = n.next; } return length; } // this is how normal people find the nth to last node of a linked list public Node getnthFromLast(Node head, int nth) { int length = getLength(head); Node n = head; int location = 0; // if list is empty or we want to go too far back or we want zeroth to last, return null if (length == 0 || nth > length || nth <= 0) return null; // 1st to last = last // 2nd to last = penultimate (length-1) // 3rd to last = length – 2 // .. and so on while (n != null) { // right location? if (location == length – nth) return n; // next spot ++location; // next node n = n.next; } } |
Simple, concise, readable. What irks me most is that not only will interviewers think code like the one from the book is good, but so will interviewees. Oh well, c’est la vie.