## Friday, January 18, 2013

### A Google interview

Question:
There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z).

Now we cannot get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?

Say we have a set, H, which has these 3-tuple data.

Value(a) = 2x3y5z
if Value(H[m]) > Value(H[n]):
H[m] > H(n)

Test:
Assume h1 = (x1,y1,z1) = (0,0,0)
Value(h1) = 20 * 30 * 50 = 1*1*1 = 1

(x2,y2,z2) = (-1,-1,-1)
Value(h2) = 2-1* 3-1* 5-1 = 0.5 * 0.33 * 0.2, a value greater than 0 but less than 1

From the above, Value(h1) > Value(h2), so according to the statement above h1 should be > h2, or (0,0,0) > (-1,-1,-1).

One quick guess is that if z1 > z2,  the Value(x1,y1,z1) would be greater than Value(x2,y2,z2), for z=[some number to infinite], because the 5^z would be more significant than the contribution of 2^x*3^y alone.