1. How to reverse a string , complexity of the problem in big O notation
2. Binary Tree Lowest Common Ancestor.
“The following is a binary tree data structure in which
each node is associated with an integer. Each node has
a set of ancestors, recursively de?ned as: every node is
its own ancestor, and the parent of an ancestor is also an
ancestor. Any two nodes have a set of common ances-
tors, de?ned as the set intersection of the two ancestor
sets. Any two nodes have a lowest common ancestor,
de?ned as their common ancestor farthest away from
the root. Write in pseudo-code an O(n) function that
takes a tree and two integers and returns the integer
associated with the lowest common ancestor of the two
nodes associated with the two inputs." The interviewer wanted me to write the code
class Tree {
Node *root;
}
class Node {
Node *left, *right;
int value;
}
int Tree::LCA(int a, int b) {
// write code
}