## Walainlord

BAN USERPre-process can be done in O(n^2) time with O(n^2) space.

Query can be done in O(1) time.

Pre-process:

1. Initialize a n by n matrix A with 0;

2. For each rectangle (x y)(x' y'), A[y'][x'] = A[y - 1][x - 1] += 1; A[y - 1][x'] = A[y'][x-1] -= 1;

3. Starting from the upper right corner of the matrix(assuming the matrix is upside down, which coincide with the coordinate), A[i][j] += A[i + 1][j] + A[i][j + 1];

4. Now A contains the corresponding coverage at each location

Query:

for a pixel at (x, y), return A[y][x]

The answer is not correct because there could be pure circles in the array. For example, given an input like 1, 2, 2, 3. The algorithm will give 3 instead of 2.

- Walainlord December 12, 2012int duplicate(int A[], int n)

{

for(int i = 0; i < n; i++)

{

while(A[i] - i != 1)

{

if(A[i] == A[A[i] - 1])

return A[i];

else

swap(A[i], A[A[i] - 1]);

}

}

}

distance traveled: D/vb, where D is the initial distance and vb is the speed of the bird;

Time U turned: infinite. Suppose finite, at the last U turn, suppose the trains are d apart, in d/(vt + vb) time, the bird run into the other train, however the trains are still d(1 - 2vt/(vt + vb))>0 apart, which means there is another U turn. contradiction

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

This could be implemented using a hash table and a RB tree. In C++ STL, it would be a hash_map and map

- Walainlord December 28, 20121. lookup, just lookup the hash_map

2. range lookup: find the key1 in map, iterate the map to key2, and while iterating, output all the values from hash_map. O(n), where n is the # of keys between key 1 and 2.