Google Interview Question

1. find connected component in 0/1 matrix, color fill algorithm, hash table store every pixel

Interview Answers

Anonymous

Mar 2, 2013

About sampling in a sphere: If in 3(or n) dimension you have a rather complex body and you want a uniform distribution on it get it's bounding rectangle get a uniform distribution on that and when you want to sample the body you sample the rectangle and if it's inside the body you return the point otherwise you resample the rectangle(Also for high dimensional spheres and their bounding n-cubes this can take a long time since the sphere and it's bounding box's ratio is decreasing exponentially by dimension).

Anonymous

Mar 2, 2013

Also for the point cloud question the answer is surprisingly negative aka O(n^2): http://stackoverflow.com/a/4181292/1514476 http://en.wikipedia.org/wiki/3SUM