SDE - 1

This question is similar to House Robber-1 , the only difference being if we loot the first house then we cannot loot the last house and vice-versa . 

Approach for House Robber-2: 
Given an array nums and n=nums.size()
1) Initialise two vectors nums1 and nums2 , where nums1 contains all the elements of nums from index 0 to index n-2 and nums2 contains all the elements of nums from index 1 to index n-1.
2)Now , find the answer for nums1 and nums2 in the same way as House Robber-1.
3)Final Answer will be max(ans1,ans2) where ans1=answer for nums1 and ans2=answer for nums2


If you have not done House Robber-1 , here is a short approach on how to find the ans1 and ans2 .

Approach for House Robber-1
Given an array nums and n=nums.size()

1)Create a recursive function (int maxLoot(vector&nums , int idx) ) which returns the max answer that we can get for the array nums if we start traversing from index idx.

2)Now , for every element we have two options :

option1 = take that element and call maxLoot func for the rest of the array = nums[idx]+maxLoot(nums,idx+1)

option2=do not take that element at all = maxLoot(nums,idx+1)

3)Finally return max(option1 , option2)

4)Base Case : If idx>=n , simply return 0 as we cannot loot anymore houses.

5)Do not forget to memoise using a 1-D dp array
dp[idx]=max(op1,op2)

This problem is a simple recursive problem. But time complexity of simple recursive calls is exponential. In O(log(n)) this problem can be solved using a simple trick.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

This method will solve this question in O(log(n)).

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))


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)

Naive Solution:

Keep an array of size k. The idea is to keep the array sorted increasing order so that the k'th largest element can be found in O(1) time.
How to process a new element of stream?
For every new element in stream, check if the new element is smaller than current k'th largest element. If yes, then ignore it. If no, then remove the smallest element from array and insert new element in sorted order. Time complexity of processing a new element becomes O(k).

Efficient Solution:

Use Min Heap of size k to store k largest elements of stream. Thr k'th largest element is always at root and can be found in O(1) time.
How to process a new element of stream?
Compare the new element with root of heap. If new element is smaller, then ignore it. Otherwise replace root with new element and call heapify for the root of modified heap.

One way to solve it is to use two basic data structures:

-A resizable O(1) container elements (std::vector in C++, ArrayList in Java)
-A hash table elemToIndex which maintains mapping from an element to index.

Inserting an element val to the data structure involves two operations:
-elements.add(val)
-elemToIndex.put(val, elements.size() - 1)

GetRandom is just randomly choosing an index from 0 to elements.size() - 1.

Searching an element is easy, just find the element from the hash table.

Now the tricky part, remove. In an ideal case removing an element from an array is O(n). 
But here since we do not care about ordering, we can simply swap the element we want to delete with the last element, and pop off the last. Then update the map as well and we are done. This takes O(1) time and hence we achieved our target.

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.

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.