Adobe Interview: What data structure to use for storing thousands of points (x,y) to perform certain operations faster

Question

We have to store thousands of points (x,y,c) c here is for color of that point. Mainly its related to pixels on the screen. We have to perform operations : given x = i, we have to change color of all the points having x = i. Similary, given y = i, we have to change color of all the points having y = i.

I proposed a solution of 2D-matrix. Then Separate Hash table for x and y coordinates. Then he asked me for even better solution. What better combinations of data structures can we use ?

Answer 1

You don't need both a 2D array and separate hashtables. If your data is dense, representing all (or most) of a rectangular region, then a 2D array by itself is sufficient. You could ask as a followup which coordinate is most likely to be used for lookup, and then structure the arrays do that the outer coordinate is that one so that lookup in that coordinate is localized in memory but otherwise you can't do much better. Conversely, for sparse data the hashtables are the best you can do. (I'm assuming you are hashing the coordinate to an array of point objects.) Was there perhaps more information given about the nature of the data or how it is most likely to be used?