SDE - 1

1. I asked some clarifying questions to better understand the constraints of the problem like number of total calls, max value of capacity to consider, number of add calls.
2. The constraints made me to think for a single traversal method and data structure.
3. To define a unit, I defined a structure Node containing key and value. 
4. Next I decided to use a doubly linked list to simulate the time stamps of the LRU cache, and the changes like deletion and updation can be done in 0(1) time if the entry/Node position is known. 
5. I felt the need of a HashMap (unordered_map in C++) to retrieve the entires in 0(1) time, so that get queries and location of that unit can be found in 0(1) time.
6. Data structures finalised were doubly linked list and HashMap.
7. I was talking while I was coding the logic.
8. The presence of an entry can be found out by searching for the key in HashMap.
9. The only part that needs attention and will be repeated is that for each operation, the node needs to be added to front of LRU list and deleted from its previous position if any.

1. I started speaking my thought process, stating that approaches like double traversal, sorting and traversal (along with their time complexities) are few intial ones coming to mind, but not the optimal one.
2. I then started thinking in direction of improving the time complexity.
3. I focused on the value of the elements being in range of [1,n].
4. This (along with my experience from preparations) gave me an idea of using these values as indices (-1 to make them 0 indexed).
5. The algorithm is to traverse(let's say currently at val) and mark the other element at its index (abs(val)-1) as negative. If that value which we are going to make negative is already negative then, it means that it is already been discovered, which in turns means that index+1 or abs(val) is the duplicate number.