Actually, this question is asked by D.E Shaw Research.

Design a data structure to store 3-dimension points in a space. This structure needs to be efficient for retrieve, deletion and insertion.

Note: The space is really large, with billions of points in it, while it has a certain size.

**My solution is:**

- Divide the space into cubes
- Store the cubes in an array
- Store points in a LinkedList in each cube

**The following questions are:**

- What is the proper number and size of the cube?
- How to retrieve the cube? (hash function, use the size of the space)
- Given a central point with its (x,y,z) coordinate, how to retrieve all the points within a sphere of radius r. (need some calculations)