atingarg1406/dsa-practice-problems

Solve some of the problems of Data Structure and Algorithm.

dsa-practice-problems's Issues

Structurally Identical program

Code the given problem in Python language.

Statement:
Given two generic trees, return true if they are structurally identical. Otherwise return false.
If the two given trees are made of nodes with the same values and the nodes are arranged in the same way, then the trees are called identical.

Input format:
The first line of input contains data of the nodes of the first tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.
The following line of input contains data of the nodes of the second tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.

Output format:
The first and only line of output contains true, if the given trees are structurally identical and false, otherwise.

Constraints:
Time Limit: 1 sec

Sample Input:
10 3 20 30 40 2 40 50 0 0 0 0
10 3 20 30 40 2 40 50 0 0 0 0

Sample Output:
true

Rain Water Trapping Problem

Provide the Brute, Better and Optimal Solution for this Question.

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

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: In this case, 6 units of rain water are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Geometric Sum Program

Code the given problem in any of the programming language.

Statement:
Given k, find the geometric sum i.e. 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k) using recursion.

Input format:
Integer k

Output format:
Geometric sum (up to 5 decimal places)

Constraints:
0 <= k <= 1000

Sample Input:
3

Sample Output:
1.87500

Staircase Program

Code the given problem in any of the programming language.

Statement:
A child is running up a staircase with N steps, and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs. You need to return number of possible ways W.

Input format:
Integer N

Output Format:
Integer W

Constraints:
1 <= N <= 30

Sample Input:
4

Sample Output:
7

Multiplication (Recursive) Program

Code the given problem in any of the programming language.

Statement:
Given two integers M & N, calculate and return their multiplication using recursion. You can only use subtraction and addition for your calculation. No other operators are allowed.

Input format:
Line 1: Integer M
Line 2: Integer N

Output format:
M x N

Constraints:
0 <= M <= 1000
0 <= N <= 1000

Sample Input:
3
5

Sample Output:
15

Replace with depth program

Code the problem in Python language. The code should be correct without any extra spaces and keywords.

Statement:
You are given a generic tree. You have to replace each node with its depth value. You just have to update the data of each node, there is no need to return or print anything.

Input format:
The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.

Output format:
The updated tree is printed level wise. Each level is printed in a new line. Please refer to sample output 1 for more details.

Constraints:
Time Limit: 1 sec

Sample Input:
10 3 20 30 40 2 40 50 0 0 0 0

Sample Output:
0
1 1 1
2 2

Count Leaf Nodes Program

Code the given problem in any of the programming language.

Statement:
Given a generic tree, count and return the number of leaf nodes present in the given tree.

Input format:
The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.

Output Format:
The first and only line of output prints the count of leaf nodes present in the given tree.

Constraints:
Time Limit: 1 sec

Sample Input:
10 3 20 30 40 2 40 50 0 0 0 0

Sample Output:
4

Node with maximum child sum program

Code the given problem in Python language.

Statement:
Given a generic tree, find and return the node for which sum of its data and data of all its child nodes is maximum. In the sum, data of the node and data of its immediate child nodes has to be taken.

Input format:
The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.

Output format:
The first and only line of output contains the data of the node with maximum sum, as described in the task.

Constraints:
Time Limit: 1 sec

Sample Input:
5 3 1 2 3 1 15 2 4 5 1 6 0 0 0 0

Sample Output:
1