Given a binary tree, write a code to print its reverse level order traversal.
For example:
The reverse or bottom-up level order traversal of this binary tree is 4, 3, 2, 1, 6, 5, 7.
In this example, first we printed last level then second last level and so on. So, we have to start printing the level from bottom-up.
Maximum consecutive ones II. Given an array which only consists of 0s and 1s. Write a code to find the maximum number of consecutive 1s in an array, if you can flip at most one 0.
For example:
Input: {1, 1, 0, 0, 1, 1, 1, 1, 1}
Output: 6
In this example, If we can flip at most one zero then the maximum number of consecutive 1s in an array is 6 {1, 1, 1, 1, 1, 1}.
Let’s discuss a interesting problem maximum sum subarray of size k
Given an array of positive integers and a positive number K. Write a code to find the maximum sum subarray of size k.
For example:
|
1 2 3 4 5 |
Example 1: Input: {2, 1, 5, 1, 3, 2}, K = 3 Output: 9 { 5, 1, 3} |
Let’s first understand what all subarrays we can form whose size is 3.
i) First subarray is {2, 1, 5} and it’s sum is 8.
ii) Second subarray is {1, 5, 1} and it’s sum is 7.
iii) Third subarray is {5, 1,3} and it’s sum is 9.
iv) Fourth subarray is {1, 3, 2} and it’s sum is 6.
Out of all these subarrays of size three, the maximum sum subarray is {5, 1, 3} and it’s sum is 9.