Associate Software Developer

You are given a sorted array 'arr' of distinct values and a target value 'm'. You need to search for the index of the target value in the array.

Note:

1. If the value is present in the array, return its index.
2. If the value is absent, determine the index where it would be inserted in the array while maintaining the sorted order. 
3. The given array has distinct integers.
4. The given array may be empty.

Example:

Input:  arr = [1, 2, 4, 7],  m = 6 

Output: 3

Explanation: If the given array 'arr' is: [1, 2, 4, 7] and m = 6. We insert m = 6 in the array and get 'arr' as: [1, 2, 4, 6, 7]. The position of 6 is 3 (according to 0-based indexing)

You are given a 2D matrix 'ARR' (containing either ‘0’ or ‘1’) of size 'N' x 'M', where each row is in sorted order.

Find the 0-based index of the first row with the maximum number of 1's.

Note :

If two rows have the same number of 1’s, return the row with a lower index.

If no row exists where at-least one '1' is present, return -1.

Example:

Input: ‘N’ = 3, 'M' = 3
'ARR' = 
[     [ 1,  1,  1 ],
      [ 0,  0,  1 ],
      [ 0,  0,  0 ]   ]

Output: 0

Explanation: The 0th row of the given matrix has the maximum number of ones.

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.

Explain a Linked List. (Learn)