SDE - 1

Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k > 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications, and output this difference.

Examples:

Input  : arr[] = {1, 15, 10}, k = 6

Output :  Maximum difference is 5.

Explanation : We change 1 to 6, 15 to  

9 and 10 to 4. Maximum difference is 5

(between 4 and 9). We can't get a lower

difference.

Input : arr[] = {1, 5, 15, 10}  

       k = 3    

Output : Maximum difference is 8

arr[] = {4, 8, 12, 7}

Input : arr[] = {4, 6}  

       k = 10

Output : Maximum difference is 2

arr[] = {14, 16} OR {-6, -4}

Input : arr[] = {6, 10}  

       k = 3

Output : Maximum difference is 2

arr[] = {9, 7}  

Input : arr[] = {1, 10, 14, 14, 14, 15}

       k = 6  

Output: Maximum difference is 5

arr[] = {7, 4, 8, 8, 8, 9}  

Input : arr[] = {1, 2, 3}

       k = 2  

Output: Maximum difference is 2

arr[] = {3, 4, 5}

Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits.

We are given two arrays which represent arrival and departure times of trains that stop.

Examples:

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}

dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

Output: 3

Explantion: There are at-most three trains at a time (time between 11:00 to 11:20)

Input: arr[] = {9:00, 9:40}

dep[] = {9:10, 12:00}

Output: 1

Given cities and roads connecting them. Roads are of three types: type 1-> 2 wheelers road, type 2 -> 4-wheelers road and type 3-> both 2 and 4 wheelers road. The problem was to find the max number of roads that can be removed s.t a path exists for every pair of cities for each 2 wheelers and 4 wheelers.

An archer is hitting the target(a circle). He fires the first shot and then second shot. GIven that his shot was better than the second. Find the probability that the third shot that he fires is best among the three. The three shots are independent of each other.

The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days. For example, if the given array is {100, 180, 260, 310, 40, 535, 695}, the maximum profit can earned by buying on day 0, selling on day 3. Again buy on day 4 and sell on day 6. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

For example, minimum height of below Binary Tree is 2.

System Design: Design a job scheduler. Tasks will be given as inputs with an extra parameter ‘delay’ meaning that task has to run after this ‘delay’ time.

Given two integer arrays A and B of size N.

There are N gas stations along a circular route, where the amount of gas at station i is A[i].

You have a car with an unlimited gas tank and it costs B[i] of gas to travel from station i

to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return -1.

You can only travel in one direction. i to i+1, i+2, … n-1, 0, 1, 2.. Completing the circuit means starting at i and

ending up at i again.

Input Format

The first argument given is the integer array A.

The second argument given is the integer array B.

Output Format

Return the minimum starting gas station's index if you can travel around the circuit once, otherwise return -1.

For Example

Input 1:

   A =  [1, 2]

   B =  [2, 1]

Output 1:

   1

 Normal segment tree with update operation on [l, r] and some constant value x  s.t add add x to a[l], x+1 to a[l+1], ……., x+r-l to a[r]. Normal range query i.e calculate the sum in [l, r].

 Given a point on the perimeter of the circle and an interior point. Find the probability that the rectangle formed with diagonal as the line segment joining these points lies inside the circle.

My wife and I recently attended a party at which there were four other married couples. Various handshakes took place. No one shook hands with oneself, nor with one's spouse, and no one shook hands with the same person more than once. After all the handshakes were over, I asked each person, including my wife, how many hands he (or she) had shaken. To my surprise each gave a different answer. How many hands did my wife shake?