SDE - 1

Linked List Sum of Nodes Between 0s

Given a linked list which contains a series of numbers separated by “0”. Add them and store them in the linked list in-place.

Note :There will not be continuous zeros in input.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Examples:

Input: arr[]   = {2, 0, 2}

Output: 2

Explanation:

The structure is like below

We can trap 2 units of water in the middle gap.

Input: arr[]   = {3, 0, 2, 0, 4}

Output: 7

Explanation:

Structure is like below

We can trap "3 units" of water between 3 and 2,

"1 unit" on top of bar 2 and "3 units" between 2  

and 4.  See below diagram also.

Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

Explanation:

The structure is like below

Trap "1 unit" between first 1 and 2, "4 units" between

first 2 and 3 and "1 unit" between second last 1 and last 2.

 Devise the most optimised way way to find an element in the rotated sorted array.

sortedPivotedArray

Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

        key = 3

Output : Found at index 8

Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

        key = 30

Output : Not found

Input : arr[] = {30, 40, 50, 10, 20}

       key = 10    

Output : Found at index 3

Connect n ropes with minimum cost

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 the sum of their lengths. We need to connect the ropes with minimum cost.

For example, if we are given 4 ropes of lengths 4, 3, 2, and 6. We can connect the ropes in the following ways.

1) First, connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6, and 5.

2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.

3) Finally connect the two ropes and all ropes have connected.

Total cost for connecting all ropes is 5 + 9 + 15 = 29. This is the optimized cost for connecting ropes. Other ways of connecting ropes would always have same or more cost. For example, if we connect 4 and 6 first (we get three strings of 3, 2 and 10), then connect 10 and 3 (we get two strings of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.