SDE - Intern

You are given ‘N’ 2-D matrices and an array/list “ARR” of length ‘N + 1’ where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix. For each matrix, the number of columns is equal to the number of rows of the next matrix. You are supposed to find the minimum number of multiplication operations that need to be performed to multiply all the given matrices.

Note :

You don’t have to multiply the matrices, you only have to find the minimum number of multiplication operations.

For Example :

ARR = {2, 4, 3, 2}

Here, we have three matrices with dimensions {2X4, 4X3, 3X2} which can be multiplied in the following ways:
a. If the order of multiplication is (2X4, 4X3)(3X2), then the total number of multiplication operations that need to be performed are: (2*4*3) + (2*3*2) = 36

b. If the order of multiplication is (2X4)(4X3, 3X2), then the total number of multiplication operations that need to be performed are  (2*4*2) + (4*3*2) = 40

‘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. 

You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

1 ‘X’: Enqueue element ‘X’  into the end of the nth queue. Returns true after the element is enqueued.

2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.

Note:

Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.

You are given a string 's' that represents a Roman number. Convert the Roman number to an integer and return it.

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Table of values:

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example:

3 is written as III in Roman numeral, just three ones added together. 13 is written as XIII, which is simply X + III. The number 25 is written as XXV, which is XX + V