Java Data Structures, Memory, and Algorithm Complexity Concepts

Q1. Draw variables and objects representation in memory after a list of Java instructions.

Primitives (int, double, etc.) are stored directly in stack memory.

Objects (e.g. arrays, Strings, custom classes) are stored in heap memory; the variable on the stack holds a reference (address) to the object.

Example:

int x = 5;

int[] arr = {1, 2, 3};

→ x stores 5 directly on the stack; arr stores a reference to an array object [1,2,3] on the heap.

Q2. Explain the keywords private, final, static, protected, interface, abstract.

private - accessible only within the same class.

final - variable: cannot change; class: cannot be subclassed; method: cannot be overridden.

static - belongs to the class, not an instance; shared among all objects.

protected - visible to same package and subclasses.

interface - defines method signatures; classes "implement" it.

abstract - class or method meant to be inherited/overridden, cannot be instantiated directly.

Q3. Determine the Big-O complexity of concatenating n strings in Java.

Each string concatenation copies all previous characters because strings are immutable.

Total cost: 1 + 2 + 3 + ... + n → O(n²).

Solution: use StringBuilder → O(n).

Q4. Explain generic classes and their significance in data structures.

Generics allow writing classes/methods that work with any data type.

Example: class Box { T value; }

Prevents casting errors and increases type safety.

Used in data structures like ArrayList or LinkedList to store specific types safely.

Q5. Describe recursion (base case, recursive case, readability, efficiency, iteration).

Recursion = function calling itself until a base case stops it.

Base case: simplest input (e.g., n == 0).

Recursive case: reduces problem size (e.g., f(n-1)).

Readability: clearer for divide-and-conquer problems.

Efficiency: slower than loops (stack overhead).

Can usually be replaced with iteration for speed and memory efficiency.

Q6. Understand what an iterative function is doing.

Iterative = uses loops instead of recursive calls.

Analyze by tracking loop variable changes and counting iterations.

Example:

int sum = 0;

for (int i = 1; i <= n; i++) sum += i;

→ adds numbers 1 through n; runs O(n) times.

Q7. Explain how to walk backward in a singly linked list using recursion or a stack.

Recursion: naturally walks to the end, then prints on return.

void printReverse(Node n) {

if (n == null) return;

printReverse(n.next);

System.out.println(n.value);

}

Stack: push nodes while going forward, pop to go backward.

Recursion works because the call stack stores the state for each function call automatically.

Q8. What are the two types of complexity we discussed in class?

Time complexity: how runtime grows with input size (n).

Space complexity: how much memory grows with input size (n).

Q9. Explain time/space complexity.

Time complexity: total number of operations.

Space complexity: total additional memory used (not counting input).

Both are expressed in Big-O notation to describe growth rate.

Q10. Convert to Big-O: 10n + O(lg(n)), 0.25n! + 2n, 1+2+3, 5 log(n), log(n²) + 100.

10n + O(lg(n)) → O(n)

0.25n! + 2n → O(n!)

1 + 2 + 3 → O(n²)

5 log(n) → O(log n)

log(n²) + 100 → O(log n)

Keep only the dominant term and drop constants. Big-O measures growth, not exact runtime.

Q11. Analyze time complexity and determine Big-O for provided code solutions. Explain variable meanings.

Define what "n" represents (input size).

Count how many times key operations run as n grows.

Example:

for (int i = 0; i < n; i++) // O(n)

for (int j = 0; j < n; j++) // O(n)

work(); // O(1)

→ total O(n²). Always identify what n represents before giving Big-O.

Q12. Explain how a method with a stated Big-O of O(1) can contain a loop.

If the loop runs a constant number of times (not dependent on n), it's still O(1).

Example:

for (int i = 0; i < 10; i++) System.out.println(i);

→ 10 iterations = constant work, not dependent on input size.

Q13. What's the difference between best case, worst case, and average case Big-O?

Best case: minimal operations (e.g., first element found).

Worst case: maximum operations (e.g., not found).

Average case: expected runtime across typical inputs.

Example: searching in an array → best O(1), worst O(n).

Q14. Explain the formal definition of Big-O.

T(n) is O(F(n)) if there are positive constants c and n₀ such that, when n ≥ n₀,

T(n) ≤ c × F(n).

This means for large n, F(n) is an upper bound on the growth rate of T(n).

Q15. Explain the difference between a dynamic array list and a linked list.

Dynamic Array List: stored in contiguous memory, fast random access (O(1)), but slow insertion/removal in middle (O(n)). Resizes when full.

Linked List: nodes connected by pointers, slow access (O(n)), but fast insertion/removal at ends (O(1)), no resizing needed.

Q16. Compare and contrast singly and doubly linked lists.

Singly Linked List: value + next pointer, can only move forward, memory efficient.

Doubly Linked List: value + next + prev, can move both directions, faster deletions, slightly more memory usage.

What does a Node class represent in a linked list?

One element (value, next, prev).

What does a LinkedList class manage?

The entire structure (head, tail, size).

What methods does a LinkedList class provide?

Methods like add/remove.

How do you add an element to a dynamic array?

void add(int val) { if (size == arr.length) resize(); arr[size++] = val; }

How do you append an element to a singly linked list?

void append(int val) { Node newNode = new Node(val); if (head == null) head = newNode; else tail.next = newNode; tail = newNode; }

How do you check if a value exists in a singly linked list?

boolean contains(int val) { for (Node cur = head; cur != null; cur = cur.next) if (cur.value == val) return true; return false; }

What is the time complexity for adding an element to a dynamic array?

O(1) amortized

What is the time complexity for traversing a linked list to check for a value?

O(n)

Q19. Explain why appending to a dynamic array list is O(n) worst case but O(1) amortized.

When array is full → must resize and copy elements (O(n)).

But resizing happens rarely → average cost per append = O(1) (amortized).

Q20. Given an array representing a list, write the code to convert it into a linked list.

Node head = null, tail = null;

for (int val : arr) {

Node newNode = new Node(val);

if (head == null) head = newNode;

else tail.next = newNode;

tail = newNode;

}

→ Result: singly linked list containing same values as the array.

Q21. Write the code to perform an [insertion | selection] sort on a singly linked list.

✅ Insertion Sort (O(n²)):

Node sorted = null;

for (Node cur = head; cur != null; ) {

Node next = cur.next;

sorted = insertSorted(sorted, cur);

cur = next;

}

✅ Selection Sort: repeatedly find min node and rebuild sorted list.

Q22. Explain the difference between a queue and a stack.

Stack: LIFO (push/pop at top).

Queue: FIFO (enqueue/dequeue at ends).

Example: stack of plates vs line of people.

Q23. If we add 'a', 'b', 'c', 'd' onto a [stack/queue] and [pop()/dequeue()], what will be returned?

Stack: pop() → 'd' (LIFO).

Queue: dequeue() → 'a' (FIFO).

Q24. Explain how to implement a [queue | stack] with a [singly | doubly] linked list with optimal Big-O.

Stack → push/pop at head → O(1).

Queue → enqueue at tail, dequeue at head → O(1) if track both ends.

Q25. Explain how to store a [stack/queue] in an array with the optimal Big-O. Explain circular queue.

Stack → use top index; push/pop in O(1).

Queue → use circular array (wrap with modulus).

front = (front+1) % capacity to reuse space → O(1) ops.

Q26. Given a series of adds and removes into a [stack | queue], draw resulting memory.

Stack: [10, 20, 30], top=2.

Queue (circular): [_, 40, 50, 60, _], front=1, rear=3, size=3.

Q27. Write the code to perform [add | remove | isEmpty | peek] for a [queue | stack].

✅ Stack:

void push(int x){ list.add(x); }

int pop(){ return list.remove(list.size()-1); }

✅ Queue:

void enqueue(int x){ list.addLast(x); }

int dequeue(){ return list.removeFirst(); }

```

Q28. Difference between a Set and a List.

Set: unordered, unique elements.

List: ordered, allows duplicates.

Q29. Difference between a Map and a Set.

Map: key-value pairs.

Set: unique values only.

Q30. Explain Hash Contract / Lazy deletion.

Hash Contract → if a.equals(b) ⇒ a.hashCode() == b.hashCode().

Lazy Deletion → mark as deleted instead of removing immediately to preserve probe chain.

Q31. Compare different collision handling approaches (open addressing vs chaining).

Chaining: linked lists per bucket (simple, uses memory).

Open addressing: probes for next empty slot (fast, harder near full).

Q32. Write code for put/get for a Map or Set.

```java

int index = key.hashCode() % capacity;

if (table[index] == null) table[index] = new LinkedList<>();

for (Pair p : table[index])

if (p.key.equals(key)) return p.value;

table[index].add(new Pair(key, value));

```

Q33. Explain load factor concept. Write code for rehashing.

Load Factor = elements / capacity.

If > threshold (e.g. 0.75), resize table.

```java

if (size >= capacity * loadFactor) rehash();

```

Q34. Explain performance of Set (ordered vs unordered).

HashSet (unordered): O(1).

TreeSet (ordered): O(log n).

LinkedHashSet: keeps insertion order, O(1).

Q35. Explain tree terms: root, descendants, ancestors, leaves, siblings, parent, child, depth, height, etc.

Root = top node, Leaf = no children, Parent/Child = direct relation, Siblings = share parent.

Depth = distance from root, Height = distance to deepest leaf.

Full tree: every node 0 or 2 children.

Complete: filled left to right.

Perfect: all leaves same level.

Balanced: subtrees differ ≤ 1.

Q36. Given a tree, identify root, leaves, height, and type.

Root → no parent.

Leaves → no children.

Height → edges root → deepest leaf.

Full → 0 or 2 children.

Complete → left-to-right filled.

Perfect → all leaves same level.

Balanced → heights differ ≤ 1.

What does the keyword 'private' signify in Java?

It restricts access to the class in which it is declared, preventing access from outside classes.

What is the purpose of the 'final' keyword in Java?

It indicates that a variable's value cannot be changed, a method cannot be overridden, or a class cannot be subclassed.

What does 'static' mean when applied to a variable or method in Java?

It means the variable or method belongs to the class itself rather than instances of the class.

What is the difference between 'protected' and 'private' access modifiers?

'Protected' allows access to subclasses and classes in the same package, while 'private' restricts access to the defining class only.

What is an interface in Java?

An interface is a reference type that can contain only constants, method signatures, default methods, static methods, and nested types.

What is an abstract class in Java?

An abstract class cannot be instantiated and may contain abstract methods that must be implemented by subclasses.

What is the Big-O complexity of concatenating n strings in Java?

O(n^2) due to the need to create a new string for each concatenation.

What are generic classes in Java?

Generic classes allow for type parameters to be specified, enabling classes and methods to operate on objects of various types while providing compile-time type safety.

How would you explain recursion?

Recursion is a process where a function calls itself to solve smaller instances of the same problem, consisting of a base case to stop recursion and a recursive case to continue it.

What is an iterative function?

An iterative function uses loops to repeat a block of code until a condition is met, as opposed to recursion.

How can you walk backward in a singly linked list?

You can use recursion or a stack to keep track of nodes as you traverse forward, allowing you to access previous nodes.

What are the two types of complexity for assessing algorithms?

Time complexity and space complexity.

What is time/space complexity?

Time complexity measures the amount of time an algorithm takes to complete, while space complexity measures the amount of memory it requires.

Convert the function 10n + O(lg(n)) to Big-O notation.

O(n)

What is the difference between 'best case', 'worst case', and 'average case' Big-O?

'Best case' refers to the minimum time an algorithm takes, 'worst case' refers to the maximum time, and 'average case' is the expected time over all inputs.

What is the formal definition of Big-O?

T(n) is O(F(n)) if there are positive constants c and n0 such that when n >= n0, T(n) <= c F(n).

What is the difference between a dynamic array list and a linked list?

A dynamic array list uses a contiguous block of memory and can resize, while a linked list consists of nodes that are not stored in contiguous memory.

What are the pros and cons of singly vs. doubly linked lists?

Singly linked lists are simpler and use less memory, while doubly linked lists allow traversal in both directions but use more memory.

What is the difference between a 'node' class and a 'linked list' class?

A 'node' class represents individual elements with a value and a reference to the next node, while a 'linked list' class manages the nodes and provides methods for list operations.

What is the worst-case Big-O of appending to a dynamic array list?

O(n), because it may require resizing the array.