A disc is completely contained inside a \(2\times 10^9\) by \(2\times 10^9\) square. The disc radius is sufficiently large that is at least \(\frac{10^9}{2}\), and the disc center is always located at integer grid point. Our job is locate the disc center using no more than 300 queries. For each query, the system will return one of three outputs: (i) hit the center, (ii) inside the disc (but not hit the center), and (iii) outside disc. Also note that one can only query integer grid points.
Original problem description can be found here.
We can uniquely determine a circle by any three different points on its boundary; see here on how to code the algorithm elegantly. Given two points that are inside and outside the disc, the segment connecting them must intersect the disc boundary exactly once, and the intersection point can then be found by binary search. (We can maintain the invariant that one end is always inside the disc and the other end is always outside the disc.) Once we identify three different points on the boundary, we can calculate the center although the calculation is not so trivial:
The only problem left is how to find these points that are inside/outside the disc. One easy solution is to find a random point that is inside the disc first. Since the disc is completely contained inside the square, all square corners must not be contained in the disc. We can therefore connect the random point in the disc with any three of the four square corners, form three different intersections. The fact that square corners are far away from each other also makes the intersections well scattered.
Finally, since the disc radius is sufficiently large, we can generally find a grid point contained inside the disc by only a few random guesses. Indeed, the expected number of attempts is no less than \((2 \times 10^9)^2 / [\pi (\frac{10^9}{2})^2] \approx 5.1\).
Since all elements are distinct in the matrix, we can pre-compute the min value per each row and the max value per each column. Then, we scan the matrix one more time and find all the candidates.
Time: O(mn)
Space: O(m + n)
Maintain each prefix increment pointwisely and lazily. Then all operations can be implemented in O(1) time.
Do an in-order traversal to obtain all the elements in BST in sorted order. Then build the balanced tree using Divide-and-Conquer.
Time: O(n)
Space: O(n)
Enumerate the engineer that has the minimum efficiency in the team. When each engineer is fixed, find those (at most) k engineers that have top speed. This algorithm can be implemented efficiently by (i) a pre-sorting on efficiency in decreasing order and (ii) using a heap or BST to maintain top-k speed.
Time: O(n log n + n log k) = O(n log n)
Space: O(k + sorting). When using (say) heap-sort, the complexity becomes O(k).
When counting in aggregation, you are probably familiar with both COUNT()
and COUNT_IF()
,
where the latter counts after a selective filter.
However, when it comes to other aggregation functions, there are simply no the corresponding _IF
versions.
One could argue that we could put the filter in WHERE
,
but this will not scale if we want to do multiple selective aggregations.
Consider the following example.
It would be really convenient to have these _IF
aggregation variants,
and otherwise one has to do each selective aggregation separately and finally join them together.
SELECT
key,
SUM_IF(val1, condition1) AS sum1,
SUM_IF(val1, condition2) AS sum2,
ARRAY_AGG_IF(val2, condition3) AS vals,
...
FROM
table
GROUP BY
1
We can now write the following query in Presto for selective aggregations.
SELECT
key,
AGG1(x) FILTER (WHERE condition1),
AGG2(y) FILTER (WHERE condition2),
AGG3(z) FILTER (WHERE condition3),
...
FROM
table
GROUP BY
1
I surfaced this cool feature from this request on Presto’s Github page.
As stated by the last comment,
Is this feature documented anywhere? I only found it because https://stackoverflow.com/questions/55504820/presto-filter-array-of-rows-inside-aggregation
As of now, I still cannot find any related document on Presto’s main page, and this feature has just been silently supported since Dec 20, 2016…
Since each number is within the range [0, 100], we can use a counting sort based approach.
Time: \(O(n)\)
Space: \(O(100)\)
Assume there are m rounds of voting, we can solve this problem by a radix sort (from the m-th round to the first round).
Time: \(O(m * (26 \log 26))\), which can be further optimized to \(O(26m)\) using counting sort.
Space: \(O(26)\)
It is hard to solve the problem in a top-down fashion since each tree node can have two choices. However, since each node has a unique parent, the upwards paths ending at any node are also unique (by its length). This suggests a DFS approach, where we just need to check whether the last m nodes on the stack match the given listed list at any time.
Time: \(O(mn)\)
Space: \(O(m + h)\)
m = linked list size, n = binary tree size, h = binary tree height
This is a single source shortest path problem.
Build the graph
Time: \(O(mn \log (mn))\), which can be further optimized to \(O(mn)\).
This is because weights of edges in this graph are either 0 or 1, so we can compute the shortest path using BFS with a Deque.
Formally, we insert to the head of the queue if the edge weight is 0 and insert to the tail of the queue if weight is 1.
Space: \(O(mn)\)
Most programming languages should have date related packages. Worth getting familiar with them.
There are multiple ways to validate a binary tree. Here is one way of doing that.
Time: \(O(n)\)
Space: \(O(n)\)
There can be at most \(\sqrt{n}\) pairs of divisors, so we can just enumerate all of them.
Time: \(O(\sqrt{n})\)
Space: \(O(\sqrt{n})\), which can be further optimized to $O(1)$.
This is a math problem. We first have two facts that are easy to verify.
Then, it is easier to solve this problem backwards, i.e., considering the digits we have to discard to make the final number as large as possible. Sum up all the digits and we have three cases based on its modulo (by 3).
Time: $O(n \log n)$, which can be optimized to $O(n)$ using counting sort.
Space: $O(n)$
This solution is complicated but marks how I started to tackle this problem.
a
and b
, where 0 <= a <= b < n
, then the largest product must be either (nums[a + 1] * nums[a + 2] * ... * nums[n - 1])
or (nums[0] * nums[1] * ... * nums[b - 1])
.
For convenience, instead of doing exactly what the above algorithm suggests, it suffices to comptue all the
prefix and suffix products and take the max. (This also covers 3.1.)Time: \(O(n)\)
Space: \(O(n)\)
if len(nums) == 1:
return nums[0]
if 0 in nums:
ans = 0
cand = []
for i in nums:
if i != 0:
cand.append(i)
else:
if cand:
ans = max(ans, self.maxProduct(cand))
cand = []
if cand:
ans = max(ans, self.maxProduct(cand))
return ans
else:
ans = nums[0]
prefix = 1
for i in nums:
prefix *= i
ans = max(ans, prefix)
suffix = 1
for i in reversed(nums):
suffix *= i
ans = max(ans, suffix)
return ans
Time: \(O(n)\)
Space: \(O(1)\)
ans = max(nums)
prefix = 1
for i in nums:
if i:
prefix *= i
ans = max(ans, prefix)
else:
prefix = 1
suffix = 1
for i in reversed(nums):
if i:
suffix *= i
ans = max(ans, suffix)
else:
suffix = 1
return ans
Further simplify the code… But it will use \(O(n)\) extra space.
Time: \(O(n)\)
Space: \(O(n)\)
A, B = nums, nums[::-1]
for i in range(1, len(A)):
A[i] *= A[i - 1] or 1
B[i] *= B[i - 1] or 1
return max(A + B)