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 a 'Nx3' 2-D array 'Jobs' describing 'N' jobs where 'Jobs[i][0]' denotes the id of 'i-th' job, 'Jobs[i][1]' denotes the deadline of 'i-th' job, and 'Jobs[i][2]' denotes the profit associated with 'i-th job'.

You will make a particular profit if you complete the job within the deadline associated with it. Each job takes 1 unit of time to be completed, and you can schedule only one job at a particular time.

Return the number of jobs to be done to get maximum profit.

Note :

If a particular job has a deadline 'x', it means that it needs to be completed at any time before 'x'.

Assume that the start time is 0.

For Example :

'N' = 3, Jobs = [[1, 1, 30], [2, 3, 40], [3, 2, 10]].

All the jobs have different deadlines. So we can complete all the jobs.

At time 0-1, Job 1 will complete.
At time 1-2, Job 3 will complete.
At time 2-3, Job 2 will complete.

So our answer is [3 80].

Low Level Design for Amazon recommender system (used heaps , hash maps etc)

What are your strengths and weaknesses?

What are your hobbies?

Why do you want to join us?