Data Structures as Culture
One of my friends (and former co-workers) just got back from the great Pacific Northwest, where he was interviewed for (and ultimately offered) a position with Microsoft’s Longhorn team. Being someone who conducts a fair number of interviews these days, as well as someone who has suffered through the terror of technical interviews on the other side of the table, I was naturally very curious about the whole affair.
The one thing that really stuck out in his account was that nearly every coding question he was asked was some sort of tree problem. Now, I do realize that tree questions are extremely common in job interviews (and that their prevalence could have had something to do with the specific job he was interviewing for), but this overwhelming emphasis on one particular data structure in two days of interviews reminded me of something I’ve noticed about Apple: for a great many people there, the hashtable seems to be something of a pet data structure. One can certainly see this in Cocoa, with its frequent use of NSDictionary objects to pass data around, and I and many other people I know have been subjected to grillings about the characteristics and implementations of hashtables in Apple interviews.
Being a person who loves to extrapolate grand cultural critical theories from probably inconsequential observations like this, I’m very tempted to ponder what this says about the two organizations’ values. My pet theory? That Microsoft emphasizes tree problems because their culture puts a high value on the kind of mental gymnastics often necessary to solve such problems, while Apple emphasizes hashtables because its aesthetically-oriented culture prizes their combination of zen-like simplicity and seemingly impossible speed. This is a broad generalization, of course (I’m sure people ask hashtable questions at Microsoft, just as people ask tree questions at Apple), but I still think it’s an interesting theory.
September 27th, 2005 at 1:30 pm
Excellent insight. This actually says a lot about the difference between the Microsoft and Apple worlds.
If I remember, a lot of MIT people back in the 70s broke the computer world into the Lisp and non-Lisp data typers. The Lisp folk took a casual attitude towards data structures - just shove them in a list, put them on a plist, stash them in a cache. If it gets slow or confusing, add some tags and a hash algorithm. Most non-Lisp folk were appalled at this. They wanted to see the data structure design up front, the data relationship dictionary, complete and comprehensive, even before any coding started.
You get a similar dichotomy today. The Microsoft people want to have a clue as to what is going on before they start working, so they build a tree structured model. They want to know what is important and what is not. The Apple people don’t care about having a clue, as long as they get something useful and usable. They know that what they think is important may not be important to their customers.
This is probably an old Apple corporate thing. The Apple II was basically a platform for running VisiCalc on, the proverbial tail wagging the dog. Excel and MarinerCalc aren’t the big reasons for buying an Apple these days. You’re more likely to want an Apple for Mosaic or SoundJam, or their successors. Apple figures that most of its users are smart, and that they’ll figure out what to do with the box, if the box lets them do it.
Microsoft, in contrast, took over the old IBM operating system monopoly, and the old OS\360 business model. Businesses are hierarchies with the boss at the top. The software has to reflect this. Everyone, and every piece of software and data, has to know its place. You can’t just have people running around making things and selling them. As long as users can get their assigned jobs done, the box and its software are great.
I suppose we should consider this progress though. Microsoft is tree oriented. The old IBM was array oriented. One step at a time.
July 24th, 2006 at 12:25 am
You can make some rocket science data stuctures out of trees, but most pactical problems are better solved with plain old arrays and hashtables.
July 24th, 2006 at 8:08 am
I think the difference between the two approaches is more technical than cultural. An application developer is expected to be facile with high level data structures such as lists, maps, etc. that are used to compose applications… whereas a systems developer is expected to be familiar with the low level representations of programming languages, objects, etc., where programs are represented via abstract syntax trees, objects have an implicit containment hierarchy, etc.
What do I think this means about Microsoft vs. Apple? It could be nothing more than a difference in the respective job positions… or - and I suppose this is possible - it could indicate that Apple fosters an object oriented approach to systems building in contrast to Microsoft, which prefers a low-level approach that is driven more by computer science theory than by software engineering best practices.
July 24th, 2006 at 2:50 pm
I think you’re over-extrapolating. I work at Microsoft: allow me to assure you that trees are not accorded any mystic special significance.
All this means is that unfortunately the interviewers on your friend’s loop didn’t get together beforehand and make sure their questions were sufficiently diverse.
If you want to accuse anyone of being over-fond of trees, how about the C++ STL authors? IIRC that had tree-based structures exclusively for years - before hash_map was added to the standard. I think that was due to comparison being considered a more basic operation than producing a hash code.
July 24th, 2006 at 5:57 pm
> .. reminded me of something I’ve noticed about Apple: for a great
> many people there, the hashtable seems to be something of a pet
> data structure.
Ahaha so true. When we were at WebObjects training years ago the group developed a phrase that we would slip in at every opportunity - “The NSDictionary is the computer!” - a (bizarre) reference to the Sun jingle of the day.
September 8th, 2006 at 8:29 am
[…] Ran across an interesting remark in a discussion of Microsoft hiring interviews: If I remember, a lot of MIT people back in the 70s broke the computer world into the Lisp and non-Lisp data typers. The Lisp folk took a casual attitude towards data structures - just shove them in a list, put them on a plist, stash them in a cache. If it gets slow or confusing, add some tags and a hash algorithm. Most non-Lisp folk were appalled at this. They wanted to see the data structure design up front, the data relationship dictionary, complete and comprehensive, even before any coding started. […]
October 2nd, 2006 at 8:31 pm
Whoa! I had no idea this would be so true industry-wide.
I work at Boeing (150,000 employees), and one thing they’re absolutely crazy about is trees, both in employee structure (management trees are *very* narrow), and programs (they like to put *everything* in big hierarchical databases). It’s insane how tree-crazy they are here. The complexity is incredible; to generalize (slightly), nobody has any taste or sense of simplicity, so everything grows very quickly in complexity beyond the ability of any mere mortals to understand it.
They even have a way to make a Gantt chart into a tree. Yeah, I know.
My previous job was at a university. They barely even used the filesystem hierarchy: almost everything was two levels deep in the folder structure. It was very manageable. If I had to pick one data structure to describe that experience, it would have to be the list (either linked, or array). Dictionaries were a close second, just to store some key,value-style metadata about the lists.
I’m now looking for another list/dict job.
November 3rd, 2006 at 5:10 pm
[…] My friend over at SciFiHiFi suggests that Microsoft likes trees, but Apple likes hash tables. Well, I think that Microsoft prefers integer arithmetic, while Apple (or at least Cocoa) likes floating point. Here’s a bunch of examples I found: […]