SDE - 1

Given an array arr of N integers. Find the contiguous sub-array with maximum sum.

Input:

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output:

Print the maximum sum of the contiguous sub-array in a separate line for each test case.

Constraints:

1 ≤ T ≤ 110

1 ≤ N ≤ 106

-107 ≤ A[i] <= 107

Example:

Input

2

5

1 2 3 -2 5

4

-1 -2 -3 -4

Output

9

-1

There are given N ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. The task is to connect the ropes with minimum cost.

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N where N is the number of ropes. The second line of each test case contains N input L[i],length of ropes.

Output:

For each testcase, print the minimum cost to connect all the ropes.

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 106

1 ≤ L[i] ≤ 106

Example:

Input:

2

4

4 3 2 6

5

4 2 7 6 9

Output:

29

62

Given a Binary Tree, print Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument.

Left view of following tree is 1 2 4 8.

         1

      /     \

    2        3

  /     \    /    \

 4     5   6    7

  \

    8    

Example 1:

Input:

  1

/  \

3    2

Output: 1 3

Example 2:

Input:

Output: 10 20 40

Print all three nodes in a binary tree such that sum of all these three nodes is greater than given x and these three nodes must hold the relationship of grandparent-parent-child. Expected Complexity – O(n)

Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. Each house has a[i] amount of money present in it.

Input:

The first line of input contains an integer T denoting the number of test cases. T testcases follow. Each test case contains an integer n which denotes the number of houses. Next line contains space separated numbers denoting the amount of money in each house.

Output:

For each testcase, in a newline, print an integer which denotes the maximum amount he can take home.

Constraints:

1 <= T <= 200

1 <= n <= 104

1 <= a[i] <= 104

Example:

Input:

2

6

5 5 10 100 10 5

3

1 2 3

Output:

110

4

Tell me about yourself.

Why are looking for a change, you recently joined a company and now again you are giving interviews.

 Mutex vs Semaphores with a real-life example.

Normalization and why it is done?

Rest API.

Rabbit MQ and Kafka.

Write a shell script to parse a log file.