SDE - 1

You have a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task is to print the time (in minutes) that it will take to burn the whole tree.

It is given that it takes 1 minute for the fire to travel from the burning node to its adjacent node and burn down the adjacent node.

For Example :

For the given binary tree: [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
Start Node: 3

    1
   / \
  2   3
     / \
    4   5

Output: 2

Explanation :
In the zeroth minute, Node 3 will start to burn.

After one minute, Nodes (1, 4, 5) that are adjacent to 3 will burn completely.

After two minutes, the only remaining Node 2 will be burnt and there will be no nodes remaining in the binary tree. 

So, the whole tree will burn in 2 minutes.

After an accident, Ninja is suffering from transient amnesia. He wants to open his safe but has forgotten his password.

The safe’s lock has 4 circular wheels. Each wheel has 10 slots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The wheels can rotate clockwise as well as anti-clockwise: for example, we can turn 9 to be 0, or 0 to be 9. Each move consists of turning one wheel in one slot.

The lock initially starts at 0000, a string representing the state of the 4 wheels.

Ninja is given a list of ‘blockages’ dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning, and Ninja would be unable to open it.

There would be a ‘result’ given representing the wheels' value that will unlock the lock, return the minimum total number of turns Ninja is required to open the lock, or -1 if it is impossible for him to open it.

Help Ninja to open his safe.

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

Example:

Median for ‘arr’ = [1,2,3,4,5] is 3.
Median for ‘arr’ = [1,2,3,4] is (2+3)/2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initialises the MedianFinder object.

1. Void addNum(int ‘num’) adds the integer ‘num’ from the datastream to the data structure.

2. Double findMedian() returns the median of all elements so far.

Note : Answers within 10^-5 of actual answer will be accepted.

Example:

Input: 
5
1 1
1 2
2
1 5
2

Output:     
1.5
2

Explanation:
MedianFinder() initialises the MedianFinder object.
Add 1 to the data structure ‘arr’, so arr = [1].
Add 2 to arr, so arr = [1,2]
Find Median of current arr, that is (1+2)/2 = 1.5.
Add 5 to arr, so arr = [1,2,5]
Find Median of current arr, that is 2.0.

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.) You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarEvents class:

MyCalendarEvents() Initializes the object.

int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Note:

Here the start of the event is included while the end is not as part of the slot i.e. the slot end right before the end.

For Example

Input:
["MyCalendarEvents", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]  
Output:
[null, 1, 1, 2, 3, 3, 3]

Explanation:
MyCalendarEvents myCalendarEvent = new MyCalendarEvents();
myCalendarEvent.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarEvent.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarEvent.book(5, 10); // return 3
myCalendarEvent.book(25, 55); // return 3

Given an array A of size n, the safe value is defined by |A[I]-A[j]|+|I-j|, find the maximum safe value in the array. (Learn)

Stark Industry is planning to organize Stark Expo, for which various departments have to organize meetings to check their preparations. Since Stark Tower has limited rooms available for the meeting, Tony decided to allot a room to each meeting so that all the meetings are organized in the least possible conference rooms, and a the moment, only one meeting will happen in one room. So, he asked JARVIS to allot each meeting a room and tell the minimum number of conference rooms to be reserved. But, since JARVIS was busy rendering another Iron Man suit model, he asked you to help.

You are given an array of integers ARR of size N x 2, representing the start and end time for N meetings. Your task is to find the minimum number of rooms required to organize all the meetings.

Note:

1. You can assume that all the meetings will happen on the same day.
2. Also, as soon as a meeting gets over if some other meeting is scheduled to start at that moment, they can then be allocated that room.

Note:

Try to solve the problem in linear time complexity.

For Example:

Consider there are three meetings scheduled with timings:
1pm - 4pm
3pm - 5pm
4pm - 6pm

At the start of time, meeting 1 will be allotted room 1, which will be occupied till 4 pm hence for meeting 2 we’ll have to provide another room. At 4 pm, meeting 3 can be organized in room 1 because by that time, meeting 1 would have ended. Hence we’ll require two rooms for holding all three meetings.