Adobe Interview: what data structure is used to store thousands of points (x, y) to perform certain operations faster

Question

We have to store thousands of points (x, y, c) c here for the color of this point. This is mainly due to the pixels on the screen. We must perform operations: given x = i, we must change the color of all points with x = i. Similary, given y = i, we must change the color of all points with y = i.

I suggested a solution to a 2D matrix. Then split the hash table for the x and y coordinates. Then he asked me even better. What are the best combinations of data structures we can use?

Answer 1

You do not need a 2D array and separate hash tables. If your data is dense, representing all (or most) of the rectangular area, then a 2D array is enough. You can ask as a continuation which coordinate is most likely to be used for searching, and then structure the arrays so that the outer coordinate is such that the search in this coordinate is localized in memory, but otherwise you cannot do much better. Conversely, for sparse data, hash tables are the best you can do. (I assume that you haveh the coordinate with an array of point features.) Is there perhaps more information about the nature of the data, or how it is most likely to be used?

Answer 2

If there is no search for one coordinate, you can offer hashing x, y coordinate pairs. Post will offer some hash with a small combination, like hash = ( y << 16 ) ^ x; .

But you want to access your data for a value for x or y. The structure for storing points and effectively performing operations on it is a QTree or Quad Tree point. See here .

Point quad is an adaptation of a binary tree used to represent two-dimensional point data. It shares the characteristics of all quadrants but is a true tree, since the center of the unit is always at a point.

A node of a point quadrant is similar to a node of a binary tree, with the main difference being that it has four pointers (one for each quadrant) instead of two ("left" and "right"), as in a regular binary tree. Also, the key is usually decomposed into two parts, referring to x and y. Therefore, a node contains the following information: 4 Pointers: quad ['NW], quad [' NE], quad ['SW] and quad [' SE]; which, in turn, contains: a key; usually expressed in x, y coordinates; e.g. name

Then you can get a recursive function to query all points in the AABB range. You can adapt this implementation of QueryRange()

 class QuadTree { function queryRange(AABB range) { Array of XY pointsInRange; // Prepare an array of results // Check objects at this quad level for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range)); return pointsInRange; } }