Today, we will tackle common interview challenges regarding linked lists, focusing on honing your problem-solving skills. We'll explore ways to streamline and refine our coding techniques when working with linked lists. By the end, you'll have a better grasp of crafting efficient algorithms and writing clean, effective TypeScript code.

In this lesson, we will use the same linked list implementation as in the previous lesson, but with one additional method to display the list:

TypeScript
Copy to clipboard
1class ListNode<T> {
2    value: T;
3    next: ListNode<T> | null;
4
5    constructor(value: T) {
6        this.value = value;
7        this.next = null;
8    }
9}
10
11class LinkedList<T> {
12    head: ListNode<T> | null;
13
14    constructor() {
15        this.head = null;
16    }
17
18    append(value: T): void {
19        const newNode = new ListNode(value);
20
21        if (this.head === null) {
22            this.head = newNode;
23            return;
24        }
25
26        let currentNode = this.head;
27        while (currentNode.next !== null) {
28            currentNode = currentNode.next;
29        }
30
31        currentNode.next = newNode;
32    }
33
34    show(): void {
35        let currentNode = this.head;
36        while (currentNode) {
37            console.log(currentNode.value);
38            currentNode = currentNode.next;
39        }
40    }
41}

Our journey begins with a linked list with several duplicate values, resembling a situation where an email campaign wants to ensure duplicates don't get sent to the same recepient. We must eliminate duplicate nodes from our linked list.

We can use a set to keep track of the node values we've encountered. When a duplicate value surfaces, we bypass the node altogether, simplifying the process to a manageable single pass through the list or an $O(n)$ operation. This method efficiently preserves our list's uniqueness.

Here’s a step-by-step breakdown of how you'd implement such a solution:

TypeScript
Copy to clipboard
1function removeDuplicates<T>(list: LinkedList<T>): void {
2    if (list.head === null || list.head.next === null) return;
3
4    let currentNode = list.head;
5    const seen = new Set<T>([currentNode.value]);
6
7    while (currentNode.next !== null) {
8        if (seen.has(currentNode.next.value)) {
9            currentNode.next = currentNode.next.next;
10        } else {
11            seen.add(currentNode.next.value);
12            currentNode = currentNode.next;
13        }
14    }
15}

We begin with an empty set. Moving through the linked list, we add each unique value to the set. Whenever we encounter a value already in the set, we skip over the node containing it. This method ensures we only include each unique value once.

Here is an example of how we might use this function:

TypeScript
Copy to clipboard
1let list = new LinkedList<number>();
2list.append(1);
3list.append(1);
4list.append(3);
5list.append(3);
6list.append(3);
7list.append(5);
8removeDuplicates(list)
9list.show();  // 1 3 5

It successfully removes all the duplicates from the defined list.

For our next challenge, let's calculate the average of every third element in a linked list. Picture yourself in a fruit orchard, tasting every third apple to understand the overall harvest quality. While you would only sample some apples, this systematic approach lets you estimate the batch's quality reliably.

Much like our orchard sampling, sampling at consistent intervals can reduce noise in signal processing, helping us focus on signal trends. Consider financial analysts, who might average quarterly results to understand a company's performance trend.

We'll keep a running sum and a tally of every third element as we traverse the linked list. Once we reach the end, we can easily calculate the average, avoiding extra storage or double-handling of nodes. This simplification keeps our operation at $O(n)$ complexity, like sampling apples directly from the tree without hauling them all back to the barn first!

Here's how to implement this sampling:

TypeScript
Copy to clipboard
1function averageOfEveryThird<T>(list: LinkedList<number>): number {
2    if (list.head === null) return 0; 
3
4    let sum: number = 0, count: number = 0, index: number = 0;
5    let currentNode: ListNode<number> | null = list.head;
6
7    while (currentNode !== null) {
8        if ((index + 1) % 3 === 0) {
9            sum += currentNode.value;
10            count++;
11        }
12        currentNode = currentNode.next;
13        index++;
14    }
15
16    return parseFloat((sum / count).toFixed(2));
17}

Our implementation starts with checks for a "no apples" scenario. Strolling through our orchard, we sample every third apple and update our running total. Note that we use (index + 1) in the condition (index + 1) % 3 === 0 because we need every third apple, and indexing starts with 0. Finally, we average our notes to convey the orchard's overall apple quality. Rounding our average to two decimal places is akin to briefly summarizing our tastings.

Here is an example of how we might use this function:

TypeScript
Copy to clipboard
1let list = new LinkedList<number>();
2list.append(2);
3list.append(3);
4list.append(7);  // to be counted
5list.append(2);
6list.append(1);
7list.append(5);  // to be counted
8console.log(averageOfEveryThird(list)); // 6

The answer is 6 because it is the average value between the third value 7 and the sixth value 5.

In this session, we've applied discernment and mathematics to solve two linked list problems you're likely to encounter in job interviews. Using clear real-world analogies, we've related practical programming approaches to everyday tasks, enabling easier comprehension. By focusing on writing efficient TypeScript code, we've unraveled the problems to clear and swift solutions. Now, it's time to apply what you've learned in practical scenarios.