This "coding" question is really math problem. Once you work out the math techniques, the coding is rather simple.
My own idea — find the median of X and median of Y. If med(X) < med(Y) then discard the lower portion of X and higher portion of Y (two portions of equal size). Then repeat.
Why can’t the final "winner"be somewhere among the lower portion of X? Because the higher portion of X and higher portion Y already constitute half the population, and all of them are higher.
Definition of lower portion —
* all lower items up to but not including med(X) If len(X) is odd
* exactly the lower half of X if len(X) is even
Hi Prof Lee,
Thanks for the lunch (including the advice part). I came up with some ideas about this brain teaser —
Q: which is bigger e^pi vs pi^e
One solution I can think of is, suppose e has a value close to 2 and pi is much larger.
Suppose e = 2 and pi = 10. Clearly e^pi wins.
Another way is, define 2 functions
f1(x) = 2.718281828^x and find the growth rate when x is slightly above e. This growth rate is e^x,
f2(x) = x^2.718281828 and find the growth rate when x is slightly above e. This grow rate is e/x * x^e, which is smaller, since x is slightly bigger than e.
Therefore, f1 grows faster than f2, over the range of (e , 3.15). Therefore e^pi wins.
Q: Given N points with positive integer coordinates, find the straight line passing through the most points
A: For each of (N*N-N)/2 pairs of points, compute a Line object identified by 2 numbers:
* a slope S = (y2 – y1)/(x2 – x1)
* intercept on y-axis.
So these 2 numbers can be computed easily from any pair.
Save each Line object as key in a hashmap. When a pair gives a Line that’s already seen, increment its count.
Intercept formula y_inter(int, int, int, int) can be assumed to exit. Writing this function isn’t relevant to a coding interview:
Suppose this value is y3, so the incept point is (0,y3), so
(y3-y1)/(0-x1) = S, so y3 = y1 – S x1
Q: You have a rectangle a and b. Determine if the two rectangles overlap. That is at least some part of either rectangle should be within the other.
I will assume the coordinates are given.
%%A: find both centers.
– case 1: identify box A’s corner that’s closes to B’s center. Check if this corner is inside B.
– case 2: if they lie on one vertical line, then only the bottom border (of upper box) vs top border (of lower box) matters.
I have seen a few PDE/SDE combos. There’s a pattern among them.
The SDE tends to describe a process as a signal-noise description. It is actually rather precise, as precise as it gets — you can compute the exact probability of the “particle” falling into a range at a given time t.
However, the SDE won’t enable us to compute today’s price as an equation can, such as “sin(x) + log(x) – sqrt(x) = pi”. Reason? The dW term is an obstacle. Therefore, we need to somehow get rid of the dW term. We end up with a differential equation, often a PDE. If there are sufficient boundary conditions, we could solve the equation to get a precise time-0 price
[[Numerical methods and optimization in finance]] has simple examples
of a PDE numerical solver. This book is more in-depth than [[basic
I think the Daniel Duffy book also covers Finite Difference method
Brute-force — often there's no other solution (like mathematician
tackling a proof) to a PDE. Numerical solution is kinda versatile.