Solve linked list, string filtering, and puzzle
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Coding & Algorithms (3 tasks)
### 1) Find the 5th node from the end (singly linked list)
You are given the head pointer of a **singly linked list**.
- Return the **value** of the node that is the **5th from the end** (i.e., counting from the tail: tail is 1st).
- If the list has fewer than 5 nodes, specify a reasonable behavior (e.g., return `null` / throw an error).
**Constraints:** Aim for \(O(n)\) time and \(O(1)\) extra space.
---
### 2) Remove “camel-pattern” triplets from a string
Given a string `s` (ASCII letters only), remove every contiguous length-3 substring `s[i..i+2]` that matches the pattern:
- `s[i] == s[i+2]` (exact same character), and
- `s[i]` and `s[i+1]` have **different letter cases** (one uppercase, one lowercase).
After removals, the remaining parts are concatenated.
**Example**
- Input: `"AaADbDEeEbcvQv"`
- Output: `"bc"`
Clarify whether removals are **single pass** or **repeated until no more matches**; design your solution accordingly.
**Constraints:** \(1 \le |s| \le 2\times 10^5\).
---
### 3) Gold bar daily pay puzzle
A worker works **7 days** and is paid **one gold bar** total. The bar can be broken into pieces with **at most two breaks**.
- How can you pay the worker **each day** such that the daily payment is equal (i.e., each day receives exactly \(\tfrac{1}{7}\) of the total bar value)?
- You may exchange pieces back and forth each day (give/take pieces) as long as the net pay per day is correct.
Quick Answer: This multi-part question evaluates proficiency with linked-list pointer manipulation and constant-space linear-time algorithms, pattern-driven string transformation with attention to iteration semantics and edge-case handling, and combinatorial reasoning about constrained resource partitioning.
Fifth Node from the End
Return the value of the fifth node from the end of a linked list represented by values, or None if too short.
Examples
Input: ([1, 2, 3, 4, 5, 6],)
Expected Output: 2
Explanation: 5th from end is 2.
Input: ([1, 2, 3, 4],)
Expected Output: None
Explanation: Too short.
Input: ([5, 4, 3, 2, 1],)
Expected Output: 5
Explanation: Exactly five nodes.
Remove Camel-Pattern Triplets
Repeatedly remove length-3 substrings aBa where endpoints match and the first two letters differ in case.
Examples
Input: ('AaADbDEeEbcvQv',)
Expected Output: 'bc'
Explanation: Prompt example reduces to bc.
Input: ('aAa',)
Expected Output: ''
Explanation: Single removal.
Input: ('abc',)
Expected Output: 'abc'
Explanation: No removal.
Input: ('AaAaA',)
Expected Output: 'aA'
Explanation: Repeated removals via stack.
Gold Bar Seven-Day Payment Schedule
Return the worker-held piece values after each day using pieces 1, 2, and 4 sevenths.
Constraints
- At most two breaks create pieces of 1/7, 2/7, and 4/7
Examples
Input: ()
Expected Output: [[1], [2], [1, 2], [4], [1, 4], [2, 4], [1, 2, 4]]
Explanation: Canonical 1/2/4 piece exchange schedule.