# Java 26 CodeSignal Interview Handbook
# Chapter 01 - Collections (Part 1)

> Difficulty: Easy → Hard
> Language: Java 26

---

# Question 1 - ArrayList vs LinkedList

## Problem

Explain the differences between `ArrayList` and `LinkedList`.
Which one should you choose and why?

---

## Solution 1 - Theory

| Operation | ArrayList | LinkedList |
|-----------|----------:|-----------:|
| get(index) | O(1) | O(n) |
| add(end) | O(1) amortized | O(1) |
| add(middle) | O(n) | O(n)\* |
| remove(end) | O(1) | O(1) |
| remove(beginning) | O(n) | O(1) |
| Memory | Low | High |

\*Insertion itself is O(1), but locating the node is O(n).

---

## Solution 2 - Code Example

```java
List<Integer> array = new ArrayList<>();
List<Integer> linked = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    array.add(i);
    linked.add(i);
}

System.out.println(array.get(900_000));   // O(1)
System.out.println(linked.get(900_000));  // O(n)
```

---

## Interview Tips

- Prefer `ArrayList` for most business applications.
- Use `LinkedList` for queue/deque style workloads.

---

# Question 2 - Vector vs ArrayList

## Brute Force Answer

```text
Vector is synchronized.
ArrayList is not.
```

Interviewers expect more.

---

## Detailed Comparison

| Feature | Vector | ArrayList |
|---------|---------|-----------|
| Thread Safe | Yes | No |
| Performance | Slower | Faster |
| Introduced | JDK 1.0 | JDK 1.2 |
| Growth | 2x | 1.5x |

---

## Solution

```java
List<String> list = new Vector<>();
list.add("Java");

List<String> fast = new ArrayList<>();
fast.add("Java");
```

---

## Modern Replacement

```java
List<String> list =
        Collections.synchronizedList(
                new ArrayList<>());
```

or

```java
CopyOnWriteArrayList<String> list =
        new CopyOnWriteArrayList<>();
```

---

# Question 3 - HashMap Internals

## Interview Question

How does `HashMap` work internally?

---

## Answer

1. Compute hashCode().
2. Spread the hash.
3. Calculate bucket index.
4. Search bucket.
5. Store entry.
6. Convert long collision chains to a red-black tree (JDK 8+) when thresholds are exceeded.

---

## Code

```java
Map<Integer,String> map = new HashMap<>();

map.put(1,"Java");
map.put(2,"Redis");
map.put(3,"Kafka");

System.out.println(map.get(2));
```

Complexity

```text
Average : O(1)

Worst   : O(log n) after treeification
```

---

# Question 4 - LinkedHashMap

Maintains insertion order.

```java
Map<Integer,String> map =
        new LinkedHashMap<>();

map.put(3,"C");
map.put(1,"A");
map.put(2,"B");

System.out.println(map);
```

Output

```text
3=C
1=A
2=B
```

Used for LRU cache.

---

# Question 5 - TreeMap

Maintains sorted keys.

```java
TreeMap<Integer,String> map =
        new TreeMap<>();

map.put(30,"C");
map.put(10,"A");
map.put(20,"B");

System.out.println(map);
```

Output

```text
10=A
20=B
30=C
```

Complexity

```text
put O(log n)

get O(log n)
```

Implemented using a Red-Black Tree.

---

# Interview Summary

| Collection | Ordered | Sorted | Thread Safe |
|------------|---------|---------|-------------|
| ArrayList | Yes | No | No |
| LinkedList | Yes | No | No |
| Vector | Yes | No | Yes |
| HashMap | No | No | No |
| LinkedHashMap | Yes | No | No |
| TreeMap | Sorted | Yes | No |