SDE - 1

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

You are given the root node of a binary tree.

Return 'true' if it is a height balanced binary tree.

Note:

Height of a tree is the maximum number of nodes in a path from the node to the leaf node.

An empty tree is a height-balanced tree. A non-empty binary tree is a height-balanced binary tree if
1. The left subtree of a binary tree is already the height-balanced tree.
2. The right subtree of a binary tree is also the height-balanced tree.
3. The difference between heights of left subtree and right subtree must not more than ‘1’.

Example:

Input: Consider the binary tree given below:

Output: 'true'

Explanation:
Consider subtree at Node ( 7 ) 
Left subtree height is ‘0’ and right subtree height is ‘0’, the absolute height difference is ‘0-0 = 0’ and ‘0’ is not more than ‘1’ so subtree at Node ( 7 ) is a height-balanced binary tree. 
Same for subtrees at Nodes ( 5, 6 ). 

Consider subtree at Node ( 4 ) 
Left subtree height is ‘1’ and right subtree height is ‘0’, the absolute height difference is ‘1-0 = 1’ and ‘1’ is not more than ‘1’ so subtree at Node ( 4 ) is a height-balanced binary tree.
Same for subtree at Node ( 3)

Consider subtree at Node ( 2 ) 
Left subtree height is ‘2’ and right subtree height is ‘1’, the absolute height difference is ‘2-1 = 1’ and ‘1’ is not more than ‘1’ so subtree at Node ( 2 ) is a height-balanced binary tree.

Consider subtree at Node ( 1 ) 
Left subtree height is ‘3’ and right subtree height is ‘2’, the absolute height difference is ‘3-2 = 1’ and ‘1’ is not more than ‘1’ so subtree at Node ( 1 ) is a height-balanced binary tree.

Because the root node ( 1 ) is a height-balanced binary tree, so the complete tree is height-balanced.

You are given an array 'arr' consisting of 'n' integers which denote the position of a stall.

You are also given an integer 'k' which denotes the number of aggressive cows.

You are given the task of assigning stalls to 'k' cows such that the minimum distance between any two of them is the maximum possible.

Print the maximum possible minimum distance.

Example:

Input: 'n' = 3, 'k' = 2 and 'arr' = {1, 2, 3}

Output: 2

Explanation: The maximum possible minimum distance will be 2 when 2 cows are placed at positions {1, 3}. Here distance between cows is 2.

Given a DAG(direct acyclic graph), return the Topological Sorting of a given graph.

It was like a rapid-fire round, to be honest. The interviewer shooted around 15-20 questions related to OS and OOPS within a span of 10 minutes. The questions were of very basic type and a bit medium. Topics include semaphore, paging, virtual memory, bankers algo, deadlock conditions, ram vs rom, class vs struct, polymorphism etc.

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.