SDE - 1

At first, I tried to think of a brute force approach in which we would try to explore each & every path from source to destination & reverse every edge that comes in the way.
While explaining the algorithm it hit me that this is somewhat like Dijkstra's algorithm.
Whenever we are at any node we can consider the outgoing edge to be of weight 0 & incoming edge to be of weight 1. 
& the number of edges we would need to reverse in the process would be the same as the cost of reaching the destination from the source in Dijkstra's algorithm.

The interviewer was happy with this approach & I was told to code it out on a Google Doc
I did that & proceeded to the next question.

I had solved this problem beforehand while practising & had a little time left to solve this question in the interview so quickly I went to the solution.
This is a basic DP problem. 
Maintain a 2D dp matrix of size (row, column) where each i, and j shows the minimum steps required to reach the end of the matrix
Start from the bottom right corner and fill the last row & last column using the (i, j+arr[i][j]) or (i+arr[i][j], j) rule.
Now start from row - 2->0 & column - 2->0 & start filling the dp matrix in reverse order. 
(Avoid going out of the bounds of the matrix).

I knew about its other variation House Robber 1 in which houses were lined up straight.
So I started thinking in that manner only but the catch was that we cannot rob 0th & n-1th house 
The simple approach that hit me was - 
Remove the first & the last house 
Therefore, the core idea is to apply dynamic programming. Two cases are considered here: 
When you rob the first house
When you don't rob the first house, i.e. you rob the last one.

This was a tricky problem 
First I tried a brute force approach in which I made a graph.
Any number Ex - 239 has an outgoing edge to every number starting with 9 & an Incoming edge from every number starting with 2.
Now after making this graph we just have to find the largest cycle in this graph.

The interviewer stopped me here & asked me about the time complexity 
O(n^2) I said.
However, the interviewer said to reduce the time complexity.

I took a few minutes & thought that we don't need to store the whole string of number 
We just need its first & last digit
I build a 2D matrix of size 10*10 
any index i,j represents a number or the maximum length of a number starting with I & ending in j.
Now whenever a number ex - 891 comes.
We already have the data of all the numbers before it ends with 8 (starting with 1, starting with 2 etc....) 
Now for index (1, 8) (2, 8), (3, 8) etc., we form a 9 numbers 
starting with 1 & ending with 1 (last digit of 891)
starting with 2 & ending with 1 (last digit of 891)
& so on.
thus updating the (1, 1) index (2, 1) index & so on.....


After iterating over all the given numbers we will find the maximum value present in the diagonal (i, i) to get the answer.

The first step of course is to find out the actual sorted order with their position.
Then 

Assume we have to collect any number say 8 whose first occurrence is at index 3 to index 9 & we are at position 6. There are 2 options now - 
1) Go to position 9 collecting all 8s & then to position 3
2) Go to position 3 collecting all 8s & then to position 9

Now start from there & move to the next greater number

So simply at every step/number we have 2 options & hence it became a 2 power n kind of approach that can be converted to a 2dp problem.
& I proceeded with that

It took me a lot of time so got a little anxious about the next question.