Amazon
  • Introduction
  • Phone Interview I
    • 53.Reverse Words in a String
    • 31.Partition Array
  • Phone Interview II
    • 167.Add Two Numbers
    • 88.Lowest Common Ancestor
  • Onsite I
    • 655.Big Integer Addition
    • 221.Add Two Numbers II
  • Onsite II
    • 158.Two Strings Are Anagrams
    • 171.Anagrams
    • 386.Longest Substring with At Most K Distinct Characters
  • Onsite III
    • 479.Second Max of Array
    • 589.Connecting Graph
  • Onsite IV
    • 532.Reverse Pairs
  • 2022
    • OA
      • work simulation
      • Greyness
      • NearestRetailer
      • Sum of Scores of Subarray
      • StrengthOfPassword
      • ProductOf1
      • Move 0/1 InArray
      • Max deviation among all substrings
      • AWS power consumption
      • searchWordResultWord
      • maxOperationOfString
      • MinHealthGame
      • EarliestMonth
      • Package ship
      • RatingConsectiveDecresing
      • LinkedListSum
      • MovingBoxes
      • ValidString
      • MaxValueAfterRemovingFromString
      • Subtree with Maximum Average
    • VO
      • 2022.3
    • BQ
      • doc
      • 2022.4
      • Freq Question
      • 11大类BQ和Follow-ups
      • Page 1
      • BQ 100
      • 35 behavioral questions asked in 95% of Amazon interviews with examples
      • Page 2
      • 反向BQ
    • LP
      • LP-1
      • LP-2
    • SD
      • Design Amazon Prime Video Recommendation System
      • Amazon Order system
    • OOD
      • Linux Find Command
      • Amazon Locker
    • AWS Identity call
    • Interviews
Powered by GitBook
On this page

Was this helpful?

  1. 2022
  2. OA

Subtree with Maximum Average

PreviousMaxValueAfterRemovingFromStringNextVO

Last updated 3 years ago

Was this helpful?

Given an N-ary tree, find the subtree with the maximum average. Return the root of the subtree. A subtree of a tree is the node which have at least 1 child plus all its descendants. The average value of a subtree is the sum of its values, divided by the number of nodes.

Example 1:

Input:
            20
	   /   \
	 12     18
      /  |  \   / \
    11   2   3 15  8

Output: 18
Explanation:
There are 3 nodes which have children in this tree:
12 => (11 + 2 + 3 + 12) / 4 = 7
18 => (18 + 15 + 8) / 3 = 13.67
20 => (12 + 11 + 2 + 3 + 18 + 15 + 8 + 20) / 8 = 11.125

18 has the maximum average so output 18.

Similar questions:

https://leetcode.com/discuss/interview-question/349617#:~:text=Amazon%20%7C%20OA%202019%20%7C%20Subtree%20with%20Maximum%20Average,-88&text=A%20subtree%20of%20a%20tree,by%20the%20number%20of%20nodes.
https://leetcode.com/problems/maximum-average-subtree