Trees

Question 1

Check if a tree is a Binary Search Tree

Answer 1

For any node u check that:
* keys in left subtree of u are smaller than or equal to u.key
* keys in right subtree of u are larger than u.key

Question 2

Longest k-good segments (subarray)
Given an integer array and an integer K, return the number of good subarrays. A good array is an array where the number of different integers in that array is exactly K.

Answer 2

Solution with two pointers technique and dynamic sliding window.
Two pointers, left and right, both starting at position 0. Keep a counter to count the number of distinct elements in the window and a map value -> # occurrences.
Until the right pointer reaches the end do:
* if the counter is <= K, move right pointer. Increment the #occurrences of the new entry in the window. If it is 1 then it is the first time that value is in the window, then increment the counter also
* else the counter is > K, move left pointer. Decrement the #occurrences of the value which is not in the window anymore. If it is 0 then that value is not in the window in other positions, then decrement the counter also
* during the loop keep track of largest subarray

Theta(n) whp: no more than 2n iterations which means theta(n) operations on the map

Question 3

Longest k-good segments (subarray)
Implement a theta(n) worst case solution if values are in [1, …, O(n)].
Given an integer array and an integer K, return the number of good subarrays. A good array is an array where the number of different integers in that array is exactly K.

Answer 3

Solution with two pointers technique and dynamic sliding window.
Two pointers, left and right, both starting at position 0. Keep a counter to count the number of distinct elements in the window and an array to store #occurrences (direct access table).
Until the right pointer reaches the end do:
* if the counter is <= K, move right pointer. Increment the #occurrences of the new entry in the window. If it is 1 then it is the first time that value is in the window, then increment the counter also
* else the counter is > K, move left pointer. Decrement the #occurrences of the value which is not in the window anymore. If it is 0 then that value is not in the window in other positions, then decrement the counter also
* during the loop keep track of largest subarray

Question 4

Euler Tour

Answer 4

It is a mix of pre and post order visits

if (node != NULL)
    do something with node.key
    EulerTour(node.left)
    EulerTour(node.right)
    do something with node.key

Question 5

Maximum Path Sum
Given a tree with n nodes, each node u has a weight w(u). Find the maximum sum of a path from one leaf to another leaf.

Answer 5

Let’s say U is the LCA (Lowest Common Anchestor) of the leaves L1 and L2. The optimal path can be decomposed into two subpaths: L1 -> U and L2 -> U.
Run a post order visit in theta(n) time, for each node U:
* compute max path sum from U to a leaf in left subtree (msl) and in right subtree (msr)
* the best maximum path sum at the node U is equal to w(u) + msl + msr (w(u) + max sum left + max sum right)

Question 6

Path Sum
Design a data structure to efficiently answer the query PathSum(u, v), which returns the sum of weights on path from u to v. Give a O(1) time solution.
TODO how to solve it if the weights change

Answer 6

If w = LCA(u, v) then
PathSum(u, v) = PathSum(w, u) + PathSum(w, v) - w(w).
We remove w(w) because it is counted twice.
Let’s assume we can compute LCA(u, v) in O(1) time. We can focus on the case PathSum(w, v) in which node w is anchestor of node v.
PathSum(w, v) = PathSum(root, v) - PathSum(root, w) + w(w).
We add w(w) because we are cancelling that weight in the subtraction.

To solve the problem the goal is to compute PathSum(root, any node)
Precompute and store all of them with a pre order visit.