Senior Software Engineer

Approach : 

The process is very much similar to binary to decimal conversion. In this case, the base of the given system is to be taken as 26. Also, in this system 1 is represented as ‘A’, 2 is represented as ‘B’ and so on till 26 is represented as ‘Z’

For example- 
CDA can be converted as 3*26*26 + 4*26 + 1

= 26(3*26 + 4) + 1

= 26(0*26 + 3*26 + 4) + 1

AB can be converted as 1*26 + 2


TC : O(N), where N = length of the input string
SC : O(1)

Lambda expression is a type of function without a name. It may or may not have results and parameters. It is known as an anonymous function as it does not have type information by itself. It is executed on-demand. It is beneficial in iterating, filtering, and extracting data from a collection.

As lambda expressions are similar to anonymous functions, they can only be applied to the single abstract method of Functional Interface. It will infer the return type, type, and several arguments from the signature of the abstract method of functional interface.

A stream is an abstraction to express data processing queries in a declarative way. 

A Stream, which represents a sequence of data objects & series of operations on that data is a data pipeline that is not related to Java I/O Streams does not hold any data permanently.
The key interface is "java.util.stream.Stream" . It accepts Functional Interfaces so that lambdas can be passed. Streams support a fluent interface or chaining. Below is the basic stream timeline marble diagram:

The Spring container is able to autowire relationships between the collaborating beans. That is, it is possible to let
Spring resolve collaborators for your bean automatically by inspecting the contents of the BeanFactory.

Different modes of bean auto-wiring are:

1) no : This is default setting which means no autowiring. Explicit bean reference should be used for wiring.

2) byName : It injects the object dependency according to name of the bean. It matches and wires its properties with
the beans defined by the same names in the XML file.

3) byType : It injects the object dependency according to type. It matches and wires a property if its type matches with
exactly one of the beans name in XML file.

4) constructor : It injects the dependency by calling the constructor of the class. It has a large number of parameters.

5) autodetect : First the container tries to wire using autowire by constructor, if it can’t then it tries to autowire by
byType.

The @SpringBootApplication annotation is equivalent to using @Configuration, @EnableAutoConfiguration, and @ComponentScan with their default attributes. Spring Boot enables the developer to use a single annotation instead of using multiple. But, as we know, Spring provided loosely coupled features that we can use for each annotation as per our project needs.

The primary annotations that Spring Boot offers reside in its "org.springframework.boot.autoconfigure" and its sub-packages. Here are a couple of basic ones :

@EnableAutoConfiguration – to make Spring Boot look for auto-configuration beans on its classpath and automatically apply them.

@SpringBootApplication – used to denote the main class of a Boot Application. This annotation combines @Configuration, @EnableAutoConfiguration, and @ComponentScan annotations with their default attributes.

Threads are basically the lightweight and smallest unit of processing that can be managed independently by a scheduler. Threads are referred to as parts of a process that simply let a program execute efficiently with other parts or threads of the process at the same time. Using threads, one can perform complicated tasks in the easiest way. It is considered the simplest way to take advantage of multiple CPUs available in a machine. They share the common address space and are independent of each other.

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.

The Thread can be created by using two ways.

1) By extending the Thread class
2) By implementing the Runnable interface

However, the primary differences between both the ways are given below:

1) By extending the Thread class, we cannot extend any other class, as Java does not allow multiple inheritances while implementing the Runnable interface; we can also extend other base class(if required).

2) By extending the Thread class, each of thread creates the unique object and associates with it while implementing the Runnable interface; multiple threads share the same object

3) Thread class provides various inbuilt methods such as getPriority(), isAlive and many more while the Runnable interface provides a single method, i.e., run().

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.

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.

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 requirements for this problem would be :
1) Given a long URL, the service should generate a shorter and unique alias of it.
2) When the user hits a short link, the service should redirect to the original link.
3) Links will expire after a standard default time span.
4) The system should be highly available. This is really important to consider because if the service goes down, all
the URL redirection will start failing.
5) URL redirection should happen in real-time with minimal latency.
6) Shortened links should not be predictable.


Tip 3: Now knowing about the requirements , note down all the important factors to take into consideration while
solving this problem . Most common factors include :
1)Traffic
2) URL Length
3) Data Capacity Modeling
4) URL Shortening Logic (Encoding basically) - Standard Hashing Techniques like Base62 , MD5 should be known
5) Choice of Database - SQL vs NoSQL


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.

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.