# Shortest Common Supersequence - Google Top Interview Questions

### Problem Statement :

```Given strings a and b, return the length of the shortest string that has both a and b as subsequences.

Example 1

Input

a = "bell"

b = "yellow"

Output

7

Explanation

One possible solution is "ybellow".```

### Solution :

```                        ```Solution in C++ :

int solve(string a, string b) {
int M = a.size(), N = b.size();
vector<int> dp1(N + 1), dp2(N + 1);
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++)
dp1[j] =
a[i - 1] == b[j - 1] ? dp2[j - 1] + 1 : max(max(dp2[j], dp1[j - 1]), dp2[j - 1]);
dp2.swap(dp1);
}
return M + N - dp2[N];
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(String a, String b) {
int ans = 0;
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}

int temp = dp[a.length()][b.length()];
ans = temp + (a.length() - temp) + (b.length() - temp);
return ans;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, a, b):
return len(a) + len(b) - self.LCS(a, b)

def LCS(self, a, b):
m = len(a)
n = len(b)

# declaring the array for storing the dp values
L = [[None] * (n + 1) for i in range(m + 1)]

"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1]"""
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
L[i][j] = ""
elif a[i - 1] == b[j - 1]:
L[i][j] = L[i - 1][j - 1] + a[i - 1]
else:
if len(L[i - 1][j]) >= len(L[i][j - 1]):
L[i][j] = L[i - 1][j]
elif len(L[i - 1][j]) < len(L[i][j - 1]):
L[i][j] = L[i][j - 1]

# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return len(L[m][n])```
```

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F