Stumbling Towards Better

Interviewing for a job is hard. Hard because it shows, in a very harsh light, your real strengths and weaknesses. While I have yet to actually sign on the dotted line and become gainfully re-employed,  I have gone through the interview process a number of times in the past month, and have learned some good and some, well, sobering things about myself.

At this point  I want to analyze what went right, and what could be improved, as shown by the interview process.

The Good
I know that being able to have job offers within a month or so of being laid off is a good metric, and that reflects on some areas that I've been paying attention to:

1. My external profile. I've been maintaining my LinkedIn profile as well as my blog. The blog, in particular, requires a lot of effort, but I tend to focus on technology and problem spaces that I find interesting, and so it's not really effort I really feel.
2. Contacts. While I'm not a 'networker' per-se, I was able to reach out to people I have worked with/met in the past.
3. In Person interviews. I had several 'out of body' experiences where I would literally be hearing very intelligent things coming out of my mouth and thinking "wow, that's really good!". People that know me find it hard to believe that I can sound polished/intelligent. I actually find this hard to believe as well, but I witnessed it firsthand. Maybe this is the result of processing a lot of information over the past couple of years and finally being able to have coherent sounding summaries. But it makes a difference when you don't sound like an aging metalhead down to his last 5 brain cells. Note to self: omitting 'Dude!' and 'Fuck yeah!' from interview vocabulary was a good thing. 

The profile maintenance resulted in me being contacted throughout the year by various companies, all of which I told "not right now, but lets keep in touch" to appease my inner doomsayer who seemed to think that layoffs were just around the corner. When he turned out to be right and I was laid off, I returned to these contacts to set up numerous interviews almost immediately. Once onsite, I could tell that I was doing well. I interview the way I would like an interviewee to behave: (1) not acting like they're the bomb -- in my case, I am definitely not the bomb, and so there is no need to go there. (2) being friendly. I like nice people. I think other people like nice people. Generally speaking, unless I'm having a bad day, I'm a nice person. (3) Listening and responding. I like to be listened to, and have seen other people respond favorably when my  responses indicate that I heard what they just said and am taking them seriously. Fairly obvious stuff, but I'm just becoming aware of how important this is, and I'm 41.

The Bad/The Ugly

Enough about "me me me..blah blah great blah blah awesome". Lets talk about what didn't work. Because what didn't work boils down to a fundamental weakness that I've got to address in order to be able to progress in my career.  This fundamental problem revealed itself during phone interviews.  As much as I hate to admit this, every phone interview failure I had was completely my fault, and completely preventable. If someone was looking at the cost benefit analysis of the phone interview for the companies that dropped me based on how I did, they would only logically conclude that there was huge benefit for relatively low cost. Phone interviews are the way of the future. I'd better start improving!

The problems I ran into during phone interviews showed me in excruciating detail that my problem solving approach is flawed. This is embarrassing because as a software engineer, I get paid a good salary to solve problems. While I've been able to get this far by being somewhat intelligent, it became very obvious during the phone screen process at several well known companies that I was missing problems that had fundamentally easy solutions because I did little to no formal analysis of the problems. I just dove in and started coding.

That may work just fine on a 'reverse a string in place' or 'show me an in order traverse of a binary search tree' problem. But the problems being discussed were not implementation specific questions. They were problems that did not have an obvious solution, but whose solution was based in computer science fundamentals, and completely accessible from the information given in the problem itself. These are problems that, while initially hard, have solutions that are possible over the phone, in 45 minutes or less.

To summarize my flawed approach, I was doing what my 9 year old son does on word problems. Rushing ahead, diving in, and ultimately making a wrong turn. While that's perfectly acceptable for Kiran because he's in third grade and just starting to think about solving problems, I simply cannot come up with a good reason why I did not formalize a solid problem solving approach earlier in my career.

Let me put the whip and the hair shirt away because they aren't moving me closer to solving the problem. In college, I was very fortunate to be around some really smart people. I majored in Physics, not because I had an aptitude for it, more because I found it fascinating. The people that did have an aptitude for it were amazing. While the rest of us were just killing ourselves to get Bs and keep our heads above water, these guys were cruising in the relative stratosphere above us, making it hard to score high on the curve, but always taking the time to help anyone who asked. One of them was my friend Eric. After a while, I started to notice his different approach to studying. Eric always stopped working by 10PM, got to sleep at the relatively sane hour of midnight, and would usually take a couple of hours the next morning before class to finish his work. The rest of us would go until 2AM, make little to no progress, and drag into class the next day barely functional. When I asked him about his approach, he told me that "hard problems got much easier after a good nights sleep". When I started following his example (and literally following him out of the physics lab at 10PM and back in at 8AM), my grades got better while my thrashing was reduced. I also really started to understand the concepts we were learning, and my enjoyment of physics grew significantly.

So, even though I'm not close to brilliant, I have been close enough to brilliant people to notice what works for them. In this case, what seems to work for the best problem solvers out there is a much more logical/well reasoned/formal approach to solving problems.

The Solution, Take 1
I don't expect this to be the final solution to my problem solving deficiencies, but it's a start, and that is better than doing nothing. Summary:

• Clarify The Problem Statement
• Evolve Initial Solutions
• Implement
• Verify

Clarify The Problem Statement (Ask Questions If Necessary!)
Here is an example of a problem: "I have an array of unsorted integers. Find me all  integers A,B, and C that sum to 0"

Here are the facts:

1. the data structure is an array.
2. the contents are integers. 
3. there are 0..N triples of integers that sum to zero.

Here is a set of questions that should be asked to clarify the facts above

1. What data structures can I use to solve the problem (answer: any)

That's a short question list, but on other problems, the question list could be about the underlying assumptions, the signature of the method you are being asked to write, the kind of inputs into that method, etc. Make sure you get to the point where you could jump in and start coding. But dont!

Evolve Initial Solutions (and Pick One!)

The problem posed above is a hard problem. Can we actually simplify it and then evolve that solution so that it solves the more complex case? 

In this case, we can simplify to "Find Me all integers A and B that sum to 0". This is a valid simplification because it can be extended to any arbitrary sum of integers. Other simplifications may not be valid. You have to prove to yourself (and the interviewer) that your simplification is indeed a valid one. 

Note that these solutions are initial, and most should be thrown out. But we need to know why we are throwing them out and use that as rationale for selecting a possible solution and proceeding forward. Because proceeding with a solution is expensive, and we want to be right before moving forward. 

Proposed Solutions for simple case (A + B = 0)

1. compare every item with every other item. This O(n^2). non optimal. OK, that's probably not the one we want. 
2. If A+B = 0, then A = -B. Since we can use another structure to instantly compare items, load the absolute values of all list items into a set (that has constant time lookup) and then traverse the list, looking abs(list[x]) in the set. The time expense of this is 2n, one for loading into a map, one for traversing. The space expense is roughly O(2n), counting the initial array as well as the minimal size of the allocated Set. Note that the actual size of the Set is larger than n, but not exponentially larger, so we can make a decent argument that Set size is closer to n than n^2

A couple of notes: this is where knowledge of data structures, algorithms, and time/space complexity comes into play. It is one thing to crank out a breadth first traversal of a tree. It is another to realize that a solution to a problem requires a breadth first tree traversal. When coming up with solutions, whether simplified or not, I've found that the following really helps:

1. simple = better. Don't use a hash when an array will do. What are the initial conditions that may permit an array based solution over a hash based solution? Trees may be overkill, can the same problem be solved with a linked list? 
2. shoot for O(n) or O(n(log(n))) solutions. Only consider n^2 solutions when the naive solution is n^3 or above. 
3. When stumped, always revisit the initial conditions. The solution is there. Especially on a (contrived) phone interview question. 

When no simplification is needed, the solution you choose to proceed with is the one you continue with. Of course, you must know at this point what the time/space complexity of your chosen solution is, or at least what you think it should be. To not know this prior to implementation is unacceptable. 

Otherwise, working through an initial solution is the next step, and evolving the initial solution into a final solution is the step (or steps) after that.

So if we take the initial solution above, and evolve it to handle A+B+C = 0, what has changed and what needs to change. 

1. First: instead of an n^2 solution, the non optimal solution has changed to at least n^3. Because you need to take every A+B (an n^2 solution) and compare with every element in the list, i.e. every 'C'. That leads to n^3 non optimal solution. The question is how can we do better?
2. Instead of A = -B, the equation has changed to A+B = -C. 
3. Taking the initial solutions from the simplified assumption, we know that to get every A+B is an n^2 operation. Can we do the final compare in O(1) time to beat the non optimal n^3 solution? 
4. Again, looking at the simplified solution, we could load all elements into a Set to do the compare in O(1) time. 
5. So the solution to all A+B+C = 0 is to do an n^2 generation of all possible A and B combinations and then compare the absolute value of those sums against the absolute value of all C elements in the list. It has O(n^2) time complexity, and O(n) space complexity, because you're using the array and a map just like in the first solution.

(3) Implement -- and Work Around Roadblocks

The implementation for the problem above is pretty straightforward because the hard part was figuring out what to do. But what if the implementation for one of your solutions runs into issues? For example, what if you are restricted in what you can use as input parameters and don't know how to work with  the requested input parameters even after arriving at a viable, known cost solution? 

The best solution at implementation time is to 'box' the problem by assuming you have a solution that renders the output in a way that it can be used by your proposed solution. This is just another way to simplify the problem domain. When solving problems like this, make sure you let the interviewer know that you are drawing a box around the problem and will revisit the solution after getting the rest of the implementation going. 

The reason this solution is good is that it compartmentalizes the problem into something smaller that you can tackle. When you revisit the sub-problem, you will most likely have a more clear idea of any transformations or other solutions you will need to do in order to solve the sub-problem because you've already specified what the outputs of that sub-problem need to be and used them in the larger solution.  Even if you don't get the mini problem, you've shown that you can solve the bigger problem in a known and deliberate way. This is way better than rushing blindly in and getting stumped. 

(4) Verify That You Did What You Said You Would Do

If you've implemented a solution whose space and time complexity is known, you have two things to do here. 

1. verify that your solution meets the expected time/space complexity. 
2. verify that your code doesn't contain any (obvious!) bugs. 

(1) should be pretty easy, but (2) is sneaky. The best way to do verification is to talk about good testing inputs to the solution, why they are good, and what they will test.  So the real key to (2) is to pick the right test conditions. In the real world, you'd be pushing those test conditions into unit tests. Just because you're coding on the phone doesn't mean you are freed from unit testing. The point here is to be able to walk through the code and  catch problems before the reviewer does, or at least before you say "it's all good, Dude! Fuck Yeah!". Sorry. Still working on my vocabulary.

The Game Plan

The game plan to get me from where I'm at right now -- aware of a solution to the deficiency I've identified above, but still prone to rushing in --  to where I want to be -- solving problems in a conscious, thoughtful, intelligent manner -- involves practice. Practice, practice, and more practice. With hard, non obvious problems that stress my knowledge of CS fundamentals while forcing me to formalize my approach to a solution. My game plan is far from complete right now because I'm trying to narrow down what exactly to focus on. When I get that list, I'll write it down, as well as a schedule for attacking it. Hopefully, I'll have to balance that schedule with the demands of a (paying) job by the time I come up with that list!