Java,
Week 1

Why languages exist, what abstraction buys us, compilers and interpreters, imperative versus declarative style, and a first look at types, ADTs and objects.

1.1What is a programming language?

Originally, a language was directly tied to the architecture of the computer. Memory locations store values and registers do the arithmetic. Even adding two numbers takes three separate steps:

• Load a value from memory location M into register R.
• Add the contents of registers R1 and R2 and store the result back in R1.
• Write the value in R1 to memory location M'.

So the lecture's first point: working directly with the machine is tedious and error prone. That is the reason programming languages exist.

1.2Abstraction: what a high-level language gives us

The ideas we already use in computational thinking are abstractions. A good language lets us express them directly, without thinking about registers:

The language then translates this "high level" code into "low level" machine language. The two translators are the compiler and the interpreter.

1.3Compiler, interpreter and where Java sits (extra)

1.4The trade-off: expressiveness for efficiency

A higher level language gives us less control over how our code is mapped to the architecture. We give that control up and get something worth more: fewer errors from a mismatch between what we intended and what we implemented.

1.5Styles of programming: imperative vs declarative

Example 1: add the values in a list

Imperative: intermediate values sum and x, and an explicit loop that examines each element.

def sum_list(l):
    sum = 0
    for x in l:
        sum += x
    return sum
print(sum_list([1, 2, 3]))

6

Declarative: describe the answer by induction. No intermediate variables.

def sum_list(l):
    if l == []:
        return 0
    else:
        return l[0] + sum_list(l[1:])
print(sum_list([1, 2, 3]))

6

• Base case: the empty list has sum 0.
• Inductive step: add the first element to the sum of the rest of the list.

Example 2: sum of squares of the even numbers up to n

def sum_square_even(n):
    sum = 0
    for x in range(n + 1):
        if x % 2 == 0:
            sum += x * x
    return sum
print(sum_square_even(10))

220

def even(x):
    return x % 2 == 0

def square(x):
    return x * x

def sum_square_even(n):
    return sum(map(square, filter(even, range(n + 1))))
print(sum_square_even(10))

220

Both give 220 (0 + 4 + 16 + 36 + 64 + 100). In the second version each tiny job has a name: even keeps, square transforms, sum combines.

The same program in Java. Each Python function becomes a static method with declared types, and filter and map become a stream pipeline (Java 8+):

import java.util.stream.IntStream;

public class Main {
    static boolean even(int x) {
        return x % 2 == 0;
    }

    static int square(int x) {
        return x * x;
    }

    static int sumSquareEven(int n) {
        return IntStream.rangeClosed(0, n)
                        .filter(Main::even)
                        .map(Main::square)
                        .sum();
    }

    public static void main(String[] args) {
        System.out.println(sumSquareEven(10));
    }
}

220

• IntStream.rangeClosed(0, n) is Python's range(n + 1): it includes n.
• Main::even hands the method even to filter, like passing the function even in Python.
• Every name now has a declared type (int, boolean): the static typing of Chapter 2.

1.6Names, types and values

• Internally everything is a sequence of bits. There is no difference between data and instructions, let alone between numbers, characters and booleans.
• For a compiler or interpreter, our code is its data: it reads our program as input.
• So we impose a notion of type to create discipline: it says how to read the bits, what values are allowed, and which operations are permitted.

Strict type-checking catches bugs early, like a dimension mismatch in science (you cannot add 5 metres to 3 seconds). There are two kinds of slip:

• Incorrect expression evaluation: an operation applied to the wrong kinds of values.
• Incorrect assignment: the value does not match the variable's type.

print(5 + "3")

TypeError: unsupported operand type(s) for +: 'int' and 'str'

int x = "hello";   // Java refuses to even compile this

error: incompatible types: String cannot be converted to int

Python found the problem only when the line ran; Java reports it before anything runs. Chapter 2 is entirely about this difference.

1.7Collections, abstract data types and objects (preview)

Collections matter: arrays, lists, dictionaries. An abstract data type (ADT) is a structured collection with a fixed interface, and its implementation is kept separate from that interface.

• A stack is a sequence, but it only allows push and pop.
• A priority queue allows insert and delete-max. It can be implemented with a sorted list, an unsorted list or a heap, and the users cannot tell which.

import heapq

class PQList:                      # unsorted list inside
    def __init__(self):
        self.items = []
    def insert(self, x):
        self.items.append(x)
    def delete_max(self):
        m = max(self.items)
        self.items.remove(m)
        return m

class PQHeap:                      # heap inside
    def __init__(self):
        self.h = []
    def insert(self, x):
        heapq.heappush(self.h, -x)
    def delete_max(self):
        return -heapq.heappop(self.h)

for pq in (PQList(), PQHeap()):
    for v in (5, 9, 2):
        pq.insert(v)
    print(pq.delete_max(), pq.delete_max())

9 5
9 5

Same interface, same answers, different insides. (The two lines of output are the two implementations.)

Object-oriented programming, in one line

OOP focuses on data types, and functions are invoked through the object instead of passing the data to the function. Python shows both styles side by side:

a = [3, 1, 2]
r = a.sort()          # method of the object: sorts a itself
print(a, r)

b = [3, 1, 2]
c = sorted(b)         # function given the data: returns a new list
print(b, c)

[1, 2, 3] None
[3, 1, 2] [1, 2, 3]

1.8What is yet to come, and why so many languages

• Java is the illustrative language: imperative, object oriented, and it incorporates almost all of these features.
• Design decisions are discussed wherever relevant, because every language makes some compromises.
• That is why there is a whole "zoo" of languages, and why new ones are still created.

1.9Exam tips and common mistakes

1.10Interview corner: what they may ask

What types are for, dynamic versus static typing, why static analysis helps, type synonyms, and type inference.

2.1The role of types

Everything is stored as bits. A type is what turns a pile of bits into something meaningful. Types do three jobs:

n = 65
print(format(n, '08b'))   # the bits of 65
print(chr(n))             # the same number read as a character

01000001
A

2.2Dynamic vs static typing

Every variable has a type. The question is how that type is decided.

x = 10
print(type(x))
x = 7.5
print(type(x))

<class 'int'>
<class 'float'>

print(y)

NameError: name 'y' is not defined

In Java the same attempt is stopped by the compiler:

int x = 10;
x = 7.5;       // not allowed

error: incompatible types: possible lossy conversion from double to int

2.3Why static typing catches what dynamic typing misses

With dynamic typing it is difficult to catch errors such as typos. This function should return all factors of n, but one name is misspelt:

def factors(n):
    factorlist = []
    for i in range(1, n + 1):
        if n % i == 0:
            factorlst = factorlist + [i]   # typo here!
    return factorlist

print(factors(6))

[]

No error at all. The typo silently created a new variable factorlst, and the real list stayed empty. The answer should have been [1, 2, 3, 6]. A statically typed language needs every name declared first, so the misspelt name is flagged immediately:

factorlst = factorlist + i;   // factorlst was never declared

error: cannot find symbol

Empty user-defined objects

A linked list is a sequence of Node objects, and the empty list is conveniently written as None. Without declaring the type of l, Python cannot say what type it has once l = None:

class Node:
    def __init__(self, v):
        self.value = v
        self.next = None

l = None
print(type(l).__name__)
l = Node(1)
print(type(l).__name__)

NoneType
Node

Node l = null;        // l is declared as a Node, and is empty for now
l = new Node(1);      // still a Node

2.4Types as organising concepts

Even simple type synonyms clarify code. A 2D point is a pair of floats and a 3D point is a triple; naming them makes the intent transparent for whoever writes, reads or maintains the code.

Point2D = tuple[float, float]
Point3D = tuple[float, float, float]

def shift(p: Point2D, dx: float) -> Point2D:
    return (p[0] + dx, p[1])

print(shift((1.0, 2.0), 0.5))

(1.5, 2.0)

Java has no typedef; you create a real type instead (a class, or a record in newer Java):

record Point2D(double x, double y) { }     // Java 16+

The bigger idea is abstract data types and objects. In a banking application Account and Customer are separate types:

customer.deposit(500);    // a Customer has no deposit()

error: cannot find symbol

2.5Static analysis

• Find errors as early as possible: it saves cost and effort.
• In general a compiler cannot check that a program will work correctly. This is the halting problem (Alan Turing): no program can decide, for every program, whether it will stop or what it will finally do.
• But with variable declarations the compiler can detect type errors at compile time. That is static analysis.
• Dynamic typing would catch these only when the code runs, and running is also slower because types are monitored at the same time.

The compiler can also optimise using what static analysis knows:

2.6Type inference

Some languages deduce the types of variables statically, from the context in which they are used. After x = 7, the line y = x + 15 forces y to be an int. If the inferred type is consistent across the whole program, everything is fine.

var x = 7;          // Java 10+: inferred as int
var y = x + 15;     // inferred as int
y = "hello";        // still an error

error: incompatible types: String cannot be converted to int

2.7Strong vs weak typing (extra)

People mix up two different questions. Static vs dynamic asks when types are checked. Strong vs weak asks how strictly mismatched types are refused.

2.8Exam tips and common mistakes

2.9Interview corner: what they may ask

Scope and lifetime, activation records on the stack, how arguments are passed, the heap, and garbage collection.

3.1Keeping track of variables: scope and lifetime

Variables store intermediate values. Most are local to a function; some are global, outside any function; and some data is created dynamically, like the nodes of a list. Two ideas keep this straight:

The lecture's example: f loops over x and calls g(x), and g also loops with its own x. The x of f is not in scope inside g, yet its storage is still allocated: it is alive but hidden. This is the "hole in the scope".

def g(m):
    for x in range(m):
        pass
    return m

def f(l):
    y = 0
    for x in l:
        y = y + g(x)
        print("f still sees its own x =", x)
    return y

print(f([2, 3]))

f still sees its own x = 2
f still sees its own x = 3
5

class Counter {
    int x = 5;                       // a field: lives as long as the object
    void show() {
        int x = 10;                  // a local x hides the field x
        System.out.println(x);       // 10
        System.out.println(this.x);  // 5   (the hidden one, reached explicitly)
    }
}

3.2The memory stack and activation records

• Each function needs storage for its local variables. When it is called, an activation record is created for it.
• Activation records are stacked: the newest is on top, and it is popped when the function exits.
• The control link points to the start of the previous record (who called me).
• The return value link tells where to store the result.

Read the picture carefully, because it is a favourite for questions. The top record is the newest call, factorial(2). Its control link goes back to the start of the record of factorial(3), and its return value link goes to the empty factorial(n-1) slot of factorial(3), which is where its answer will be written.

def factorial(n, depth=0):
    pad = "  " * depth
    print(pad + "call   factorial(" + str(n) + ")   stack depth", depth + 1)
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(pad + "return factorial(" + str(n) + ") =", result)
    return result

factorial(3)

call   factorial(3)   stack depth 1
  call   factorial(2)   stack depth 2
    call   factorial(1)   stack depth 3
    return factorial(1) = 1
  return factorial(2) = 2
return factorial(3) = 6

• Scope of a variable: it is in the activation record at the top of the stack.
• Lifetime: the storage is still allocated on the stack, so it is alive even when buried under newer records.

A finite stack can overflow

A stack has a fixed size. A function that calls itself with no stopping condition keeps pushing records until it runs out:

def forever(n):
    return forever(n + 1)

forever(0)

RecursionError: maximum recursion depth exceeded

Java does the same and reports a StackOverflowError. Both are the stack running out, caused by missing or unreachable base cases.

3.3Passing arguments to a function

When a function is called, the arguments are substituted for the formal parameters. The parameters are part of the activation record, filled in at the call, as if there were implicit assignment statements at the start of the function. For f(x, myl) with def f(a, l): that means a = x and l = myl.

def f(a, l):
    a = a + 1            # changes only the copy
    l.append(99)         # changes the shared list
    l = [0]              # only re-points l
    print("inside:", a, l)

x = 7
myl = [8, 9, 10]
f(x, myl)
print("outside:", x, myl)

inside: 8 [0]
outside: 7 [8, 9, 10, 99]

Java: always pass by value (the classic interview question)

static void change(int a, int[] arr) {
    a = 99;                    // changes only the copy
    arr[0] = 99;               // changes the shared array
    arr = new int[] {0};       // only re-points the local copy of the reference
}

int x = 7;
int[] m = {8, 9, 10};
change(x, m);
// x is still 7;   m is now {99, 9, 10}

• Java always copies the value of the argument.
• For a primitive (int, double...) the value is the number itself, so the caller never sees a change.
• For an object or array the value that is copied is the reference. Both names then reach the same object, so changing its contents is visible, but re-pointing your copy of the reference is not.

3.4The heap

Consider a function that inserts a value into a linked list. The storage for the new node is allocated inside the function, yet the node must persist after the function exits. It cannot live in the activation record, because that is popped. We need a separate area for such dynamically allocated data: the heap.

class Node:
    def __init__(self, v, nxt=None):
        self.value = v
        self.next = nxt

def push_front(head, v):
    node = Node(v, head)       # created inside the function
    return node                # ...but it outlives the call

head = None
for v in (9, 7, 3):
    head = push_front(head, v)

cur = head
while cur is not None:
    print(cur.value, end=" ")
    cur = cur.next

3 7 9 

• The heap is not the "heap" data structure used for priority queues. It is just a memory area.
• Conceptually it is allocated from the opposite end of memory to the stack; the free space is in between.
• Heap storage outlives the activation record. It is reached through some variable that is in scope.

3.5Managing heap storage: manual vs garbage collection

On the stack, storage is freed when the function exits. On the heap, after we delete a node from a linked list it becomes dead storage: nothing points to it any more. How do we get that memory back?

import gc, weakref

class Node:
    pass

a = Node()
b = Node()
a.other = b
b.other = a                    # a and b point at each other (a cycle)
probe = weakref.ref(a)         # a probe that does not keep a alive
del a, b                       # no variable reaches them any more
print(probe() is None)         # still in memory?
gc.collect()                   # a collection pass
print(probe() is None)

False
True

Nothing could reach the two nodes after del, yet they were still in memory (False) because they pointed at each other. Reachability from variables, not "is anything pointing at me", is the test, so one collection pass freed them (True).

• Java's collector is generational: new objects start in a young area that is cleaned often, and survivors are moved to an old area cleaned rarely.
• Collection can pause the program briefly: that is the performance penalty from the lecture.
• System.gc() is only a request; you cannot force a collection.
• Garbage collection does not make leaks impossible: an object that is still reachable but no longer needed (for example kept in a static list that only grows) is never freed.

3.6Where does each thing live? (a Java snapshot)

static void demo() {
    int count = 3;                 // value 3 on the stack
    int[] marks = new int[3];      // reference on the stack, array object on the heap
    Account a = new Account();     // reference on the stack, Account object on the heap
}                                  // record popped; the objects become garbage
                                   // once nothing reaches them

3.7Exam tips and common mistakes

3.8Interview corner: what they may ask

Stepwise refinement (program and data), components with interfaces and specifications, and the language features that support abstraction.

4.1Stepwise refinement

• Begin with a high-level description of the task.
• Refine the task into subtasks, then elaborate each subtask further.
• Subtasks can be coded by different people.
• Program refinement focuses on the code; the data structures hardly change.

This is the classic top-down method. Each level says what in a little more detail until the last level is real code. Here is level 3 turned into Python:

def first_primes(count):            # fill table p with the first `count` primes
    p = []
    n = 2
    while len(p) < count:
        if all(n % q != 0 for q in p if q * q <= n):
            p.append(n)
        n += 1
    return p

p = first_primes(1000)              # declare table p, then fill it
print(len(p), p[0], p[-1])          # print table p (summary only)

1000 2 7919

1000 primes, the first is 2 and the 1000th is 7919. Notice that the three top-level steps (declare, fill, print) can be written, tested and replaced independently.

4.2Data refinement, and why it cascades

Take a banking application. Typical functions: CreateAccount(), Deposit() / Withdraw() and PrintStatement(). How do we represent each amount? We only need the current balance, so overall an array of balances is enough.

balance = [0, 0]                       # one number per account

def deposit(acc, amt):
    balance[acc] += amt

def withdraw(acc, amt):
    balance[acc] -= amt

def print_statement(acc):
    print("balance", balance[acc])

deposit(0, 1000)
withdraw(0, 200)
withdraw(0, 300)
print_statement(0)

balance 500

Now the bank asks for PrintTransactions(). We must record every transaction of each account, so the data representation changes. That is data refinement, and it has a cascading impact: every function that touches accounts must be rewritten.

transactions = [[], []]                # a list of amounts per account

def deposit(acc, amt):
    transactions[acc].append(+amt)         # rewritten

def withdraw(acc, amt):
    transactions[acc].append(-amt)         # rewritten

def print_statement(acc):
    print("balance", sum(transactions[acc]))   # rewritten

def print_transactions(acc):               # new
    for t in transactions[acc]:
        print(t)

deposit(0, 1000)
withdraw(0, 200)
withdraw(0, 300)
print_statement(0)
print_transactions(0)

balance 500
1000
-200
-300

This is the problem that objects solve. If the data and the functions that use it live together in one class, refining the data representation only touches that class. Users of Account call deposit() and never see the list:

class Account:
    def __init__(self):
        self.transactions = []         # private business of Account
    def deposit(self, amt):
        self.transactions.append(+amt)
    def withdraw(self, amt):
        self.transactions.append(-amt)
    def balance(self):
        return sum(self.transactions)
    def print_transactions(self):
        for t in self.transactions:
            print(t)

a = Account()
a.deposit(1000)
a.withdraw(200)
a.withdraw(300)
print(a.balance())
a.print_transactions()

500
1000
-200
-300

4.3Modular software development

• Use refinement to divide the solution into components.
• Build a prototype of each component to validate the design.
• Improve each component independently, preserving its interface and specification.

In Java the word interface is literal: it lists the operations and says nothing about how they are done. The specification travels as a documentation comment.

interface PriorityQueue {
    /** Adds x to the queue. */
    void insert(int x);

    /** Removes and returns the largest value. Must not be called on an empty queue. */
    int deleteMax();
}

class ListPQ implements PriorityQueue { /* unsorted list inside */ }
class HeapPQ implements PriorityQueue { /* heap inside */ }

• The main challenge is a suitable language to write specifications: it must balance abstraction and detail, and should not become another programming language.
• We cannot algorithmically check that a specification is met. That is the halting problem again.

4.4How a language supports abstraction

The lecture's example of broken data abstraction: if a stack is implemented as a list, we should not be able to observe or modify the internal elements. Python cannot stop us:

class Stack:
    def __init__(self):
        self.items = []
    def push(self, x):
        self.items.append(x)
    def pop(self):
        return self.items.pop()

s = Stack()
s.push(1)
s.push(2)
s.items[0] = 99          # reaches inside the representation
print(s.pop(), s.pop())

2 99

A real stack would give 2 1. The outsider rewrote the bottom element through a back door. In Java, private List<Integer> items; closes that door at compile time. Chapter 6 shows why this matters.

4.5Top-down vs bottom-up

4.6Exam tips and common mistakes

4.7Interview corner: what they may ask

What an object is, where OOP came from, and its four distinguishing features: abstraction, subtyping, dynamic lookup and inheritance.

5.1Objects

An object is a uniform way of packaging any mix of data and behaviour. It can hold one integer, such as a counter, or it can be an entire file system or database.

class Counter:
    def __init__(self):
        self.count = 0
    def click(self):
        self.count += 1
    def value(self):
        return self.count

c = Counter()
c.click()
c.click()
print(c.value())

2

The lecture names four distinguishing features of object-oriented programming. Each gets a section below.

5.2History: Simula and the event queue

Objects were first introduced in Simula, a simulation language from the 1960s. Event-based simulation follows one basic pattern:

• Maintain a queue of events to be simulated.
• Simulate the event at the head of the queue.
• Add all the events it spawns to the queue.

The challenge. A well-typed queue holds values of one type, yet this queue must hold all kinds of events, and we want one generic simulate step without elaborate checking of cases. First the clumsy way:

def simulate(event):
    if event == "arrival":
        print("customer joins")
    elif event == "departure":
        print("customer leaves")
    elif event == "breakdown":
        print("machine stops")
    # a new kind of event means editing this function again

for e in ["arrival", "departure", "breakdown", "arrival"]:
    simulate(e)

customer joins
customer leaves
machine stops
customer joins

And the object way: every kind of event is its own type with its own simulate:

class Event:
    def simulate(self):
        raise NotImplementedError

class Arrival(Event):
    def simulate(self):
        print("customer joins")

class Departure(Event):
    def simulate(self):
        print("customer leaves")

class Breakdown(Event):
    def simulate(self):
        print("machine stops")

queue = [Arrival(), Departure(), Breakdown(), Arrival()]
for e in queue:
    e.simulate()                 # one generic call, no case checks

customer joins
customer leaves
machine stops
customer joins

5.3Feature 1: Abstraction

• Objects are similar to abstract data types: public interface, private implementation.
• Changing the implementation should not affect interactions with the object.
• It is a data-centric view: focus on what data we need to maintain and manipulate.
• Recall stepwise refinement: it could affect code and data. Tying methods to data makes that easier to coordinate, because refining the data naturally goes with updating the methods that use it.

public class Counter {
    private int count;                 // hidden
    public void click()  { count++; }  // public operations
    public int value()   { return count; }
}

5.4Feature 2: Subtyping

A well-typed queue holds values of a fixed type, yet the simulation queue holds many kinds. The way out is to arrange types in a hierarchy. A subtype is a specialisation of a type.

• If f() is a method in B and A is a subtype of B, then every object of A also supports f().
• The implementation of f() can be different in A.

Event e = new Arrival();      // Arrival is a subtype of Event, so this is allowed
Event[] queue = { new Arrival(), new Departure(), new Breakdown() };

5.5Feature 3: Dynamic lookup

• Whether a method can be called on an object is a static property: type-checking decides it.
• How the method acts is a dynamic property of how the object is implemented.
• In a graphics program, different kinds of objects are rendered with the same operation; each object knows how to render itself.

class Shape:
    def draw(self):
        print("some shape")

class Circle(Shape):
    def draw(self):
        print("circle")

class Square(Shape):
    def draw(self):
        print("square")

for s in [Circle(), Square(), Shape()]:
    s.draw()

circle
square
some shape

Different from overloading. The operation + is addition for int and for float: the internal implementation differs, but the choice is made from the static types. With dynamic lookup a variable v of static type B may refer to an object of subtype A, and the implementation that runs depends on the runtime type A.

static void show(Shape s)  { System.out.println("shape");  }
static void show(Circle c) { System.out.println("circle"); }

Shape s = new Circle();    // static type Shape, runtime type Circle
show(s);                   // prints "shape"  : overloads are picked by the STATIC type
s.draw();                  // Circle's draw() : overriding is picked by the RUNTIME type

5.6Feature 4: Inheritance

Inheritance is re-use of implementations. Example: different types of employees. Employee objects store basic personal data and the date of joining. Manager objects retain all of that and add more: a date of promotion and a seniority in the current role.

class Employee:
    def __init__(self, name, joined):
        self.name = name
        self.joined = joined
    def describe(self):
        return self.name + " joined " + str(self.joined)

class Manager(Employee):
    def __init__(self, name, joined, promoted):
        super().__init__(name, joined)     # reuse Employee's setup
        self.promoted = promoted
    def seniority(self, today):
        return today - self.promoted

m = Manager("Asha", 2015, 2020)
print(m.describe())                         # inherited, not rewritten
print(m.seniority(2026))

Asha joined 2015
6

• Usually one hierarchy of types captures both subtyping and inheritance: A can inherit from B if A is a subtype of B.
• Philosophically they differ: subtyping is a relationship of interfaces; inheritance is a relationship of implementations.

class Manager extends Employee {
    private int promoted;
    Manager(String name, int joined, int promoted) {
        super(name, joined);            // reuse Employee's constructor
        this.promoted = promoted;
    }
}

5.7Subtyping vs inheritance: the Deque example

• A deque is a double-ended queue: insert-front(), delete-front(), insert-rear(), delete-rear().
• A stack can be built from it using only insert-front and delete-front; a queue using only insert-rear and delete-front.
• So Stack and Queue inherit from Deque, reusing its implementation.
• But they are not subtypes of Deque. If v of type Deque points to a Stack, we cannot safely call insert-rear() or delete-rear(). Their interfaces are not compatible.
• In fact Deque is a subtype of both Stack and Queue: it supports every operation they do.

class Deque:
    def __init__(self):
        self.items = []
    def insert_front(self, x):
        self.items.insert(0, x)
    def delete_front(self):
        return self.items.pop(0)
    def insert_rear(self, x):
        self.items.append(x)
    def delete_rear(self):
        return self.items.pop()

class Stack(Deque):              # inherits ALL of Deque's code
    pass

s = Stack()
s.insert_front(1)
s.insert_front(2)
print(s.delete_front(), s.delete_front())   # stack behaviour
s.insert_rear(7)                             # Python lets a Stack do this...
print(s.items)

2 1
[7]

The inheritance worked (the code was reused), but the last two lines show the problem: a Stack that offers insert_rear is not a real stack interface. Python does not stop us; Java's design pushes you towards the right choice:

class Stack {
    private final Deque deque = new Deque();   // reuse by composition
    void push(int x) { deque.insertFront(x); }
    int pop()        { return deque.deleteFront(); }
    // insertRear is simply not available on a Stack
}

5.8Lecture words vs interview words

Interviewers usually ask for the "four pillars". They are the same ideas under slightly different names, so link them in your head:

5.9Exam tips and common mistakes

5.10Interview corner: what they may ask

Class versus object, constructors and methods, changing a class's internals, and why Python's lack of enforcement leads to Java.

6.1Programming with objects: class and object

Example: 2D points. A point has coordinates (x, y). Each point object stores its own x and y; these are called instance variables. For a point p they are p.x and p.y. Inside the class, self is a special name for the current object (Java calls it this).

6.2The constructor

When we create an object we need to set it up. A constructor function with a fixed name is called implicitly. In Python it is __init__() and its first parameter is always self.

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

p = Point(5, 7)
q = Point()
print(p.x, p.y, q.x, q.y)

5 7 0 0

public class Point {
    private double x, y;               // instance variables

    public Point(double a, double b) { // constructor: same name as the class, no return type
        this.x = a;
        this.y = b;
    }
    public Point() { this(0, 0); }     // Java has no default arguments: overload instead
}

6.3Adding methods: changing state vs just reading it

Translation shifts a point by $\Delta x, \Delta y$: $(x, y) \mapsto (x+\Delta x,\; y+\Delta y)$. It updates the instance variables. Distance from the origin, $d = \sqrt{x^2 + y^2}$, does not change the object: its state is unchanged.

import math

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

    def translate(self, dx, dy):       # changes the state
        self.x += dx
        self.y += dy

    def odistance(self):               # only reads the state
        return math.sqrt(self.x * self.x + self.y * self.y)

p = Point(3, 4)
print(p.odistance())
p.translate(3, 8)
print(p.x, p.y)
print(p.odistance())

5.0
6 12
13.416407864998739

6.4Changing the internal implementation

Suppose we store the point in polar coordinates $(r, \theta)$ instead, with $r = \sqrt{x^2+y^2}$ and $\theta = \tan^{-1}(y/x)$. Now the distance from the origin is just r. Translation must convert $(r,\theta)$ back to $(x,y)$ using $x = r\cos\theta,\ y = r\sin\theta$, add $\Delta x, \Delta y$, and recompute $r, \theta$.

import math

class Point:
    def __init__(self, a=0, b=0):
        self.r = math.sqrt(a * a + b * b)
        if a == 0:
            self.theta = math.pi / 2
        else:
            self.theta = math.atan(b / a)

    def odistance(self):
        return self.r

    def translate(self, dx, dy):
        x = self.r * math.cos(self.theta)
        y = self.r * math.sin(self.theta)
        x += dx
        y += dy
        self.r = math.sqrt(x * x + y * y)
        if x == 0:
            self.theta = math.pi / 2
        else:
            self.theta = math.atan(y / x)

p = Point(3, 4)
print(p.odistance())
p.translate(3, 8)
print(round(p.odistance(), 6))

5.0
13.416408

Same interface (Point(a, b), translate, odistance), same answers, completely different insides. Users need not know whether the representation is $(x,y)$ or $(r,\theta)$. That is abstraction working.

import math
a, b = -3, 4
theta = math.atan(b / a)                  # lecture version
r = math.sqrt(a * a + b * b)
print(round(r * math.cos(theta), 6), round(r * math.sin(theta), 6))
theta = math.atan2(b, a)                  # correct version
print(round(r * math.cos(theta), 6), round(r * math.sin(theta), 6))

3.0 -4.0
-3.0 4.0

6.5When abstraction is not enforced: breaking changes

Python allows direct access to instance variables from outside the class:

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

p = Point(5, 7)
p.x = 4                      # the point is now (4, 7)
print(p.x, p.y)

4 7

This defeats the purpose of abstraction. If another programmer wrote p.x = 4 and we later switch to the polar representation, that code breaks. A change to the internals that damages other code is called a breaking change:

import math

class Point:                                  # now the polar version
    def __init__(self, a=0, b=0):
        self.r = math.sqrt(a * a + b * b)
        self.theta = math.atan2(b, a)

p = Point(5, 7)
print(p.x)

AttributeError: 'Point' object has no attribute 'x'

6.6Subtyping and inheritance in classes: Rectangle and Square

Define Square as a subtype of Rectangle: a different constructor, the same instance variables.

class Rectangle:
    def __init__(self, w=0, h=0):
        self.width = w
        self.height = h
    def area(self):
        return self.width * self.height
    def perimeter(self):
        return 2 * (self.width + self.height)

class Square(Rectangle):
    def __init__(self, s=0):
        self.width = s
        self.height = s

s = Square(5)
print(s.area(), s.perimeter())

25 20

Square inherits area() and perimeter() from Rectangle, and it all works. Now the subclass author wants a nicer instance variable, side:

class Rectangle:
    def __init__(self, w=0, h=0):
        self.width = w
        self.height = h
    def area(self):
        return self.width * self.height
    def perimeter(self):
        return 2 * (self.width + self.height)

class Square(Rectangle):
    def __init__(self, s=0):
        self.side = s

s = Square(5)
print(s.area(), s.perimeter())

AttributeError: 'Square' object has no attribute 'width'

A subtype is not forced to be an extension of its parent: width and height were never defined for a Square. Worse, the subclass and the parent class are usually developed separately. The author of Rectangle may rename the variables:

class Rectangle:
    def __init__(self, w=0, h=0):
        self.wd = w
        self.ht = h
    def area(self):
        return self.wd * self.ht
    def perimeter(self):
        return 2 * (self.wd + self.ht)

class Square(Rectangle):
    def __init__(self, s=0):
        self.width = s
        self.height = s

s = Square(5)
print(s.area())

AttributeError: 'Square' object has no attribute 'wd'

• Square constructor sets width and height, but the parent now uses wd and ht: the names changed.
• We need a way to hide private implementation details: declare each component private or public.
• But then how can the Square constructor set the private wd and ht? Square does not, and should not, know their names.
• So we need elaborate declarations: the type and the visibility of every variable, with static type checking to catch mistakes early.

How Java solves it

class Rectangle {
    private double width, height;               // hidden: no outsider, no subclass, can touch them

    Rectangle(double w, double h) { width = w; height = h; }
    double area()      { return width * height; }
    double perimeter() { return 2 * (width + height); }
}

class Square extends Rectangle {
    Square(double side) {
        super(side, side);                      // ask the parent to set up ITS OWN variables
    }
}

• The fields are private, so renaming them cannot break a subclass: nobody else could use the names.
• super(side, side) lets the child construct the parent part without knowing the parent's variable names.
• Static typing catches a wrong use immediately: sq.wd from outside is "has private access", a compile-time error.

6.7Language support: what Python leaves to discipline

6.8Exam tips and common mistakes

6.9Interview corner: what they may ask

What is likely to be asked from Week 1, with 30-second answers, deeper explanations and code-reading practice.

Interviewers use these concepts to test whether you understand Java, not whether you can type it. Every answer below starts with a 30-second version; open the button, then read the details.

7.1Interview heat-map: what is most likely

7.2Fundamentals

7.3Memory

static void change(int a, int[] arr, StringBuilder sb) {
    a = 99;
    arr[0] = 99;
    sb.append("!");
    arr = new int[] {0};
    sb = new StringBuilder("new");
}

void demo() {
    int count = 3;
    int[] marks = new int[3];
    Account a = new Account();
}

7.4Object-oriented programming

Shape s = new Circle();
s.draw();            // runs Circle's draw(), not Shape's

public class Account {
    private int balance;                    // hidden data
    public void deposit(int amt) { balance += amt; }
    public int  balance()        { return balance; }
}

7.5Code-reading questions to expect

Interviewers love a snippet and the question "what does this print?". Try each one before you open the answer.

static void tweak(int[] a, int[] b) {
    a[0] = 1;
    b = new int[] {9};
    b[0] = 2;
}
// main:
int[] p = {0}, q = {0};
tweak(p, q);
System.out.println(p[0] + " " + q[0]);

1 0

class Animal { void speak() { System.out.println("..."); } }
class Dog extends Animal { void speak() { System.out.println("woof"); } }

static void call(Animal a) { System.out.println("animal"); }
static void call(Dog d)    { System.out.println("dog"); }

Animal x = new Dog();
x.speak();
call(x);

woof
animal

Node a = new Node();
Node b = new Node();
a.next = b;
b.next = a;
a = null;
b = null;

Week 1 on one page: a lecture-by-lecture glance, key terms, the pairs to tell apart, the errors you can now read, a checklist and corrections to the source notes.

8.1Week 1 at a glance

8.2Key terms, lecture by lecture

8.3The pairs you must tell apart

8.4Messages and errors you can now read

8.5Last-minute checklist

8.6Corrections made to the source notes