I had google phone screen interview few days back. This was the question :
Given a plane with empty collection , implement function addPoint(point) that adds the point to collection and returns the co-ordinate of the box formed by the points. Implement function removePoint(point) which removes the point from collection and returns the updated co-ordinatres of the box.
e.g. :

addPoint([1,2]) -> return  [[1,2],[1,2]]
addPoint([0,8])  -> return [[0,2] , [1,8]]
removePoint([0,8]) -> return [[1,2]]

explanation : 

addPoint([1,2]) -> return [[1,2],[1,2]] means the only point present in the collection, that itself is the box
addPoint([0,8]) -> return [[0,2] , [1,8]], now collection contains [1,2] & [0,8] so if we make a box along the x and y axis, the other two points will be [0,2] & [1,8]
removePoint([0,8]) -> return [[1,2]] , once we remove[0,8], only [1,2] remains

I implemented using heap but that was not optimal. I was thinking and finally ran out of time. Missed opportunity to be part of my dream company :(