Hacker News new | past | comments | ask | show | jobs | submit login
The Mother of All Interview Questions (raganwald.posterous.com)
263 points by raganwald on Aug 2, 2011 | hide | past | favorite | 128 comments



> Does your process involve invention? If so, please describe the three most recent things you have invented and why it was necessary to invent something new.

If you're asked this in an interview, you can't respond "no". If I were being interviewed, I'd hear it as somewhat like "Do you like unicorns, which are awesome? If so, describe your three favorite awesome activities with unicorns."

Which is fine, if you're on one of the teams that likes to innovate, but I'd just suggest that there's probably a more neutral phrasing that might allow a candidate to respond "I prefer to use existing solutions to problems, and here's why". Maybe:

> The last three times you faced a "build or buy (/use open source)" situation, which did you choose, and why?

Which may give you a better grasp of how the employee understands the economics of the situation, rather than just asking him to talk about the last three times he chose "build" given that choice.


The question of bias is an excellent one to ponder. I agree that my phrasing is biased, but so is:

  The last three times you faced a "build or buy (/use open source)”
  situation, which did you choose, and why?
...in a way, as it only covers places where there is a perception that there was a straight-up choice.

One of the things I am interested in is places where the invetion-oriented folks didn’t perceive there was a buy/borrow option, because they had bought into a requirement that seemed to necessitate invention.


When I was at Google I wished they had a few 'uncoders', people who made it their goal in life to leave the source tree with fewer lines of source than they found it.

True story: I went to a talk given by one of the 'engineering elders' (these were low Emp# engineers who were considered quite successful and were to be emulated by the workers :-) This person stated when they came to work at Google they were given the XYZ system to work on (sadly I'm prevented from disclosing the actual system). They remarked how they spent a couple of days looking over the system which was complicated and creaky, they couldn't figure it out so they wrote a new system. Yup, and they committed that. This person is a coding God are they not? (sarcasm) I asked what happened to the old system (I knew but was interested on their perspective) and they said it was still around because a few things still used it, but (quite proudly) nearly everything else had moved to their new system.

So if you were reading carefully, this person created a new system to 'replace' an existing system which they didn't understand and got nearly everyone to move to the new system. That made them uber because they got something big to put on their internal resume, and a whole crapload of folks had to write new code to adapt from the old system to this new system, which imperfectly recreated the old system (remember they didn't understand the original), such that those parts of the system that relied on the more obscure bits had yet to be converted (because nobody undersood either the dependent code or the old system apparently).

Was this person smart? Blindingly brilliant according to some of their peers. Did they get things done? Hell yes, they wrote the replacement for the XYZ system from scratch! One person? Can you imagine? Would I hire them? Not unless they were the last qualified person in my pool and I was out of time.

That anecdote encapsulates the dangerous side of smart people who get things done. Sometimes they are too smart and do too much. So when the question of 'invention' comes up I like to wrap it around discovery. Sort of 'Tell me about a time where you built something that you had no idea how to build it when you started.' Things I look for are how did you go about discovering the path? What resources did you engage? What options did you consider? When did you 'call the vote'[1] ? My experience has been that things built by two or three people, working as peers, are often much 'better' (meet the needs better, cover more cases, have a more consistent model) than things built by one person.

[1] 'call the vote' - in parlimentary terms when continuing debate will not help you make a better decision, it is time to stop debate and to vote on the decsion. Good leaders look for this point, and move forward once all the voices have been heard.


I hate to depart from the group think, but there's another explanation aside from a smart engineer getting carried away with their own brilliance:

    They remarked how they spent a couple of days looking over the system which was complicated and creaky, they couldn't figure it out
Now it may be the case that they didn't really try to fix it and are just using that as an excuse, but OTOH, they may actually have been stumped despite best efforts.

If the system really did defeat this smart engineer's days of study, then in my opinion, and the opinion of at least one discussion I've seen on HN, the software should have been rewritten. (IMO) this really needs more clarification before scorn is passed.


It is difficult to agree or disagree on the basis of a few paragraphs of anecdote. For example, I have often heard programmers say they don’t understand some code. When I probe, what I discover is that they have figured out what it does, but they disagree with why it is built the way it is built.

So they may explain that making such-and-such a change will take two days instead of a few hours, thanks to all the FactoryFactoryFactoryAPIXMLDescriptorSchemas they have to write. That is obviously a hugely different thing to having no idea how the code works and what they need to do to add or change features.

Or for another example, say instead of understanding a system in a day, it takes a week. The system sucks. But if it is relatively stable, even six days of lost time is trivial compared to the time needed for a rewrite and the risks involved.

I am not saying that this particular rewrite of Google’s XYZ is correct or incorrect, just saying that sometimes we might be right to leave well enough alone. Development time is not free, and in addition to figuring out the ROI of writing a new system, we should consider the opportuinity cost of having Mr. Brilliant rewriting a working but terribly written system vs. inventing something else that might confer a greater benefit to his employer.


I think that if we are going to live in snarky-genius-programmer-land for a little while, it's best for management to set the "guideline of griping" if you will-

- if a programmer who thinks of him/herself and/or is thought of by others as a genius comes to you and bluntly/opaquely describes their confusion over some code, just call them out as an idiot.

Make them realize that if they are going to come and describe a problem they're having, and they're going to spend/waste your time doing it, they better have their ducks lined up and already have details ready. "Oh I understand what the code does, I just don't understand why the coder did it that particular way" is an admission that the previous statement wasn't a qualified one. It's an admission that the programmer had no intention of approaching management with a rational conversation on the topic, just a, "Hey boss I'm going to re-do this whole thing". No one wants conversations like that in a professional environment, people are too busy with actual real problems for that kind of thing.

It takes a more technical manager than most IMHO to properly adjust for that kind of behavior, however. Many managers don't understand the technology as much as those they manage (perhaps it's different in strictly programming environments), and at some point "have to trust" what someone is telling them in shorthand. That is bad in this business. It may work in other industries, but it won't work here. A technical manager needs to be able to challenge a technical idea on it's merits, not on the aura of the challenger.

It doesn't mean coders have to approach managers with a four-page paper rationalizing their need to tie their shoes differently, and as the team gets used to the increased communication and personalities, shorthand understandings relevant to the team will become used. But it should always be placed on the foundation of proof. Trust but verify.

Treat your coders like adults, hold them to that higher burden of proof standard, and hold yourself as a manager to a higher technical standard to understand it, and the entire team can avoid this kind of junk. I come from network administration, and on medium to larger sized teams I've found that at first the smarter guys hate this method because they're used to being left alone to save the day. Being challenged ruffles their feathers in the beginning. After a little while, however, they realize that they're going to earn more respect because everyone around them, or at least their boss, is actually going to understand their brilliance.


Indeed. If i cannot understand a system (in my field) in a couple of days (depending on the size), and have been asked to work on it, chance is i'll ask for a rewrite, with documentation and readable code.

If your system is not readable and undocumented, don't blame the guy who will come and decide to rewrite it.


So you have a legacy system that is being used by other systems, you're the new super genius and can't understand the system, so you rewrite? Discounting the potential release iterations and bug fixes that are in the legacy system? Your "improved" version can't include that knowledge since you didn't understand the legacy system. Also discounting the company wide knowledge of the legacy system, warts and all that exists? Also having two identical systems isn't fantastic. Rewriting a system because someone can't understand it is rarely the correct solution. It most likely means the rewriter doesn't understand the problems that are being solved by the legacy system either.


And chance is, when you meet the 62k rows of code authentication system that is way too complicated and does way too much, that you will not be permitted to rewrite it in a more sane and modular way.


He didn't say this system was unreadable or undocumented, only "complicated and creaky," One particular programmer who was regarded as "smart" couldn't figure out what it did, but it may just have been too complex for him.


The problem is not that the system was rewritten; it may well have needed it. The problem is that the engineer did not replace the existing system. Now they have two systems that do nearly the same thing.


For clarity, the above is what I considered the 'problem' and was what I learned folks who invent new stuff and about interviewing those folks on how they got to the point where they needed to come up with something from whole cloth. I am sure there are horror stories on the other side as well, with systems which haven't been changed but need to be because no one is willing to risk it.

My issue wasn't that they re-implemented the subsystem, it was that they did so without understanding all of what it originally did and so they were guaranteed to burden users of that system with a huge migration task. Folks who were previous users of the old system had to figure out what he had implemented and where their features had gone, and a series of iterative steps as folks educated this person on their particular requirements, and a series of changes, the new system was eventually a nearly complete replacement.

The opportunity cost of those developers who were rewriting their code to talk to the replacement wasn't considered, there wasn't really a solid metric for 'goodness', it had none of the old bugs but it certainly had its share of new ones, it increased the technical debt of the source code base.

So here was a brilliant engineer who did write a crap ton of code and got it working, but the path they took caused a bunch of other engineers a lot of work as well. They did not acknowledge, in any way that I could see, the burden they had imposed.

The converse, fixing a large number of problems with precise surgical changes to the code base, were not things that were being held up as the model for success. That was a sad outcome of that culture, but one I value highly both in myself and in others.

So when someone tells me they re-wrote something from scratch, I'm always curious to see how they got to that conclusion. There are many good reasons to rewrite something, whether it was a prototype that ended up being shipped and kept alive with a hodge-podge of fixes, or circumstance changes where the total code lines would be less re-doing it than amending it. I enjoy figuring out these sort of 'coral reef' architectures, emergent things that were born of the bones of a million quick fixes over the years, and I have blown up a few in my time. Sometimes the reasoning is from external sources (like a system that had inadvertently become tainted with proprietary information).


It is often not possible for the rewritter to change all the uses of the old system.


The things which weren't said explicitly but which we can assume are that the original implementer wasn't around any more, and that nobody else understood the system either.

With these pieces of information, the decision to re-implement seems like a reasonable one.


If just looking at it doesn't help you figure it out, you start writing tests and use test coverage analysis to ensure completeness of your tests. Then you can refactor safely.


I once read the following story about a famous hacker. If I remember right it was about Woz, and recounted in the book Founders At Work.

At some point Apple was taken over by beancounters who wanted reports from programmers saying how many lines of code they'd written. Woz spent a day or two refactoring something, removed 5000 lines of code, and thoughtfully submitted a form with LOC marked "-5000".

They exempted him from having to submit any more forms.



You wrote that reasonably smart people couldn't figure out the old system, even with a couple of days' investigation. How is this a good system? If people can't figure it out, how are they supposed to use it?

Then you wrote that, when the new system appeared, "nearly everyone" moved to it. Doesn't this suggest that the new system was actually better? Why would most of the old system's clients, for example, pay the price to move to the new system unless they believed it was improved enough to be worth the migration cost?

I'm not saying that your conclusions are wrong, just that from reading your anecdote, it's not clear how to reconcile your claim that the rewrite was an mistake with the evidence that the result of that mistake seems to be preferred by nearly everyone who had the choice to keep using the old system.


I had a working mapreduce job that was 300 lines of fairly high level java code. Compact, terse, expressive, everything you don't see in most Java. I came back over a the weekend and my boss/coworker made it 'configurable' which means he added 800 lines of code.

I fucking cried.

He was like, "I hoisted out some stuff that should have been behind interfaces." ... I didn't need an interface because I only had ONE and specifically made the API have a low surface area so this could occur IF IT NEEDED TO.

I sucked it up and took it in stride.

Jumping in and solving a problem is usually the last thing you want to do, but that character trait(flaw) is what people think of as a good leader. Someone who will take you over a cliff with conviction.


>Compact, terse, expressive

Does 'Compact' mean that you originally did:

if( foo ) while( foo ){ do something }

all on one line and the boss split them up into multiple lines?

I ask because I worked a job where statements were combined on single lines for ease or reading and it was a nightmare.


By compact I mean the domain logic was all in one place and not diluted like a fine mist across the code. You could read it like english and it made sense. Consistency in abstraction levels and not too much genericism.


"Adding interfaces" to improve is when i start to freak out too, also splitting a well-defined piece of code into multiple classes. I call that symptom "knowing object oriented programming principles too well".


'Well-defined' piece of code or SRP-violating?


I've never met a class I didn't want to inherit.


The only time I was ever fired from a job, it was for doing this. I rewrote an entire web crawler stack using parallel event driven programming, yielding a crawler that could crawl the same number of sites they currently needed 10+ EC2 instances for on my laptop without breaking a sweat. I did it in a one-week + weekend maniac code binge.

I was a little peeved, but looking back not so much. I was receiving pressure and what I felt were conflicting orders from the CTO and CEO, and any company that lets someone go for showing initiative is not a place I want to work. I found a more fitting job doing high-speed creative product prototyping (where they want that kind of thing) afterwords, and for more money.

(It was a startup, and I now see it as having had some funny politics going on. I also think that one of the co-founders wanted me gone since I didn't graduate from one of the "right schools." He was a huge school-snob.)


I did the exact same thing a while back. The company I worked with used 4 fully-loaded servers driving Java spiders while I used 2 y/o laptop and 100 lines of Erlang.

Showed the code to my manager, he left the room saying I should do some "real" sysadmin work and stop playing around.

Just for a test, I started spidering big local news sites with I think 10000 threads and left it running for about 15 minutes.

Two things happened: 1. I consumed all bandwidth, rendering Internet unusable for the whole company, and 2. got about 10% of data other 4 Java servers could gather in a day

This stunt didn't get me fired, but my manager insisted I delete the program I wrote. Nobody was interested in results I got so nothing happened.

But it was fun watching bandwidth usage RRD graphs go through the roof :)


Interesting, the link to your blog in your profile goes to a parked domain (just FYI).

I hear these sorts of tales occasionally and I recognize a manager who is out of their league when comes to keeping someone with your skill set engaged. If crawling the big local news sites was something useful for the company, moving your application to a hosted machine where it had access to more bandwidth would have been a start, of course a demonstration is just that, a demonstration. The next step which is a bit harder might be to crunch the data into some sort of data structure for later analysis.

If this is the kind of problem you enjoy working on and are in the SF Bay area we should talk :-)


Yeah. In general, nobody knows how to write network code. I have seen tons of network apps that perform horribly and use utterly absurd amounts of resources for trivial tasks.


Used to work in a fortune 500 company that would send email notifications to customers telling them their monthly statements were available. Unfortunately, the monkeys who coded the email sending didn't understand the protocol, obviously had not read the RFC. The code would blindly send smtp commands without waiting for a response. One day the smtp server decided to change its behavior due to a dns misconfiguration and many emails were lost.


a startup fired you for showing initiative and doing more with less? messed up.


IMHO, I think they really fired me because I one of the co-founders didn't like me because graduated from the University of Cincinnati instead of MIT, Stanford, Harvard, etc.

I figured this out later when I checked their blog and he had prominently mentioned how they like to make sure their candidates are the "right people" from the "right schools." It was a very explicit statement, essentially that being from the "right school" is part of being the "right person."

I encountered this a lot in Boston actually, to the point that I developed a complex about how I couldn't really do anything because I hadn't gone to Harvard. Then I moved away and realized that the rest of the world outside this bubble doesn't care about that.


Whoa, I'm in Cincinnati. Are you still in the area? What are your thoughts on UC nixing the ComSci program?


Similar story here. The company I work for had a system that worked just fine, but apparently lots of things weren't done the right way, documentation was lacking etc... They decided to rewrite the whole thing, incorporate processes and after nearly 18 months of hard work they relaunch the app. That was the last time anything worked properly. Now we are left with a beautiful system that just doesn't work.


Not understanding the system is rarely a good reason to rewrite it. Let me guess, the system they rewrote was Google Groups? Because I remember back in 2006 it was working perfectly. Now their search of Usenet posts can hardly find anything.

Anyhow, I was working on a system once which had a very crappy implementation. Thousands lines of code in each source file. Spaghetti code everywhere. I spent a lot of time fixing bugs in that system. Clearly it wasn't productive. I decided to completely rewrite it. Spent a couple of months working on it, but when it was done, it had a cleaner implementation and far fewer bugs. I noticed that I hardly spend any time on that system any more - an indirect indication that the decision to rewrite was the right one.

Fast forward two years. I moved on to other projects. A new guy comes along (senior than me actually). His task is to make the old system work with new requirements. He comes with an idea - a complete rewrite. Since I worked on that system before, I get to review his design. He explains to me how his new implementation is going to have various "new" features. Then I ask him if he knows that the existing implementation does all that already and more. He had to admit that he have no idea how the existing system works, so he doesn't want to touch it - thence the desire to rewrite.

I gave him my advice but he proceeded with the rewrite anyway. The old code obviously got scrapped. Now, looking back I can't see where his new code ended up. Most likely his rewrite failed, so the new implementation never saw the light of day.

The moral of the story: even if you don't like the old system, you have to understand how it works in order to create something better.


Wow. So when you rewrite something, it's perfectly justified. When someone else decides to do the same thing, you twist the argument around on its head. Sounds completely hypocritical, mate.


Rewrite without deep understanding is bad. alexeiz claimed that the original implementation was bad, but still tried to work on it and decided to rewrite it, in the end, to something he considers clean, and as such, a good work base. The next guy did not even try to work with it, even though alexeiz seemed to have clear ideas on how to implement it on his system (which is, two years later, quite a good indicator of the sanity of the thing). You did not read that carefully, did you ?


Rewriting might still be faster then understanding an existing implementation.


If you don't understand it, how do you know what to write?


You know the know and understand the goals, but you don't understand the internals.


But look at the example cited: Google ended up with TWO systems, because he didn't fully understand what the program did.


Nope, because you have to understand in depth the existing work in order to rewrite it properly. Then only good rewrite is when you understand the existing stuff enough to see what is wrong with it. You can't rewrite something if you don't know what it does.


That's a pretty dim view. Sometimes systems are too complicated, or have swaths of dead code that you spend hours figuring out only to find out they're never referenced anymore.

I'm currently working on a project which was written somewhat poorly with little technical oversight, the result being a minefield of code which is slightly brittle and full of dead codepaths. The old system (which works, is complicated and creaky, and I spent some days figuring out out things worked) needs rewritten and if we weren't pressed for time I'd rewrite it in a heartbeat.

Given a goal, an API spec, expected behavior one can rewrite a system which one doesn't truly understand and still do it better.

Certainly, something built by one person is rarely the best. That being said, what's wrong with occasionally taking out the trash?


Personal confession, I was stuck with the NFS lock manager in SunOS 4.0. I inherited it after it had been written by a mathematician who understood the theory of how it would work, but unfortunately could not write code, and it was then given to a person who could make anything work, even if they didn't understand how it was supposed to work.

The result was exactly as you describe, functions which had clear logical errors but they were never called so it didn't matter, data structures where a third of the members were never populated. It took me a couple of months of back and forth before I felt I could even begin to attack it. And after implementing the kernel half and starting in on the daemon proper, Sun discovered 'divisions' and I found myself documenting like crazy so that I could 'hand off' something that wasn't a 'networking' problem.

I particularly liked the n-level deadlock detection algorithm, that was the experience that taught me that a data structure can represent a large set of potential computations all at once.


In my experience, when you have a system that works, is creaky, and you have to spend days to understand how thing work, there is at best a significant gap between actual and specified behavior. Most of the times, there is actually no spec at all, it is mostly implementation defined. And you rarely have the same team as the one who did the previous team (people left, have to work on other projects, etc...).

That's one of the fundamental issue with complete rewritea: the systems you could most easily rewrite are often the one you don't need to.


> My experience has been that things built by two or three people, working as peers, are often much 'better' (meet the needs better, cover more cases, have a more consistent model) than things built by one person

I concur, but for a different reason than you seem to imply (which seems to be "being conservative with changes and goal-oriented" -- nothing wrong with that on its own though). I noticed that my own coding improved dramatically after I started working with others. This is due to several things: (1) competition and trying to be better than others, (2) once you work with several people, you take extra time to document what you are doing, which occasionally leads to you rethinking how you should be doing what you are doing in the first place, (3) don't know about you, but I am personally far more prone to taking "shortcuts" when working on my own (no one to embarrass myself in front of), (4) last but not least, when working with others, you can learn directly from others.


Exactly the same I think.

I have found that unless I can explain something to someone else, then I must not completely understand it. And working with another forces you to be able to communicate and explain, and that gives you both a better understanding. The result is you find things you missed.


I hired a guy who did that once. Twice, actually, ten years apart. One was right out of the military and one was right out of the university. It would have been the biggest mistake of my life not to have hired each of them. They each created something awesome with no help from anyone except me. They each literally changed the world.


Marvellous anecdote and some incredibly sage advice about interpreteting someone’s evidence of how smart they are and how much they get done. Thank you.


Your asking us to assume that an unspoken goal in that particular software development endeavor was to not grow the total amount of code or libraries or systems, unless absolutely necessary. But was it? What if minimal system growth was a goal, but weighted at 0.5 and just get something running was also a goal, weighted at 0.99, because there was lot of money to be made with a working system.


Actually I don't think I was asking that at all, if you read it that way then I didn't communicate it clearly.

The topic of conversation here is interviewing, and the importance of trying to develop as qualified an understanding of a potential candidate as possible in an interview. Reginald posited the 'mother of all interview questions' around the question of invention and perhaps more subtly the question of building it yourself versus leveraging the work of others.

Its a great question because it starts a lot of interesting discussions around how someone evaluates tasks they are given and allows them to talk about what tools they can bring to bear on those problems.

I related that anecdote from Google because I gave more importance in my mind to 'invention' rather than 'discovery' before I went to work at Google. Google is, in my opinion, the technical equivalent of Mecca for invention. One of the things I learned from my time there was that you could go overboard on invention. Not simply 'not invented here' syndrome, but literally lowering the barrier to creating new systems so far, that the net result is a negative rather than a positive. (Google doesn't see it that way, which I understand too, this is simply an opinion after all).

I practical terms you are absolutely correct that getting something running will have a weight. maintainability will have a weight, and maybe continuity will have a weight too. And if someone ponders those weights, gets some feedback to test their understanding of the relative importance of them, and executes based on that feedback, that is a very good thing indeed.

The person I was listening too at Google either didn't do that, or didn't understand the implications of their choices with respect to the impact on the company, or perhaps the simpler answer was they just didn't think about it. Had they thought it through, I'm sure they would have mentioned it in their talk as the talk was supposed to be about best practices and that would have been a great point to get across.


I think Chuck isn't making the point well in his reply to you, so I'd like to summarize it as I see it.

Ultimately, all software advice cashes out as 'something running right'. (Or 'make money', if you prefer. The following is true regardless of what you see as the ultimate goal.) However, we do not have perfect information about whether arbitrary changes will increase that. Our decisions and estimates are going to be approximate and heuristic.

Chuck has provided an example of how decisions can be suboptimal because employees/smart-people are rewarded for looking good, not for actually increasing the amount of things running right.

One way to correct this bias towards overwriting is to include in the decisions a fudge factor against writing new code - expressed as an anecdote summed up in 'Sometimes they are too smart and do too much'.


Make no mistake about it. Being too quick to rewrite a system is bad. It causes unnecessary work for others and can throw a schedule behind drastically.

That said, I think it's important not to go to the opposite extreme. Personally, I'm in the camp of being too quick to rewrite things myself. And though I've learned to control my gut instinct in this regard, I've also learned that sometimes it's right.

I can name several instances where everyone would have come out better just by rewriting the damn thing up front rather than trying to fix or maintain the old system.

TL;DR - Sometimes discarding your peers' work is the best way to respect them.


I'm surprised no one has suggested refactoring yet. Joel Spolsky wrote most eloquently on resisting the urge to rewrite quite some years ago. Often the best response to a convoluted brittle looking system is to just attack it with a series of small refactorings that clearly preserve the current behavior, while eliminating unnecessary confusion and complexity until you can finally see clearly the bigger picture.


'Working Effectively With Legacy Code' by Mike Feathers is an excellent read for tackling systems like this. Basically a series of down-in-the-trenches strategies for getting legacy code under unit tests - even if you're not sure what it's supposed to do - so you can start refactoring with a safety net.


There is an opposite extreme seen on government software efforts...imagine systems that have been around 15,20,25 years. Interfaces frozen from the days of mainframe, millions upon millions of lines of code, written not necessarily by software engineers, but other engineers.

There's a point where it is really really smart to throw away pieces of that system and regenerate them. You produce a lot of cruft of 20 years.


It's just good engineering practice to ask yourself periodically, why are we building this new component? If the answer ever ceases to be convincing, yell, scream and bitch until your team (btw, you should probably spearhead this effort) can convince you otherwise.

That's really the hardest part of working by yourself; it is very hard to strike the right balance between self-criticism and unwavering focus required to create something, be it code or a work of art.


It seems to primarily be an ego issue. This person must of thought that since he/she is so smart any system that isn't understood obviously shouldn't exist.


One of my new favorite interview questions is: When researching how to integrate a feature, you come across a chunk of code that is atrocious, but unrelated to your feature - what do you do? The answer can be very telling.


My first counter question would be "Do I have access to the original coder?" ;)


I almost fit this category, except when I replace a system, I make it backwards compatible, and put [Obsolete("Please use NewClass.Method instead")] on everything...

I wonder if you would hire me...


one person work is not advisable I have come out with challenging projects with just two people coming with good work, we dont need even three at times..


i like to hit the delete key by 'accident' all the time.


> If you're asked this in an interview, you can't respond "no".

I don't see why not! It would save lots of time.

This is a poor question as phrased. If you want to know about the developer's attitude toward reuse versus DIY, then simply ask that. The common usage of the word "invention" today invokes questions about intellectual property, patent rights, copyright et al - topics most developers would likely rather avoid.


Yes,

All programming is inventing.

But not all good programmers see programming as inventing. I'm not sure you wind-up better by weeding out those who don't programming as inventing.


Your second part is spot on, but the first question is not about the "yes/no" but the "why". Of course we invent, but the question is to find to what extent they are willing to go.


Exactly. Software design is a matter of tradeoff. Build vs buy is one of them.


I like Larry Wall's conceptual framework for this.

The chapter of Programming Perl regarding software libraries starts out with a discussion of Laziness, Impatience, and Hubris (http://c2.com/cgi/wiki?LazinessImpatienceHubris ), but more importantly, it also explicitly mentions the ideas of False Laziness, False Impatience, and False Hubris, which each in turn lead software developers from making poor choices as to whether they should build a new software library, reuse an existing library, or just get on with their damn job, and write something easy.

But this essay gets right to the same core here. How is it that we do our jobs as software developers? What is the right way to approach a particular problem? These are hard questions to answer in abstract, but thinking about the nature of invention is a pretty good proxy.


I also like Larry Wall's "Waterbed theory of complexity" (http://en.wikipedia.org/wiki/Waterbed_theory) which fundamentally says complexity needs to be handled at layer or the other in a system.

Which primarily brings the eternally asking the question of "Using the right tools" for the job. Apart from knowing all the CS know-how behind how things work. Practical software is all about knowing if there are existing off the shelf solutions that can be just plugged into take care of that part of the complexity.

I think innovation is more than just code, its also about how you can go about solving a particular business problem in the most practical way.

I think in MIT lecture series of Structure and Interpretation of computer programs, the instructor bring about a very point. Its something like this "A part of understanding and building large complex systems is to know what parts to neglect".

We often test people with knowing about the granular details. But we never see if they know how to build powerful abstractions. Which is basically the core any large complex system.


Thank you, may I quote this?


Please do!


The word "invention" is ambiguous. I invent what I don't know, therefore, the less I know, the more I invent. Incompetence is the mother of invention.

IMHO, creativity is a better word: creativity builds on previous knowledge.

(I'd like to expand on this but after many rewrites of this comment I can't phrase properly what I want to say so I'll just leave it at that.)


I'm a bit confused with what the word invention means in this context. Does it mean truly inventing some new algorithm (not in Knuth) as a normal part of your work. Or does it mean just writing new code from scratch rather thanh using a library?

I've written a lot of code in my career (and as a hobby), but I doubt that I've truly invented something new.


Start a blog and write it out!


Thank you Reginald. You always make me think, more reliably than any other writer about software. You pose interesting questions and have interesting viewpoints and discussion related to those questions. I hope you feel proud about this ability, because you should.

I also appreciate that you have chosen to publish your writing more in a blog format just like on http://weblog.raganwald.com instead of the GitHub experiment, I never really got into reading your stuff there.

As for the question posed, I believe I'm biased towards invention. I would prefer to work in a research department in a company or in a small company that have a business idea (partly) based on research. I hope I'm wise enough to avoid NIH, that is not really inventing anyway, so it's not as much fun as real inventing. (Working in a university seems to come with too much bureaucracy for my taste, but I do like the teaching part.)


That is a pretty cool question. Aside from ferreting out the mentality of the candidate or team (like are you bio-sciences and need to invent, or are you a CRM software maker and have NIH?), it probably tells a lot about the kinds of problem you're dealing with.

It turns out that I don't invent anything. I discover things that I never realized and perhaps nobody else has realized. Things like commonalities in seemingly different problems, generalized approaches to solving those problems, and other things that are intrinsic to the domain but not necessarily apparent. This is distinct from creating something new in that domain, and I think it's important to recognize that.

update: based on this, I'm going to start asking "Have you ever discovered something?" It really doesn't matter if it's original, but I want to work with the kinds of people who are capable of making discoveries for themselves.


The problem with this is that its just too damn ambiguous. What does "discover" mean in the context of software development? You have your own idea (which is a good one), but communicating that to a candidate so you're on the same page might take more time than its worth.


It has nothing specifically to do with software development, but toward that, I remember discovering many things. I discovered that I could keep track of an arbitrary sequence of dynamically created objects, but I didn't invent linked lists. I also discovered that I could sort things without comparing each item to every other item, and that it was "obviously" more efficient, but I didn't invent merge sort or Big O.

If I'm talking to a razorblade salesman who figured that he can make recurring sales of razorblades when gives away handle to hold it with, I don't conclude that he invented the loss leader. I think it's fascinating to have arrived there not by way of rote.

Surely you've made an independent discovery in whatever it was you were interested in at one time or another...

This is just editorial now, and it's deviating from OP's concept. I find that I like to work with people that have strong ties to their crafts, whatever they are, and those people tend to have made discoveries, not necessarily inventions.

Back to the point: really, how many individuals can say that he truly invented something? Great question, but "yes" to that would raise a flag for me.


The question as written is highly imperfect. I’m very ok with the idea that perhaps one asks a series of questions getting atthe underlying ideas even if the words you use would differ from mine, or if the questions in one interview might differ from the questions in another.


I think it's inspiring. Thanks for getting my wheels turning.


Most of my work in the last 8 years or so involves 'glue' or 'connections'. That is take two (or more) boxes and hook them together into a pipeline. Not sure if that qualifies one way or the other. The work certainly didn't exist before but I'm not entirely sure I'd call it 'invention'. I suppose in the interview suggested, I'd probably answer yes and then go on to describe as much as my NDAs allow...


Yeah, the language is a little pretentious but I believe that's the sort of invention they're looking for


No, I don't think so. I don't think the question presumes that inventing is a good thing and not inventing is a bad thing. In fact, here, you would probably say that the current work does not involve inventing things, but rather putting existing things together. That's supposed to be a valid answer, as well, and a useful one.


What sort of invention is NOT putting existing things together? In fact, to me that sounds like as good a definition of "invention" as any.


Invention vs re-use. Unless the candidate is willing to take an honest, logical approach to this decision (involving defendable reasoning), I'd be wary.

Is it a solved problem? No? Invent it.

Is the solution available to you within your constraints? No? Make your own implementation (unless there's a way to acceptably compromise in the design).

Is the solution cost-effective to use (performance, ease-of-use, bugginess, support, etc)? No? Make a better implementation.

Otherwise just re-use an existing solution.


  Is it a solved problem? No? Invent it.
Something to consider: Sometimes we can change the rules. If given requirements A, B, and C, and we discover that “A” is not a solved probloem, we could go ahead and invent a solution. Then again, perhaps we can push back and ask if some lesser requirement A’ (which is a solved problem) is sufficient for success.

The converse is possible as well. Given requirements X, Y, and Z, all of which are solved problems, sometimes we can raise our hands and say “Will we really be successful implementing another Me-Too thingummy? If we take a chance and try to add feature W—which is not a solved problem—we will have a competitive advantage.”

I agree with your basic premise, but want to point out that given a certain bias, we can sometimes fark around with the requirements to suit ourselves. So a candidate in an interview could easily convince you that he had to invent a way to synchronize documents while supporting offline editing, but aother candidate in the same situation might have avoided the requirement necessitating invention in the first place. Or the reverse!


> please describe the three most recent things you have invented

The "most recent" qualifier makes this a short answer, which would be:

Of the last three of my inventions, two are trade secrets and the third has not completed the patent application process. I am not able to discuss any of these. Would you rather discuss some of the patents I hold that are public instead? While you are considering I would like to know what your company's exact policy is regarding the projects and things I will be inventing outside work hours using my own equipment. Obviously the policy will have a major impact on whether I decide to consider accepting an offer to work here.


Why would you be so combative? Wouldn't you grant the interviewer the benefit of the doubt and describe the most recent three things you can talk about? Is the question somehow offensive?


There's nothing at all combative in what I said. If you see it as such, the problem is with the way you relate to people.

If someone asks me today specifically for the most recent three things I have invented, I am not going to lie in my answer. I am going to explain why I can not disclose any of those three and ask if they would rather hear about ones I can disclose. That you see this response, which is correct, true and factual, as "combative" shows that you have a problem.


I don't want to be an ass, please take this as friendly advice. You are obviously smart and good at what you do, but I really feel you are not coming across as well as you think you are. Your answer was quite combative, and I can illustrate how. Obviously it was terse, but I assume that was merely for illustration and not how you would actually speak.

Firstly, your first answer is a direct parry to the question. Whilst factual, it doesn't assume good faith of the interviewer, that they would be happy to hear about three recent things that you can talk about. I think you are on the wrong side of the line between the principle of quality and the principle of quantity -- you mention it would be lying not to talk about the literal three most recent, but I don't think most people would interpret it that way.

You then make what could easily be interpreted as a boast in relation to the multiple patents you hold. This is not a directly aggressive statement, but it is an offensive move in the status game you are playing with the interviewer. I wouldn't say it is the wrong thing to say; but it might be the wrong time to say it.

You then riposte with a reasonable question, but given you just slammed their question and asked them to clarify, it is unfortunate to then ask another question, basically forcing them to decide whether to mollify you or continue their own questioning.

Finally, you make another powerful status signalling move. Think of it this way -- if the people are impressed by these signals, they want to hire you already so why are you even having an interview? Therefore, chances are this interview is for someone else's benefit (HR or management) and neither of those groups will respond well to your attempt to take high status.

It's not a bad answer, it could certainly work well in some circumstances, obviously it could come across differently in actual conversation, but as it appeared it is combative.

I recommend reading http://en.wikipedia.org/wiki/Cooperative_principle and http://en.wikipedia.org/wiki/Gricean_maxims.


No, it was combative, regardless how true and factual. True and factual != polite and neutral. (Do you let every overweight person you see, know that they are fat? It's true and factual, so if they take issue with it, it's because they have a problem!?).

In fact, your response to the parent was fairly combative as well. Instead of pointing out a problem in the parents point you have instead tried to find fault in the parents character.


It reminds me of Zed's excellent distinction between invention and implementation: http://zedshaw.com/essays/c2i2_hypothesis.html


This is definitely a great question, although llimllib is spot-on about a needed neutralizing of the question.

I think it's most useful when you can: a)present both options in a positive light ("I am a github/mashable-whisperer and can string libraries and API's together at ridiculous speed!" for instance) and b) it's clear that there is no wrong answer.

I'm not saying there shouldn't be a wrong answer for your organization, but I am saying that the question will become less useful if there is, because your candidate will be tempted to fudge.


Man, just reading that question makes me a little giddy. I'd be pretty excited to hear that in an interview.

Also, a punny title which is actually a pun on the subject of the article? I think I might be in love.


I think that a throttled balancing act between total-invention and mild-integration is probably the best outlook to take at 90% of issues right from the start. There are exceptions to all rules, and the interviewer will have a better grasp on where in this spectrum they need the candidate to fall, but this "describe something you've built/hacked" seems to be a fairly common question that shouldn't come as a surprise to anyone interviewing.


Once you start calling anything an invention, the next logical step is to allow to patent it. OK it's too late for the US, but we still have some hope in Europe, so unless you are writing stuffs using concepts and algorithms never used before, and not even appearing in TAOCP, which i highly doubt, stop calling your shit an invention. Also don't do it because that is very probably insulting to Knuth, Dijkstra, et al.


Once you start calling anything an invention, the next logical step is to allow to patent it.

“Invention” and “Patent-worthy Discovery” are not synonymous:

  An invention is a better or more effective composition,
  device, or process. An invention may be derived from a
  pre-existing model or idea, or it could be independently
  conceived in which case it may be a radical breakthrough...

  An invention that is novel and not obvious to others
  skilled in the same field may be able to obtain the legal
  protection of a patent.
https://secure.wikimedia.org/wikipedia/en/wiki/Invention

It is possible and normal to invent things that are not novel, or may be obvious to others skilled in the same field. It’s still invention, it just isn’t “Big I” Invention, it’s a more modest creative process.

Think of it this way: We have the expression “re-inventing the wheel.” If it wasn’t possible to invent things that already exist, it wouldn’t be possible to “re-invent” anything, would it?


Once upon a time, in a kingdom not far from here, a king summoned two of his advisors for a test. He showed them both a shiny metal box with two slots in the top, a control knob, and a lever. "What do you think this is?"

One advisor, an engineer, answered first. "It is a toaster," he said. The king asked, "How would you design an embedded computer for it?" The engineer replied, "Using a four-bit microcontroller, I would write a simple program that reads the darkness knob and quantizes its position to one of 16 shades of darkness, from snow white to coal black. The program would use that darkness level as the index to a 16-element table of initial timer values. Then it would turn on the heating elements and start the timer with the initial value selected from the table. At the end of the time delay, it would turn off the heat and pop up the toast. Come back next week, and I'll show you a working prototype."

The second advisor, a computer scientist, immediately recognized the danger of such short-sighted thinking. He said, "Toasters don't just turn bread into toast, they are also used to warm frozen waffles. What you see before you is really a breakfast food cooker. As the subjects of your kingdom become more sophisticated, they will demand more capabilities. They will need a breakfast food cooker that can also cook sausage, fry bacon, and make scrambled eggs. A toaster that only makes toast will soon be obsolete. If we don't look to the future, we will have to completely redesign the toaster in just a few years."

"With this in mind, we can formulate a more intelligent solution to the problem. First, create a class of breakfast foods. Specialize this class into subclasses: grains, pork, and poultry. The specialization process should be repeated with grains divided into toast, muffins, pancakes, and waffles; pork divided into sausage, links, and bacon; and poultry divided into scrambled eggs, hard- boiled eggs, poached eggs, fried eggs, and various omelet classes."

"The ham and cheese omelet class is worth special attention because it must inherit characteristics from the pork, dairy, and poultry classes. Thus, we see that the problem cannot be properly solved without multiple inheritance. At run time, the program must create the proper object and send a message to the object that says, 'Cook yourself.' The semantics of this message depend, of course, on the kind of object, so they have a different meaning to a piece of toast than to scrambled eggs."

"Reviewing the process so far, we see that the analysis phase has revealed that the primary requirement is to cook any kind of breakfast food. In the design phase, we have discovered some derived requirements. Specifically, we need an object-oriented language with multiple inheritance. Of course, users don't want the eggs to get cold while the bacon is frying, so concurrent processing is required, too."

"We must not forget the user interface. The lever that lowers the food lacks versatility, and the darkness knob is confusing. Users won't buy the product unless it has a user-friendly, graphical interface. When the breakfast cooker is plugged in, users should see a cowboy boot on the screen. Users click on it, and the message 'Booting UNIX v.8.3' appears on the screen. (UNIX 8.3 should be out by the time the product gets to the market.) Users can pull down a menu and click on the foods they want to cook."

"Having made the wise decision of specifying the software first in the design phase, all that remains is to pick an adequate hardware platform for the implementation phase. An Intel 80386 with 8MB of memory, a 30MB hard disk, and a VGA monitor should be sufficient. If you select a multitasking, object oriented language that supports multiple inheritance and has a built-in GUI, writing the program will be a snap. (Imagine the difficulty we would have had if we had foolishly allowed a hardware-first design strategy to lock us into a four-bit microcontroller!)."

The king wisely had the computer scientist beheaded, and they all lived happily ever after.

---

http://www.tik.ee.ethz.ch/~lubichh/extdoc/jokes/cs-ee.html


(Shrug) I'd use a knob, a bimetallic strip, and a pair of tungsten contacts, but I'm weird that way.


The problem with that approach is that tuning it is hard, i.e. it's rather harder to ensure that the knob somewhat linearly adjust from "not toasted" to "black" and the useable control range isn't just a tiny part at one end of the full range.

Luckily changing software doesn't (usually) require a solder iron.


I'm not sure I buy "invention", the creation of something new.

I prefer to ask questions that determine whether people are able to mine their own experience and apply solutions from one domain to another entirely different domain.

It seems to me, that most invention is finding novel approaches to existing problems, and that most problems already have solutions that just need to be discovered and matched up with their problem. The harder part is that it is usually the case that the solution is in a different problem domain than the problem at hand.

The most inventive people I know are the ones who are open to learning everything, who consume all knowledge and are always listening. These people store solutions in a problem-domain invariant way, such that when they encounter a problem they already know the solution even though it's non-trivial for everyone else.


There's probably nothing truly new in the context as 'new' in the question needs qualification. Following on does invent mean, bring to the table [as they've done something similar elsewhere] or something innovative. Some questions might sound great, but they have to placed within context and not just thought up as being clever, but they actually have a YARDSTICK to measure the candidate.

I'm not a programmer, I just do mark-up but I do like the question as it's a development of personal and business aspects of the candidate.

With interview it will show:

Does the candidate show initiative, problem solving and application. Finally, it ought to involve an answer of business acumen: Does spending 6 months developing it vs. returns of a version update. This ought to show a right fit and if the candidate can 'fit' to the business and process aims of the company.


This question is a great yardstick. If you are at a startup and want to swing for the fences, this question makes very clear your intentions.


This is a great question that requires an answer that is both philosophically and technologically deep

Most articles I've read with a headline like this, the question posed involves an impractical show of technical prowess


Here's a metaphor about a special case where invention is justified.

Suppose you have no cell phone and you need to get to your mad science lab before your apprentice does so that you can lock up the monster you created the night before — otherwise it will eat him. You spot him ten cars ahead of you on the two-lane highway, but he doesn't notice you.

It is 100% guaranteed that he will arrive at the lab before you if you stay behind him on the highway. Then the monster will eat him.

There's a shortcut to the mad science lab through the back roads. Usually the highway is faster, but every once in a while the highway has a traffic jam and the back roads don't. If you take the back roads, you have a 30% chance of reaching the lab before your apprentice.

30% is better than 0%, so that's what you should do. Even though the back roads are probably slower, they're your only possible way to win the race.

In a business context, you may find yourself competing against an incumbent strictly on the basis of their core competency. If you have no way out of that situation, one possible strategy is to pursue an angle of development that is simply different from theirs — even if your best knowledge suggests that their angle is probably the best one. Your only hope is that they run into an unexpected traffic jam on the road they're taking, and that you're on a different road.

My reading is that this is basically the story of AMD64. As I understand it, mainstream opinion in the late 90s and early 2000s was that we were going to have to import some version of VLIW's explicit ILP into CPU design in order to keep getting single-threaded performance improvements, so that was what Intel went with for their 64-bit CPU architecture. AMD announced their alternative path, hobbling themselves with backward compatibility, in 1999.

They got lucky: Intel's "Itanium" turned out to be an Itanic; it hit a performance iceberg and sank, and since 1999, AMD64 has become the mainstream CPU architecture, displacing not only i386, but also PowerPC, SPARC, Alpha, MIPS (except in the very low-end), PA-RISC, POWER, System 360, AS/400, and half a dozen vector supercomputer architectures. (Alpha, PA-RISC, and the AS/400 aren't even on the market any more. SPARC, POWER, System 360, and vector supercomputers are still available, but most of their uses have been replaced with AMD64, running Linux.)


>Alpha, PA-RISC, and the AS/400 aren't even on the market any more

Strictly speaking it's not correct: AS/400 was rebranded, but you still can buy hardware with OS/400 running on it. Also, it never was replaced by AMD64 - it's using CPU-independent byte-code and happily migrated over different CPU architectures few times.


You're right — I misread http://en.wikipedia.org/wiki/AS/400 to be saying that AS/400 was killed in 2008, but the replacement hardware still runs OS/400. Thank you!

> In April 2008, IBM announced its integration with the System p platform. The unified product line is called IBM Power Systems and features support for the IBM i (previously known as i5/OS or OS/400), AIX and Linux operating systems. Power4 or older hardware ran OS/400 exclusively.


That blog post is less about interviewing than the title suggests. It's an interesting dichotomy.


One of the reasons that discussions about interview questions/techniques generate such heated discussions is because they cut right to the core of our self-image and mercilessly strip naked our views about software development.


On a related note, job interviews (some times) have a special quality that you rarely meet in other situations. I think for those exact reasons.

Of course another explanation could be that I'm narcissistic and it's the perfect setting to talk about my self. But then I equally enjoy interviewing candidates, so perhaps not.


Good idea. You should try using fewer words to describe it though.


Here is a blog post I wrote in seventeen paragraphs over lunch. Had I more time, I would have written it in seven.


Does anyone know the answer to the problem posed in the XKCD comic? http://xkcd.com/356/




While certainly a nicely written and interesting post, it's not a solution, it's a rough numeric approximation.


DANGER - BAD QUESTION - asking this question is asking a candidate (currently employed or otherwise) to violate the terms of the Confidentiality Agreement with their previous employer. Asking prospective employer this question is doing the same thing.

THE CORRECT ANSWER TO THIS QUESTION - "Answering this question necessitates that I violate my duty of confidentiality.


I really think you’re getting a little over-enthusiastic here, Kenneth. Not everyobody has signed a rigorous confidentiality agreement. Not all such agreements prevent someone from discussing technical inventions in general terms. And if someone is prevented from answering, well, they will say so and the interviewer can decide what to do next.

If this is a “bad question,” are there any good questions?


Appreciate your reply. This question likely places candidates in a difficult situation, especially younger candidates who are excited about the opportunity, or those needing the job.

If the interviewer plans on asking this question, they ought to have conducted a patent search prior to the interview.

If patents or applications are found - ask the candidate about the problem that was solved by the claimed invention. Ask if the candidate was the one who noted the problem, and ask further questions based upon the answer.

If no patents/published applications naming the candidate are found, don't ask the question.

If the interviewer doesn't want to take the 5 minutes to search, or HR doesn't provide these materials to interviewers as a routine part of the interviewing process then they ought to ask "Are you listed as an inventor on any issued patents or published patent applications?" and then they ought to suggest that in the future HR conduct a quick patent and published application search and distribute the results to those interviewing a candidate.

A candidate ought to conduct a patent search prior to interviewing and use that information to ask a variety of questions and point out noted intersections between tech development and the candidates knowledge and experience.


If no patents/published applications naming the candidate are found, don't ask the question.

We can’t possibly be conducting the same kinds of interviews with the same kinds of candidates. Or possibly you are talking a very narrow view of the word “invention.” Or you work in a phenomenally litigious sector.

For my purposes, “Describe a technical problem you encountered at XYZCorp and how you solved it” is a standard interviewing question. I suspect that if you don’t allow the question I posed in this blog post, you wouldn’t allow this one either.


search for patents and published applications at:

http://appft1.uspto.gov/netahtml/PTO/search-adv.html http://patft.uspto.gov/netahtml/PTO/search-adv.htm

the query to use is:

in/lastname-firstname

If you don't find any references, then asking the candidate to describe a technical problem and means by which they solved it is less likely to be received as a request for confidential information.

Hope you find the above links and search query useful!

Best.


A great follow up question, or daughter question, would be: "What tools do you think best contribute to the process of invention?"


really? what kind of answer were you expecting and what would it tell you?


Personally, I'd like to hear something along the lines of "tools that best fit the team and the problem." Languages come and go but algorithms are forever.


That's a tough one, but I'd still rather field that question than the one that I had to answer when I interviewed at Dell in the early 90s: "What will happen to your current employer (a ~12-person company) when you leave?"


I don't 'get it'. Sounds like an easy question and not "The Mother of All Interview Questions".

But, for me, part of the answer is that the "process" has involved solving practical problems only in part with software, and some of the "invention" has been not really in the software.

Do the following examples count?

(1) A prof wrote a package for statistics for students and in the testing found that one of the operations was too slow and another one gave numerically poor results.

For the slow operation, looking, there were two loops, each that ran in time proportional to n^2. Using the existing storage in a tricky way, I converted the loops to (n)ln(n) which was then plenty fast.

For the bad numerical result, I used some orthogonal polynomials instead of statistics normal equations, and that solved the numerical accuracy problem.

(2) At a growing company, the Board wanted some revenue projections. There wasn't much for ideas, so I got involved. We knew the current revenue. We knew the maximum long term revenue because of the capacity we had in mind. Revenue growth was to be 'viral'. So, let t denote time in days with t = 0 the current time. Let the revenue at time t be y(t). So, y(0) is the current revenue. Let b be the maximum revenue.

From virality, the growth rate in revenue should be proportional to (i) the revenue from current customers y(t) and (ii) the revenue from the customers not yet served (b - y(t)).

The growth rate in revenue is dy(t)/dt = y'(t), that is, the calculus first derivative of y(t). So for some constant k,

     y'(t) = k y(t) (b - y(t))
Solve for y(t) in closed form, select a reasonable k, and done.

(3) A company had a cute marketing opportunity and wanted to allocate marketing resources the best way. They formulated the problem as a 0-1 integer linear program (ILP) maximization problem with, for a first test case, 40,000 constraints and 600,000 variables. Seeing that no ILP package would take that problem as it was, they tried a genetic heuristic, ran for days, and quit.

I looked at the problem, saw an approach via non-linear duality theory and Lagrange multipliers. So, the dual problem was to minimize a convex function approximated by some hyperplanes.

I wrote the software, and after 500 hyperplanes had a good approximation to the dual and a feasible solution to the original problem within 0.025% of the optimal answer.

(4) Another company had another cute marketing problem and wanted to allocate resources to maximize results. The problem was integer linear programming again, but I saw that it was also a problem in least cost network flows on a network with integers for arc capacities. So, use the network simplex algorithm and get an optimal answer quickly with the integer constraints honored for free.

(5) A software project was to analyze some data collected at sea. I looked at the specification for estimating the power spectra and saw some problems: For the low frequency resolution they wanted, they needed too much data. To illustrate, I wrote some software to generate a sample path of a second order stochastic process with a known power spectrum, accumulate the sample power spectrum, and showed how slowly the sample power spectrum converged to the spectrum of the process. This work surprised and pleased the customer, and we got the competitive software contract.

(6) In a project, needed to look at a few million numbers and end up with the, say, 100 largest. So, go to classic heap sort, and start with an ascending heap of 100 locations that has the 100 largest so far and with the smallest at the root of the implicit tree of the heap. So, given the next one of the 100 million numbers, one comparison with that root value says if that next number is among the 100 largest so far; if so, then replace the root value with the next value and 'sift' to rebuild the heap.

The worst case would be given the 100 million numbers in ascending order in which case the computational time complexity should be proportional to (n)ln(n) for n = 100 million. Otherwise for large n the execution time should be only slightly slower than proportional to n (exercise: for n independent, identically distributed numbers with a distribution absolutely continuous with respect to Lebesgue measure so that the probability of ties is zero, find the actual expected running time up to a constant of proportionality).

(7) A server reports numerical data on each of 10 variables at 20 a second. You have data from three months when, from that data and more evidence, the server seemed to be 'healthy'.

Your mission, should you decide to accept it, is to implement real time monitoring for this server that uses the data from the three months and also real time data. Your solution will be a statistical hypothesis test with known, adjustable Type I error (false alarm rate). Your work will necessarily be the world's first class of statistical hypothesis tests that are both multi-variate and distribution-free. You need to show that your test is not 'trivial', and for that consider the classic S. Ulam result on 'tightness'. You should also show that in a powerful sense, asymptotically the test is best possible in a sense similar to the classic Neyman-Pearson result.

Also, design and implement a fast algorithm for the computations.

Do such examples count?


You lost me at (6):

Shouldn't it be proportional to O(n log 100) ~ 0(n) aka linear time?


Yup! I typed too fast! You are correct. I was thinking the right thing but typing the wrong thing! I'm too used to typine (n)ln(n)!. So, sure, worst case, n times have to do a heap 'sift' which is time proportional to ln(100) as you said.

Short answer: I blew it!

But for the exercise, that is, when there are no ties among the n numbers and all permutations are equally probable, for 100 < m < n, the probability that number m is among the 100 largest so far and, thus, causes a heap 'sift', seems to be 100/m. So, the expected work on number m is proportional to just (m - 100)/m + ln(100) (100/m), first cut, wild guess, don't hold me to it! So, sum this on m and get the expected work (computational time complexity) up to a constant of proportionality. Maybe! That is, so far, first cut, the exercise looks simple! When do the sum, I smell a ln(n) term!


Those sound like ideal examples to me!




Consider applying for YC's first-ever Fall batch! Applications are open till Aug 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: