SDE - Intern

Chintu has a long binary string ‘str’. A binary string is a string that contains only 0 and 1. He considers a string ‘beautiful’ if and only if the number of 0's and 1's in the string are equal.

For example :

0011 , 1100 , 101010 etc are beautiful strings whereas 1110, 0001,10101 etc are not beautiful strings.

Now Chintu wants to split the string into substrings such that each substring is beautiful. Can you help Chintu to find the maximum number of beautiful strings he can split the string into? If it is not possible to split the string in such a way that all strings are beautiful, return -1.

For example :

Let the given string be “101001”
We will return 3 as we can divide the string into 3 beautiful strings “10” “10” and “01’.

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.

Ninja bought a plane that can cover a distance of at most ‘K’ units in one flight. Now, the ninja wants to show this plane to his best friend, whose house lies at point (X, 0) on the x-axis. There are multiple airports on the x-axis marked by 1. If there is no airport at any point, then it is marked as 0.

Given an integer array ‘AIRPORTS’ of size ‘N’ containing the information about airports on the x-axis, can you find the minimum number of stops that must be taken by the plane to reach the destination (X,0) on the x-axis. If the destination is unreachable, return -1. The plane starts from the origin (0, 0).

For example:

You are given AIRPORTS = [1, 1, 1, 0, 1, 0], ‘K’ = 2 and ‘X’ = 4.
The answer will be 1. The plane makes its first stop at (2, 0) and then reaches the destination (4, 0) in the next fight. Hence the total number of stops is 1.

Design and implement a data structure which supports the following operations:

insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.

Four types of queries denote these operations:

Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.

Note:

It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.

Follow Up:

Can you implement every operation such that it works in O(1) time?

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again. 

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6.