Katkat
Back

Solve palindrome and list tasks

RedditMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate string prefixes to satisfy palindromic properties and your skill in performing in-place linked list reordering based on node index parity.

Part 1: Shortest Palindrome

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can create by performing this transformation.

Example: Input: s = "aacecaaa" Output: "aaacecaaa"

Input: s = "abcd" Output: "dcbabcd"

Part 2: Linked List Parity Reordering

Given the head of a singly linked list, group all nodes with odd indices together followed by nodes with even indices. Note that this refers to the 1-based index of the node in the list. The relative order inside both the odd and even groups should remain as it was in the input.

You must solve this in O(n) time complexity and O(1) space complexity.

Example: Input: head = [1, 2, 3, 4, 5] Output: [1, 3, 5, 2, 4]

Explanation:

  • Odd indices: 1st (1), 3rd (3), 5th (5)
  • Even indices: 2nd (2), 4th (4)
  • Result: 1 -> 3 -> 5 -> 2 -> 4

Constraints:

  • s length: 0 to 5 * 10^4
  • Linked list length: 0 to 10^4

Hints

Hint 1

For the palindrome task, consider finding the longest palindromic prefix of the original string; the remaining suffix must be reversed and prepended.

Hint 2

For the linked list task, maintain two separate pointers (or dummy heads) to track the odd and even chains as you iterate through the list.

Hint 3

In the linked list task, ensure you correctly terminate the 'odd' chain by connecting it to the start of the 'even' chain after the traversal.

Follow-up questions

  • How would your approach for the shortest palindrome change if you were allowed to add characters to either the beginning OR the end?
  • Can you modify the linked list solution to perform the reordering in groups of three (1st, 4th, 7th...) instead of simple parity?
  • What are the implications of recursion vs. iteration for the linked list manipulation in terms of stack depth and readability?