Deep or Wide (Job Interview Preparation)

I had the pleasure of a going through a couple of job interviews in the past month. I was pleased with my performance on both. They were pleased with my performance on at least one.

Both companies are cool tech firms, but the interviews were very different.


Wide Company

Wide Company wanted to know if I was a real, modern software developer. This means that they wanted to know about my knowledge of tools and techniques, and my understanding of the principles of modern software architecture. They belted out a series of short-answer questions that sounded something like this:

  • What is a design pattern? (A well-structured solution to a common software problem. Most of the time means creating an interface where you weren’t planning to use one.)
  • Can you name a design pattern? (Sure – me laughing – Singleton)
  • OK, what’s a Singleton? (OK, here is where I expressed regret at not naming Decorator or Composite, since those are more interesting. But a Singleton is a pattern – or antipattern if you don’t like it – that only allows one instance through a factory method. It accurately models resources such as the operating system in some instances.)
  • How familiar are you with JavaScript? (Pretty good. I know what variable hoisting is.)
  • How familiar are you with Java? (Pretty darned good. I can solve problems using Java in job interviews.)
  • Have you ever used git? (I deploy my web sites using git and use it extensively at work, independent of our official VCS.)
  • Do you know about AngularJS? (Well, I know it is an app framework, something resembling MVC. I don’t really know it right now.)
  • Have you ever deployed anything to the cloud? (Well, not really.)
  • What is a Lambda expression? (Roughly an anonymous function that may or may not capture some lexical scope. If it does capture variable values in this way, it can be called a closure.)
  • What is dependency injection? (Also called inversion of dependency, it’s when you decouple a class from a class it uses by having the latter conform to an interface and having the object specified at run time rather than instantiating it directly. The Spring framework automates this pattern.)

There were more, but I have forgotten them. Or perhaps blocked out the painful memories…


Deep Company

Deep Company wanted to know how I solve problems using algorithms, data structures, and software.

They sent me a shared document and asked me to type solutions that they reviewed live during the interview. They gave me programming problems, and I chose to solve the problems in Java. In this interview, the questions resembled exam problems from a university course, and they asked me not to reveal any questions outside of the interview. So I won’t! Instead, I’ll make up problems of similar difficulty :

  • Suppose you have two circular linked lists. Write a method that tells me if the two lists are equal. The signature might look like this :

boolean areEqual (Node a, Node b)

Now this is the point where you are supposed to ask questions, which I did. But I tried to provide my own answers where I could.

  1. Can I assume Node has fields Node.next, and Node.value?
  2. Are the passed nodes “head”, “tail”, or neither? A: Neither. There is no head or tail, and elements do not have a position index. It does not follow the traditional list API.
  3. Are the lists considered equal if the contain the same values in any orientation, regardless of whether a and b point to the same location in those lists?
  4. Can the nodes be null? Are there any one-element lists?
  5. And so on…

If you take the restriction that the nodes passed are supposed to be equal, and every element value matches at every position going around the list, then this problem can be solved by iterating around the list and checking each value for a match, and stopping when you reach the first node again. I wrote my answer mostly ignoring null edge cases at first,

  • Now write the same method, but without the assumption that the passed node positions have to match. Now a and b represent any arbitrary node in the circular list, but I want equals to be true if either list matches the other where you are allowed to start at any position.

Here I actually wrote down sample data structure instances as an example, and asked if they would be considered equal or not.

            a        b
            |        |
            v        v
Apple -> Banana -> Cherry ---
  ^                         |
  |--------------------------

I hope that you understand my ASCII art. I may need to work on my posting skills. Please comment if you have a cool tool for drawing data structures in WordPress or HTML.

And, yes, those two structures are supposed to return true for equality.

Now the problem becomes harder, but is still doable. You can brute-force the solution with a two-level loop, one rotate the starting position until the starting elements match in value, another to check each position for equality after that.

  • Can you optimize your solution?

Optimization depends on the use cases. An optimization for one case makes other cases run slower.

Suppose the lists contain lots of repeat values. If that is true, then keeping a count of the number of occurrences of each value in a hash table would allow you to short-circuit the method and return false right away if the lists do not contain the same content counts. But if the counts match, you must continue and check their structure to make sure that matches as well.


So, to the future : I am preparing for more interviews. But which way? Deep or wide?

Do I write some sample codes in Spring, AngularJS, and EJB 3.0?

Or do I solve algorithm puzzles and then optimize them?

I’ll do a little of both.

Wish me luck!

How did my HEAD get detached?

I would not have started this blog if I was afraid to look stupid in public. Here is my latest attempt:

http://stackoverflow.com/questions/38437946/how-can-a-one-entry-git-repo-be-in-detached-head-status

OpenGL 16 Years Ago

A funny thing happened this morning. I found my Masters Thesis online! It was in the ProQuest Dissertations and Theses Global database. I have uploaded it to ResearchGate.net.

At the time, OpenGL was the cross-platform 3D platform of choice. That’s still true, although OpenGL has changed and evolved a great deal!

JavaScript Promise

I was mildly surprised to learn that the Promise class has been built-in to JavaScript. I was trying to fully grok the functional library Bacon when I ran into the JavaScript documentation for Promise. A Promise looks like this :

var p = new Promise( /* executor */ function(resolve, reject) { ... } );

A Promise can be in one of three states at all times : Pending, Fulfilled, or Rejected. This is actually not a new idea. Ever play with Java Scanner? Its hasNext() method returns a boolean indicating the presence of another token on the data stream. But one must understand that some streams, such as network packet streams, may postpone answering while waiting for a slow client. Thus, hasNext() returns true if another packet of data has been received, false if the client has disconnected, and simply blocks (does not return) if the network client is being quiet. This corresponds to Fulfilled, Rejected, and Pending. A Promise is much more explicit.

The Promise constructor calls function before anything else. function is expected to spawn asynchronous work but not call resolve or reject immediately. is created only after function has returned. Once the asynchronous work completes, function will call resolve or reject, which notifies the Promise object of the new state.

Here is an example that fetches tweets from twitter using a Promise to handle the asynchronous call.

var http = require('http')

url = 'http://maps.googleapis.com/maps/api/geocode/json?address=New York, NY, U.S.A' 

//url = 'http://maps.googleapis.com/maps/api/geocode/json?address=Mungalatoid'

var p = new Promise((resolve, reject) => {
	console.log("Kicking off an HTTP request")
	// kicks off an asynchronous HTTP request
	http.get(url, (response) => {
		var data = ''
		console.log('HTTP response received')
		response.on('data', (buffer) => {data += buffer})
		response.on('end', () => {
			var twitterObject = JSON.parse(data)
			if (twitterObject.status == 'ZERO_RESULTS') {
				reject(data)
			} else {
				resolve(data) 
			}
		})
		response.on('error', () => {reject('HTTP Error')})
	})
	console.log("HTTP request has been made")
})

console.log("Evaluating Promise")
p.then(
	(resolvedValue) => {console.log("Promise resolved " + resolvedValue)}
).catch(
	(failureReason) => {console.log("Promise rejected " + failureReason)}
)

Try changing between the URLs to see what happens when Google cannot find a match for the place name. Notice that Evaluating Promise is printed before the http.get callback function is called.

Mind you, this whole thing is much simpler just using node’s fetch, which actually returns a promise given a URL.