The Mother of All Interview Questions

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?

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?

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?

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.

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.