Programming, OOP, Data Structures (Java & Python)

DSSSB TGT CS — Section B P1 (Rank 5). Concise MCQ-ready notes.

---

1. OOP Pillars

Pillar	Meaning	Exam keyword
Encapsulation	Bundle data + methods; hide internals	private fields, getters/setters
Inheritance	Child reuses/extends parent	extends (Java), IS-A
Polymorphism	Same interface, different behavior	overloading / overriding
Abstraction	Show essential, hide detail	abstract class / interface

• Compile-time polymorphism: method overloading (same name, different params)
• Runtime polymorphism: method overriding (subclass redefines; dynamic dispatch)

Trap: Overloading ≠ overriding. Overriding needs inheritance + same signature (compatible return).

---

2. Class vs Object; Constructors

Class	Object
Blueprint / template	Instance of a class
Defines attributes & methods	Occupies memory at runtime

Constructor

• Special method to initialize object
• Same name as class (Java); no return type
• Default constructor if none written (Java)
• Parameterized constructor sets values
• Constructor overloading allowed
• Called with new (Java)

---

3. Java Basics

JVM & bytecode

• Source .java → compiler → bytecode .class → JVM executes
• “Write once, run anywhere” via JVM on each platform
• JRE = JVM + libraries; JDK = JRE + development tools

Access modifiers

Modifier	Class	Package	Subclass	World
private	Y	N	N	N
default (package)	Y	Y	N*	N
protected	Y	Y	Y	N
public	Y	Y	Y	Y

*Subclass outside package: protected OK for inheritance access; default not.

static

• Belongs to class, not instance
• Shared among objects; callable via ClassName
• Static methods cannot use instance (this) members directly

Interface vs Abstract class

Feature	Abstract class	Interface
Instantiation	No	No
Methods	Abstract + concrete	Abstract (+ default/static in modern Java)
Fields	Instance fields OK	Typically public static final
Inheritance	One class extends one abstract	Class can implement many interfaces
Constructor	Can have	No (traditionally)

Exception handling

try { ... } catch (ExceptionType e) { ... } finally { ... }

• Checked: must handle/declare (e.g., IOException)
• Unchecked: RuntimeException and subclasses
• throw / throws; finally almost always runs

String vs StringBuilder

String	StringBuilder
Immutable	Mutable
+ creates new objects	Efficient append/modify
Thread-safe pool reuse of literals	Not synchronized (StringBuffer is)

Trap: == on Strings compares references; prefer .equals() for content.

---

4. Python Basics

Mutable vs Immutable

Immutable	Mutable
int, float, str, tuple, frozenset	list, dict, set

Core collections

Type	Ordered*	Mutable	Duplicates	Access
list	Y	Y	Y	index
tuple	Y	N	Y	index
dict	Y (3.7+)	Y	keys unique	key
set	N	Y	N	membership

*Insertion-ordered dicts from Python 3.7+.

Indentation

• Blocks defined by indentation (usually 4 spaces) — syntax, not style-only

Functions

def f(a, b=0):
    return a + b

• Default args, keyword args
• *args: variable positional arguments → tuple
• **kwargs: variable keyword arguments → dict (know the idea)

File modes

Mode	Meaning
'r'	Read (default)
'w'	Write (truncate/create)
'a'	Append
'x'	Exclusive create
'b'	Binary
't'	Text (default)
'+'	Read/write update

---

5. Data Structures

Array

• Contiguous elements, same type (classic); O(1) index access; insert/delete middle O(n)

Stack (LIFO)

• Operations: push, pop, peek/top
• Uses: recursion call stack, undo, postfix evaluation, balanced parentheses

Queue (FIFO)

• Enqueue rear, dequeue front
• Variants: circular, deque, priority queue

Linked list

• Nodes: data + pointer(s)
• Singly / doubly / circular
• Insert/delete at known node O(1) pointer work; search O(n)
• No random access like arrays

Tree

• Hierarchical; root, parent, child, leaf, depth/height
• Binary tree: ≤ 2 children
• BST: left < node < right (typical); search/insert average O(log n), worst O(n) if skewed

Graph

• Vertices (nodes) + edges
• Directed / undirected; weighted / unweighted
• Cyclic / acyclic (DAG); connected components
• Representations: adjacency matrix, adjacency list
• Traversal: BFS, DFS

---

6. Searching

Method	Idea	Time
Linear	Scan one by one	O(n)
Binary	Sorted array; mid compare	O(log n)

Trap: Binary search needs sorted data.

---

7. Sorting — Time Complexities

Algorithm	Best	Average	Worst	Space	Stable?
Bubble	O(n)†	O(n²)	O(n²)	O(1)	Y
Selection	O(n²)	O(n²)	O(n²)	O(1)	N
Insertion	O(n)	O(n²)	O(n²)	O(1)	Y
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Y
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)*	N††

† With optimized early exit; * average stack; †† typical in-place quicksort unstable.

Ideas (1-liners)

• Bubble: adjacent swaps
• Selection: pick min each pass
• Insertion: build sorted prefix
• Merge: divide & merge sorted halves
• Quick: pivot partition

---

8. Recursion

• Function calls itself with smaller input + base case
• Uses call stack; deep recursion → stack overflow risk
• Examples: factorial, Fibonacci, tree traversals, divide-and-conquer sorts

---

9. Time Complexity (Big-O) — Common Cases

Complexity	Name	Example
O(1)	Constant	Array index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Single loop
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Nested loops / bubble
O(2ⁿ)	Exponential	Naive subset / Fib recursion
O(n!)	Factorial	All permutations

Order (slow → fast growth): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Trap: Big-O is upper bound asymptotic; ignore constants & lower terms for MCQs unless asked precisely.

---

Quick traps checklist

1. Encapsulation hides; abstraction simplifies view.
2. JVM runs bytecode; JDK includes compiler tools.
3. static → class-level.
4. Interface: multiple inheritance of type; abstract class: single extend.
5. String immutable; StringBuilder mutable.
6. list mutable; tuple immutable; set unique unordered.
7. Stack LIFO; Queue FIFO.
8. BST left < root < right.
9. Binary search needs sorted input.
10. Quick worst O(n²); Merge always O(n log n).