SDE - 1

Inorder traversal requires that we print the leftmost node first and the right most node at the end. 
So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. So the steps would be : 
1.Start with the root node. 
2. Push the node in the stack and visit it's left child.
3. Repeat step 2 while node is not NULL, if it's NULL then pop the topmost node from the stack and print it.
4. Now move to node's right child and repeat step 1
5. Repeat the above steps while node is not NULL and stack is not empty

Structure of an LRU Cache :

1) In practice, LRU cache is a kind of Queue — if an element is re accessed, it goes to the end of the eviction order
2) This queue will have a specific capacity as the cache has a limited size. Whenever a new element is brought in, it is added at the head of the queue. When eviction happens, it happens from the tail of the queue.
3) Hitting data in the cache must be done in constant time, which isn't possible in Queue! But, it is possible with HashMap data structure
4) Removal of the least recently used element must be done in constant time, which means for the implementation of Queue, we'll use DoublyLinkedList instead of SingleLinkedList or an array.

LRU Algorithm :

The LRU algorithm is pretty easy! If the key is present in HashMap, it's a cache hit; else, it's a cache miss.

We'll follow two steps after a cache miss occurs:

1) Add a new element in front of the list.
2) Add a new entry in HashMap and refer to the head of the list.

And, we'll do two steps after a cache hit:

1) Remove the hit element and add it in front of the list.
2) Update HashMap with a new reference to the front of the list.

Tip : This is a very frequently asked question in interview and its implementation also gets quite cumbersome if you are doing it for the first time so better knock this question off before your SDE-interviews.

The idea here is to represent the grid as a graph and all the adjacent land cells are connected via an edge. Finally, do DFS on the grid and find the number of connected components after each query operation.

The algorithm is as follows:

1. Declare an ‘ANS’ array to store the number of islands after each query.
2. Declare a 2D array 'GRID' with ‘N’ rows and ‘M’ columns, where ‘GRID[i][j]’ = 0 or 1, 0 representing water and 1 representing land.
3. Declare a ‘DX’ array representing and set it to {1, 0, -1, 0}, representing the directions of all four neighboring cells.
4. Declare a ‘DY’ array representing and set it to {0, 1, 0, -1}, representing the directions of all four neighboring cells.
5. Iterate from ‘P’ = 0 to ‘Q.size() - 1’,
   • Declare a variable ‘X’ and set it to ‘Q[i][0]’.
   • Declare a variable ‘Y’ and set it to 'Q[i][1]'.
   • Set ‘GRID[X][Y]’ to 1, i.e i.e cell is converted into the land.
   • Declare a variable 'NUMBEROFISLANDS' and set it to 0.
   • Declare a 2D array ‘VISITED’ with ‘N’ rows and ‘M’ columns, where ‘VISITED[i][j]’ = 0 or 1, 0 representing the current cell being visited and 1 representing not visited.
   • Iterate from ‘i’ = 0 to ‘N’ - 1,
     • Iterate from ‘j’ = 0 to ‘M’ - 1,
       • If ‘GRID[i][j]’ == 1 && ‘VISITED[i][j]’ == 0,
         • This means the current cell is an island that is not seen before.
         • Run a ‘DFS’ function and mark all the connected lands as ‘VISITED’ that are connected to the cell (i,j).
         • Increment 'NUMBEROFISLANDS' by 1.
   • Append 'NUMBEROFISLANDS' to ‘ANS’.
6. Return the ‘ANS’ array.

A Java synchronized block marks a method or a block of code as synchronized. A synchronized block in Java can only be executed a single thread at a time (depending on how you use it). Java synchronized blocks can thus be used to avoid race conditions.
Synchronization is needed for objects, which are shared among multiple threads, to avoid any corruption of state or any kind of unexpected behavior. Synchronization in Java will only be needed if shared object is mutable.
It helps in concurrent programming. The synchronized keyword in Java provides locking, which ensures mutually exclusive access to the shared resource and prevents data race.