Q1 What are the advantages and disadvantages of B-star trees over Binary trees? (Asked by Motorola people)
A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.
Q2 Write the psuedo code for the Depth first Search.(Asked by Microsoft)
A2
dfs(G, v) //OUTLINE
Mark v as "discovered"
For each vertex w such that edge vw is in G:
If w is undiscovered:
dfs(G, w); that is, explore vw, visit w, explore from there
as much as possible, and backtrack from w to v.
Otherwise:
"Check" vw without visiting w.
Mark v as "finished".
Q3 Describe one simple rehashing policy.(Asked by Motorola people)
A3 The simplest rehashing policy is linear probing. Suppose a key K hashes to location i. Suppose other key occupies H[i]. The following function is used to generate alternative locations:
rehash(j) = (j + 1) mod h
where j is the location most recently probed. Initially j = i, the hash code for K. Notice that this version of rehash does not depend on K.
Q4 Describe Stacks and name a couple of places where stacks are useful. (Asked by Microsoft)
A4 A Stack is a linear structure in which insertions and deletions are always made at one end, called the top. This updating policy is called last in, first out (LIFO). It is useful when we need to check some syntex errors, such as missing parentheses.
Q5 Suppose a 3-bit sequence number is used in the selective-reject ARQ, what is the maximum number of frames that could be transmitted at a time? (Asked by Cisco)
A5 If a 3-bit sequence number is used, then it could distinguish 8 different frames. Since the number of frames that could be transmitted at a time is no greater half the numner of frames that could be distinguished by the sequence number, so at most 4 frames can be transmitted at a time.
4 Comments on C++ algorithm specific interview questions
A1, the major difference between B-tree and binary tres is that B-tree is a external data structure and binary tree is a main memory data structure. The computational complexity of binary tree is counted by the number of comparison operations at each node, while the computational complexity of B-tree is determined by the disk I/O, that is, the number of node that will be loaded from disk to main memory. The comparision of the different values in one node is not counted.
pseudo code for depth first search:
dfs(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L is not empty)
remove edge (v, w) from end of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}
search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to
pseudo code for depth first search:
dfs(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
HERE L IS EMPTY YOU HAVE TO INSERT X TO L SEARCH ONLY FIND X IT WILL NOT MAKE INSERT
while(L is not empty)
remove edge (v, w) from end of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}
search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to
another 2 examples of the use of stack:
1. infix to postfix expression convertion, or evaluation
2. floodfill algrithm to segment an image