- Follow the Rule: 108 Operations
| Length of Input (N) | Worst Accepted Algorithm |
|---|---|
| ≤ [10..11] | O(N!), O(N6) |
| ≤ [15..18] | O(2N * N2) |
| ≤ [18..22] | O(2N * N) |
| ≤ 100 | O(N4) |
| ≤ 400 | O(N3) |
| ≤ 2000 | O(N2 * logN) |
| ≤ 104 | O(N2) |
| ≤ 105 | O(N * logN) |
| ≤ 106 | O(N), O(logN), O(1) |
-
If we have given any string let's say "abc":
- Total Substring/Subarray: n(n+1)/2, here we have 6 (a, ab, abc, b, bc, c).
- Total Subsequence/Subset: 2^n, here we have 8 (_, a, b, c, ab, bc, ac, abc).
-
How many operations can a CPU do?
- It can do 1,000,000 operations per 1/1000th of a second.
-
Handshake Formula:
handshake(n) = (n-1) + handshake(n-1) = (n-1) + (n-2) + handshake(n-2) = (n-1) + (n-2) + .... 1 + 0 = n * (n - 1)/2 -
Catalan Number:
- Recursive Formula:
-
General Formula:
(2n)! / ((n + 1)!n!)
- Divide the number by 16.
- Get the integer quotient for the next iteration.
- Get the remainder for the hex digit.
- Repeat the steps until the quotient is equal to 0.
| Division by 16 | Quotient | Remainder | Hex |
|---|---|---|---|
| 7562 / 16 | 472 | 10 | A |
| 472 / 16 | 29 | 8 | 8 |
| 29 / 16 | 1 | 13 | D |
| 1 / 16 | 0 | 1 | 1 |
| Division by 16 | Quotient | Remainder | Hex |
|---|---|---|---|
| 35631 / 16 | 2226 | 15 | F |
| 2226 / 16 | 139 | 2 | 2 |
| 139 / 16 | 8 | 11 | B |
| 8 / 16 | 0 | 8 | 8 |
- Arrays:
- Sudoku and chess boards are 2D arrays.
- Contacts on a cell phone.
- Your viewing screen is also a multidimensional array of pixels.
- 2D arrays (as matrices) are used in image processing.
- Matrix:
- Matrices are used for making seismic surveys.
- Used for plotting graphs, statistics, and surveys and also to do scientific studies and research in almost all different fields.
- String:
- Spam email detection.
- Plagiarism detection.
- Linear Search:
- Finding a word in a lexicographically-unsorted physical dictionary book.
- Binary Search:
- Finding Page Number in a Book, e.g., Target Page Number is 35, you open at Page No. 15, it’s less, you move ahead and open 43, it is greater, you again move backward.
- Linked List:
- The Browser's Next and Previous Button (Linked List of URLs).
- A Music Player that allows you to skip to the next or previous song (Doubly Linked List).
- In the Ludo game, the turn was passed to each player in a circular manner (Circular Linked List).
- Stack:
- Undo/Redo operation.
- Recursion (Inbuilt Stack).
- Used in IDEs to check for proper parentheses matching.
- Scratch card’s earned after Google pay transaction.
- Queue:
- Your browser deletes the history past one month.
- If you delete a picture on your phone, it will be in the "recently deleted" folder, which says "the images will be deleted permanently after one week."Here, all the images are stored in the queue, so it's easier to pop them from the rear, based on the image deletion date.
- Waiting list: During online registration, sometimes you'll be put on the waiting list, all the requests are stored in the queue.
- Tree:
- File system: Folders and subfolders (N-ary tree).
- E-commerce websites : Category -> Sub-categories -> Products.
- Auto-suggestion when you google or Autocomplete feature in searching (Trie).
- Graph:
- Uber, Ola cab booking: show me the nearest available cars (BFS)
- Scheduling Problems (DFS).
- While booking buses/flights, you get a list of available routes.
- In Facebook, users are considered to be the vertices, and if they are friends, then there is an edge running between them. Facebook’s "friend suggestion" algorithm uses graph theory. Facebook is an example of an undirected graph.