← Pinterest Interview Insights

Pinterest·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
May 2026

Summary

Pinterest ML engineer interview, technical phone screen that was basically a pure DSA session. Two parts to one problem, both on trees and linked lists. Nothing ML-specific came up at all, which surprised me.

Questions Asked (2)

Q1

Given a binary search tree, convert it in-place to a sorted circular doubly linked list where the left pointer acts as predecessor and the right pointer as successor. The smallest element's predecessor should wrap around to the largest. Solve in O(n) time with O(h) extra space.

Algorithms & Data Structures
Author's notes

The in-place constraint is where it gets annoying.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use an in-order traversal to visit nodes in sorted order, maintaining a pointer to the previously visited node to link them. After traversal, connect the first and last nodes to form the circular doubly linked list. This achieves O(n) time and O(h) space due to recursion stack.

Pro tip: Emphasize that the conversion is in-place and that the space complexity is O(h) from the recursion stack, not O(n). Mention that an iterative Morris traversal could achieve O(1) space, but it modifies the tree temporarily and may not be suitable for all contexts.

1. Clarify requirements and constraints

Confirm that the conversion should be in-place, the list should be circular, and the left/right pointers become predecessor/successor. Note the O(n) time and O(h) space constraints.

2. Choose traversal method

Select in-order traversal to process nodes in sorted order. Decide between recursive (simpler, O(h) space) or iterative (explicit stack, O(h) space) approaches.

3. Link nodes during traversal

Maintain a 'prev' pointer. For each node, set node.left = prev and if prev exists, prev.right = node. Update prev to current node.

4. Close the circular list

After traversal, connect the first node (smallest) and last node (largest): first.left = last and last.right = first.

5. Analyze complexity and edge cases

Discuss time O(n) and space O(h). Handle edge cases: empty tree, single node, skewed tree (h = n).

Key Points to Mention

  • In-order traversal yields nodes in sorted order, which is essential for a sorted linked list.
  • Maintain a 'prev' pointer to link nodes as you traverse, updating left and right pointers accordingly.
  • After traversal, connect the first and last nodes to make the list circular.
  • Time complexity is O(n) because each node is visited once; space complexity is O(h) due to recursion stack (or explicit stack).
  • Edge cases: empty tree returns null; single node points to itself; skewed tree has O(n) space if recursive.
  • The conversion is in-place, meaning no new nodes are created; only pointers are rearranged.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Follow-up: given the sorted circular doubly linked list from the previous problem, write a function to insert a new value while keeping the list sorted. Your solution must correctly handle an empty list, inserting before the smallest element, inserting after the largest element, and duplicate values.

Algorithms & Data Structures
Author's notes

The edge cases are the whole point of this question.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the structure and edge cases, then design an algorithm that traverses the list to find the correct insertion point, handling empty, smallest, largest, and duplicate scenarios. Write clean code with careful pointer updates, and test with examples covering all cases.

Pro tip: Use a sentinel node or handle the empty list as a special case upfront to simplify pointer manipulation and avoid null checks throughout the traversal.

1. Clarify requirements and edge cases

Confirm the list is sorted in ascending order, circular, and doubly linked. Discuss how to handle empty list, insertion before smallest, after largest, and duplicates (e.g., insert before or after existing duplicates).

2. Design the algorithm

If the list is empty, create a new node pointing to itself. Otherwise, traverse from the head to find the first node with value >= new value. If all values are smaller, insert after the tail (which is the node before head).

3. Implement pointer updates

Carefully update next and prev pointers of the new node and its neighbors. Ensure the circular links are maintained, especially when inserting at the head or tail.

4. Test with examples

Walk through test cases: empty list, insert at beginning, middle, end, and duplicate values. Verify that the list remains sorted and circular.

Key Points to Mention

  • Handling empty list by creating a self-referential node.
  • Traversal termination condition: stop when current node's value >= new value or when we complete a full circle.
  • Insertion before the smallest element: update head pointer if necessary.
  • Insertion after the largest element: insert between tail and head.
  • Duplicate values: decide whether to insert before or after existing duplicates (typically before to maintain stability).
  • Time complexity O(n) and space complexity O(1).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.