Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
1) compute GCD for every 2 adjacent point, then we need a matrix with size N*N/2
2) compute GCD for every 4 adjacent point, then we need a matrix with size N*N/4
....
the total space N^2(1/2+1/4+....) <= n^2
each step we can reuse the previous result. so the time complexity is also the same n^2
To compute GCD for every submatrix, first we divide the big matrix into the small submatrixs that we prepossessed. And then we compute the GCD of them.
This is probably the simplest correct algorithm based on GCD properties.
From Wikipedia: "The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers."
Well, but isn't that still O(N^2)? It may be N/2 ^ 2 if you divide into grids of 2x2, but that's still O(N^2).
I'm thinking about running sums (here, products), somehow.
The query rectangle has to completely enclose any pre-computed GCD squares for it to use it - all I can think of is to make some constant number of levels, top-down rather than bottom-up, as bottom up makes it dependent on N - just pick a number - and make a quadtree of pre-computed GCD squares down to that level. Not the answer, I'm sure.
Nah, top-down doesn't make any difference, any regular grid of cells will be N^2 one way or another.
Lawrence, in your solution, let's say n = 10, which element remembers GCD for
A[i][4], A[i][5], A[i][6], A[i][7]
? To cover all the combinations within i, shouldn't we keep n * (n - 1) / 2 values per each row? Also, calculating multiple GCD values on runtime seems not easy...
Here is how I thought. My problem is it requires a little more than n^2, but not in n-polynomial way:
Prep:
1. Create an array of n^2, call it
PrimesOnly
.
PrimesOnly[i][j]
will have multiplied value of prime numbers for the original array
A[i][j]
. For example, A's value 9 (3^2) will be stored as PrimesOnly value 3. 16 (2^4) will be 2. 24(2^3 * 3) will be 6 (2*3).
2. Create a dictionary<int, int[]>
PrimeList
, to keep 2 => {2}, 3 => {3}, 6 => {2, 3}, etc. (Again, this is a small array but I am violating the rule here.)
Query:
1. For the given range values, get PrimesOnly values, and then get the list of PrimeList value arrays.
2. Get common prime set among those arrays found in step #1.
If your A values were {24, 36}, PrimeOnly will be {6, 6} and common prime set will be {2, 3}.
If your A values were {16, 24, 36}, common prime set should be {2} only.
3. For each elements in common prime set found in step #2, get the power number by dividing each A values in the range, starting from ^1, ^2, ^3, etc. If we get remainder on any of them, we have identified maximum value for the element.
4. Multiply all the elements and power numbers identified in step #3.
i think you can try segment tree containing segment tree as data . the first representing squares on lets say X axis the internal rectangle on the y axis . giving you time complexity of O(long(n) ^3) , as GCD takes O(log(n)) .
It can also be intuitively created by 4 levels of arrays of arrays too represent without a complex data , as all interval here are simple power of 2 and multiplication , so first array is for rectangular with the index as the exponent , the second level index is the constant multiplier .
the third level array will then represent the other axes upto 4 level. easily created.
I'll try to present a Segment Tree based approach, which takes O(n^2) time and space to pre-process, and answers each query in O(r * log(c)) time. r and c are the number of rows and columns in the query.
- Lawrence December 18, 2013For each row A[i] in the matrix A, we build a segment tree, such that each node remembers GCD(A[i][a..b]) for some range [a,b). The root node remembers GCD(A[i][0..n]), its children remembers GCD(A[i][0..n/2]) and GCD(A[i][n/2..n]), and so on. The tree allows us to query GCD(A[i][a..b]) in O(log n) time for some row i and an arbitrary range [a,b). The memory complexity of each segment tree is O(n), which gives us O(n^2) total memory complexity.
To answer a query, we just query GCD(A[y1][x1..x2]), GCD(A[y1+1][x1..x2]), ... GCD(A[y2][x1..x2]) and take a GCD on all these numbers.
We can further improve the query time to O(logn * logn) by building one 2-d segment tree for the entire matrix, but I doubt whether it's feasible to implement a 2-d segment tree within the timespan of an interview.