find median@2 sorted arrays(same len) #Trexquant

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


e^pi vs pi^e

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.

find the line passing the most points #solved

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

2 overlapping rectangles


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

PDE solver – phrasebook

[[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.

Fwd: comparing exp( (a+b)/2 ) vs 0.5 exp(a) + 0.5 exp(b)

How about Jensen’s inequality?

Hi Richard (Qu Miao),

brain teaser — compare
A = exp( (a+b)/2 )    vs
B = 0.5 exp(a) + 0.5 exp(b)
Here’s my solution. See if it is correct.
Denote f = 2B/A. So f = exp(.5a  – .5b)  +  exp(.5b  – .5a) ….. symmetry
Denote x = .5a – .5b , so f(x) = exp(x) + exp(-x).
Now f(x) curve goes to infinity on both sides. So f(x) has minimum value of 2 occurring at x=0.
That means 2B/A has a minimum value of 2. In other words, B >= A