Software Developer

You have been given a Binary Tree of integers. You are supposed to return the level order traversal of the given tree.

For example:

For the given binary tree

The level order traversal will be {1,2,3,4,5,6,7}.

You are given an arbitrary binary tree consisting of N nodes numbered from 1 to N, an integer 'K', and a node 'TARGET_NODE_VAL' from the tree. You need to find the Kth ancestor of the node 'TARGET_NODE_VAL'. If there is no such ancestor, then print -1.

The Kth ancestor of a node in a binary tree is the Kth node in the path going up from the given node to the root of the tree. Refer to sample test cases for further explanation.

Note:

1. The given node 'TARGET_NODE_VAL' is always present in the tree.
2. The value of each node in the tree is unique.
3. Notice that the Kth ancestor node if present will always be unique.

You have been given a Binary Search Tree of integers. You are supposed to convert it to a greater sum tree such that the value of every node in the given BST is replaced with the sum of the values of all the nodes which are greater than the value of the current node in the tree.

A Binary Search Tree is a tree, whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Note :

You need to modify the given tree only. You are not allowed to create a new tree.

For example:

For the given binary search tree

11 will be replaced by {15 + 29 + 35 + 40}, i.e. 119.
2 will be replaced by {7 + 11 + 15 + 29 + 35 + 40}, i.e. 137.
29 will be replaced by {35 + 40}, i.e. 75.
1 will be replaced by {2 + 7 + 11 + 15 + 29 + 35 + 40}, i.e. 139.
7 will be replaced by {11 + 15 + 29 + 35 + 40}, i.e. 130.
15 will be replaced by {15 + 29 + 35 + 40}, i.e. 104.
40 will be replaced by 0 {as there is no node with a value greater than 40}.
35 will be replaced by {40}, i.e. 40.

Given a string ‘str’ and a string ‘pat’. The string s has some wildcard characters i.e ‘?’ and ‘*’.

If any character is a ‘?’ we can replace that character with any other character. 

If a character is a * we can replace * with any sequence of characters including the empty sequence.  

Your task is to determine if it is possible that we can make ‘str' = 'pat’ using appropriate conversions in ‘str’.

For example:

Let str = “abc?" and pat= “abcd”

We return true as ‘?’ can be replaced with ‘d’ and this makes ‘str’ and ‘pat’ same.

A ninja needs to complete ‘n’ tasks. Each task is represented by an uppercase letter of the English alphabet. Different letters are assigned to different tasks. A ninja can complete tasks in any order. He takes one unit of time to complete one task. For each unit of time, he could complete either one task or just be idle.

Ninja easily gets bored by doing the same task again. So he decided to keep at least ‘t’ units of time between any two same tasks.

You are given a string ‘tasks’ consisting of ‘n’ uppercase letters of the English alphabet, representing the tasks ninja need to complete, and an integer ‘t’ representing the least units of time between any two same tasks. Find out the minimum total units of time ninja will take to complete all ‘n’ tasks.

You have been given a board where there are '2' rows and 'N' columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways:

1. Horizontally as 1x2 tile
2. Vertically as 2x1 tile

Count the number of ways to tile the given board using the available tiles.

Note :

The number of ways might be large so output your answer modulo 10^9 + 7.

Here an example of tile and board for 'N' = 4 :