## Clone linked list with next and random pointer

in
Algorithm,
Datastructure,
Linked List
- on 05:47:00
- No comments

Clone linked list with next and random pointer

You are given a Doubly Link List with one pointer of each node pointing to the next node just like in a singly link list.The second pointer however can point to any node in the list and not just the previous node.

You are given a Doubly Link List with one pointer of each node pointing to the next node just like in a singly link list.The second pointer however can point to any node in the list and not just the previous node.

**Lets understand the problem statement graphically and it will be more clear,**## Serialize and Deserialize a Binary Tree

in
Binary Tree,
Interviews
- on 10:55:00
- No comments

Serialize and Deserialize a Binary Tree

Design an algorithm to serialize and deserialize given Binary Tree. Serialization is to store tree in a File/String, so that it can be later restored.

Deserialization is reading tree back from file.

We need to Serialize given Binary Tree into String(So that we can write it to File or transfer it).

Also, we need to read the Serialized String and Deserialize it back to original Binary Tree.

Design an algorithm to serialize and deserialize given Binary Tree. Serialization is to store tree in a File/String, so that it can be later restored.

Deserialization is reading tree back from file.

**Lets understand the problem statement graphically and it will be more clear,**We need to Serialize given Binary Tree into String(So that we can write it to File or transfer it).

Also, we need to read the Serialized String and Deserialize it back to original Binary Tree.

## Trapping Rain Water between Towers

in
Algorithm,
Datastructure,
Interviews
- on 13:07:00
- No comments

How Much Water Can A Bar Graph Hold

Given an bar graph, encoded as an array of non-negative integers, calculate the units of water that this bar graph can hold.

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.

Input = [2, 0, 2]

Output = 2

Input = [3, 0, 0, 2, 0, 4]

Output = 10

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

Output = 6

Given an bar graph, encoded as an array of non-negative integers, calculate the units of water that this bar graph can hold.

**Let us put in technical terms,**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.

**Lets understand the problem statement graphically and it will be more clear,****Case 1:**Input = [2, 0, 2]

Output = 2

**Case 2:**Input = [3, 0, 0, 2, 0, 4]

Output = 10

**Case 3:**Input = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output = 6