SDE - 1

You are given a list of ‘transactions’ between ‘n’ number of friends. who have to give each other money. The list consists of data of receiver, sender, and transaction.

Your task is to minimize the cash flow and the total number of transactions should also be minimum.

For example :

In figure 1 : friend-1 has to pay 2000$ to friend-2, and 4000$ to friend-3 and friend-2 has to pay 3000$ to friend-3.

In figure 2 : so we can minimize the flow between friend-1 to friend-2 by direct pay to friend-1 to friend-3

Cole is going on a date with Lili. But this date is a little strange, and it will last for ‘N’ days (day 1, day 2… day ‘N’) continuously. They will be going to the place known as ‘Kausani’. There are (‘N’ + ‘K’ - 1) restaurants (1, 2, …, ’N’ + ‘K’ - 1) situated on a line in ‘Kausani’.

On the ‘i-th’ day, they can go to any one of the restaurants from ‘i’ to ‘i’ + ‘K’ - 1, which Lilli will decide(one restaurant can be visited any number of times). You are given an array ‘A’ in which the ‘j-th‘ number denotes the number of coins that will be spent on restaurant ‘j’.

Cole is worried and wants to know the maximum total number of coins required on these N-dates with Lilli. Find the maximum total number of coins needed.

Examples:

‘N’ = 2
‘K’ = 2
‘A’ = {2, 3, 1}

On the 1st date, they can go to restaurant 1 or restaurant 2.
On the 2nd date, they can go to restaurant 2 or restaurant 3.

The possible combination of restaurants: 
‘1’ and ‘2’ on 1st date and 2nd date respectively = 2 + 3 = 5
‘1’ and ‘3’ on 1st date and 2nd date respectively = 2 + 1 = 3
‘2’ and ‘2’ on 1st date and 2nd date respectively = 3 + 3 = 6
‘2’ and ‘3’ on 1st date and 2nd date respectively = 3 + 1 = 4

Maximum Total number of coins = max(5, 3, 6, 4) = 6

There is a kingdom with ‘N’ cities that are connected by roads. The cities are connected to form a tree, where cities represent the nodes, and the roads represent the edges. The cities are numbered from 0 to ‘N-1’ and the length of each road is 1 unit.

A tree is a hierarchical data structure defined as a collection of nodes.

Now, a battle is going on in some cities of the kingdom, where the king must visit to restore peace. Initially, the king is at the 0th node(root node). The cities where battles are going on will be given as an input array, and the king has to visit in the same order as given in the input array 'battles'. You have to find the total length of the road the king has to travel to restore peace in all the cities.

For Example:

For the test case:
N = 3, Q = 2
Edge 1 connects 0 and 1
Edge 2 connects 0 and 2
battles = [1, 2]

The king has to visit first city 1 and then city 2. To visit city 1, he has to travel 1 unit, and now he is in city 1. To visit city 2 from city 1, he has to travel another 2 units. So overall, he has to travel 3 units of distance.

Ninja has ‘N’ gardens labeled from [1, N] under his supervision. He created an array that stores bidirectional paths between I1 and I2, where I1 and I2 are gardens stored at the position I in the array. In each garden, he wants to plant 4 types of flowers.

You need to choose a flower type for each garden such that any two gardens connected by a path, have different types of flowers.

Note:

1. All gardens have at most three paths coming into or leaving the garden. 
2. There can be more than one possible answer to this question. You need to print the smallest valid answer when all possible answers are sorted in lexicographical order.

You are given an integer ‘N’. You need to find an array of size 2*N that satisfies the following two conditions.

1. All numbers from 1 to N should appear exactly twice in the array.

2. The distance between the second occurrence and the first occurrence of any number should exactly be equal to the value of that number.

The distance between two numbers at indices ‘i’ and ‘j’ is defined as (j-i-1) where i < j.

If no such array exists, then you should return an empty array.

For example :

For N = 3 one valid array is [3,1,2,1,3,2].