FastPrepCount Ancestor Pairs under a Product Bound
Problems/Count Ancestor Pairs under a Product Bound

Count Ancestor Pairs under a Product Bound

Intuit logoIntuit● MediumFULLTIMEOA

Updated Oct 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: One OA report uses product <=K and another uses <K. This version uses the inclusive report; for a strict integer threshold call it with K-1. Root and parent-array conventions are practice assumptions; about 90% match.

The nodes of a rooted tree are labeled 1..n, with root 1. parents[v-1] gives the parent of node v and parents[0] is zero. Count pairs (u,v) where v is a strict ancestor of u and u*v <= k. A node is not its own ancestor. Each ancestor-descendant pair is counted once.

Function

ancestorPairs(parents: int[], k: long) → long

Examples

Example 1

parents = [0,1,1,2]k = 4return = 3

The qualifying products are 1*2, 1*3, and 1*4; 2*4 exceeds four.

Example 2

parents = [0,1,1,2]k = 8return = 4

The additional ancestor pair (4,2) meets equality.

Constraints

  • For this exercise, assume a valid rooted tree with 1 <= n <= 100000 and 0 <= k <= 10^10. Return a signed 64-bit pair count.

More Intuit Online Assessment questions

  • Employee Promotion OpportunitiesOA · Seen Oct 2026
  • Next Pascal Row CoefficientOA · Seen Oct 2026
  • Parse Router LogsOA · Seen Oct 2026
  • Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
  • Maximum Square-Free DivisorOA · Seen Oct 2026
  • Two Tribes from Taller-Person CountsOA · Seen Oct 2026
  • Shortest Path from an Encoded GraphOA · Seen Sep 2026
  • Oldest and Youngest EmployeesOA · Seen Sep 2026
  • Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
  • Submask Sum QueriesOA · Seen Sep 2026

Similar questions at other companies

  • Minimum Snapshots for a Version TreeAdobe · OAAdobe interview questions
  • Perfect AND Tree Leaf UpdatesPure Storage · ONSITE INTERVIEWPure Storage interview questions
  • Subtree Access OverridesPinterest · PHONE SCREENPinterest interview questions
  • Count Prime Values in SubtreesVisa · OAVisa interview questions
  • Minimum N-ary Tree Depth DeletionsSnowflake · OA · PHONE SCREENSnowflake interview questions
  • Part 1: The Narrowest KeyScale AI · OAScale AI interview questions
  • Photo AlbumHonda R&D · OA
  • Tree Pythagorean TriplesIBM · OAIBM interview questions
  • Rolling MetricsAkuna Capital · OAAkuna Capital interview questions
  • Centered Block Placement QueriesRoblox · OARoblox interview questions

Interview reports that mention this question

  • Intuit OA: What It Tests (2026)

Intuit interview experiences

  • Intuit Software Engineering Intern - Full Stack OA Format
All Intuit interview questionsSee Intuit hiring insights
Saved
class Solution {
    public long ancestorPairs(int[] parents, long k) {
        // Write your code here
    }
}
Checking account…