Advanced Prog Exam Prep

Name the most important quality of a good program

Correctness

What is a precondition?

A fact that must hold true at the BEGINNING of a method.

What is a postcondition?

A fact that holds true at the END of a method.

Define Abstract Data Type

An ADT is a pair where V is a set of VALUES and O is a set of OPERATIONS on those values.

What is Information Hiding and why does it matter?

Information Hiding separates Client Views from Implementor Views..

What are the 3 requirements for a recursive method?

1. A stop case (base case) that terminates the recursion

2. Each recursive call must move TOWARDS the stop case

3. The problem must be expressible in terms of a SIMPLER version of itself

What are the operations of a Stack and what order does it follow?

A Stack follows LIFO (Last In, First Out). Operations: push, pop, peek/top, isEmpty.

What is a Deque and how is it implemented?

A Deque can add/remove from EITHER end. Operations: addLeft, addRight, removeLeft, removeRight, rightHead, leftHead, isEmpty.

Define a proper binary tree

A binary tree where every node has EITHER 0 or 2 children (no node has exactly 1 child). Also known as a full binary tree.

BST property: where are smaller values placed relative to larger ones?

All values in the LEFT subtree of a node are LESS THAN the node's value. All values in the RIGHT subtree are GREATER THAN the node's value.

How do you delete a node with two children from a BST?

Replace the node's value with its IN-ORDER SUCCESSOR (the smallest value in the right subtree), then delete the in-order successor from the right subtree.

What are the three depth-first traversal orders for a binary tree?

Pre-order, In-order, Post-order

What is a Dictionary ADT? What are its operations?

Stores (key, value) pairs where keys are unique. All access is by KEY not by position.

What is a collision in hashing?

Collisions happen when two different keys hash to the same index.

How are collisions handled in Internal hashing?

probe sequentially for next empty slot (linear probing). Slots can be empty, occupied, or deleted. Deleted ≠ empty — searches must skip deleted slot

How are collisions handled in External hashing?

each slot is a bucket (linked list) of all keys hashing there. No fixed size, avoids clustering.

Compare Sequential Search vs Binary Search

Sequential: works on unsorted OR sorted lists. Worst/average O(n).

Binary: requires SORTED array. Compare target with middle element, eliminate half. At most log₂n + 1 comparisons → O(log n). Can search 1,000,000 items in ≤ 20 comparisons.

What is an Interpolated Binary Search and what is its complexity?

Like binary search but instead of always looking at the midpoint, it INTERPOLATES where the target likely is based on the values at the left and right ends.

What are Java Generics?

Generics allow writing one class/method for ANY type.

What is the Comparable interface ?

Comparable is a standard interface that enables ordering comparisons between objects.

What is an Iterator in Java?

An Iterator is an object that allows traversal of a data structure WITHOUT exposing its internal structure.

Describe how binary search tree search works

Start at root. If target < node, go left. If target > node, go right. If equal, found. Repeat until found or null.