SDE - 1

You are given three strings “A”, “B” and “C”. Your task is to check whether “C” is formed by an interleaving of A and B. C is said to be interleaving “A” and “B”, if the length of “C” is equal to the sum of the length of A and length of B, all the characters of “A” and “B” are present in “C”, and the order of all these characters remains the same in all three strings.

For Example:

If A = “aab”, B = “abc”, C = “aaabbc”
Here C is an interleaving string of A and B. Because C contains all the characters of A and B and the order of all these characters is also the same in all three strings.

If A = “abc”, B = “def”, C = “abcdefg”
Here C is not an interleaving string of A and B as neither A nor B contains the character ‘g’.

You have been given a text message. You have to return the Run-length Encoding of the given message.

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as the character and a single count. For example, the string "aaaabbbccdaa" would be encoded as "a4b3c2d1a2".

You are given a class named as BSTIterator that represents an iterator over inorder traversal of a binary search tree. You need to implement the following things as follows:

1. BSTIterator(Node root) - It is a parameterized constructor in which you are given the root of the Binary search tree. It will be called whenever an object of BSTIterator is created.

2. next() - This member function will return the next smallest element in the in-order traversal of the binary search tree. You need to implement this function.

3. hasNext() - This function will return true if there exists the next smallest element in the traversal else it will return false. You need to implement this function

The binary search tree has ‘N’ nodes you need to print the inorder traversal of the tree using the iterator.

You are given an arbitrary binary tree consisting of N nodes, where each node is associated with a certain value, and two node values, a and b, you need to check if these nodes are cousins.

Two nodes are cousins of each other if they are at the same level and have different parents. Two nodes are said to be at the same level if the distance of both the nodes from the root node is the same.

A binary tree (BT) is a data structure in which each node has at most two children.

For the given binary tree:

4 and 7 are cousins of each other since they are at the same level and have different parents, 3 and 2 respectively.