How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Reddit.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Reddit during technical interviews.

Solve palindrome and list tasks | Reddit Coding Question

Solve palindrome and list tasks

Company: Reddit

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are asked to solve two coding problems. 1. **Build the shortest palindrome by prepending characters**: Given a string `s`, add characters only to the **front** of the string so that the final string is a palindrome. Return the shortest possible result. Aim for a solution better than checking every prefix naively. 2. **Reorder a linked list by index parity**: Given the head of a singly linked list, reorder the list so that all nodes at **odd 1-based positions** appear first, followed by all nodes at **even 1-based positions**. Preserve the relative order within the odd group and within the even group, and return the new head. For both problems, explain the algorithm and analyze time and space complexity.

Quick Answer: This question evaluates proficiency in string algorithms and linked list manipulation, specifically techniques for constructing the shortest palindrome by prepending characters and reordering singly linked lists by 1-based index parity.

Part 1: Build the shortest palindrome by prepending characters

Given a string s, add characters only to the front of the string so that the final result is a palindrome. Return the shortest possible palindrome. A naive approach that checks every prefix one by one is too slow for large inputs, so design a near-linear-time algorithm.

Constraints

0 <= len(s) <= 100000
s consists of lowercase English letters

Examples

Input: "aacecaaa"

Expected Output: "aaacecaaa"

Explanation: The longest palindromic prefix is "aacecaa", so only "a" must be added to the front.

Input: "abcd"

Expected Output: "dcbabcd"

Explanation: Only the first character is a palindromic prefix, so prepend the reverse of "bcd", which is "dcb".

Input: ""

Expected Output: ""

Explanation: The empty string is already a palindrome.

Input: "a"

Expected Output: "a"

Explanation: A single character is already a palindrome.

Input: "aaaa"

Expected Output: "aaaa"

Explanation: The entire string is already a palindrome, so nothing needs to be added.

Input: "abbacd"

Expected Output: "dcabbacd"

Explanation: The longest palindromic prefix is "abba". The remaining suffix is "cd", so prepend its reverse, "dc".

Hints

The key is to find the longest prefix of s that is already a palindrome.
Try building a pattern from s and reversed(s), then use a prefix-function such as KMP to find the overlap efficiently.

Part 2: Reorder a linked list by index parity

You are given a singly linked list and must reorder it so that all nodes at odd 1-based positions come first, followed by all nodes at even 1-based positions. Preserve the relative order within the odd-positioned nodes and within the even-positioned nodes. For easy testing in this version, the function receives a Python list of node values in linked-list order and should return the reordered values as a Python list.

Constraints

0 <= n <= 100000, where n is the number of nodes
Each node value fits in a 32-bit signed integer

Examples

Input: [1, 2, 3, 4, 5]

Expected Output: [1, 3, 5, 2, 4]

Explanation: Values at odd 1-based positions are 1, 3, and 5. Values at even positions are 2 and 4.

Input: [2, 1, 3, 5, 6, 4, 7]

Expected Output: [2, 3, 6, 7, 1, 5, 4]

Explanation: Odd-positioned values are 2, 3, 6, 7. Even-positioned values are 1, 5, 4.

Input: []

Expected Output: []

Explanation: An empty list remains empty.

Input: [10]

Expected Output: [10]

Explanation: A single node is already correctly ordered.

Input: [4, 4, 4, 4]

Expected Output: [4, 4, 4, 4]

Explanation: Odd-positioned values are [4, 4] and even-positioned values are [4, 4], so the final list looks the same.

Input: [-1, -2, -3, -4, -5, -6]

Expected Output: [-1, -3, -5, -2, -4, -6]

Explanation: Odd-positioned values are -1, -3, -5 and even-positioned values are -2, -4, -6.

Hints

Maintain two running chains: one for odd-positioned nodes and one for even-positioned nodes.
Save the head of the even chain before relinking so you can attach it after the odd chain at the end.

Quick Overview

This question evaluates proficiency in string algorithms and linked list manipulation, specifically techniques for constructing the shortest palindrome by prepending characters and reordering singly linked lists by 1-based index parity.