Katkat
Back

Solve two linked list/array tasks

MetaMachine Learning Engineer · Technical Screen
EasyMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked list pointers to detect cycles and solve a classic array-based problem using the two-pointer technique to find specific target sums.

Part 1: Linked List Cycle Detection

Given the head of a singly linked list, write a function hasCycle(head) that returns true if the linked list contains a cycle, and false otherwise. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer.

Signature

def hasCycle(head: Optional[ListNode]) -> bool:

Example

Input: head = [3, 2, 0, -4], cycle pos = 1 Output: true Explanation: There is a cycle where the tail connects to the 2nd node.

Part 2: Two Sum in a Sorted Array

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed) as an array [index1, index2].

  • You may assume that each input would have exactly one solution.
  • You may not use the same element twice.
  • Your solution must use only O(1) extra space.

Signature

def twoSum(numbers: List[int], target: int) -> List[int]:

Example

Input: numbers = [2, 7, 11, 15], target = 9 Output: [1, 2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • -1000 <= target <= 1000

Hints

Hint 1

For the cycle detection, consider using two pointers moving at different speeds to see if they eventually meet.

Hint 2

For the sorted array problem, leverage the fact that the array is sorted by placing one pointer at the beginning and one at the end.

Hint 3

If the sum of the two pointers is too small, move the left pointer forward; if it is too large, move the right pointer backward.

Follow-up questions

  • In the cycle detection problem, what is the time and space complexity of your solution?
  • How would you modify the two-sum approach if the input array were not sorted?
  • What happens to your cycle detection logic if the linked list has only one node and no cycle?