Katkat
Back

Solve linked list reversal and minima problems

FortinetSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked list pointers iteratively and perform efficient binary search on a structurally complex matrix.

Part 1: Linked List Minimum

Given the head of a singly linked list of integers, write a function find_min(head) that returns the minimum value in the list. Assume the list is non-empty.

Part 2: Reverse Linked List

Write a function reverse_list(head) that reverses a singly linked list in-place and returns the new head.

Part 3: Search in Rotated Sorted Matrix

You are given an m x n matrix where each row is sorted in non-decreasing order and the first element of each row is greater than the last element of the previous row. However, the entire matrix has been 'rotated' such that it is no longer strictly increasing across the flat sequence.

Actually, consider a simpler variant: Given an m x n matrix where every row is sorted, and every column is sorted, write a function search_matrix(matrix, target) that returns True if target exists in the matrix, otherwise False.

Constraints:

  • Linked List: List length N is between 1 and 10^4. Values are between -10^6 and 10^6.
  • Matrix: M, N are between 1 and 500.

Examples:

Example 1 (List): Input: 3 -> 1 -> 4 -> 2 Output: Min = 1, Reversed = 2 -> 4 -> 1 -> 3

Example 2 (Matrix): Input: [[1, 4, 7], [2, 5, 8], [3, 6, 9]] Target: 5 Output: True

Hints

Hint 1

For the linked list, use a temporary pointer to track the current node and update the 'next' pointers one by one during traversal.

Hint 2

For the reversed list, keep track of 'prev', 'current', and 'next' nodes to avoid losing the rest of the list.

Hint 3

For the matrix search, start from the top-right corner; if the current element is greater than the target, move left, otherwise move down.

Follow-up questions

  • What is the time and space complexity of your list reversal in terms of N?
  • Can you implement the linked list reversal recursively instead of iteratively? What are the stack space implications?
  • If the matrix was rotated like a single sorted array (e.g., [4, 5, 6, 1, 2, 3]), how would you modify your search strategy to maintain O(log N) time?