In this post, we will solve **Boleyn Salary HackerRank Solution**. This problem **(Boleyn Salary)** is a part of **HackerRank Functional Programming** series.

Contents

**Task**

Boleyn Su runs a company called Acme. There are *N* employees in the company, and each one of them is represented by a unique employee id whose range lies in *[1, N]*. Being the head of company, Boleyn’s employee id is *1*.

Each employee, except Boleyn, has exactly one direct superior. This means that the hierarchial structure of the company is like a tree, where

- Boleyn, employee id 1, represents the root node.
- Each pair of employee is directly or indirectly connected to one another.
- There is no cycle.

Let’s represent the salary by the array *s = {s[1], s[2], s[3]…, s[N]}*, where *s[i]* is the salary of the *i ^{th}* employee. Salary structure in the company is non-uniform. Even a subordinate may get a higher salary than her superior. Some of the employees in Acme are curious about who gets the

*k*lowest salary

^{th}*among her subordinates*. Help them in solving their query.

**Note**

*1*Â lowest salary is equivalent to lowest salary,Â^{st}*2*Â lowest means lowest salary which is greater thatÂ^{nd}*1*Â lowest salary, and so on.^{st}- Salary of each employee is different.
- It is not necessary that the people who are placed higher on hierarchy will have a greater salary than their subordinates.

**Input Format**

The first line contains two space separated integers,Â *N Q*, whereÂ *N*Â is the number of employees in Acme, andÂ *Q*Â is the number of queries.

Then followsÂ *N-1*Â lines. Each of these lines contain two space separated integers,Â *u p*, whereÂ *p*Â is the superior ofÂ *u*.Â *u*Â andÂ *p*Â are employees id.

In the next line there areÂ *N*Â space separated integers,Â *s[1] s[2] … s[n]*, whereÂ *s[i]*,Â *i âˆˆ [1..N]*, is the salary ofÂ *i ^{th}*Â employee.

Then,Â

*Q*Â queries follow. Each query contains two space separated integers,Â

*v k*. See output format for it’s definition.

**Output Format**

For the first query, print the id of employee who has theÂ *k ^{th}*Â lowest salary among the subordinates ofÂ

*v*.

For the subsequent queries, we need to find theÂ

*k*Â lowest salary of the subordinates ofÂ

^{th}*v+d*, whereÂ

*d*Â is the answer of previous query.

**Constraints**

- 1 â‰¤Â
*N*Â â‰¤ 3*10^{4} - 1 â‰¤Â
*Q*Â â‰¤ 3*10^{4} - 1 â‰¤Â
*s[i]*Â â‰¤ 10^{9},Â*i*Â âˆˆÂ*[1..N]* *s[i]*Â â‰ s[j], 1 â‰¤ i < j â‰¤Â*N*- 1 â‰¤Â
*u, p*Â â‰¤Â*N*,Â*u*Â â‰ Â*p* *-N*Â â‰¤Â*d*Â â‰¤Â*N*- ForÂ
*1*Â query, 1 â‰¤Â^{st}*v*Â â‰¤Â*N* - For later queries, 1 â‰¤Â
*v+d*Â â‰¤Â*N* - For each query, 1 â‰¤Â
*K*Â â‰¤ Number_of_subordinates

**Sample Input**

```
8 7
2 1
3 2
4 2
7 4
8 4
5 1
6 5
70 40 60 80 10 20 30 50
2 1
-6 5
-4 1
-5 3
2 1
-5 4
2 2
```

**Sample Output**

```
7
8
7
3
6
2
8
```

**Explanation**

Tree structure will be

```
1(70)
/ \
/ \
2(40) 5(10)
/ \ \
/ \ \
3(60) 4(80) 6(20)
/ \
/ \
7(30) 8(50)
```

*Query #1*Â `Node = 2`

,Â `k = 1`

: Subordinates, in increasing order of salary, areÂ *(7, 30), (8, 50), (3, 60), (4, 80)*. So employeeÂ *7*Â has theÂ *1 ^{st}*Â lowest salary among the subordinates ofÂ

*2*.

*Query #2*Â

`Node = -6+7 = 1`

,Â `k = 5`

: Subordinates areÂ *(5, 10), (6, 20), (7, 30), (2, 40), (8, 50), (3, 60), (4, 80)*Â .Â

*8*Â employee has theÂ

^{th}*5*Â lowest salary among the subordinate ofÂ

^{th}*1*.

*Query #3*Â

`Node = -4+8 = 4`

,Â `k = 1`

: Subordinates areÂ *(7, 30), (8, 50)*Â . Similarly 7 is the answer of this query.

*Query #4*Â

`Node = -5+7 = 2`

,Â `k = 3`

: Subordinates areÂ *(7, 30), (8, 50), (3, 60), (4, 80)*. Similarly 3 is the answer for this query.

*Query #5*Â

`Node = 2+3 = 5`

,Â `k = 1`

: Subordinates areÂ *(6, 20)*.Â

*6*Â employee has the most, and only, lowest salary.

^{th}*Query #6*Â

`Node = -5+6 = 1`

,Â `k = 4`

: Subordinates areÂ *(5, 10), (6, 20), (7, 30), (2, 40), (8, 50), (3, 60), (4, 80)*. 2 is answer of this query.

*Query #7*Â

`Node = 2+2 = 4`

,Â `k = 2`

: Subordinates areÂ *(7, 30), (8, 50)*. EmployeeÂ

*8*Â has the second lowest salaries among the subordinates of 4.

**Solution – Boleyn Salary – HackerRank Solution**

**Scala**

import java.util.Scanner import scala.collection.immutable.TreeMap object Solution { def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val n = sc.nextInt val q = sc.nextInt val links = (0 until n - 1).map(_ => (sc.nextInt, sc.nextInt)) .groupBy(_._2) .map { case (key, list) => key -> list.map(_._1) } val salaries = (0 until n).map(_ => sc.nextInt) case class Node(index: Int, count: Int, children: Seq[Node], data: TreeMap[Int, Int]) val nodes = Array.ofDim[Node](n + 1) def create(index: Int): Node = { val children = links.get(index) match { case None => Nil case Some(v) => v.map(create) } val sortedChildren = children.sortBy(-_.count) val data = if (children.isEmpty) TreeMap[Int, Int]() else sortedChildren.tail.foldLeft(sortedChildren.head.data + (salaries(sortedChildren.head.index - 1) -> sortedChildren.head.index))( (acc, c) => acc ++ c.data + (salaries(c.index - 1) -> c.index) ) val res = Node(index, children.map(_.count).sum, children, data) nodes(index) = res res } create(1) var answer = 0 (0 until q).foreach(_ => { val v = sc.nextInt val k = sc.nextInt val id = answer + v answer = nodes(id).data.drop(k - 1).values.head println(answer) }) } }

**Note:** This problem **(Boleyn Salary)** is generated by **HackerRank** but the solution is provided by** CodingBroz**. This tutorial is only for **Educational** and **Learning** purpose.