06-12-2020

# Aptitude

Find the missing term: 2, 3, 5, 7, 11, ?, 17

A. 12

B. 13

C. 14

D. 15

Ans : 13 Clearly, the given series consists of prime numbers starting from 2. So, the missing term is the prime number after 11, which is 13.

# Technical MCQ

A binary tree has 20 nodes. Then how many null branches have the tree?

• 0

• 20

• 21

• 40

Ans : 21 If the tree has 3 nodes then it has 4 null branches.ie 3+1. If the tree has 5 nodes then it has 6 null branches.ie 5+1. In general a binary tree with n nodes has exactly n+1 null nodes. So 20 nodes has 21 null branches.

# Coding Question

There are a row of N houses, each house can be painted with one of the three colors: red, blue or green.

The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a N x 3 cost matrix A.

For example, A is the cost of painting house 0 with color red; A is the cost of painting house 1 with color green, and so on.

Find the minimum total cost to paint all houses.

`Input :A = [ [1, 2, 3] [10, 11, 12] ]Output : 12`

Example Explanation Explanation 1:

Paint house 1 with red and house 2 with green i.e A + A = 1 + 11 = 12

## Solution :

Let:

1. dp[i] represent the minimum total cost to paint the houses till i where house i is colored in red.

2. dp[i] represent the minimum total cost to paint the houses till i where house i is colored in green.

3. dp[i] represent the minimum total cost to paint the houses till i where house i is colored in blue.

So if you paint house ‘i’ with red then you can paint house ‘i-1’ only in blue or green. So dp[i] = A[i] + min(dp[i-1],dp[i-1]) Similarly: dp[i] = A[i] + min(dp[i-1], dp[i-1]) dp[i] = A[i] + min(dp[i-1], dp[i-1])

At last output the minimum of (dp[n-1],dp[n-1],dp[n-2][2)

Time Complexity:O(N). Space Complexity:O(N).

`int Solution::solve(vector<vector<int> > &A) {    int n=A.size();    int dp[n+1];    int i,j;    for(i=0;i<=2;i++)    dp[i]=0;    for(i=1;i<=n;i++)    {        dp[i]=A[i-1]+min(dp[i-1],dp[i-1]);        dp[i]=A[i-1]+min(dp[i-1],dp[i-1]);        dp[i]=A[i-1]+min(dp[i-1],dp[i-1]);    }        return min(dp[n],min(dp[n],dp[n]));}`