1) Given two strings find the longest common substring. We can use dynamic programming for this.
We define the optimal substructure as follows:
Let S be a string of length m and T be a string of length n. Recall that the pattern matching of strings involved computing a prefix. Here too we find all possible prefixes and taking any two prefixes, we choose the one with the longest suffix.
This can be written as
The longest common suffix =
LCSuffix(S1p-1, T1..q-1)+1 if S[p] = T[q]
0 otherwise
0 otherwise
Then we can choose the longest common substring as the max of the longest common suffixes for i ranging from 1 to m and j ranging from 1 to n.
LCSubstr(S,T) = max 1<= i <=m and 1<= j <=n LCSuffix(S1..i, T1..j)
We will investigate suffix tree for solving this. A suffix tree helps arrange the strings as a path from the root to the leaves with the strings denoted by numbers and appearing at the leaves of the suffix tree. The problem then can be translated to one which finds out which strings appear below each node. The tree is traversed bottom up ( which means level order traversal with the results reversed level wise) and a bit vector is maintained for all possible strings. Alternatively the lowest common ancestor of two strings can be found out.
Suffix tree reminds us of a trie. A prefix tree is also a trie. Both have special terminators on the nodes to signify the end of a string or word.
Another interview question is as follows:
Given a csv of name and age of persons, sort it by age. For this we could use a list data structure that already has a method sort and can take an IComparer for duplicates. And duplicate elements can also be stored as lists within the overall list. Of course, .Net also provides a tuple collection.
Another interview question is based on levels of friendship:
Given the input as
A: B C D
D: B E F
E: C F G
This produces the output as
Level 1 : B, C, D
Level 2 : E, F
Level 3 : G
The given example has no cycles in the graph. So starting at the root as the chosen node, we can form a tree and then complete a Level wise traversal to find the next levels of friendship.
However, the problem may not be restricted to acyclic graph even if it is directed. Hence we maintain a queue for each level
We will investigate suffix tree for solving this. A suffix tree helps arrange the strings as a path from the root to the leaves with the strings denoted by numbers and appearing at the leaves of the suffix tree. The problem then can be translated to one which finds out which strings appear below each node. The tree is traversed bottom up ( which means level order traversal with the results reversed level wise) and a bit vector is maintained for all possible strings. Alternatively the lowest common ancestor of two strings can be found out.
Suffix tree reminds us of a trie. A prefix tree is also a trie. Both have special terminators on the nodes to signify the end of a string or word.
Another interview question is as follows:
Given a csv of name and age of persons, sort it by age. For this we could use a list data structure that already has a method sort and can take an IComparer for duplicates. And duplicate elements can also be stored as lists within the overall list. Of course, .Net also provides a tuple collection.
Another interview question is based on levels of friendship:
Given the input as
A: B C D
D: B E F
E: C F G
This produces the output as
Level 1 : B, C, D
Level 2 : E, F
Level 3 : G
The given example has no cycles in the graph. So starting at the root as the chosen node, we can form a tree and then complete a Level wise traversal to find the next levels of friendship.
However, the problem may not be restricted to acyclic graph even if it is directed. Hence we maintain a queue for each level
No comments:
Post a Comment