Monday, July 05, 2004

 

Interview FAQ picked by mxclxp - 2

4. Misc. Topics

1. Differences between Mac, Windows, UNIX

MacOS (up until osX, anyhow) was single-user and (technically) did not have multitasking capabilites (some people will try to tell you that the mac has "cooperative multitasking", but I wouldn't even cosider that multitasking, since it requires each running program to voluntarily pause and wait for others to run).

Windows, starting with Win95 (*) is a single-user, multasking OS. Although newer versions like XP and 2000 support file permissions via EFS, the DO NOT allow multiple users to be logged in at once. (NEWS: win 2003 support this)

UNIX is 100% multi-user and multitasking, and is therefore (why therefore?) inherently stable, secure, and confusing. Once you go UNIX, though, you'll never go back! UNIX (in all caps) was developed by AT&T waaaay back, Unix (no caps) usually refers to a family of operating systems (including the free-but-overrated Linux) that are based on UNIX. Solaris, BSD, OSF, SCO, and Tru64 are all flavors of Unix.

2.How does Windows programming differ from DOS programming?

Windows – GUI DOS - CUI.
Windows - 32bit O.S Dos is 16 bit O.S.
Windows - multithreading and multitasking O.S Dos is stranger to these concepts.

Traditional dos programming is procedural, meaning that your program starts at one place, and steps through the code sequentially.

Windows programming is event-based, meaning that each time an event (like a button-click) occurs; a handler is invoked to produce a response. The difference can be frustrating, since in event-driven code you can inadvertently have several functions running simultaneously on the same data.

3.What is the advantage of Windows?

GUI, Multitasking, Multithreaded O.S., you can also add: supports a vast variety of devices and has a large base of developers and software.

4.What does winmain and wndproc do?

wndmain is the entry point for a win32 app (like main() would be in a dos/unix app). It is used in almost exactly the same way, except that you pass it a lot of worthless params that your code probably won't use anyhow.

wndproc (aka "window procedure") is a function that will be run by your program to process events that occur within it. The wndproc is specified when you call CreateWindow() and usually consists of several nested switch() statements.

5.How does user input are trapped in Windows?

6.Define and explain COM.

COM is a binary standard on Microsoft (and some UNIX platforms) that enables objects to interoperate in a networked environment regardless of the language in which they were developed or on which computers they reside. COM allows an object to expose its functionality to other components and to host applications. It defines both how the object exposes itself and how this exposure works across processes and across networks. COM also defines the object's life cycle.

7.What is IUnknown and what are its three parts?

IUnknown is the Basic COM interface on which all others are based on.
The Three methods of IUnknown are
1) QueryInterface
2) Addref
3) Release
All the COM interfaces inherit these three methods from IUnknown.

8.What is Marshalling?

Marshalling is the process of converting data into a format for transferring over the network.

9.Differences between Windows 3.1, Windows 95/98, and Windows NT

Windows 3.1 : 16-bit
Windows 9x : 32-bit
Windows NT : 32-bit, more secure, users must login

10.Describe a two tier Windows NT Domain.

11.Describe the file system layout in the UNIX OS.

Bin, boot, dev, etc, home, initrd, lib, lost+found, misc, mnt, opt, proc, root, sbin, tmp, usr, var…

12.In UNIX, are the files allocated contiguous blocks of data?
a) if no, how is the fragmented data kept track of
b) describe the direct blocks and indirect blocks in UNIX file system

13.How is a thread different from a process?

A process runs in its own address space. No two processes share their address space.

Threads will run in the same address space of the process that owns them. Threads belonging to the same process will run in the same address space. They will also share the process's stack and heap. No two processes will share their stacks or their heaps.

14.How is multithreading useful for a web server? A browser?

Web Servers are typically capable of serving multiple clients concurrently, this is achieved using Multi Threading.

15.Why not use multi-process for this? Why would you WANT to run a multi-process web server?

Because if you have a high performance webserver handling thousands of requests, if each of them spawns a new process this creates a lot of overhead. Threads are cheaper.

The reason you use a multi-process web server is for robustness in the face of failure. On a multithreaded server one thread can wipe out all the rest when it crashes the server. In a multi-process server only the offending process goes down. As far as speed is concerned most multi-process servers allow you to spawn at the beginning any number of processes to handle requests so speed differences on a running system are not much different between multi-threading and multi-process servers.

16.What locking constructs are available on platform X (NT = semaphore, critical section, mutex), What are the main differences between them?

17.Familiar with multi-reader, single writer locks?

18.How could you implement that given a simple binary semaphore OS construct?

19.How does this implementation behave? Can it starve readers? Starve writers?

5. General/Fundamentals

1. How would you redesign an ATM?

--ATM machine would "eat" your card if you give "three strikes" failure. This is what I hate the most. So I would add a feature so that a user could regain the card. For example, let user have way to add a secrete question and answer to that question.

--I would eliminate the need for a physical card an opt for some kind of biometric id such as a retinal scan or some such.

--I would orient the display to eliminate the opportunity for overlookers to view it - ie. make it horizontal like a table.

--I would eliminate the masking of account information behind names such as 'checking', 'savings', etc. and ensure that at least the balances are always displayed. This would help eliminate a good deal of 'you don't have enough funds'-type msgs.

--Add an Undo capability where appropriate, i.e. for transfers/deposits. It would also negate any costs associated with the original transaction.

--Remember the most common transactions done by the user and make them macros automatically.

--I would add a way for the system to intermingle different languages during the transaction. This way, you could learn how to take out money in foreign languages while you were at the bank machine. Cool.

--Some possibilities are: security, user interface, user privacy, minimize datacom traffic, make ATM cheaper to build/program. Like all engineering, it's a matter of balancing tradeoffs. If we were optimizing for user interface, the first thing to do is to analyze what we're doing to annoy current users and stop doing that (application of basic Hippocratic Oath "above all do no harm"). One basic UI problem I've noticed with many ATMs is that the keyboard is not near the screen. Users need to keep shifting eye focus. This change might make ATMs more expensive to build... so we're back to making engineering tradeoffs.

2.What is a balanced tree?

A binary tree is balanced if the depth of two subtrees of every node never differs by more than one, can also be called AVL trees.

3.How would you decide what to test for given that there isn't enough time to test everything you want to?

--Prioritize what you want to test, in the order,
.whether is taking right input and giving right output,
.whether all the output conditions expected are meet,
.which really can crash the system, checking the boundary conditions
.which really annoy the user, hanging etc.
.Which can cause loss of data, like memory corruption, memory leaks etc?

--Use the requirements to dictate your tests. If your product satify the requirments, then you can ship it. That's how they do it a MS. :-)

--If you are a tester, ask the developer or the manager for more time or simply automize a part of testing so that multiple parts of the system can be tested in parallel. The product should and cannot be shipped without complete testing.

-- The goal of any project is to test the entire code base, but in reality that doesn't always happen. In many cases a 'ship date' is dictated and changing it, to allow more testing, is not in a company's best interests. The quality of a product is a factor similar to features and resources required. Testing for most products should be prioritized the same way features are.

So, automate as much as possible and ensure that the most important features are tested.

4.What is Lex? Yacc? What are they used for?

5.Tell me about fundamentals of RPC.

Remote Procedure Call (RPC) is a protocol that one program can use to request a service from a program located in another computer in a network without having to understand network details. (A procedure call is also sometimes known as a function call or a subroutine call.) RPC uses the client/server model. The requesting program is a client and the service-providing program is the server. Like a regular or local procedure call, an RPC is a synchronous operation requiring the requesting program to be suspended until the results of the remote procedure are returned. However, the use of lightweight processes or threads that share the same address space allows multiple RPCs to be performed concurrently.

When program statements that use RPC are compiled into an executable program, a stub is included in the compiled code that acts as the representative of the remote procedure code. When the program is run and the procedure call is issued, the stub receives the request and forwards it to a client runtime program in the local computer. The client runtime program has the knowledge of how to address the remote computer and server application and sends the message across the network that requests the remote procedure. Similarly, the server includes a runtime program and stub that interface with the remote procedure itself. Results are returned the same way.

6.Tradeoff between time spent in testing a product and getting into the market first.

-- In Microsoft’s case. Ship it out. Who cares about bugs...just fix it in the next release.

-- I think it depends more on the market situation...many a times, in the hi-tech market, you are going to be able to sell only if u are the first guy out with the product. It is really really important to be the market pioneer. If the market demands it, u better get the product out and ask the developers and testers to go to hell. Getting a prototype of the product into the market is the least you can do. At the same time if you can afford the time (no pressure from competitors, new entrants, substitute products or buyers) then do as much as testing as possible.

The balance between testing and the release should totally depend on the market!

7.You're part of the QA team for a large web-site. You want to create as much automated testing as possible. What could/would you test? How? How much maintenance would these tests require as the web site changes?

I would write automated tests that do the following:

1. A poller that just checks to see if the site is up and running.
2. A test that pushes a lot of test data to the site and measure time taken for push.
3. A test that pulls a lot of test data from site and measure time taken.
4. Programatically invoke applets, ActiveX controls and verify results of operation.
5. Simulate a multiple user scenario and stress out the web site, determine its breaking point.

8.What would be your language of choice for implementing CGI programs on a web server? Why?

I think Perl has extremely flexible and not a strict language by any means. Ideal for quick and dirty (?) web applications.

9.How do you multiply a variable by 16 without using the multiplication operator '*'?

10.How do you swap two integers without using any extra memory?



a=a+b;
b=a-b;
a=a-b;

a becomes (a XOR b)
b becomes (b XOR a)
a becomes (a XOR b)

// only when b <> 0
a = a * b;
b = a / b;
a = a / b



11.What was the most difficult program you had to write?

12.Describe the most interesting software project you've done in school.

13.Name 7 layers of OSI models and define their functionality.



7. Electrical/Physical
----------------------
Responsible for defining various Electrical standards, like standardized Cables, Bit Stream Standards etc, to be used while communicating between HOSTS (Computers).


6. Link Layer
-------------
Responsible for Encoding & subsequent
De-Coding of Data Packets at various
Network points.

5. Network Layer
----------------
Responsible for providing LOGICAL paths for
Data packets to pass through. It basically
provides SWITCHING & ROUTING facilities.

4. Transport Layer
------------------
Responsible for TRANPARENT flow of data
between HOSTS (Computers), without due
consideration to HARDWARE details. This
layer is not concerned as to which
applications are sharing data; rather it
is only concerned with TRANSFERRING
DATA PACKETS FROM ONE POINT TO ANOTHER-

3. Session Layer
----------------
Responsible for maintaining a REGISTRY of
all currently active connections from
various HOSTS (Computers).

2. Presentation Layer
---------------------
Responsible for isolating different Data
formats from each other. Ex.: Encryption
process involves the AUTOMATIC conversion
of Application data Format to Network Format
& Vice-Versa.

1. Application Layer
--------------------
Responsible for END-USER friendly protocols,
like HTTP, FTP, TELNET etc. Software
Developers directly interact with this
layer of protocol to write programs.

6. Algorithms/Coding

1、Write a function to print the Fibonacci numbers.



-- int fib ( int n ){
if (n == 0) return 1;
else return fib(n-1) + fib(n-2);
}

-- int fibo (int n)
{
int i, current, one_back, two_back;

if (n <= 1)
return 1;
else {
one_back = 1;
two_back = 1;
for ( i = 2; i <= n; i++) {
current = one_back + two_back;
one_back = two_back;
two_back = current;
} /* end for loop */
} /* end else block */
return current;
}



-- There are better ways to find a solution to this problem instead of using Recursion. Recursion is a disaster as someone has already mentioned. Try giving 20 or more elements in your series and your program will take awful lot of time to compute. For every element in series you're finding the element before using recursion though you theoretically you would have computed it before!!!

2.Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.

-- if (x > 0 && (x & (x-1)) == 0)

-- I think all the answers here are either wrong completely, partially, or too complex. The best answer so far, by jinaljhaveri, was if(!(x&(x-1))), which I believe works for all powers of 2, but also for 0, which is not a power of 2.

Basically, an integer which is the power of 2 will have one and only one bit set in its binary representation. If you subtract 1 from that, you will get all bits set (equal to 1) before the original 1 bit, and the rest are 0. Taking advantage of this, the answer is

if ((x << 1) == 1 + (x | (x - 1))) {}

The term x | (x - 1) makes an integer with all bits set starting from the original set bit. Adding 1 will set the next bit and clear all the previous bits, effectively doubling x, which is the same as x << 1.

It’s a pity that the second solutions work for 0 too, which is just what he/she wants to avoid.

3.Implement an algorithm to sort a linked list.

直接插入排序、直接选择排序、归并排序。

如果可以使用的额外的内存空间,会比较的简单;否则,则需要一点思考了。

4.Reverse a string.



void str_rev(char s[])
{
int len = strlen(s);
int i;
char temp;

for(i=0; i



{
temp = s[i];
s[i] = s[(len-1) - i];
s[(len-1) - i] = temp;
}
}





5.Given a linked list which is sorted, how will you insert in sorted way.

U have already very familiar with it if you did question 3 (sort a linked list) by direct insertion sort.

6.Implement an algorithm to insert in a sorted list.

7.Delete an element from a doubly linked list.

void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}

8.Implement an algorithm to sort an array.

An array can be sorted using any of the classic algorithms like quicksort , heapsort and the inefficient bubblesort.

9.Given a sequence of characters, how will you convert the lower case characters to upper case characters?

void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S>='a' && *S<='z')?(*S-'a'+'A'):*S;
S++;
}
}

10.Write a routine that prints out a 2-D array in spiral order.



int NumbersPerTime = SIZE; // 绕圈的边长

int tInit = 0; // 绕圈的起始值



for(int i = 0 ; i < (SIZE+1)/2; i++)

{

int t = tInit;



for(int j = 0; j < NumbersPerTime-1; j++)

{

// out here

printData(t);

t += SIZE;

}

for(j = 0; j < NumbersPerTime-1; j++)

{

// out here

printData(t);

t += 1;

}

for(j = 0; j < NumbersPerTime-1; j++)

{

// out here

printData(t);

t -= SIZE;

}

for(j = 0; j < NumbersPerTime-1; j++)

{

// out here

printData(t);

t -= 1;

}



NumbersPerTime -= 2;

tInit += SIZE + 1;

}



11.Give a fast way to multiply a number by 7.

int num = (n<<3) – n;

12.Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.



int str2int(const char *str)
{
int value = 0;
int sign = (str[0] == '-')?-1:1;
int i = (str[0] == '-')?1:0;
char ch;

while(ch = str[i++])

{
if ((ch >= '0')&&(ch <= '9'))
value = value*10 + (ch - '0');
else
return 0; // return 0 denotes error occurs
}
return value*sign;
}



13.How would you print out the data in a binary tree, level by level, starting at the top?

1) Put the root node into a queue;
2) while the queue is not empty, do as follows;
3) Get a node from the queue, print its value, and put its children into the queue;

14.Write a routine to draw a circle given a center coordinate (x, y) and a radius (r) without making use of any floating point computations.

In order to avoid floating point calculations, we can do two things:

1) Instead of fixing one co-ordinate and looking for another via the equation, search the whole co-ordinate space from x +- r and y +- r. Plot the point that is close. But this is a costly N*N algo.

2) To go for an efficient workhorse, go for Bresenham's circle drawing algo, found in any of the good graphics textbooks.

15.You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.



#include
#include
main() {
char str1[5] = "abcd";
char str2[3] = "bc";
int len = strlen(str1);
int i =0;
char newstr[len];
int cntr = 0;
for ( i = 0; iif ( strchr(str2,str1[i]) == NULL ) {
newstr[cntr++] = str1[i];
}
}
newstr[cntr] = '\0';
printf("%s%s%s", "The new str is ", newstr, "\n");
}



16.Write a small lexical analyzer for expressions like "a*b" etc.

bool is_astarb(char* s)
{
if (*s++ != 'a') return false;
while(*s++);
if (*--s != 'b') return false;
return true;
}

17.Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).

-- Traverse array to compute sum, subtract 99*100/2, the sum of integers between 1 and 99.

-- Create a new array of b[100], elements initialized all to 0



int b[100];
for ( i=0;i<100;i++)
b[i]=0;
int tm;
for ( i=0;i<100;i++)
{
tm=t[i] ;
if b[tm]== 1;
return(tm); // return the duplicate number
else b[tm]=1;
}
printf(" there is no duplication");
return 0; // 0 indicates no duplication



O(n square ) ... just sort all numbers and check if two consecutive numbers are same by traversing the sorted array..

18.Write efficient code for extracting unique elements from a sorted list of array.



#include

main()
{
int a[10] = {0,4,4,4,5,6,6,8,9,9};
int i;

for(i=0; i<10; i++)
{
if(a[i] == a[i+1] )
{
while(a[i] == a[i+1]) i++;
}
else
printf("%d ", a[i]);
}
printf("\n");
}



We do print the ununiqued numbers out, but we do not extract them!

19.Print an integer using only putchar. Try doing it without using extra storage.



1) void printInt(int a);
int b = a;
char *str;
int i = 1;
int len = 0;
while (b) {
b /= 10;
i *= 10;
len++;
}
i /= 10;

while (i > 0) {
putchar(a/i + 48);
a = a%i;
i /= 10;
}
}

2) This can be done by recursion. Since the number of recursive calls is not significant, it does not affect the performance much.

printnumber(int i)
{
if(i == 0)
return;
printnumber(i/10);
putchar('0' + i%10);
}



20.Write a function that allocates memory for a two-dimensional array of given size(parameter x & y)

--array=(int**)malloc(x*sizeof(int*));
for(i=0;iarray[i]=(int*)malloc(y*sizeof(int));

--I prefer this method because it uses less memory allocation calls and the memory is in a contiguous line. I used calloc.. which can easily be swaped out with malloc. Also, this makes a 2d array of integers but that is easily changed as well.

int x = 0, y = 0;
Array = (int **) calloc( Height, sizeof(int *));
*(Array) = (int *) calloc( Width * Height, sizeof(int));

for(y = 0; y < Height; y++)
{
Array[y] = &(Array[0][x]);
x += Width;
}

21.How would you do conditional compilation ?

#ifdef/ifndef
#else/elif
#endif

#pragma token-string // provide compiler or machine specific instructions and arguments

22.Write an algorithm to draw a 3D pie chart ?

23.Write a function that finds repeating characters in a string.

Maintain a character count table like -- int char_count[255];

//Initialize to 0 here
Keep adding the count of each characters.
Scan throughout the array and print the characters with count more than 1.

24.Write a routine to reverse a series of numbers without using an array.



-- int reverse(int i)
{
int rev=0, x=0;
if((i /10) ==0)
return i;
while((i /10) >0)
{
x = i %10;
i= i/10;
rev= (rev *10) +x;
}
rev= rev*10 +i;

return rev;
}

-- # include
void main()
{
int i = 12345, y =0;
while(i !=0)
{
y = y *10 + i %10;
i /=10;
}
cout<}



25.Write a function to find the nth item from the end of a linked list in a single pass.

I would think keeping a gap is "n" between fptr and sptr would do. Then advance both together till fptr->next (fptr is the one in front) = NULL, the sptr is what we want.

26.Write a function to compute the factorial of a given integer.

27.Give me an algorithm for telling me the number I didn't give you in a given range of numbers. (Numbers are given at random)

1. say the range of numbers is 0 to n-1
2. Initialize an array say, seen[n] to 0
3. for every number i given set seen[i] to 1.
4. in the end, print all indices for which seen[index] = 0

28.Write a function that finds the last instance of a character in a string.

main() {

char *x= "acbcd";

char y = 'c';

int len = strlen(x);

int i=0,j=0;

for( i = len-1; i>= 0; i-- ) {

if ( x[i] == y ) {

break;

}

}

printf("%s%c%s%d%s","the # of last occur of ",y," is ",i+1,"\n");

}



<< Home

This page is powered by Blogger. Isn't yours?