Java OOP
&
Collections
Mastery

public class BankAccount {
    private double balance;   // encapsulated

    public void deposit(double amount) {
        if (amount > 0) balance += amount;
    }
    public double getBalance() { return balance; }
}

class Animal {
    void breathe() { System.out.println("Breathing"); }
}
class Dog extends Animal {
    void bark() { System.out.println("Woof!"); }
}
// Dog can breathe() AND bark()

class Shape {
    void draw() { System.out.println("Drawing Shape"); }
}
class Circle extends Shape {
    @Override
    void draw() { System.out.println("Drawing Circle"); }
}
Shape s = new Circle();  // Runtime polymorphism
s.draw();  // "Drawing Circle" — not "Drawing Shape"

abstract class Vehicle {
    abstract void start();   // "kaise start hoga" chhupa hai
    void stop() { System.out.println("Stopping"); }
}
class Car extends Vehicle {
    void start() { System.out.println("Car starts with key"); }
}

Animal a = new Dog();  // compile time: type = Animal
a.sound();             // runtime: JVM checks Dog's vtable → Dog.sound()

// IS-A
class Dog extends Animal { }  // Dog IS-A Animal

// HAS-A
class Car {
    private Engine engine;  // Car HAS-A Engine (Composition)
}

// Assume ye allowed hota — INVALID Java code
class A { void greet() { print("A"); } }
class B extends A { void greet() { print("B"); } }
class C extends A { void greet() { print("C"); } }
class D extends B, C { }  // D.greet() → B ka lega ya C ka?

interface B { default void greet() { print("B"); } }
interface C { default void greet() { print("C"); } }
class D implements B, C {
    public void greet() { B.super.greet(); }  // must override
}

class Animal {
    Animal create() { return new Animal(); }
}
class Dog extends Animal {
    @Override
    Dog create() { return new Dog(); }  // Dog is subtype of Animal ✓
}

class Address {
    String city;
    Address(String c) { city = c; }
}

class Person implements Cloneable {
    String name;
    Address address;

    // SHALLOW COPY (default clone)
    protected Object shallowClone() throws CloneNotSupportedException {
        return super.clone();  // address reference copied, not new object
    }

    // DEEP COPY
    protected Object deepClone() throws CloneNotSupportedException {
        Person cloned = (Person) super.clone();
        cloned.address = new Address(this.address.city);  // new Address object
        return cloned;
    }
}

interface Serializable { }  // No methods — just a tag!
interface Cloneable { }
interface Remote { }       // java.rmi

interface Greeter {
    void greet(String name);  // abstract — implement karna mandatory

    default void greetAll(String... names) {  // default — override optional
        for (String n : names) greet(n);
    }

    static Greeter formal() {  // static — interface se call karo
        return name -> System.out.println("Good day, " + name);
    }
}

@FunctionalInterface
interface Calculator {
    int calculate(int a, int b);  // only ONE abstract method
}

// Lambda = anonymous implementation of Functional Interface
Calculator add = (a, b) -> a + b;
Calculator multiply = (a, b) -> a * b;

System.out.println(add.calculate(3, 4));  // 7

interface Config {
    int MAX_SIZE = 100;  // automatically: public static final int MAX_SIZE = 100;
    // int count = 0;  ← This is ALSO final, can't be changed!
}

abstract class DataMiner {
    final void mine() {   // template method — final so can't be overridden
        String data = extractData();
        String parsed = parseData(data);
        analyzeData(parsed);
    }
    abstract String extractData();   // subclass implements
    abstract String parseData(String d);
    void analyzeData(String d) { System.out.println("Analyzing: " + d); }
}

interface SortStrategy { void sort(int[] arr); }
class Sorter {
    private SortStrategy strategy;
    void setStrategy(SortStrategy s) { strategy = s; }
    void sort(int[] arr) { strategy.sort(arr); }
}
// Runtime mein strategy change kar sakte hain!

abstract class Animal {
    protected String name;
    protected int age;

    Animal(String name, int age) {  // constructor in abstract class
        this.name = name;
        this.age = age;
        System.out.println("Animal created: " + name);
    }
}
class Dog extends Animal {
    Dog(String name, int age) {
        super(name, age);  // Abstract class constructor called here
    }
}
// new Dog("Rex", 3) → prints "Animal created: Rex"

class Counter {
    static int totalCount = 0;  // shared — Method Area
    int id;                       // per object — Heap

    Counter() {
        totalCount++;
        id = totalCount;
    }
}
Counter c1 = new Counter(); // totalCount=1, c1.id=1
Counter c2 = new Counter(); // totalCount=2, c2.id=2

class Demo {
    static int x;

    static {
        x = 10;
        System.out.println("Static Block 1: x = " + x);
    }

    static {
        x = 20;
        System.out.println("Static Block 2: x = " + x);
    }

    Demo() { System.out.println("Constructor"); }
}

/* Output when: new Demo(); new Demo();
   Static Block 1: x = 10   ← only once!
   Static Block 2: x = 20   ← only once!
   Constructor
   Constructor                ← twice
*/

class Parent {
    static void greet() { System.out.println("Parent static"); }
    void hello() { System.out.println("Parent instance"); }
}
class Child extends Parent {
    static void greet() { System.out.println("Child static"); }  // HIDING
    @Override
    void hello() { System.out.println("Child instance"); }  // OVERRIDING
}

Parent p = new Child();
p.greet();   // "Parent static" ← compile-time type = Parent!
p.hello();   // "Child instance" ← runtime type = Child!

// Best approach: Bill Pugh Singleton (Initialization-on-demand holder)
public class Singleton {
    private Singleton() { }  // private constructor

    private static class Holder {
        static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getInstance() {
        return Holder.INSTANCE;  // lazy, thread-safe, no sync overhead
    }
}

// Double-Checked Locking (less preferred)
public class Singleton2 {
    private volatile static Singleton2 instance;  // volatile important!
    public static Singleton2 getInstance() {
        if (instance == null) {
            synchronized (Singleton2.class) {
                if (instance == null) instance = new Singleton2();
            }
        }
        return instance;
    }
}

enum EnumSingleton { INSTANCE; }  // Thread-safe, Serialization-safe

class Test {
    int getValue() { return 1; }
    // double getValue() { return 1.0; } ← COMPILE ERROR — ambiguous

    // Ye overloading hai (parameters different):
    int add(int a, int b) { return a + b; }
    double add(double a, double b) { return a + b; }  // ✓ valid
}

class Parent {
    void read() throws IOException { }
}
class Child extends Parent {
    void read() throws FileNotFoundException { }  // ✓ narrower
    // void read() throws Exception { }  ← ✗ broader — COMPILE ERROR
    // void read() throws RuntimeException { }  ← ✓ unchecked OK
}

// Primitives — pure call by value
void change(int x) { x = 100; }
int a = 5;
change(a);
System.out.println(a); // 5 — unchanged! New copy of 5 passed

// Objects — reference value copied (NOT the object)
void modify(StringBuilder sb) {
    sb.append(" World");  // ✓ modifies original — same object
    sb = new StringBuilder("Hello");  // ✗ local reassignment only
}
StringBuilder s = new StringBuilder("Hello");
modify(s);
System.out.println(s); // "Hello World" — append worked, reassign didn't

String s1 = "Hello";  // String Pool mein jaata hai
String s2 = "Hello";  // Same pool reference
String s3 = new String("Hello");  // Heap mein new object

System.out.println(s1 == s2);      // true (same pool reference)
System.out.println(s1 == s3);      // false (different object)
System.out.println(s1.equals(s3)); // true (same content)

s1 = s1 + " World";  // s1 doesn't change! New String object created

// final
final int MAX = 100;          // constant — can't reassign
final class String { }       // can't extend
final void doSomething() {}  // can't override

// finally
try {
    // risky code
} catch (Exception e) {
    // handle
} finally {
    // ALWAYS runs — even if return/exception in try or catch
    connection.close();  // cleanup here
}

// finalize (DEPRECATED — don't use!)
protected void finalize() throws Throwable {
    // called by GC before collecting — unpredictable, slow
}

try {
    System.exit(0);  // JVM terminates here
} finally {
    System.out.println("This NEVER prints");  // skipped!
}

int test() {
    try { return 1; }
    finally { return 2; }  // returns 2! finally overrides try's return
}

// Old way — verbose and error-prone
BufferedReader br = null;
try {
    br = new BufferedReader(new FileReader("file.txt"));
} finally {
    if (br != null) br.close();  // Can itself throw exception!
}

// New way — clean, automatic
try (BufferedReader br = new BufferedReader(new FileReader("file.txt"))) {
    String line = br.readLine();
}  // br.close() called automatically — even if exception thrown

class Circle {
    final double radius;  // blank final — no value yet

    Circle(double r) {
        radius = r;  // must initialize in constructor
    }
    // Cannot have: Circle() { } ← compiler error — radius not initialized
}

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));

// 1. Index-based — OK for ArrayList, BAD for LinkedList
for (int i = 0; i < list.size(); i++) { ... }

// 2. for-each — uses Iterator internally, safe for reading
for (String s : list) { ... }

// 3. Iterator — only safe way to remove during iteration
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("b")) it.remove();  // ✓ SAFE
}

// ConcurrentModificationException — structural mod during for-each
for (String s : list) {
    if (s.equals("b")) list.remove(s);  // ✗ THROWS CME!
}

// Java 8 solution
list.removeIf(s -> s.equals("b"));  // ✓ Safe and clean

// Simplified HashMap internals
class HashMap<K, V> {
    Node<K, V>[] table;  // Array of buckets
    int size;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;  // linked list for collision
    }

    void put(K key, V value) {
        int hash = key.hashCode() ^ (key.hashCode() >>> 16);
        int index = hash & (table.length - 1);  // bucket index

        // Check for existing key
        for (Node<K,V> n = table[index]; n != null; n = n.next) {
            if (n.hash == hash && n.key.equals(key)) {
                n.value = value;  // update existing
                return;
            }
        }
        // Add new node to bucket
        table[index] = new Node(hash, key, value, table[index]);
        size++;
        // Check if resize needed
        if (size > table.length * DEFAULT_LOAD_FACTOR) resize();
    }
}

static final int TREEIFY_THRESHOLD = 8;   // 8+ entries → convert to tree
static final int UNTREEIFY_THRESHOLD = 6;  // resize ho toh tree → list back
static final int MIN_TREEIFY_CAPACITY = 64; // total capacity ≥ 64 needed

class MutableKey {
    String data;
    int hashCode() { return data.hashCode(); }
}

Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey();
key.data = "hello";
map.put(key, "World");  // stored at bucket for "hello".hashCode()

key.data = "bye";       // key MUTATED! hashCode now different!
map.get(key);           // looks in WRONG bucket → null!

class HashSet<E> {
    private final HashMap<E, Object> map = new HashMap<>();
    private static final Object PRESENT = new Object();  // dummy value

    boolean add(E e) {
        return map.put(e, PRESENT) == null;  // key = element, value = dummy
    }

    boolean contains(Object o) {
        return map.containsKey(o);
    }
}

// HashMap null handling
Map<String, Integer> map = new HashMap<>();
map.put(null, 1);      // ✓ null key goes to bucket 0
map.put("a", null);   // ✓ null value allowed

// VIOLATION: equals without hashCode override
class BadKey {
    int id;
    public boolean equals(Object o) {
        return ((BadKey) o).id == this.id;
    }
    // hashCode NOT overridden → inherits Object.hashCode (memory address)
}

BadKey k1 = new BadKey(); k1.id = 1;
BadKey k2 = new BadKey(); k2.id = 1;
k1.equals(k2);  // true (same id)

Set<BadKey> set = new HashSet<>();
set.add(k1);
set.contains(k2);  // FALSE!! Different hashCode → different bucket!

// All go to same bucket — worst case O(n)
Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(i * 16, "val");  // all map to bucket 0 with capacity 16!
}

class Point {
    private final int x, y;  // final = immutable

    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);  // good hash combining both fields
    }
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "origin");
map.get(new Point(1, 2));  // "origin" ✓ — equals+hashCode both correct

Map<String, List<Integer>> map = new HashMap<>();

// get — null return karta hai if key missing
map.get("a");  // null

// getOrDefault — default value deta hai
map.getOrDefault("a", new ArrayList<>());  // empty list (not stored)

// computeIfAbsent — stores AND returns default
map.computeIfAbsent("a", k -> new ArrayList<>()).add(1);
// map now has "a" → [1]

// merge — common pattern: word frequency count
Map<String, Integer> freq = new HashMap<>();
freq.merge("apple", 1, Integer::sum);  // increment by 1, or put 1 if absent

// LinkedHashMap — insertion order preserved
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("banana", 2);
linked.put("apple", 1);
linked.put("cherry", 3);
System.out.println(linked);  // {banana=2, apple=1, cherry=3} — insertion order!

// LRU Cache — access order mode
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String,Integer> eldest) {
        return size() > 3;  // keep max 3 entries
    }
};

Set<String> set = new LinkedHashSet<>();
set.add("c"); set.add("a"); set.add("b");
System.out.println(set);  // [c, a, b] — insertion order maintained

// Use case: Deduplicate while preserving order
List<String> withDupes = Arrays.asList("x", "y", "x", "z", "y");
Set<String> unique = new LinkedHashSet<>(withDupes);
System.out.println(unique);  // [x, y, z] — unique, insertion order

// Comparable — natural order
class Student implements Comparable<Student> {
    String name; int age;
    public int compareTo(Student other) {
        return Integer.compare(this.age, other.age);  // sort by age
    }
}

// Comparator — custom, multiple orderings
Comparator<Student> byName = Comparator.comparing(s -> s.name);
Comparator<Student> byAgeDesc = Comparator.comparingInt(Student::getAge).reversed();
Comparator<Student> byNameThenAge = Comparator.comparing(Student::getName)
    .thenComparingInt(Student::getAge);

list.sort(byName);
TreeSet<Student> ts = new TreeSet<>(byName);  // custom order

TreeSet<String> ts = new TreeSet<>();
ts.add(null);  // NullPointerException!

// Workaround: Custom Comparator that handles null
TreeSet<String> ts2 = new TreeSet<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
ts2.add(null); ts2.add("b"); ts2.add("a");
System.out.println(ts2);  // [null, a, b]

// Min-Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
minHeap.poll();  // 1 (minimum)

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
maxHeap.poll();  // 5 (maximum)

// Custom object priority
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    LRUCache(int capacity) {
        this.capacity = capacity;
        // accessOrder=true: moves accessed entry to end
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
                return size() > capacity;  // remove LRU when full
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);  // moves to end (most recent)
    }

    public void put(int key, int value) {
        cache.put(key, value);  // auto removes eldest if over capacity
    }
}

// Test
LRUCache lru = new LRUCache(2);
lru.put(1, 10);
lru.put(2, 20);
lru.get(1);      // 10 — key 1 is now most recent
lru.put(3, 30); // evicts key 2 (least recently used)
lru.get(2);      // -1 — evicted!

public char firstNonRepeating(String s) {
    // LinkedHashMap preserves insertion order
    Map<Character, Integer> freq = new LinkedHashMap<>();

    for (char c : s.toCharArray()) {
        freq.merge(c, 1, Integer::sum);
    }

    for (Map.Entry<Character, Integer> e : freq.entrySet()) {
        if (e.getValue() == 1) return e.getKey();
    }
    return '\0';
}
// "aabbcde" → 'c'; Time: O(n), Space: O(1) — max 26 chars

public List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> map = new HashMap<>();

    for (String word : words) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);  // "eat","tea","ate" → "aet"

        map.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
    }

    return new ArrayList<>(map.values());
}
// Input: ["eat","tea","tan","ate","nat","bat"]
// Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
// Time: O(n·k·log k) where k = max word length

public int[] topKFrequent(int[] nums, int k) {
    // Step 1: Count frequencies
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // Step 2: Min-heap of size k
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        Comparator.comparingInt(freq::get)
    );

    for (int key : freq.keySet()) {
        pq.offer(key);
        if (pq.size() > k) pq.poll();  // remove least frequent
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = pq.poll();
    return result;
}
// Time: O(n log k), Space: O(n+k)

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[] { seen.get(complement), i };
        }
        seen.put(nums[i], i);  // store: value → index
    }
    throw new IllegalArgumentException("No solution");
}
// Time: O(n), Space: O(n) — one pass HashMap