Software Backend Engineer

You want to get tutelage under the Ultimate Ninja Ankush, but for that you have to pass his test. His test is simple: he has given you a relation function, F(n) = 2*F(n-1) + 3*F(n-2),where F(0) = F(1) = 1 and wants you to find the ‘N’th term for the function.

The 'N'th term can be very large, return it after modulus 10^9 + 7.

For example:

Given ‘N’ = 3,
F(3) = 13,This is because F(0) = 1, F(1) = 1, Therefore F(2) = 2*F(1) + 3*F(1), therefore F(2) = 5, and F(3) = 2*F(2) + 3*F(1), therefore F(3) = 13.

There was an SQL query asked in which we are given 2 tables and we need to write a nested query for finding the required answers. (Medium Level)

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

You are given a string 'S' of length 'N', you need to find the frequency of each of the characters from ‘a’ to ‘z’ in the given string.

Example :

Given 'S' : abcdg
Then output will be : 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Design a data structure that stores a mapping of a key to a given value and supports the following operations in constant time.

1. INSERT(key, value): Inserts an integer value to the data structure against a string type key if not already present. If already present, it updates the value of the key with the new one. This function will not return anything.

2. DELETE(key): Removes the key from the data structure if present. It doesn't return anything.

3. SEARCH(key): It searches for the key in the data structure. In case it is present, return true. Otherwise, return false.

4. GET(key): It returns the integer value stored against the given key. If the key is not present, return -1. 

5. GET_SIZE(): It returns an integer value denoting the size of the data structure. 

6. IS_EMPTY(): It returns a boolean value, denoting whether the data structure is empty or not. 

Note :

1. Key is always a string value.
2. Value can never be -1.

Operations Performed :

First(Denoted by integer value 1):  Insertion to the Data Structure. It is done in a pair of (key, value).

Second(Denoted by integer value 2):  Deletion of a key from the Data Structure.

Third(Denoted by integer value 3): Search a given key in the Data Structure.

Fourth(Denoted by integer value 4): Retrieve the value for a given key from the Data Structure.

Fifth(Denoted by integer value 5): Retrieve the size of the Data Structure.

Sixth(Denoted by integer value 6): Retrieve whether the Data Structure is empty or not.

Many sql queries were asked including nested queries and then some question around DBMS like ACID property, indexing were asked.

How would you make a class Immutable?