Duplicate subtree in Binary Tree

Given a binary tree, find out whether it contains a duplicate sub-tree of size two or more, or not.

Alien Dictionary

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.

Optimal Strategy For A Game

You are given an array A of size N. The array contains integers and is of even length. The elements of the array represent N coin of values V1, V2, ….Vn. You play against an opponent in an alternating way.

In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin.

You need to determine the maximum possible amount of money you can win if you go first.

Note: Both the players are playing optimally.

The Celebrity Problem

A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of N people, find if there is a celebrity in the party or not.
A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j is set to 1 it means ith person knows jth person. Here M[i][i] will always be 0.

Note: Follow 0 based indexing.

Find triplets with zero sum

Given an array arr[] of n integers. Check whether it contains a triplet that sums up to zero.

Merge two BST ‘s

Given two BSTs, return elements of both BSTs in sorted form.

Root to leaf paths sum

Given a binary tree of N nodes, where every node value is a number. Find the sum of all the numbers which are formed from root to leaf paths.

Count BST nodes that lie in a given range

Given a Binary Search Tree (BST) and a range l-h(inclusive), count the number of nodes in the BST that lie in the given range.

• The values smaller than root go to the left side
• The values greater and equal to the root go to the right side

Count of strings that can be formed using a, b and c under given constraints

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

Find largest word in dictionary

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.