Software Engineer

Your friends gifted you a lot of things on your birthday, and now it's your turn to give some return gifts to them. You went to a gift store and decided to buy some Binary Search Trees (BST).

There is no salesperson in the store. So you are supposed to guess the price of a given BST, which is the minimum value in its nodes.

‘Hashing’ is a technique in which a large non-negative integer is mapped with a smaller non-negative integer using a function called ‘hash function’ and this smaller integer is used as an index of an array called ‘hash table’.

We define ‘Collision’ as a situation when a large integer is mapped to the index in a hash table that is already mapped with some other integer.

‘Quadratic Probing’ is a collision handling technique in which we take the original hash value and successively add ‘i*i’ in ‘ith’ iteration until an unmapped index is found in the hash table. This technique works as follows:

Let ‘x’  be a larger integer, ‘n’ be the size of the hash table, and ‘h(x) = x mod n’ be a hash function. Then in Quadratic Probing -:

1. If we find that the index h(x), is already mapped to some other integer in the hashtable, then we try for index (h(x) + 1 * 1) mod n. 

2. If the index (h(x) + 1*1) mod n, is also already mapped to some other integer in the hashtable, then we try for index (h(x) + 2 * 2) mod n.

3. If the index (h(x) + 2*2) mod n, is also already mapped to some other integer in the hashtable, then we try for index ‘(h(x) + 3 * 3) mod n. 

4. We repeat this process until an unmapped index is found in the hashtable or index values start repeating.

In Quadratic probing, sometimes, it is possible that we cannot map an integer with any index in the hashtable.

Given an array ‘keys’ consisting of ‘n’ non-negative integers. Let's consider the hash function h(x) = x mod n. Assume that you are traversing the array ‘keys’ from left to right and you need to insert all these keys in the hash table. For each element of the array ‘keys’, your task is to determine the index by which this element is mapped in the hash table if ‘Quadratic Probing’ technique is used to handle the collision. Return an array ‘hashTable’ of size ‘n’ where the element at index ‘i’ is the element from the given array ‘keys’ that is mapped to that index or -1 if no element is mapped to that index.

For Example -:  Consider, array  ‘keys’ = {50, 49, 76, 85, 92, 73, 18},  ‘n’ = 7 and the hash function h(x) = x mod 7. Then -:

1. h(50) = 50 mod 7 = 1, thus it will be mapped to index ‘1’ in the hashtable.

2. h(49) = 49 mod 7 = 0, thus it will be mapped to index ‘0’ in hashtable.

3. h(76) = 76 mod 7 = 6, thus it will be mapped to index ‘6’ in the hashtable.

4. h(85) = 85 mod 7 = 1, thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’is already mapped with 50,  so we try for index (h(85) + 1*1) mod 7 = ‘2’, as index ‘2’ is not mapped previously, thus it will be mapped to index ‘2’ in hashtable’.

5. h(92) = 92 mod 7 = 1,  thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’ is already mapped with 50, so we try for index (h(92) + 1*1) mod 7 = 2,  but index ‘2’ is also occupied so we try for index (h(92) + 2*2) mod 7 = ‘5’, as index ‘5’ is not mapped previously, thus it will be mapped to index ‘5’ in hashtable

6. h(73) = 73 mod 7 = 3,  thus it will be mapped to index ‘3’ in the hashtable.

7. h(18) = 18 mod 7 = 4,  thus it will be mapped to index ‘4’ in the hashtable. 
Thus the resultant array ‘hashTable’ should be {49, 50, 85, 73, 18, 92, 76}.

Note:

1. Consider ‘0’ based indexing.
2. Don’t print anything, just return the integer array ‘hashTable’.

Implement a queue data structure which follows FIFO(First In First Out) property, using only the instances of the stack data structure.

Note:

1. To implement means you need to complete some predefined functions, which are supported by a normal queue such that it can efficiently handle the given input queries which are defined below.


2. The implemented queue must support the following operations of a normal queue: 

a. enQueue(data) : This function should take one argument of type integer and place the integer to the back of the queue.

b. deQueue(): This function should remove an integer from the front of the queue and also return that integer. If the queue is empty, it should return -1.

c. peek(): This function returns the element present in the front of the queue. If the queue is empty, it should return -1.

d. isEmpty(): This function should return true if the queue is empty and false otherwise.


3. You will be given q queries of 4 types:

a. 1 val - For this type of query, you need to insert the integer val to the back of the queue.

b. 2 - For this type of query, you need to remove the element from the front of the queue, and also return it.

c. 3 - For this type of query, you need to return the element present at the front of the queue(No need to remove it from the queue).

d. 4 - For this type of query, you need to return true if the queue is empty and false otherwise.


4. For every query of type:

a. 1, you do not need to return anything.

b. 2, return the integer being deQueued from the queue.

c. 3, return the integer present in the front of the queue.

d. 4, return “true” if the queue is empty, “false” otherwise.

Example

Operations: 
1 5
1 10
2
3
4

Enqueue operation 1 5: We insert 5 at the back of the queue.
Queue: [5]

Enqueue operation 1 10: We insert 10 at the back of the queue.
Queue: [5, 10]

Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
Output: 5
Queue: [10]

Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
Output: 10
Queue: [10]

IsEmpty operation 4: We check if the queue is empty.
Output: False
Queue: [10]

Q1. Had to design DB for an ecom website.
Q2. Had to design a DB and system design of a company don't exactly remember 
Q3. It was algo design for a computer graphic type problem.

What keeps you motivated?

Who is your role model?