batra98/Useful-Resources

Contains topic-wise sorted resources that I think are useful.

Useful Resources for Placement 2020

A to-do list of programing and non-programing topics to study.

---

CP related topics

Complexity analysis

• Cheat Sheet

Data Structures

• Arrays
• Linked Lists
• Stack
  • Nearest Smallest number on left
• Queue

Advanced Data Structures

• Hash Table [unordered set,map in C++]

Search

• Binary search [upper_bound(), lower_bound(), binary_search() in C++]
• Binary search on solution
• Ternary search
  • Theory
    • Ternary Search and its applications
  • Problems

Bit Operations

• Bitmasking
• Bitwise Operations
  • AND in l to r.

Trees & Graphs

• Binary Search Trees (BSTs).
• Heap
• Trie
• Pair with Minimum Xor.
• Segment Trees
• AVL [theory]

Graph Algorithms

• DFS
  • lexicographic shortest path
  • topological sorting
  • components
• BFS
  • shortest paths in unweighted or weighted with constraints
• cycle detection
  • directed graph
  • undirected graph
• tree specific (tree is always undirected)
  • ONLY 1 PATH between two nodes
  • LCA [used to find distance between two nodes]
    • Naive O(N)
    • Using euler tour
    • Lec: 18 class notes
• shortest paths (SSSP)
  • topo sort approach in DAG
  • bellman ford
    • identify negative weight cycle (reachable from source)
    • SSSP for any general graph
  • dijkstra
• spanning trees (for weighted connected undirected graph)
  • cycle and cut property
  • prim's algorithm (selects vertices in mst)
  • prim O(N^2) modification for dense graph
  • kruskal's algorithm (selects edges in mst)
  • DSU
• shortest paths (APSP)
  • repeated squaring (V^3logV)
  • floyd warshall (V^3)
  • johnsons algorithm (V(V+E)logV)

Sorting

• inversion count
• comparison between different algos
• custom sort in C++

Recursion

Hashing

DP

• knapsack
  • 01 knapsack
  • fractional knapsack (greedy by sorting based on value/weight ratio)
• LIS
• coin change
• edit distance
• subset sum (similar to knapsack and coin change)
• minsum partition
• longest common subsequence
• longest common substring
• longest pailndromic subsequence
• longest palindromic substring
• PRINTING DP
• max subarray

Strings

• Palindrome problems -Longest Panlindromic Substring.

Number Theory

• GCD
• permutation [also inbuilt in C++]
• Prime factorization
• Prime sieve
• FEP
• modular operations
• Fibonacci series
• Combinatorics
• Probability [Specific to finance companies]
• newton method of square root

Standard Problems

• Histogram using stacks
• Linked list loop detection

CP Theoretical

• NP, NP-Complete
• Approximate Algorithms

Miscellaneous

• Atcoder Alsing D - Maths
• Recursion Tree
• Partition into K equal sum subsets.
• https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/.

---

Non CP related topics

Javascript

• callbacks
• promise
• event loop
• closure
• async-await
• generators
• prototypes - methods
• prototype Inheritance
• event bubbling
• sets
• local storage and cache
• Array functions - reduce
• call, apply, bind
• XMLHTTPRequest | Ajax
• binding - new, explicit, implicit
• web APIs

Object-Oriented Programming

Operating System

• Cache
  • LRU Cache
    • Theory
      • The Magic of LRU Cache (100 Days of Google Dev)
      • Implementing LRU
• Processes and Threads
  • Operating Systems.
  • Main Topics
    • Processes, Threads and Concurrency.
      • Processes
      • Threads
      • Difference between process and threads.
      • Locks
      • Mutexes
      • Semaphores
      • Monitors
      • Deadlock
    • Interrupts, Context Switching.
    • Paging, Segmentation and Virtual Memeory.
• Scheduling
• Endianess

Computer Networks

Unix Command line tools

Distributed Systems

Database Systems

---

HR Questions

• Tell me about yourself

---

Previous Year

---