Interview Questions

1. Simulate a seven-sided die using only five-sided

2. Giving Two Strings, Find out whether they are Anagrams or not?

3. find the longest palindrome in a string?

4. find longest common substring in 2 strings using suffix tree

Some terms:

• suffix tree of a string S: a tree whose edges are labeled with strings, such that each suffix of S corresponds to exactly one path from the tree's root to a leaf.
• trie: each edge is labelled with a single character
• radix tree, Patricia tree/trie: edges are labelled with a string instead of single character
  

suffix tree: a special type of radix tree

• How to construct suffix tree?
• How to find longest common substring using suffix tree?

DP algorithm runs in O(mn).

Reference:
Fast String Searching With Suffix Trees