← AppLovin Interview Insights

AppLovin·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Had a coding round at Applovin that was basically a twist on a classic BST validation problem. Not a brutal interview but the variant caught me a little off guard since I'd only ever practiced the boolean version.

Questions Asked (1)

Q1

Given a binary tree, instead of just checking whether it's a valid BST, return the count of nodes that violate the BST property, meaning nodes whose values fall outside the valid range for their position during an in-order traversal.

Algorithms & Data Structures
Author's notes

I knew the standard recursive approach with low/high bounds, so the structure came to me fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a recursive DFS that passes down the valid (min, max) range for each node, counting nodes that fall outside their allowed range. For each node, if its value is outside the range, increment the count and do not update the range for its children (since the subtree is already invalid). Otherwise, recurse left with (min, node.val) and right with (node.val, max).

Pro tip: Clarify the definition of 'violating node' upfront: a node is counted if its value is outside the range determined by its ancestors, regardless of whether its own children are valid. This avoids ambiguity and shows attention to detail.

1. Clarify the problem and edge cases

Confirm that a node is counted if its value is outside the valid range for its position, and that we count each violating node once. Discuss edge cases: empty tree, single node, duplicates (if allowed), and how to handle nodes that are part of a violating subtree.

2. Define the recursive function

Design a helper function that takes a node, a lower bound, and an upper bound, and returns the count of violating nodes in the subtree. Use long integers or null to represent unbounded ranges.

3. Implement the recursion with range propagation

At each node, check if its value is outside (lower, upper). If so, increment count and recurse on children with the same bounds (since the subtree is already invalid). Otherwise, recurse left with (lower, node.val) and right with (node.val, upper).

4. Analyze complexity and test

State that the time complexity is O(n) since each node is visited once, and space complexity is O(h) for recursion stack. Walk through a small example to verify correctness.

Key Points to Mention

  • Use of range propagation (min/max bounds) to validate each node's position.
  • Handling of integer overflow by using long or null for bounds.
  • Decision to not update bounds for children of a violating node to avoid double-counting.
  • Time and space complexity analysis.
  • Edge cases: empty tree, single node, duplicates (if allowed).
  • Difference from standard BST validation: counting violations instead of just returning boolean.

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