Senior Java Developer

Approach : 
1) Maintain two pointers – reference pointer and main pointer. 
2) Initialize both reference and main pointers to head. 
3) First, move the reference pointer to n nodes from head.
4) Now move both pointers one by one until the reference pointer reaches the end. 
5) Now the main pointer will point to nth node from the end. 
6) Return the main pointer.

TC : O(N) where N=length of the Linked List
SC : O(1)

Approach :

I) Using Hashing :

Basically, we need to find a common node of two linked lists. So we hash all nodes of the first list and then check the second list.

Note : Hash the nodes not the node value

1) Create an empty hash set.
2) Traverse the first linked list and insert all nodes' addresses in the hash set.
3) Traverse the second list. For every node check if it is present in the hash set. If we find a node in the hash set, return the node

TC : O(m+n)
SC : O(min(m,n))

II) Using Two pointers :

1) Initialize two pointers ptr1 and ptr2 at the head1 and head2.
2) Traverse through the lists,one node at a time.
3) When ptr1 reaches the end of a list, then redirect it to the head2.
4) Similarly when ptr2 reaches the end of a list, redirect it the head1.
5) Once both of them go through reassigning, they will be equidistant from the collision point
6) If at any node ptr1 meets ptr2, then it is the intersection node.
7) After second iteration if there is no intersection node it returns NULL.

TC : O(m+n) where m=Length of LL-1 and n=Length of LL-2
SC : O(1)

In Java, a thread always exists in any one of the following states. These states are:

1) New
2) Active
3) Blocked / Waiting
4) Timed Waiting
5) Terminated

Explanation of Different Thread States : 

1) New: Whenever a new thread is created, it is always in the new state. For a thread in the new state, the code has not been run yet and thus has not begun its execution.

2) Active: When a thread invokes the start() method, it moves from the new state to the active state. The active state contains two states within it: one is runnable, and the other is running.

2.1) Runnable: A thread, that is ready to run is then moved to the runnable state. In the runnable state, the thread 
may be running or may be ready to run at any given instant of time. It is the duty of the thread scheduler to provide 
the thread time to run, i.e., moving the thread the running state.

2.2) Running: When the thread gets the CPU, it moves from the runnable to the running state. Generally, the most 
common change in the state of a thread is from runnable to running and again back to runnable.

3) Blocked or Waiting: Whenever a thread is inactive for a span of time (not permanently) then, either the thread is in the blocked state or is in the waiting state.

For example, a thread (let's say its name is A) may want to print some data from the printer. However, at the same time, the other thread (let's say its name is B) is using the printer to print some data. Therefore, thread A has to wait for thread B to use the printer. Thus, thread A is in the blocked state. 


4) Timed Waiting: Sometimes, waiting for leads to starvation. For example, a thread (its name is A) has entered the critical section of a code and is not willing to leave that critical section. In such a scenario, another thread (its name is B) has to wait forever, which leads to starvation. To avoid such scenario, a timed waiting state is given to thread B. Thus, thread lies in the waiting state for a specific span of time, and not forever. 

5) Terminated: A thread reaches the termination state because of the following reasons:

i) When a thread has finished its job, then it exists or terminates normally.
ii) Abnormal termination: It occurs when some unusual events such as an unhandled exception or 
segmentation fault.

A terminated thread means the thread is no more in the system. In other words, the thread is dead, and there is no way one can respawn (active after kill) the dead thread.

Approach 1 (Recursive) :

1) Compare the head of both linked lists.
2) Find the smaller node among the two head nodes. The current element will be the smaller node among two head nodes.
3) The rest elements of both lists will appear after that.
4) Now run a recursive function with parameters, the next node of the smaller element, and the other head.
5) The recursive function will return the next smaller element linked with rest of the sorted element. Now point the next of current element to that, i.e curr_ele->next=recursivefunction()
6) Handle some corner cases. 
6.1) If both the heads are NULL return null.
6.2) If one head is null return the other.

TC : O(N) where N=length of the Linked List
SC : O(N)


Approach 2 (Iterative) :

1) Traverse the list from start to end.
2) If the head node of second list lies in between two nodes of the first list, insert it there and make the next node of second list the head. Continue this until there is no node left in both lists, i.e. both the lists are traversed.
3) If the first list has reached end while traversing, point the next node to the head of second list.

Note: Compare both the lists where the list with a smaller head value is the first list.

TC : O(N) where N=length of the Linked List
SC : O(1)

Answer : 

Structure of an LRU Cache :

1) In practice, LRU cache is a kind of Queue — if an element is reaccessed, 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.

Answer :

DELETE command:

1) This command is needed to delete rows from a table based on the condition provided by the WHERE clause.
2) It can be rolled back if required.
3) It maintains a log to lock the row of the table before deleting it and hence it’s slow.

TRUNCATE command:
1) This command is needed to remove complete data from a table in a database. It is like a DELETE command which has no WHERE clause.
2) It removes complete data from a table in a database.
3) It can be rolled back even if required.
4) It doesn’t maintain a log and deletes the whole table at once and hence it’s fast.

Answer :

1) Garbage Collection in Java is a process by which the programs perform memory management automatically.
2) The Garbage Collector(GC) finds the unused objects and deletes them to reclaim the memory. I
3) In Java, dynamic memory allocation of objects is achieved using the new operator that uses some memory and the
memory remains allocated until there are references for the use of the object.
4) When there are no references to an object, it is assumed to be no longer needed, and the memory, occupied by
the object can be reclaimed.
5) There is no explicit need to destroy an object as Java handles the de-allocation automatically.

The technique that accomplishes this is known as Garbage Collection. Programs that do not de-allocate memory can
eventually crash when there is no memory left in the system to allocate. These programs are said to have memory
leaks.

Garbage collection in Java happens automatically during the lifetime of the program, eliminating the need to de-
allocate memory and thereby avoiding memory leaks.

In C language, it is the programmer’s responsibility to de-allocate memory allocated dynamically using free() function.
This is where Java memory management leads.

Tip 1: Firstly, remember that the system design round is extremely open-ended and there’s no such thing as a standard answer. Even for the same question, you’ll have a totally different discussion with different interviewers.

Tip 2:Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service.

Some standard steps that are being followed with respect to this question are :

1) The first step is to provide the total number of passengers and submit all the necessary details of the passengers.
2) The next step is to enter the source and destination.
3) A list of available trains will appear. Among them, the user has to choose one.
4) The ticket value will be evaluated. The system will ask to enter the seat choice by showing the seat matrix. At last, a receipt will be generated on the screen.

Design your structure and functions according to the requirements and try to convey your thoughts properly to the interviewer so that you do not mess up while implementing the idea .



Finally , for acing System Design Rounds I would suggest watching Gaurav Sen's System Design Videos on YouTube and for hands on practice there is a Guided Path solely for System Design on CodeStudio which is very useful while preparing for these type of rounds.

JVM is platform dependent because it takes java byte code and generates byte code for the current operating system. So Java software is platform dependent but Java language is platform independent because different operating system have different JVMs.