Nov 11, 2026

Data Structures

Arrays

An array stores elements in a contiguous, ordered sequence and gives constant- time access and updates by index. Searching for an unsorted value is usually linear, while inserting or removing an element may require shifting later elements. Arrays are central to interview techniques such as two pointers, sliding windows, binary search, prefix sums, sorting, and matrix traversal.

Java arrays have a fixed size and a single declared element type, including primitive types such as int and reference types such as String. Resizable operations require a collection such as ArrayList, and comparator-based sorting requires object arrays rather than primitive arrays. Python’s list is a dynamic array that supports appending and removing elements directly. Python also provides concise built-ins such as min, while its bisect module gives explicit left and right insertion boundaries; Java’s Arrays.binarySearch returns any matching duplicate index and encodes a missing value’s insertion point as a negative result.

Java arrays are not inherently thread-safe. For fixed-size storage with atomic element operations, use AtomicIntegerArray, AtomicLongArray, or AtomicReferenceArray<E>. For a resizable, array-like collection in a read-heavy workload, CopyOnWriteArrayList<E> provides snapshot iteration but copies its backing array on every mutation. An array treated as immutable can also be shared safely after proper publication, provided no code can mutate it. Declaring an array reference volatile makes replacement of the reference visible across threads; it does not make access to the individual elements volatile or atomic.

Official documentation for Python3 list (mutable sequence) type, Java Array class and List interface.

int[] numbers = {3, 1, 2};                                 // initialize
boolean[] flags = {true, false};
char[] letters = {'a', 'b', 'c'};
String[] names = {"Alice", "Bob"};
TreeNode[] nodes = new TreeNode[10];
int first = numbers[0];                                    // read
numbers[1] = 10;                                           // update

int length = numbers.length;
int minNum = Arrays.stream(numbers).min().orElseThrow();
int minWithLoop = numbers[0];
for (int number : numbers) {
	minWithLoop = Math.min(minWithLoop, number);
}
int[] copy = Arrays.copyOf(numbers, numbers.length);
boolean equal = Arrays.equals(numbers, copy);              // true: same values
boolean sameArray = numbers == copy;                       // false: different arrays
Arrays.sort(numbers);                                      // primitives cannot use comparators
Integer[] boxedNumbers = {3, 1, 2};
Arrays.sort(boxedNumbers, Comparator.reverseOrder());

String[] words = {"Bob", "Alexander", "Amy"};
Arrays.sort(words, Comparator.comparingInt(String::length));
Arrays.fill(numbers, 0);                                   // set every element to 0
// shorter truncates; longer pads with the type's default value (0, false, null, '\u0000')
int[] resizedCopy = Arrays.copyOf(numbers, numbers.length + 2);

int[] sorted = {1, 2, 2, 2, 3, 5};
int found = Arrays.binarySearch(sorted, 2);                // any matching index from 1 to 3
int missing = Arrays.binarySearch(sorted, 4);              // -6: -(insertion index 5) - 1

List<Integer> list = new ArrayList<>(List.of(3, 1, 2));
int first = list.getFirst();
int last = list.getLast();
String[] array = {"A", "B"};
List<String> fixedList = Arrays.asList(array);             // mutable, but size cannot change
fixedList.set(0, "X");                                     // also updates array[0]

List<String> mutableList =
	new ArrayList<>(Arrays.asList(array));                 // resizable
mutableList.add("C");
list.set(1, 10);                                           // update
list.add(4);                                               // append
list.remove(Integer.valueOf(10));                          // remove by value
list.remove(list.size() - 1);                              // remove last
list.remove(0);                                            // remove by index
Collections.sort(list);
Collections.reverse(list);

numbers = [3, 1, 2]                                        # initialize
first = numbers[0]                                         # read
numbers[1] = 10                                            # update
numbers.append(4)                                          # append
numbers.remove(10)                                         # remove by value
numbers.pop()                                              # remove last
numbers.pop(0)                                             # remove by index

length = len(numbers)
min_num = min(numbers)
numbers.sort()
numbers.reverse()
copy = numbers.copy()
equal = numbers == copy                                    # True: same values
same_list = numbers is copy                                # False: different lists

from bisect import bisect_left, bisect_right
sorted_numbers = [1, 2, 2, 2, 3, 5]
left = bisect_left(sorted_numbers, 2)                      # 1: first matching index
right = bisect_right(sorted_numbers, 2)                    # 4: index after the last match

2D Arrays

A 2D array represents data in rows and columns, making it useful for grids, matrices, game boards, and graph-like traversal problems. Accessing or updating a cell by its row and column indices is constant time. Most interview solutions traverse every cell in O(rows * columns) time, often checking neighboring cells with a small set of direction offsets.

Java uses arrays of arrays, so each row can technically have a different length. Python uses a list of lists and is dynamic in both dimensions. In Python, each row should be created independently; repeating the same inner list would cause multiple rows to reference one object. In both languages, a normal outer-array or outer-list copy is shallow, so copying each row is the safer choice when the grid will be modified.

int[][] grid = {
	{1, 2, 3},
	{4, 5, 6}
};                                                         // initialize
int[][] zeros = new int[3][4];                             // 3 rows, 4 columns, init to defaults

int rows = grid.length;
int columns = grid[0].length;
int value = grid[1][2];                                    // read
grid[1][2] = 10;                                           // update

for (int row = 0; row < rows; row++) {
	for (int column = 0; column < grid[row].length; column++) {
		System.out.println(grid[row][column]);
	}
}

for (int[] row : grid) {
	for (int number : row) {
		System.out.println(number);
	}
}

Arrays.sort(grid[0]);                                      // sort one row
Arrays.fill(grid[0], 0);                                   // fill one row

int[][] copy = new int[grid.length][];
for (int row = 0; row < grid.length; row++) {
	copy[row] = Arrays.copyOf(grid[row], grid[row].length);
}

boolean equal = Arrays.deepEquals(grid, copy);             // true: same nested values
boolean shallowEqual = Arrays.equals(grid, copy);          // false: compares row references
boolean sameGrid = grid == copy;                           // false: different outer arrays
boolean sameRow = grid[0] == copy[0];                      // false: rows were also copied

int[][] directions = {
	{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};                                                         // up, down, left, right

grid = [
	[1, 2, 3],
	[4, 5, 6],
]                                                          # initialize
zeros = [[0 for _ in range(4)] for _ in range(3)]

rows = len(grid)
columns = len(grid[0])
value = grid[1][2]                                         # read
grid[1][2] = 10                                            # update

for row in range(rows):
	for column in range(len(grid[row])):
		print(grid[row][column])

for row in grid:
	for number in row:
		print(number)

grid[0].sort()                                             # sort one row
grid[0] = [0] * len(grid[0])                               # fill one row

copy = [row[:] for row in grid]                            # copy every row
equal = grid == copy                                       # True: same nested values
same_grid = grid is copy                                   # False: different outer lists
same_row = grid[0] is copy[0]                              # False: rows were also copied

directions = [
	(-1, 0), (1, 0), (0, -1), (0, 1)
]                                                          # up, down, left, right

Strings

Strings are ordered sequences of characters used to represent and process text. Reading a character by index is constant time, while searching, comparing, or creating a modified string is generally linear in the string’s length. Common interview patterns include two pointers, sliding windows, frequency counting, palindrome checks, parsing, and matching prefixes or substrings.

Strings are immutable in both Java and Python, so replacing a character or concatenating text creates a new string. Java compares string contents with equals, not ==, and uses StringBuilder for repeated modifications. Python uses == for content comparison, supports concise slicing, and commonly builds strings by collecting pieces and calling join. Java’s split argument is a regular expression, while Python’s split normally treats its argument as a literal separator.

Official documentation for Python3 str type, Java String and StringBuilder classes.

String text = "hello";                                     // initialize, double quotes
String empty = "";                                         // ""
char first = text.charAt(0);                               // 'h', single quotes
char last = text.charAt(text.length() - 1);                // 'o'
int length = text.length();                                // 5
boolean isEmpty = text.isEmpty();                          // false

// Strings are immutable, so an update creates a new string.
String updated = text.substring(0, 1)
	+ "a"
	+ text.substring(2);                                   // "hallo"

String copy = new String(text);                            // "hello"
boolean equal = text.equals(copy);                         // true: same value
boolean sameString = text == copy;                         // false: different objects
boolean ignoreCase = "HELLO".equalsIgnoreCase(text);       // true
int comparison = "apple".compareTo("banana");              // negative: apple comes first

String slice = text.substring(1, 4);                       // "ell"; end is exclusive
boolean contains = text.contains("ell");                   // true
boolean starts = text.startsWith("he");                    // true
boolean ends = text.endsWith("lo");                        // true
int firstIndex = text.indexOf('l');                        // 2
int lastIndex = text.lastIndexOf('l');                     // 3
int missing = text.indexOf('z');                           // -1

String replaced = text.replace('l', 'x');                  // "hexxo"
String upper = text.toUpperCase();                         // "HELLO"
String lower = text.toLowerCase();                         // "hello"
String trimmed = "  hello  ".trim();                       // "hello"

String[] parts = "red,green,blue".split(",");              // ["red", "green", "blue"]
String joined = String.join("-", parts);                   // "red-green-blue"

char[] characters = text.toCharArray();                    // ['h', 'e', 'l', 'l', 'o']
Arrays.sort(characters);                                   // ['e', 'h', 'l', 'l', 'o']
String sorted = new String(characters);                    // "ehllo"

StringBuilder builder = new StringBuilder(text);           // "hello"
builder.append(" world");                                  // "hello world"
builder.insert(5, ",");                                    // "hello, world"
builder.setCharAt(0, 'H');                                 // "Hello, world"
builder.deleteCharAt(5);                                   // "Hello world"
builder.reverse();                                         // "dlrow olleH"
String result = builder.toString();                        // "dlrow olleH"

text = "hello"                                             # initialize
empty = ""                                                 # ""
first = text[0]                                            # "h"
last = text[-1]                                            # "o"
length = len(text)                                         # 5
is_empty = not text                                        # False

# Strings are immutable, so an update creates a new string.
updated = text[:1] + "a" + text[2:]                        # "hallo"

copy = text[:]                                             # "hello"
equal = text == copy                                       # True: same value
same_string = text is copy                                 # may be True; do not compare with is
ignore_case = "HELLO".casefold() == text.casefold()        # True
comes_first = "apple" < "banana"                           # True

slices = text[1:4]                                         # "ell"; end is exclusive
contains = "ell" in text                                   # True
starts = text.startswith("he")                             # True
ends = text.endswith("lo")                                 # True
first_index = text.find("l")                               # 2
last_index = text.rfind("l")                               # 3
missing = text.find("z")                                   # -1

replaced = text.replace("l", "x")                          # "hexxo"
upper = text.upper()                                       # "HELLO"
lower = text.lower()                                       # "hello"
trimmed = "  hello  ".strip()                              # "hello"

parts = "red,green,blue".split(",")                        # ["red", "green", "blue"]
joined = "-".join(parts)                                   # "red-green-blue"

characters = list(text)                                    # ["h", "e", "l", "l", "o"]
characters.sort()                                          # ["e", "h", "l", "l", "o"]
sorted_text = "".join(characters)                          # "ehllo"

pieces = []                                                # []
pieces.append("hello")                                     # ["hello"]
pieces.append("world")                                     # ["hello", "world"]
result = " ".join(pieces)                                  # "hello world"
reversed_text = text[::-1]                                 # "olleh"

Linked Lists

A linked list stores each value in a node that references the next node and, for a doubly linked list, the previous node. Linked lists do not support direct indexing, so reaching a specific position requires following each preceding node’s link and takes linear time. Inserting or removing a known node is constant time because no later elements need to shift.

Coding interview problems usually provide a custom singly linked ListNode rather than a library collection. Java also has a built-in LinkedList, while Python’s deque provides the commonly needed constant-time operations at both ends. Java’s LinkedList is not thread-safe and can be wrapped with Collections.synchronizedList when multiple threads share it. Python’s deque supports thread-safe appends and pops at either end, although compound sequences of operations still require separate synchronization. The custom-node examples below cover construction, traversal, insertion, and deletion.

Official documentation for Python3 deque type, Java LinkedList class.

// List.of() returns an unmodifiable list, but new LinkedList<>(collection)
// constructs a new LinkedList containing the collection’s elements.
LinkedList<Integer> values =
	new LinkedList<>(List.of(10, 20));                     // [10, 20]
values.addFirst(5);                                        // [5, 10, 20]
values.addLast(30);                                        // [5, 10, 20, 30]
int first = values.getFirst();                             // 5
int last = values.getLast();                               // 30
int removedFirst = values.removeFirst();                   // 5
int removedLast = values.removeLast();                     // 30
boolean contains = values.contains(20);                    // true

List<Integer> synchronizedValues =
	Collections.synchronizedList(
		new LinkedList<>(List.of(10, 20))
	);                                                     // thread-safe wrapper

class ListNode {
	int value;
	ListNode next;

	ListNode(int value) {
		this.value = value;
	}
}

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);                          // 1 -> 2 -> 3

int headValue = head.value;                                // 1
ListNode current = head;
while (current != null) {
	System.out.println(current.value);                     // 1, 2, 3
	current = current.next;
}

ListNode inserted = new ListNode(10);
inserted.next = head.next;
head.next = inserted;                                      // 1 -> 10 -> 2 -> 3

head.next = head.next.next;                                // delete 10: 1 -> 2 -> 3

from collections import deque

values = deque([10, 20])                                   # thread-safe appends and pops
values.appendleft(5)                                       # deque([5, 10, 20])
values.append(30)                                          # deque([5, 10, 20, 30])
first = values[0]                                          # 5
last = values[-1]                                          # 30
removed_first = values.popleft()                           # 5
removed_last = values.pop()                                # 30
contains = 20 in values                                    # True

class ListNode:
	def __init__(self, value, next_node=None):
		self.value = value
		self.next = next_node

head = ListNode(1, ListNode(2, ListNode(3)))               # 1 -> 2 -> 3

head_value = head.value                                    # 1
current = head
while current:
	print(current.value)                                   # 1, 2, 3
	current = current.next

inserted = ListNode(10, head.next)
head.next = inserted                                       # 1 -> 10 -> 2 -> 3

head.next = head.next.next                                 # delete 10: 1 -> 2 -> 3

Stacks

A stack follows last-in, first-out order: the most recently pushed value is the first one removed. Push, peek, and pop are normally constant-time operations. Stacks are common in bracket matching, expression evaluation, undo histories, monotonic-stack problems, and iterative depth-first search.

Java commonly uses ArrayDeque through the Deque interface instead of the legacy Stack class. Its stack operations use the front of the deque. Python usually uses a dynamic list, where append pushes to the top and pop removes from it. Both implementations raise an error when removing from an empty stack, so interview code should check emptiness when needed.

Official documentation for Java Deque interface and ArrayDeque class, and Python list type.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);                                            // top: 10
stack.push(20);                                            // top: 20
stack.push(30);                                            // top: 30

int top = stack.peek();                                    // 30; does not remove
int removed = stack.pop();                                 // 30
int newTop = stack.peek();                                 // 20
int size = stack.size();                                   // 2
boolean empty = stack.isEmpty();                           // false

while (!stack.isEmpty()) {
	System.out.println(stack.pop());                       // 20, 10
}

Integer missing = stack.peek();                            // null when empty
// stack.pop();                               // throws NoSuchElementException

stack = []
stack.append(10)                                           # top: 10
stack.append(20)                                           # top: 20
stack.append(30)                                           # top: 30

top = stack[-1]                                            # 30; does not remove
removed = stack.pop()                                      # 30
new_top = stack[-1]                                        # 20
size = len(stack)                                          # 2
empty = not stack                                          # False

while stack:
	print(stack.pop())                                     # 20, 10

# stack[-1]                                  # raises IndexError when empty
# stack.pop()                                # raises IndexError when empty

Queues

A queue follows first-in, first-out order: values enter at the back and leave from the front. Enqueue, front inspection, and dequeue are normally constant-time operations. Queues are central to breadth-first search, level-order tree traversal, scheduling, and processing work in arrival order.

Java typically declares a Queue and constructs an ArrayDeque. offer, peek, and poll are convenient because they use return values instead of throwing when an operation cannot be completed. Python uses collections.deque; appending at the right and calling popleft implements a queue without the linear-time front removal of a Python list.

Java’s Queue interface does not itself guarantee thread safety, and the commonly used ArrayDeque requires external synchronization. For producer-consumer applications, LinkedBlockingQueue provides thread-safe, optionally bounded, blocking operations. Python’s deque supports thread-safe individual appends and pops, while queue.Queue adds locking, optional capacity limits, and blocking put and get operations. Compound sequences still require careful synchronization.

Official documentation for Java Queue interface, ArrayDeque class, LinkedBlockingQueue class, Python deque type, and Python’s queue module.

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);                                           // front: 10
queue.offer(20);                                           // [10, 20]
queue.offer(30);                                           // [10, 20, 30]

int front = queue.peek();                                  // 10; does not remove
int removed = queue.poll();                                // 10
int newFront = queue.peek();                               // 20
int size = queue.size();                                   // 2
boolean empty = queue.isEmpty();                           // false

while (!queue.isEmpty()) {
	System.out.println(queue.poll());                      // 20, 30
}

Integer missing = queue.poll();                            // null when empty
// queue.remove();                             // throws NoSuchElementException

from collections import deque

queue = deque()
queue.append(10)                                           # front: 10
queue.append(20)                                           # deque([10, 20])
queue.append(30)                                           # deque([10, 20, 30])

front = queue[0]                                           # 10; does not remove
removed = queue.popleft()                                  # 10
new_front = queue[0]                                       # 20
size = len(queue)                                          # 2
empty = not queue                                          # False

while queue:
	print(queue.popleft())                                 # 20, 30

# queue[0]                                    # raises IndexError when empty
# queue.popleft()                             # raises IndexError when empty

Deques

A deque, pronounced “deck,” is a double-ended queue that supports insertion, inspection, and removal at both the front and back. These operations are normally constant time. Deques can act as either queues or stacks and are useful whenever a problem needs efficient access to both ends.

Java uses the Deque interface with ArrayDeque for most interview code. Python’s collections.deque exposes equivalent operations with append, appendleft, pop, and popleft. Python deques also support a fixed maxlen, which automatically discards values from the opposite end when full.

Java’s Deque methods often come in pairs: one form throws an exception when the operation fails, while the other returns false or null.

Operation	Front: throws	Front: special value	Back: throws	Back: special value
Insert	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Remove	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Examine	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

Deque extends Java’s Queue interface, so every deque implementation must provide all six queue methods. When used as a FIFO queue, values enter at the back and leave from the front. Java does not define a Stack interface; the older Stack type is a concrete legacy class. Instead, Deque defines three stack-style methods that operate at the front for LIFO usage. The combined table is intentionally asymmetric: the six queue methods are inherited from Queue, while Deque defines only three corresponding stack operations.

Queue method	Equivlt. `Deque` method	Stack method	Equivlt. `Deque` method
`add(e)`	`addLast(e)`	`push(e)`	`addFirst(e)`
`offer(e)`	`offerLast(e)`	`pop()`	`removeFirst()`
`remove()`	`removeFirst()`	`peek()`	`getFirst()`
`poll()`	`pollFirst()`
`element()`	`getFirst()`
`peek()`	`peekFirst()`

For thread safety, Java’s ArrayDeque requires external synchronization when shared across threads. LinkedBlockingDeque is thread-safe and supports blocking producer-consumer operations, although a sequence of multiple calls is not automatically one atomic operation. Python’s deque provides thread-safe appends and pops at both ends, but compound actions such as check-then-pop should still be protected with a threading.Lock.

Official documentation for Java Deque interface and ArrayDeque class, LinkedBlockingDeque class, and Python deque type.

// public ArrayDeque(Collection<? extends E> collection)
Deque<Integer> deque =
	new ArrayDeque<>(List.of(10, 20, 30));                 // [10, 20, 30]

deque.offerFirst(5);                                       // [5, 10, 20, 30]
deque.addFirst(0);                                         // [0, 5, 10, 20, 30]
deque.offerLast(40);                                       // [0, 5, 10, 20, 30, 40]
deque.addLast(50);                                         // [0, 5, 10, 20, 30, 40, 50]

int front = deque.peekFirst();                             // 0; null if empty
int back = deque.peekLast();                               // 50; null if empty
int first = deque.getFirst();                              // 0; throws if empty
int last = deque.getLast();                                // 50; throws if empty

int removedFront = deque.pollFirst();                      // 0
int removedBack = deque.pollLast();                        // 50
int removedFirst = deque.removeFirst();                    // 5
int removedLast = deque.removeLast();                      // 40

int size = deque.size();                                   // 3
boolean empty = deque.isEmpty();                           // false

deque.clear();
empty = deque.isEmpty();                                   // true
Integer missing = deque.peekFirst();                       // null
// deque.getFirst();                                       // throws NoSuchElementException

// LinkedBlockingDeque(n) is a thread-safe, bounded producer-consumer queue.
// Individual operations are thread-safe; multi-step sequences are not atomic.
BlockingDeque<Integer> bounded =
	new LinkedBlockingDeque<>(2);                           // maximum capacity: 2
bounded.offerLast(1);                                      // true
bounded.offerLast(2);                                      // true
boolean inserted = bounded.offerLast(3);                   // false: full
// Existing elements remain [1, 2]; nothing is discarded.

// These blocking methods throw InterruptedException.
// bounded.putLast(3);                                     // waits while full
// new LinkedBlockingDeque<Integer>().takeFirst();          // waits while empty
boolean timedInsert =
	bounded.offerLast(4, 1, TimeUnit.SECONDS);               // false after 1 second
Integer timedPoll =
	bounded.pollFirst(1, TimeUnit.SECONDS);                  // 1; returns immediately

from collections import deque

values = deque()
values.appendleft(20)                                      # deque([20])
values.appendleft(10)                                      # deque([10, 20])
values.append(30)                                          # deque([10, 20, 30])
values.extend([40, 50])                                    # deque([10, 20, 30, 40, 50])

front = values[0]                                          # 10
back = values[-1]                                          # 50
removed_front = values.popleft()                           # 10
removed_back = values.pop()                                # 50
size = len(values)                                         # 3
empty = not values                                         # False

values.rotate(1)                                           # deque([40, 20, 30])
values.rotate(-1)                                          # deque([20, 30, 40])

recent = deque(maxlen=3)                                   # rolling buffer
for number in [1, 2, 3, 4]:
	recent.append(number)
# deque([2, 3, 4]); append(4) discarded 1 from the left
recent.appendleft(0)
# deque([0, 2, 3]); appendleft(0) discarded 4 from the right
# append/appendleft do not return False, block, or reject the new value.

empty_deque = deque()
# empty_deque[0]                                           # raises IndexError
# empty_deque.popleft()                                    # raises IndexError

Hash Maps

A hash map associates unique keys with values. Lookup, insertion, update, and removal take constant time on average, though severe hash collisions can make an operation slower. Hash maps are essential for frequency counting, grouping, caching, recording indices, and replacing repeated linear searches.

Internally, Java’s HashMap uses an array of buckets. A key’s hash selects a bucket, and equals distinguishes keys that collide in the same bucket. In OpenJDK 21, collisions begin as linked nodes and heavily populated buckets may be converted into balanced tree bins. The internal bucket array grows, and its entries are redistributed, when the number of stored mappings exceeds capacity * load factor (default 0.75). CPython’s dict instead uses an open-addressed hash table: when a position is occupied, it probes other positions until it finds the key or an available slot. Both implementations keep spare capacity to make collisions uncommon and average lookups fast.

Java uses the Map interface with HashMap; methods such as getOrDefault, merge, and computeIfAbsent make counting and grouping concise. Python’s built-in dict preserves insertion order and provides get, setdefault, items, and dictionary comprehensions. In both languages, keys need stable hash and equality behavior while stored. Java keys rely on hashCode and equals, while Python keys must be hashable; mutable lists and dictionaries therefore cannot be Python dictionary keys.

For thread safety, Java’s HashMap requires external synchronization, such as Collections.synchronizedMap, and iteration or multi-step operations still need an explicit lock. CPython protects individual built-in dictionary operations, but this is an implementation detail rather than a general Python guarantee. Compound operations such as read-modify-write should therefore use threading.Lock in both regular and free-threaded Python builds.

Official documentation for Java Map interface and HashMap class, synchronizedMap, Python dict type, and Python’s thread-safety guidance.

Map<String, Integer> counts = new HashMap<>();
counts.put("apple", 1);                                    // {apple=1}
counts.put("banana", 2);                                   // {apple=1, banana=2}
counts.put("apple", 3);                                    // update apple to 3

int apples = counts.get("apple");                          // 3
Integer missing = counts.get("pear");                      // null
int pears = counts.getOrDefault("pear", 0);                // 0
boolean hasApple = counts.containsKey("apple");            // true
boolean hasTwo = counts.containsValue(2);                  // true

counts.merge("apple", 1, Integer::sum);                    // apple becomes 4
counts.merge("orange", 1, Integer::sum);                   // orange becomes 1

Map<Character, Integer> frequencies = new HashMap<>();
for (char letter : "banana".toCharArray()) {
	frequencies.merge(letter, 1, Integer::sum);
}                                                          // {a=3, b=1, n=2}

Map<Character, List<String>> groups = new HashMap<>();
for (String word : List.of("ant", "apple", "bat")) {
	groups.computeIfAbsent(word.charAt(0), key -> new ArrayList<>())
		.add(word);
}                                                          // a=[ant, apple], b=[bat]

// Iterates over the HashMap
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
	System.out.println(entry.getKey() + ": " + entry.getValue());
}

Integer removed = counts.remove("banana");                 // 2
bool canRemove = counts.remove("apple", 1);                // false
bool canRemove2 = counts.remove("apple", 4);               // true
int size = counts.size();                                  // 2
boolean empty = counts.isEmpty();                          // false

// HashMap is not thread-safe; wrap it when multiple threads share the map.
Map<String, Integer> sharedCounts =
	Collections.synchronizedMap(new HashMap<>());
sharedCounts.put("apple", 1);                               // synchronized method

// Iteration still requires manually locking the synchronized wrapper.
synchronized (sharedCounts) {
	for (Map.Entry<String, Integer> entry : sharedCounts.entrySet()) {
		System.out.println(entry.getKey() + ": " + entry.getValue());
	}
}

counts = {}
counts["apple"] = 1                                        # {"apple": 1}
counts["banana"] = 2                                       # add a key
counts["apple"] = 3                                        # update apple to 3

apples = counts["apple"]                                   # 3
pears = counts.get("pear", 0)                              # 0
has_apple = "apple" in counts                              # True
has_two = 2 in counts.values()                             # True

counts["apple"] = counts.get("apple", 0) + 1               # apple becomes 4
counts["orange"] = counts.get("orange", 0) + 1             # orange becomes 1

frequencies = {}
for letter in "banana":
	frequencies[letter] = frequencies.get(letter, 0) + 1
# {"b": 1, "a": 3, "n": 2}

groups = {}
for word in ["ant", "apple", "bat"]:
	groups.setdefault(word[0], []).append(word)
# {"a": ["ant", "apple"], "b": ["bat"]}

for key, value in counts.items():
	print(key, value)

removed = counts.pop("banana")                             # 2
size = len(counts)                                         # 2
empty = not counts                                         # False

Hash Sets

A hash set stores unique values without associating them with separate values. Membership, insertion, and removal take constant time on average. Hash sets are useful for duplicate detection, visited-state tracking, fast membership tests, and set operations such as union, intersection, and difference.

Java uses the Set interface with HashSet; add returns whether the value was newly inserted, and remove returns whether the value was present and removed. Python’s built-in set supports mathematical operators such as |, &, and -; remove raises KeyError for a missing value, while discard does nothing. Neither HashSet nor set should be treated as having a stable iteration order.

Official documentation for Java Set interface and HashSet class, and Python set type.

Set<Integer> seen = new HashSet<>();
boolean addedTen = seen.add(10);                           // true
boolean addedAgain = seen.add(10);                         // false; duplicate ignored
seen.add(20);                                              // {10, 20}

boolean contains = seen.contains(10);                      // true
boolean removedPresent = seen.remove(20);                  // true; 20 was removed
boolean removedMissing = seen.remove(99);                  // false; set unchanged
int size = seen.size();                                    // 1

int[] numbers = {1, 2, 1, 3, 2};
Set<Integer> unique = new HashSet<>();
for (int number : numbers) {
	unique.add(number);
}                                                          // {1, 2, 3}

Set<Integer> left = new HashSet<>(Set.of(1, 2, 3));        // mutable copy
Set<Integer> right = Set.of(3, 4);                         // unmodifiable

Set<Integer> union = new HashSet<>(left);
union.addAll(right);                                       // {1, 2, 3, 4}

Set<Integer> intersection = new HashSet<>(left);
intersection.retainAll(right);                             // {3}

Set<Integer> difference = new HashSet<>(left);
difference.removeAll(right);                               // {1, 2}

boolean subset = union.containsAll(left);                  // true

seen = set()
seen.add(10)                                # {10}
seen.add(10)                                # duplicate ignored
seen.add(20)                                # {10, 20}

contains = 10 in seen                       # True
seen.discard(20)                            # no error if missing
size = len(seen)                            # 1

numbers = [1, 2, 1, 3, 2]
unique = set(numbers)                       # {1, 2, 3}

left = {1, 2, 3}
right = {3, 4}
union = left | right                        # {1, 2, 3, 4}
intersection = left & right                 # {3}
difference = left - right                   # {1, 2}
subset = left <= union                      # True

removed = left.pop()                        # removes an arbitrary value
# left.remove(99)                           # raises KeyError
left.discard(99)                            # no error

Trees

A tree organizes nodes hierarchically under a root. Every node except the root has one parent, and nodes with no children are leaves. A node’s depth is its distance from the root, while a tree’s height describes its longest downward path to a leaf.

Interview questions normally provide a node class rather than a standard tree container. Java and Python therefore use small custom classes, with lists or arrays holding children. The examples below focus on basic construction, child access, leaf checks, and depth; traversal algorithms belong in a separate post.

Official documentation for Java List interface and Python list type.

Binary Trees

A binary-tree node has at most a left child and a right child. Basic operations include creating nodes, connecting or replacing children, reading values, checking whether a node is a leaf, and measuring depth.

class TreeNode {
	int value;
	TreeNode left;
	TreeNode right;

	TreeNode(int value) {
		this.value = value;
	}
}

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

boolean isLeaf = root.right.left == null
	&& root.right.right == null;                           // true

int rootValue = root.value;                                // 1
int leftValue = root.left.value;                           // 2
root.right.value = 30;                                     // update 3 to 30

int maxDepth(TreeNode node) {
	if (node == null) return 0;
	return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
int depth = maxDepth(root);                                // 3

class TreeNode:
	def __init__(self, value, left=None, right=None):
		self.value = value
		self.left = left
		self.right = right

root = TreeNode(
	1,
	TreeNode(2, TreeNode(4)),
	TreeNode(3),
)

is_leaf = (
	root.right.left is None
	and root.right.right is None
)                                                          # True

root_value = root.value                                    # 1
left_value = root.left.value                               # 2
root.right.value = 30                                      # update 3 to 30

def max_depth(node):
	if node is None:
		return 0
	return 1 + max(max_depth(node.left), max_depth(node.right))

depth = max_depth(root)                                    # 3

N-ary Trees

An N-ary node can have any number of children, usually stored in a list. Basic operations use that list to add, remove, access, or count children. A node is a leaf when its children list is empty.

class TreeNode {
	int value;
	List<TreeNode> children = new ArrayList<>();

	TreeNode(int value) {
		this.value = value;
	}
}

TreeNode root = new TreeNode(1);
TreeNode two = new TreeNode(2);
TreeNode three = new TreeNode(3);
TreeNode four = new TreeNode(4);
root.children.addAll(List.of(two, three, four));           // root.children is mutable
three.children.add(new TreeNode(5));                       // 1 -> [2, 3, 4], 3 -> [5]

boolean isLeaf = two.children.isEmpty();                   // true
int childCount = root.children.size();                     // 3
int secondChildValue = root.children.get(1).value;         // 3
root.children.remove(four);                                // children: [2, 3]

class TreeNode:
	# Avoid children=[]: mutable defaults are shared across calls.
	def __init__(self, value, children=None):
		self.value = value
		self.children = [] if children is None else children

two = TreeNode(2)
three = TreeNode(3, [TreeNode(5)])
four = TreeNode(4)
root = TreeNode(1, [two, three, four])                     # 1 -> [2, 3, 4]

is_leaf = not two.children                                 # True
child_count = len(root.children)                           # 3
second_child_value = root.children[1].value                # 3
root.children.remove(four)                                 # children: [2, 3]

Heaps and Priority Queues

A heap is a complete tree-shaped structure that keeps its highest-priority element at the root. A min-heap exposes the smallest value; a max-heap exposes the largest. Reading the root is constant time, while insertion and removal take logarithmic time. Building a heap from existing values takes linear time.

Priority queues use a heap to process values by priority instead of insertion order. Java’s PriorityQueue is a min-heap by default and accepts comparators for max-heaps or custom objects. Python’s heapq operates directly on lists as min-heaps; max-heaps are commonly simulated by negating numeric priorities, and tuples provide concise custom priorities.

Java’s PriorityQueue is neither thread-safe nor bounded; its capacity constructor sets only the initial storage size. PriorityBlockingQueue is thread-safe but remains unbounded, so enforcing a strict limit requires separate coordination such as a Semaphore. Python’s heapq likewise provides only heap operations on a regular list. For threaded producer-consumer code, queue.PriorityQueue(maxsize=n) combines priority ordering, synchronization, blocking operations, and an optional maximum capacity.

Official documentation for Java PriorityQueue and PriorityBlockingQueue classes, and Python heapq library and PriorityQueue class.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(30);
minHeap.offer(10);
minHeap.offer(20);                                         // heap contains 10, 20, 30

int smallest = minHeap.peek();                             // 10; does not remove
int removed = minHeap.poll();                              // 10
int newSmallest = minHeap.peek();                          // 20
int size = minHeap.size();                                 // 2

PriorityQueue<Integer> fromValues =
	new PriorityQueue<>(List.of(4, 1, 3));                 // heap built from values
int first = fromValues.poll();                             // 1

PriorityQueue<Integer> maxHeap =
	new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(30);
maxHeap.offer(20);
int largest = maxHeap.peek();                              // 30

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
	Comparator.comparingInt(Task::priority)
);
tasks.offer(new Task("email", 3));
tasks.offer(new Task("fix outage", 1));
tasks.offer(new Task("meeting", 2));
Task next = tasks.poll();                                  // name: "fix outage", priority: 1

while (!minHeap.isEmpty()) {
	System.out.println(minHeap.poll());                    // 20, 30
}

// PriorityQueue is not thread-safe and has no maximum-capacity option.
PriorityQueue<Integer> initialCapacity =
	new PriorityQueue<>(10);                                // 10 is not a limit

// PriorityBlockingQueue is thread-safe, but it is still unbounded.
BlockingQueue<Integer> concurrent =
	new PriorityBlockingQueue<>(10);                        // 10 is initial capacity

// Use a Semaphore to enforce capacity around a PriorityBlockingQueue.
Semaphore slots = new Semaphore(3);                        // maximum 3 elements
slots.acquire();
concurrent.put(10);                                        // producer consumes permit
int value = concurrent.take();                             // highest-priority value
slots.release();                                           // consumer restores permit

import heapq

min_heap = [30, 10, 20]
heapq.heapify(min_heap)                                    # linear-time heap construction

smallest = min_heap[0]                                     # 10; does not remove
removed = heapq.heappop(min_heap)                          # 10
heapq.heappush(min_heap, 5)                                # add 5
new_smallest = min_heap[0]                                 # 5
size = len(min_heap)                                       # 3

pushed_then_removed = heapq.heappushpop(
	min_heap,
	15,
)                                                          # 5

max_heap = []
for number in [10, 30, 20]:
	heapq.heappush(max_heap, -number)
largest = -max_heap[0]                                     # 30
removed_largest = -heapq.heappop(max_heap)                 # 30

tasks = []
heapq.heappush(tasks, (3, "email"))
heapq.heappush(tasks, (1, "fix outage"))
heapq.heappush(tasks, (2, "meeting"))
priority, name = heapq.heappop(tasks)                      # 1, "fix outage"

ordered = []
while min_heap:
	ordered.append(heapq.heappop(min_heap))
# ordered contains the remaining values in ascending order

# heapq uses a normal list: no capacity limit or thread coordination.
# queue.PriorityQueue combines priority, thread safety, and bounded capacity.
from queue import Empty, Full, PriorityQueue

bounded = PriorityQueue(maxsize=3)                         # maxsize <= 0 is unbounded
bounded.put((2, "meeting"))
bounded.put((1, "fix outage"))
bounded.put((3, "email"))                                  # queue is now full

try:
	bounded.put_nowait((4, "report"))
except Full:
	print("Queue is full")

priority, task = bounded.get()                             # 1, "fix outage"
bounded.task_done()

# put() waits when full; get() waits when empty.
empty_queue = PriorityQueue()
try:
	empty_queue.get_nowait()
except Empty:
	print("Queue is empty")

# Under concurrency, these values are only approximate snapshots.
size = bounded.qsize()                                     # approximately 2
is_empty = bounded.empty()                                 # False
is_full = bounded.full()                                   # False

Programming to an Interface

In Java, it is common to declare variables using an interface type on the left side and instantiate a concrete implementation class on the right side. The left side describes what behavior the variable should support, while the right side creates the actual object that provides that behavior. This style is often called programming to an interface, and it makes the code more flexible because the implementation can be changed later without changing the rest of the code that only depends on the interface.

Examples:

List<Integer> list = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
Deque<Integer> queue = new ArrayDeque<>();
Deque<Integer> stack = new ArrayDeque<>();
PriorityQueue<Integer> heap = new PriorityQueue<>();