SDE - 1

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.

Approach 1(Using Hashing) :

We are going to maintain a lookup table(a Hashmap) that basically tells if we have already visited a node or not, during the course of traversal.

Steps :
1) Visit every node one by one, until null is not reached.
2) Check if the current node is present in the loop up table, if present then there is a cycle and will return
true, otherwise, put the node reference into the lookup table and repeat the process.
3) If we reach at the end of the list or null, then we can come out of the process or loop and finally, we can
say the loop doesn't exist.

TC : O(N), where N is the total number of nodes.
SC : O(N)


Approach 2 (Using Slow and Fast Pointers) :

Steps :
1) The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to
every jump slow pointer takes, fast pointer takes 2 jumps. If there exists a cycle, both slow and fast
pointers will reach the exact same node. If there is no cycle in the given linked list, then fast pointer will
reach the end of the linked list well before the slow pointer reaches the end or null.
2) Initialize slow and fast at the beginning.
3) Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.
4) If after adjusting slow and fast, if they are referring to the same node, there is a cycle otherwise repeat
the process
5) If fast reaches the end or null then the execution stops and we can conclude that no cycle exists.

TC : O(N), where N is the total number of nodes.
SC : O(1)

ArrayList :
1) ArrayList internally uses a dynamic array to store the elements.
2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory.
3) An ArrayList class can act as a list only because it implements List only.
4) ArrayList is better for storing and accessing data.

LinkedList :
1) LinkedList internally uses a doubly linked list to store the elements.
2) Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
3) LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
4) LinkedList is better for manipulating data.

The main difference between abstraction and inheritance is that abstraction allows hiding the internal details and displaying only the functionality to the users, while inheritance allows using properties and methods of an already existing class.

Java is not fully object oriented because it supports primitive data type like it,byte,long etc.,which are not objects. Because in JAVA we use data types like int, float, double etc which are not object oriented, and of course is what opposite of OOP is. That is why JAVA is not 100% objected oriented.

Answer :
1) A pipe is a form of redirection (transfer of standard output to some other destination) that is used in Linux and other Unix-like operating systems to send the output of one command/program/process to another command/program/process for further processing.

2) The Unix/Linux systems allow stdout of a command to be connected to stdin of another command. We can make it do so by using the pipe character ‘|’.

3) Pipe is also used to combine two or more commands, and in this, the output of one command acts as input to another command, and this command’s output may act as input to the next command and so on.

4) It can also be visualized as a temporary connection between two or more commands/ programs/ processes. The command line programs that do the further processing are referred to as filters.

Examples :
1) Listing all files and directories and give it as input to more command.
$ ls -l | more

2) Use sort and uniq command to sort a file and print unique values.
$ sort record.txt | uniq

3) Use head and tail to print lines in a particular range in a file.
$ cat sample2.txt | head -7 | tail -5

Answer :
1) Static variables are initialized only once.
2) The compiler persists with the variable till the end of the program.
3) Static variables can be defined inside or outside the function.
4) They are local to the block.
5) The default value of static variables is zero.
6) The static variables are alive till the execution of the program.

Here is the syntax of static variables in C language,

static datatype variable_name = value;

Here,
datatype − The datatype of variable like int, char, float etc.
variable_name − This is the name of variable given by user.
value − Any value to initialize the variable. By default, it is zero.

Ans : No 
Approach : Each domino we set on the chessboard will always take 1 Black and 1 White square.Therefore, 31 dominos will take 31 white square and 31 black squares exactly. On this chessboard however, we must have 32 black and 30 white squares. Hence it is not possible to do so.

Steps :
Let's call 5L jar as X and 3L jar as Y.

1) We'll take the first jar, i.e, X. Fill X completely.
2) Then empty the X content in Y. We are left with 2 L in the X.
3) Now we will empty the Y jar and then Fill 2L from X into Y. We are left with 0L in X and 2L in Y.
4) Now again we will fill X with 5L and then empty till Y gets full.
5) As Y is already full with 2L from previous operation so it can only accomodate 1L now from X. So when
Y jar is full automatically we will have 4L left in X. This is how we will calculate 4L