Skip to content

Latest commit

 

History

History
108 lines (84 loc) · 6.3 KB

README.md

File metadata and controls

108 lines (84 loc) · 6.3 KB

DSA Central 101

This Repository Contains Various Approaches to Solving a Problem, Serves as a Guide to Preparing for Interviews

How to Avoid TLE

  • Number of Elementary Operations that can be done in 1 Sec is 10^8. If your algorithm is achieving it in <=10^8 (Including Constraints), then we can use bruteforce approach to solve the problem.

Use the information in a question to your advantage! It will often implicitly tell you how efficient your algorithm should be to get full points. Consider the fact that a computer can run 10^8 iterations per second. You’re usually going to be given an array or string; call its size n. Note that you cannot be asked to come up with a solution better than O(n) in this case (even if one exists); the reason is that it takes linear time to input the test array itself! With that in mind,

  • If (n >= 10^4), aim for a O(n) or a O(n log n) solution.
  • If (n <= 10^3), aim for a O(n2) solution
  • I(n <= 10^2), aim for a O(n3) solution
  • If (n < 20), a O(2n) solution should be fine.

alt text

Time Complexities of Common Operations for Java Collections

Operation ArrayList LinkedList HashSet HashMap TreeMap
Access (get) O(1) O(n) N/A N/A O(log n)
Search (contains) O(n) O(n) O(1) O(1) O(log n)
Insert (add at end) O(1) O(1) O(1) O(1) O(log n)
Insert (add at specific index) O(n) O(n) N/A N/A O(log n)
Delete (remove at end) O(1) O(1) O(1) O(1) O(log n)
Delete (remove at specific index) O(n) O(n) N/A N/A O(log n)
Sort (using default comparator) O(n log n) O(n log n) N/A N/A O(n log n)
Sort (using custom comparator) O(n log n) O(n log n) N/A N/A O(n log n)
Count Occurrences O(n) O(n) O(n) O(n) O(n)
Synchronized View O(1) O(1) O(1) O(1) O(1)
Unmodifiable View O(1) O(1) O(1) O(1) O(1)

Note:

  • ArrayList and LinkedList are different implementations of the List interface.

  • HashSet, HashMap, and TreeMap are implementations of the Set and Map interfaces.

  • N/A indicates that the operation is not applicable for that particular data structure.

  • Synchronized View: Functions like Collections.synchronizedList(), Collections.synchronizedSet(), and Collections.synchronizedMap() return synchronized (thread-safe) views of the specified collections.

  • Unmodifiable View: Functions like Collections.unmodifiableList(), Collections.unmodifiableSet(), and Collections.unmodifiableMap() return unmodifiable views of the specified collections, making them read-only.

Best Resources for Preparation

Best Explanations(Theortical / Visually)

Best Problems Listed

Best Videos/Blogs for Learning Java

Best Tools / Sites for Understanding Algorithms and Problems

CheatSheets