SDE - Intern

You are given an ‘N x N’ matrix ‘GRID’. Initially, every cell is locked, and ‘GRID[i][j]’ represents the time at which the cell at ‘(i, j)’ will unlock. You can move from one cell to another 4-dimensionally adjacent cell if and only if both cells are unlocked. You can move through infinite cells in zero time. Also, you cannot leave the boundaries of the grid.

If you start at the cell ‘(0, 0)’, what is the least time required to reach the last cell ‘(N - 1, N - 1)’.

Example:

‘GRID’ =

We cannot reach the cell ‘(2, 2)’ until the time is ‘5’. When the time is ‘5’, we move along the path: 
0 -> 1 -> 4 -> 3 -> 5

The cell with value ‘1’ will be unlocked when the time is ‘1’.
At time = 1: 0 -> 1

Similarly, the cell with value ‘4’ is unlocked when the time is ‘4’. At that time the cell with value ‘3’ will also be unlocked, as it unlocks at time ‘3’.    
At time = 4: 0 -> 1 -> 4 -> 3

The cell with value ‘5’ will be unlocked when the time is ‘5’.
At time = 5: 0 -> 1 -> 4 -> 3 -> 5

So, the least time to reach cell ‘(2, 2)’ is ‘5’.

Note:

1. All elements in the ‘GRID’ are unique.

2. ‘GRID[i][j]’ is a permutation of [0, 1, … , (N ^ 2) - 1].

You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array.

Example:

Let ‘N’ = 4,  ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3.  
then the elements of this array in ascending order is [1, 2, 4, 5].  Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively.

Design and implement a data structure which supports the following operations:

insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.

Four types of queries denote these operations:

Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.

Note:

It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.

Follow Up:

Can you implement every operation such that it works in O(1) time?

You are given a 2-D plane, and some 'N' integer coordinates in the form of (X, Y), where 'X' is the x-coordinate and 'Y' is the y-coordinate, all of which lie on that plane. You need to find the maximum number of coordinates among these which can form a straight line.

Note:

1. All the coordinates are integer coordinates.
2. There can be two identical coordinates.

1. Why did you decide to apply to this role?
2. What experience do you have that would be relevant to this role?
3. Tell me about your experience in.
4. What did you like most about the job description?
5. Why are you leaving your current job? 
6. Tell me about this gap in your resume.