- Auxiliary space complexity: Its the space required by the algorithm only, not taken by the inputs.
object.hasOwnProperty() Source: MDN - Click here
- Array.slice() => O(n)
- Array.splice() => O(n)
- Why pseduo code is important? Becoz often times problems asked in interview are not supposed to be solved but they want to know the approach you have formulated so just in case you run of time atleast the interviewer know where you're heading.
More short solution:
FYI: You can state in interview that in some cases regular expression can be more expensive as we can see the stats for it in below case study:
- so we can use charcodeAt() fn to re-write that fn to make it more efficient like that:
- Commonly Patterns
Anagrams Problem can be solved by use of Frequency Counter Patterns as well:
Solution of Anagrams Question:
- Solution with Two Pointer (O(n)) and another O(n) solution from author:
Question:
Solution with "Sliding Window" pattern:
Divide and Conquer Pattern:
Question:
Naive Solution:
Solution with Divide and Conquer Pattern:
- Recursion:
- current function called is always on top of the "Call Stack":
- Sample question without recursion:
Same above sample question with recursion:
Sum Range function wth recursion:
Iterative (i.e, using iterations or Non-recursive) Solution for finding factorial:
Recursive solution for finding factorial:
- collectOddValues() fn with recursion pattern:
- Pure Recusion (no nested recursive fn)
Linear Search:
- Binary Search Pseudocode:
Time Complexity for binary search?
Naive String Search: In main string, we find the nummber of match found for sample string.
Pseudeo Code:
From author:
Sorting:
- Sound of sorting Algorithms: Click here @ YouTube Playlist
- Sorting Algorithms Animations | Toptal®: Click here
Bubble Sort: (Also you can browser website: visualgo.net)
So two pairs of items are compared and larger one is switched to right side if thats the case. So this makes the sorting done for the last item, i.e, the last item is definitely the largest number in the array after the first (n-1) iterations over the array. Next we do it again starting from start again.
Bubble Sort Pseudocode:
Selection Sort
Pseudo code for Selection sort:
Insertion Sort - Really good when we want to put new item into the already sorted array becoz it knows exactly where to put the element.
FYI: Insertion and Bubble sort performs very good when data is nearly sorted. See here.
Learn Insertion sort here by ~ Tekena: Insertion sort in 2 minutes: Click here
My simplified way using i as key index for incrementor:
My Demonstration with vscode breakpoints:
insertion_sort.mp4
Merging Arrays Pseudo code:
Merge arrays code:
Callstack for merge sort:
- Quick Sort - Intro (NEED TO REVIEW BACK)
- Radix Sort - TODO: Need to do this. 17. Radix Sort
Folder sizes:
Data Structures:
Array:
Singly Linkedlist:
Hash table:
Binary Heap:
Binary Search Tree:
Graph - Unweighted Undirected Graph
Graph - Unweighted Directed Graph
Popular Quetions in Interviews:
- reverse a singly linkedlist
- implement a priority queue
- balance a binary tree
Gps data suits graph data structure becoz its easy find the shortest path distance b/w two values:
Singly Lined Lists
BigO of Doubly Linked List:
stack and queue are collections
- stack is LIFO (Last in first out)
- queue is FIFO (first in first out)
There are more than one way of implementing the STACK:
- Array Implementation
- Linked List implementation
Builtin Array data structure in javascript uses STACK data structure principle:
Builtin Arrays also works on QUEUE principles as well as far as FIFO is concerned: (But internally compiler needs to re-index the rest of the items in the array when you insert/remove at the beginnign and that is very costly as we studied earlier becoz of re-indexing of those items):
Big O of STACK:
Queue: First in first out. Example: Airport line when you're buying tickets. So the first person in the line gets the ticket first.
Queue implementation with builtin arrays(east to use but not the best implementation for queue as removing/adding from top is quite costly in builin array methods i.e, shift and push):
Queue using Unshift/pop
BigO Queue:
Tree
Use of tree data structure:
BST
Inserting node in BST: