Senior Systems Engineer

Approach (Using Sieve of Eratosthenes) : 

1) We'll create a global sieve and store values of prime numbers in it and use it to get prime numbers for all queries in constant time.

2) Define global variable MAXSIZE as 10^6+5 and an empty ARRAYOFPRIMES.

3) Initialize boolean array ISPRIME[i] to TRUE for each 2<=i <=MAXSIZE

4) Iterate for each 2 <= p <= MAXSIZE:
4.1) If IsPrime[P] is not changed, then it is a prime. I.e. if ISPRIME[P] is TRUE :
i) Update all multiples of P greater than or equal to the square of it numbers which are multiples of p and are less than P^2 are already been marked, i.e. for each P*P <= i <= MAXSIZE:

ii) Assign FALSE to ISPRIME[i] and increment i by P.

5) Store all prime numbers in an array, i.e. for each 2<= P <= MAXSIZE, if ISPRIME[P] is TRUE then add P to ARRAYOFPRIMES.

6) Now, once the array is created, you can check and return ARRAYOFPRIMES[N]. Thus the retrieval of Nth prime number can be done in constant time.


TC : O(N* log(log N)), where N = the Nth prime number that we have to find.
SC : O(N)

The differences between Abstract Class and Interface are as follows : 

Abstract Class:
1) Abstract classes have a default constructor and it is called whenever the concrete subclass is instantiated.

2) It contains Abstract methods as well as Non-Abstract methods.

3) The class which extends the Abstract class shouldn’t require the implementation of all the methods, only Abstract
methods need to be implemented in the concrete sub-class.

4) Abstract class contains instance variables.



Interface:
1 )It doesn’t have any constructor and couldn’t be instantiated.

2) The abstract method alone should be declared.

3) Classes that implement the interface should provide the implementation for all the methods.

4) The interface contains only constants.

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.

No one wants its software to fail or crash. Exceptions are the major reason for software failure. The exceptions can be handled in the program beforehand and prevent the execution from stopping. This is known as exception handling.
So exception handling is the mechanism for identifying the undesirable states that the program can reach and specifying the desirable outcomes of such states.
Try-catch is the most common method used for handling exceptions in the program.

According to ConcurrentHashMap Oracle docs,

The constructor of ConcurrentHashMap looks like this :

public ConcurrentHashMap (int initialCapacity, float loadFactor, int concurrencyLevel)

So the above line creates a new, empty map with the specified initial capacity, load factor and concurrency level.
where,
Important Parameters to consider from ConcurrentHashMap Constructor :

initialCapacity - the initial capacity. The implementation performs internal sizing to accommodate this many elements.

concurrencyLevel - the estimated number of concurrently updating threads. The implementation performs internal
sizing to try to accommodate this many threads.

In the ConcurrentHashMap Api , you will find the following constants.

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

initial capacity parameter and concurrency level parameters of ConcurrentHashMap constructor (or Object) are set to
16 by default.

1) Thus, instead of a map wide lock, ConcurrentHashMap maintains a list of 16 locks by default ( number of locks equal
to the initial capacity , which is by default 16) each of which is used to lock on a single bucket of the Map.

2) This indicates that 16 threads (number of threads equal to the concurrency level , which is by default 16) can modify the collection at the same time , given ,each thread works on different bucket. 

3) So unlike hashtable, we perform any sort of operation ( update ,delete ,read ,create) without locking on entire map in ConcurrentHashMap.


Retrieval operations (including get) generally do not block, so may overlap with update operations (including put and
remove). Retrievals reflect the results of the most recently completed update operations holding upon their onset.


1) The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument
(default 16), which is used as a hint for internal sizing. 

2) The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. 

3) Because placement in hash tables is essentially random, the actual concurrency will vary. 

4) Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. 

5) Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention.

In Java, the final keyword is used as defining something as constant /final and represents the non-access modifier.

1) final variable :
i) When a variable is declared as final in Java, the value can’t be modified once it has been assigned.

ii) If any value has not been assigned to that variable, then it can be assigned only by the constructor of the class.


2) final method :
i) A method declared as final cannot be overridden by its children's classes.

ii) A constructor cannot be marked as final because whenever a class is inherited, the constructors are not inherited.
Hence, marking it final doesn't make sense. Java throws compilation error saying - modifier final not allowed here


3) final class :
i) No classes can be inherited from the class declared as final. But that final class can extend other classes for its
usage.

1) Storage area : In string, the String pool serves as the storage area. For StringBuilder and StringBuffer, heap
memory is the storage area.

2) Mutability : A String is immutable, whereas both the StringBuilder and StringBuffer are mutable.

3) Efficiency : It is quite slow to work with a String. However, StringBuilder is the fastest in performing operations. The
speed of a StringBuffer is more than a String and less than a StringBuilder. (For example appending a character is
fastest in StringBuilder and very slow in String because a new memory is required for the new String with appended
character.)

4) Thread-safe : In the case of a threaded environment, StringBuilder and StringBuffer are used whereas a String is
not used. However, StringBuilder is suitable for an environment with a single thread, and a StringBuffer is suitable for
multiple threads.

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.

start(): In simple words, the start() method is used to start or begin the execution of a newly created thread. When the start() method is called, a new thread is created and this newly created thread executes the task that is kept in the run() method. One can call the start() method only once. 

run(): In simple words, the run() method is used to start or begin the execution of the same thread. When the run() method is called, no new thread is created as in the case of the start() method. This method is executed by the current thread. One can call the run() method multiple times.

BlockingQueue basically represents a queue that is thread-safe. Producer thread inserts resource/element into the queue using put() method unless it gets full and consumer thread takes resources from the queue using take() method until it gets empty. But if a thread tries to dequeue from an empty queue, then a particular thread will be blocked until some other thread inserts an item into the queue, or if a thread tries to insert an item into a queue that is already full, then a particular thread will be blocked until some threads take away an item from the queue.

Thread starvation is basically a situation or condition where a thread won’t be able to have regular access to shared resources and therefore is unable to proceed or make progress. This is because other threads have high priority and occupy the resources for too long. This usually happens with low-priority threads that do not get CPU for its execution to carry on.

Thread Scheduler: It is a component of JVM that is used to decide which thread will execute next if multiple threads are waiting to get the chance of execution. By looking at the priority assigned to each thread that is READY, the thread scheduler selects the next run to execute. To schedule the threads, it mainly uses two mechanisms: Preemptive Scheduling and Time slicing scheduling. 

Time Slicing: It is especially used to divide CPU time and allocate them to active threads. In this, each thread will get a predefined slice of time to execute. When the time expires, a particular thread has to wait till other threads get their chances to use their time in a round-robin fashion. Every running thread will get executed for a fixed time period.

The SOLID principle is an acronym of the five principles which is given below :

1) Single Responsibility Principle (SRP)
2) Open/Closed Principle
3) Liskov’s Substitution Principle (LSP)
4) Interface Segregation Principle (ISP)
5) Dependency Inversion Principle (DIP)

Uses of SOLID design principles :

1) The SOLID principle helps in reducing tight coupling.
2) Tight coupling means a group of classes are highly dependent on one another which we should avoid in our code.
3) Opposite of tight coupling is loose coupling and our code is considered as a good code when it has loosely-
coupled classes.
4) Loosely coupled classes minimize changes in your code, helps in making code more reusable,
maintainable,flexible and stable.

Explaining the 5 SOLID principles one by one :

1) Single Responsibility Principle : This principle states that “a class should have only one reason to change” which
means every class should have a single responsibility or single job or single purpose.
Use layers in your application and break God classes into smaller classes or modules.


2) Open/Closed Principle : This principle states that “software entities (classes, modules, functions, etc.) should be
open for extension, but closed for modification” which means you should be able to extend a class behavior, without
modifying it. Using this principle separates the existing code from the modified code so it provides better stability,
maintainability and minimizes changes as in your code.


3) Liskov’s Substitution Principle : According to this principle “Derived or child classes must be substitutable for their
base or parent classes“. This principle ensures that any class that is the child of a parent class should be usable in
place of its parent without any unexpected behavior.


4) Interface Segregation Principle : This principle is the first principle that applies to Interfaces instead of classes in
SOLID and it is similar to the single responsibility principle. It states that “do not force any client to implement an
interface which is irrelevant to them“. Here your main goal is to focus on avoiding fat interface and give preference to
many small client-specific interfaces.


5) Dependency Inversion Principle : Two key points are here to keep in mind about this principle
a) High-level modules/classes should not depend on low-level modules/classes. Both should depend upon
abstractions.
b) Abstractions should not depend upon details. Details should depend upon abstractions.

Although both HashSet and TreeSet are not synchronized and ensure that duplicates are not present, there are certain properties that distinguish a HashSet from a TreeSet.

1) Implementation: For a HashSet, the hash table is utilized for storing the elements in an unordered manner. However, TreeSet makes use of the red-black tree to store the elements in a sorted manner.

2) Complexity/ Performance: For adding, retrieving, and deleting elements, the time amortized complexity is O(1) for a HashSet. The time complexity for performing the same operations is a bit higher for TreeSet and is equal to O(log n). Overall, the performance of HashSet is faster in comparison to TreeSet.

3) Methods: hashCode() and equals() are the methods utilized by HashSet for making comparisons between the objects. Conversely, compareTo() and compare() methods are utilized by TreeSet to facilitate object comparisons.

4) Objects type: Heterogeneous and null objects can be stored with the help of HashSet. In the case of a TreeSet, runtime exception occurs while inserting heterogeneous objects or null objects.

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.

Tip : For an experienced professional seeking a change, this is a common question. The easiest method to respond
to this question is to state that you are leaving your current work in order to advance your career. Make sure you don't
criticize or speak poorly about the company where you now work.