55. LL- hard

1. Flatten LL✅
2. Rotate LL✅
3. reverse LL in groups of size K✅
4. Clone LL with random pointer & next pointer✅
5. Design Browser History✅
6. LRU cache✅
7. LFU cache🔥✅

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

1. Reverse in groups of K
step-1: put temp at head
step-2: figure out kth node
step-3: point kth node's next to null but before it preserve the next node
step-4: reverse this group of LL
step-5: do , head = kth node & prvNode = temp 
step-6: do, temp = next node (which we preserved in step 3) 
step-7: repeat from step 2
step-8: if for a group there are < k elements, then attach all elements of such group starting from temp to the previous node.

-----------------------------------------------------------------------------------------------------------------------------
2. Rotate a LL

-----------------------------------------------------------------------------------------------------------------------------
3. Flattening a LL⭐⭐⭐
given- a LL with each node having next and child pointer
         - vertical LL are sorted
solution- flattened sorted vertical LL
----------------------
Brute-

Optimal-
use 2 pointers to merge 2 vertical LL-


----------------------------------------------------------------------------------------------------------------------------
4. Clone a LL with random & next ptr-
Brute-

1. saare nodes ki copy create krke map mein old nodes ko new nodes se map krdo
2. old LL pe traverse krke map ke according new LL ke nodes ke next aur random pointers ko set karo
3. new LL ka head return kardo
-----------------------------------------------------------
Optimal-⭐⭐

1. insert copy nodes in between og list
2. assign random ptrs of clone nodes
3. assign next ptrs to clone nodes by extracting clones from modified LL and restoring og LL


  
-----------------------------------------------------------------------------------------------------------------------------
5. Design browser history-
write class with following functions-
1. browser(homepage)
2. visit(url)
3. back(steps)
4. forward(steps)
-----------------------------------------------------------------------------------------------------------------------------
6. LRU cache-
(Least Recently used cache)
matlab jisko fetch ya update krte jaoge vo key value pair LRU mein upar aata jayega
aur agar capacity full hone ke baad add kr rhe ho kisi pair ko toh LRU wala hatega aur insert wala top pe aayega
-----------------------------(see entire code on my LC submission)
Implementation- (DLL)

1. take a dummy head and a dummy tail storing key, value pairs

2. create a map< key, Node* > to keep track of already added keys

3. for adding new node:-  check if node exist or not using map, if do not exist then insert it just after the head & add it to the map

4. for getting node data:- find node from map using key, return its value => delete this node from curr position from LL and insert it after head

5. to add new node when cap = full, delete (tail->prev) node from list and from map as well => create new node after head => also update map with this node

6. updating a node:- update its value => delete from existing pos => insert after head 

----------------------------------------------------------------------------------------------------------------------------
7. LFU cache-⭐
(Least Frequently used cache)
this time the node with least freq is deleted and in case of a tie, we prefer the node which is LRU
freq of a key is incremented at insertion, updation or fetching

ek tarah se freq ko vertically mein dekho aur lru ko ek particular horizontal level pe dekho
--------------------------------------------
here, we will need 2 extra stuff- 
1. map < freq, dll > mpp
2. int minfreq
--------------------------------------------
1. check if node to be inserted already exist or not
2. check if capacity of list is not full
3. now insert the node in list as per lru logic and update both maps and minfreq
-----------
if cap is full and u want to insert then check for list corr to minfreq and check if there are >1 elements in it then pop out as per lru
-----------
for fetching-->delete node from curr freq list and add to next freq list as per lru and return ans
if freq list for a freq is empty then update minfreq variable
-----------







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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more