1.Question: Suppose that data is an array of 1000 integers. Write a single function call that will sort the 100 elements data [222] through data [321].
Answer: quicksort ((data + 222), 100);
2.Question: Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?
Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.
3.Question: What is the difference between an external iterator and an internal iterator? Describe an advantage of an external iterator.
Answer: .An internal iterator is implemented with member functions of the class that has items to step through. .An external iterator is implemented as a separate class that can be "attach" to the object that has items to step through. .An external iterator has the advantage that many difference iterators can be active simultaneously on the same object.
4.Question: Why are arrays usually processed with for loop?
Answer: The real power of arrays comes from their facility of using an index variable to traverse the array, accessing each element with the same expression a[i]. All the is needed to make this work is a iterated statement in which the variable i serves as a counter, incrementing from 0 to a.length -1. That is exactly what a loop does.
5.Question: What is an HTML tag?
Answer: An HTML tag is a syntactical construct in the HTML language that abbreviates specific instructions to be executed when the HTML script is loaded into a Web browser. It is like a method in Java, a function in C++, a procedure in Pascal, or a subroutine in FORTRAN.
What is pure virtual function?
A class is made abstract by declaring one or more of its virtual functions to be pure. A pure virtual function is one with an initializer of = 0 in its declaration
Q. Write a Struct Time where integer m, h, s are its members
struct Time
{
int m;
int h;
int s;
};
Q. How do you traverse a Btree in Backward in-order?
Process the node in the right subtree
Process the root
Process the node in the left subtree
Q. What is the two main roles of Operating System?
As a resource manager
As a virtual machine
Q. In the derived class, which data member of the base class are visible?
In the public and protected sections.
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.
1. In C++, what is the difference between method overloading and method overwriting?
Overloading a method (or function) in C++ is the ability for functions of the same name to be defined as long as these methods have different signatures (different set of parameters). Method overwriting is the ability of the inherited class rewriting the virtual method of the base class.
2. What methods can be overwritten in Java?
In C++ terminalogy, all public methods in Java are virtual. Therefore, all Java methods can be overwritten in subclasses except those that are declared final, static, and private.
3. In C, What is the difference between a static variable and global variable?
A static variable declared outside of any function is accessible only to all the functions defined in the same file (as the static variable). However, a global variable can be accessed by any function (including the ones from different files).
4. In C, why is the void pointer useful?
The void pointer is useful becuase it is a generic pointer that any pointer can be cast into and back again without loss of information.
5. What are the defining traits of an object-oriented language?
The defining traits of an object-oriented langauge are:
encapsulation
inheritance
polymorphism
Q: What is the difference between Stack and Queue?
A: Stack is a Last In First Out (LIFO) data structure.
Queue is a First In First Out (FIFO) data structure
Q: Write a fucntion that will reverse a string. (Microsoft)
A: char *strrev(char *s)
{
int i = 0, len = strlen(s);
char *str;
if ((str = (char *)malloc(len+1)) == NULL) /*cannot allocate memory */
err_num = 2;
return (str);
}
while(len)
str[i++]=s[--len];
str[i] = NULL;
return (str);
}
Q: What is the software Life-Cycle?
A: The software Life-Cycle are
1) Analysis and specification of the task
2) Design of the algorithms and data structures
3) Implementation (coding)
4) Testing
5) Maintenance and evolution of the system
6) Obsolescence
Q: What is the difference between a Java application and a Java applet?
A: The difference between a Java application and a Java applet is that a
Java application is a program that can be executed using the Java
interpeter, and a JAVA applet can be transfered to different networks
and executed by using a web browser (transferable to the WWW).
Q: Name 7 layers of the OSI Reference Model? (from Cisco)
A: -Application layer
-Presentation layer
-Session layer
-Transport layer
-Network layer
-Data Link layer
-Physical layer
1. How do you write a function that can reverse a linked-list? (Cisco System)
void reverselist(void)
{
if(head==0)
return;
if(head->next==0)
return;
if(head->next==tail)
{
head->next = 0;
tail->next = head;
}
else
{
node* pre = head;
node* cur = head->next;
node* curnext = cur->next;
head->next = 0;
cur->next = head;
for(; curnext!=0; )
{
cur->next = pre;
pre = cur;
cur = curnext;
curnext = curnext->next;
}
curnext->next = cur;
}
}
2. What is polymorphism?
Polymorphism is the idea that a base class can be inherited by several classes. A base class pointer can point to its child class and a base class array can store different child class objects.
3. How do you find out if a linked-list has an end? (i.e. the list is not a cycle)
You can find out by using 2 pointers. One of them goes 2 nodes each time. The second one goes at 1 nodes each time. If there is a cycle, the one that goes 2 nodes each time will eventually meet the one that goes slower. If that is the case, then you will know the linked-list is a cycle.
4. How can you tell what shell you are running on UNIX system?
You can do the Echo $RANDOM. It will return a undefined variable if you are from the C-Shell, just a return prompt if you are from the Bourne shell, and a 5 digit random numbers if you are from the Korn shell. You could also do a ps -l and look for the shell with the highest PID.
5. What is Boyce Codd Normal form?
A relation schema R is in BCNF with respect to a set F of functional dependencies if for all functional dependencies in F+ of the form a->b, where a and b is a subset of R, at least one of the following holds:
a->b is a trivial functional dependency (b is a subset of a)
a is a superkey for schema R
No comments:
Post a Comment