SDE - 2

Design a distributed system

The lowest common ancestor (LCA) is a concept in graph theory and computer science.

Let ‘T’ be a rooted tree with ‘N’ nodes. The lowest common ancestor is defined between two nodes, ‘u’ and ‘v’, as the lowest node in ‘T’ that has both ‘u’ and ‘v’ as descendants (where we allow a node to be a descendant of itself). - Wikipedia

For the given tree, The LCA of nodes 5 and 8 will be node 2, as node 2 is the first node that lies in the path from node 5 to root node 1 and from node 8 to root node 1.

Path from node 5 to root node looks like 5 → 2 → 1.

Path from node 8 to root node looks like 8 → 6 → 2 → 1.

Since 2 is the first node that lies in both paths. Hence LCA will be 2.

Given any two nodes ‘u’ and ‘v’, find the LCA for the two nodes in the given Tree ‘T’.

Note: For each test case, the tree is rooted at node 1.

You are given a list of ‘N’ jobs which are to be performed. Each job can be characterized by three parameters-

• Start Time, denoting the start time of the job.
• End Time, denoting the end time of the job.
• Profit associated with the job.

You are required to schedule the jobs in such a way that total profit will be maximized.

Note: Only one job can be scheduled at a time, and jobs can be scheduled at only integer moments of time greater than or equal to one.

For example-

Let there be three jobs ‘A’, ‘B’, and ‘C’-
• Start time, End time and profit associated with job ‘A’ being 1, 1 and 30.
• Start time, End time and profit associated with job ‘B’ being 1, 2 and 40.
• Start time, End time and profit associated with job ‘C’ being 3, 4 and 30.

We will perform job ‘B’ at time t = 1 and job ‘C’ at time t = 3. The total profit will be 70. There is no other sequence of jobs which can fetch us a better overall profit.