Katkat
Back

Solve linked list, string filtering, and puzzle

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked list pointers in-place, apply conditional string filtering with index tracking, and solve a greedy resource partitioning puzzle.

Part 1: Linked List Reversal

Given the head of a singly linked list, reverse the order of the nodes such that the last node becomes the first. You must perform this in-place with O(1) extra space.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    pass

Part 2: String Filtering

Given a string s, remove all characters that appear at an even index (0-indexed). Return the resulting string. Your solution should be O(n) in time.

Example: Input: s = "abcdef" Output: "bdf" (Indices 0, 2, 4 are 'a', 'c', 'e', which are removed.)

Part 3: Resource Partitioning

You have N items of equal size and K containers. Each container must hold at least one item. What is the maximum number of items that can be placed into a single container such that every container still satisfies the requirement? Provide the mathematical formula or logic to determine this.

Constraints:

  • Linked list length: 0 to 10^4
  • String length: 0 to 10^5
  • N >= K
  • All inputs are non-negative integers or standard strings.

Hints

Hint 1

For the linked list, use three pointers (prev, current, next) to track the nodes while rerouting the 'next' references.

Hint 2

For the string filtering, iterate through the string and collect characters only if their index modulo 2 is not zero.

Hint 3

For the partitioning puzzle, to maximize one container, distribute the minimum required amount (1 item) to all other (K-1) containers first.

Follow-up questions

  • How would you modify the linked list reversal to only reverse nodes between position M and N?
  • If the string filtering was restricted to `O(1)` extra space (ignoring the output string), how would you approach it in languages like C++ where strings are mutable?
  • How does the resource partitioning logic change if each container has a specific capacity limit?