SDE - Intern

Ninja has been given two sparse matrices ‘MAT1’ and ‘MAT2’ of integers having size ‘N’ x ‘M’ and ‘M’ x ‘P’, respectively.

A sparse matrix is a matrix that contains very few non-zero elements.

Ninja has to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’. As Ninja is busy with some other tasks so he needs your help. Can you help Ninja to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’?

Note: The number of columns in ‘MAT1’ i.e ‘M’ is equal to the number of rows in ‘MAT2’ i.e ‘M’. It means we can always multiply ‘MAT1’ with ‘MAT2’.

For example:

For the ‘MAT1’ and ‘MAT2’ given below, ‘MAT3’ is the matrix formed by multiplying ‘MAT1’ and ‘MAT2’. 

1. MAT3[0][0] = MAT1[0][0] * MAT2[0][0] + MAT1[0][1] * MAT2[1][0]  ie. 2 * 1 + 1 * 4 = 6
2. MAT3[1][0] = MAT1[1][0] * MAT2[1][0] + MAT1[1][1] * MAT2[1][0] ie. 0 * 6 + 0 * 4 = 0

‘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’. Hash Table is the table in which we store large numbers corresponding to mapped indices.

While hashing a list of elements, we define ‘Collision’ as a situation when the hash function for a large integer in list returns an index which is already mapped with some other large integer in a list.

‘Linear Probing’ is a collision handling technique in which we find the next vacant place in the hash table for mapping. What we do is that we take the original hash value and successively add 1 in each iteration until an unmapped index is found in the hash table.

Given an array KEYS consisting of N non-negative integers. For each element in a given array, you need to determine the index by which this element is mapped in the hash table if the ‘Linear Probing’ technique is used to handle collision.

The hash function you need to consider is H(X) = X mod N i.e. index = X mod N.

Return an array ‘HASH_TABLE’ of size N in which:

HASH_TABLE[ i ] = KEYS[ j ] where, i = KEYS[ j ] mod N.

In short, an element at index ‘i’ is the element from the given array KEYS which is mapped to that index.

You can refer to the example given below:

The answer for the above example will be [18, 21, 6, 15].

Note:

1. Consider ‘0’ based indexing.

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

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]