55. Linked-List: (hard)

3. Flatten LL✅
4. Clone LL with random pointer & next pointer✅
---------------------------------------------------------------------------------------------------------------

1. Reverse in groups of size K⭐

Do not alter node's values, instead only change links
----------------------------
Approach- Check if k nodes exist & reverse one group at a time

-----------------------------------------------------------------------------------------------------------------------------

2. Rotate a LL

Brute- time: O(n)   space:O(n)

store all elements in an array & then rotate the array & then over write the LL with this rotated array elements
--------------
Better- time: O(nk)  space: O(1)

do this k times- remove last node and add it to the front
before this do (k = k % n) so we can reduce extra iterations
----------------
Optimal- time: O(n)  space: O(1)

just change link of (n-k)th node and point it to null
the nodes from (n-k+1)th node to the last node comes to the start and 
last node (nth) now points to first node

-----------------------------------------------------------------------------------------------------------------------------

3. Flattening a LL⭐

------------------------------------------------------
Brute- time: O(nlogn)  space: O(n)

store all elements in a vector
sort the vector
over write the list with elements from this vector

--------------------------------------------------------
Optimal-  time: O(n*m)  space: O(1) ⭐

using divide & conquer

- since, each LL is already sorted vertically, so we can merge them 

- use 2 pointers to merge 2 vertical LL

- we will create a dummy node to help in the process

----------------------------------------------------------------------------------------------------------------------------

4. Clone a LL with random & next ptr-

Brute- time: O(n)  space: O(n)

using a map
(use unordered map for O(1) operations)

1. create a copy of old LL with just next pointers taken into account at first
2. Also, while doing this map old nodes with new nodes in a map
3. Now for random pointer connections in new LL , traverse the old LL and use the map

-----------------------------------------------------------
Optimal- time: O(n)  space: O(1)

( by links changing )

1. insert clone nodes in b/w nodes of original LL

2. assign random ptrs to clone nodes

3. assign next ptrs to clone nodes ⭐
(connect clones to ans LL & remove clones from b/w nodes &  join original nodes back  )

  

-----------------------------------------------------------------------------------------------------------------------------

5. Design browser history-

write class with following functions-
1. browser(homepage)
2. visit(url)
3. back(steps)
4. forward(steps)

-----------------------------------------------------------------------------------------------------------------------------

6. LRU cache-

- initialise a data structure with a given capacity x
- we can add x no. of key value pairs
- if we try to add an element, after capacity is full, then first removal of LRU takes place & then new element goes to top
- if we add/ update/ fetch an element, then it goes to the top in LRU
- get & put run in O(1) time
------------------------------------------------------------
(see entire code on my LC submission)
----------------------------------------------------

Implementation-

Brute: vector based

create a vector <pair<int,int>> :

1. get():  iterate to find key, if found return value, and remove this key from current position and push back it to the last, if key is not found return -1

2. put(): iterate & check if it already exists, if yes, then remove it from current position & push back to the last, else simply push back new element if capacity allows, else remove LRU element and then push back current element to the last
--------------------------------------------------------
Optimal: DLL based

since in vector based implementation, erasing was costly:
- so we now prefer linked list as our data structure, so erase can happen in constant time by just changing links

- also, we will use a map storing (element, node address) so that we do not have to traverse the entire Linked list to reach the node to be deleted
- also we prefer DLL over SLL so that we can easily change links
- we will use a dummy head & dummy tail for simplifying LL related operations
--------------------------
1. create a dummy head & a dummy tail storing (key, value) pairs
2.  create a map< int, Node* > for constant access to address of a node corr to a key

4. Fetching a node data-
- find node from map using key, return its value
- delete this node from curr position from LL
- insert it after head

2.1 Updating existing node's value:-
- delete from existing pos
- insert after head 
- change value 

2.2 Inserting if (cap = full):
- delete last node (tail->prev)
- also remove it from map
- insert new node after head
- also update map with the new node

2.3 Inserting new node- 
- check if node exist or not using map
- if do not exist, then insert it just after the head
- update the map

----------------------------------------------------------------------------------------------------------------------------

7. LFU cache-⭐

(Least Frequently used cache)

- this time the node with least freq is deleted
- in case of a tie, we prefer the node which is LRU
- freq of a key is incremented at insertion/ updation/ fetching

--------------------------------------------

Data structures to be used- 

1. map < freq, list of keys > 
2. map < key, node > 

3. int minfreq (so we do not need to iterate entire map to find minimum frequency)
4. DLL ( each node stores {key, val, its current freq} )
--------------------------------------------
1. For insertion: 
- Check if node to be inserted already exist or not :use map
- Check if capacity is full :use map
( pop Lru element from list of keys with minfreq )
- Now insert the node in list as per lru logic and update both maps and minfreq
------
2. For fetching:
- delete node from curr freq list
- add it to next freq list as per lru 

- if freq list for a freq is empty, then update minfreq variable & create a new list
-----------
see LC submission for code

-----------------------------------------------------------------------------------------------------------------------------