SDE - 1

You are given an unsorted array containing ‘N’ integers. You need to find ‘K’ largest elements from the given array. Also, you need to return the elements in non-decreasing order.

You are the receptionist at a hotel which has 10 floors, numbered from 0 to 9 and each floor has 26 rooms named from ‘A’ to ‘Z’. Being a receptionist your task is to handle booking queries.

You get booking queries in the form of strings of size 3 where 1st character is ‘+’ means room is booked, or ‘-’ means room is freed. Second character represents the floor of the room i.e, ‘0’ to ‘9’. Third character represents the room name i.e, ‘A’ to ‘Z’.

On booking of each room you collect 1 coin from the customer. After the end of all the booking queries you have to count the number of coins you collected.

You may assume that the list describes a correct sequence of bookings in chronological order i.e., only free rooms can be booked, and only booked rooms can be freed.

For Example:-

Consider booking queries to be ["+1A", "+3E", "-1A", "+4F", "+1A", "-3E"]
+1A: Room A on the 1st floor is booked and you collected 1 coin.
+3E: Room E on the 3rd floor is booked and you collected 1 coin.
-1A: Room A on the 1st floor is freed.
+4F: Room F on the 4th floor is booked and you collected 1 coin.
+1A: Room A on the 1st floor is booked and you collected 1 coin.
-3E: Room E on the 3rd floor is freed.
So you collected 4 coins.

You have been given a string STR. Your task is to find the total number of palindromic substrings of STR.

Example :

If the input string is "abbc", then all the possible palindromic substrings would be: ["a", "b", "b", c", "bb"] and hence, the output will be 5 since we have 5 substrings in total which form a palindrome.

Note :

A string is said to be a 'Palindrome' if it is read the same forwards and backwards. 
For example, “abba” is a palindrome, but “abbc” is not.

A 'Substring' is a contiguous sequence of characters within a string. 
For example, "a", "b", "c", "ab", "bc", "abc" are substrings of "abc".

You are given 'N' stones labeled from 1 to 'N'. The 'i-th' stone has the weight W[i]. There are 'M' colors labeled by integers from 1 to 'M'. The 'i-th' stone has the color C[i] which is an integer between 1 to 'M', both inclusive.

You have been required to fill a Knapsack with these stones. The Knapsack can hold a total weight of 'X'.

You are required to select exactly 'M' stones; one of each color. The sum of the weights of the stones must not exceed 'X'. Since you paid a premium for a Knapsack with capacity 'X', you are required to fill the Knapsack as much as possible.

Write a program to calculate the best way to fill the Knapsack - that is, the unused capacity should be minimized.

You are given a binary tree having 'n' nodes.

The boundary nodes of a binary tree include the nodes from the left and right boundaries and the leaf nodes, each node considered once.

Figure out the boundary nodes of this binary tree in an Anti-Clockwise direction starting from the root node.

Example :

Input: Consider the binary tree A as shown in the figure:

Output: [10, 5, 3, 7, 18, 25, 20]

Explanation: As shown in the figure

The nodes on the left boundary are [10, 5, 3]

The nodes on the right boundary are [10, 20, 25]

The leaf nodes are [3, 7, 18, 25].

Please note that nodes 3 and 25 appear in two places but are considered once.