Misc Interview Questions

1) very good puzzle lists and answers;
http://www.techinterview.org/archive/index.html

discussion: http://discuss.fogcreek.com/techInterview/

more puzzles
http://puzzle786.blogspot.com/

2) interview questions

general interview

[ http://steve.yegge.googlepages.com/five-essential-phone-screen-questions this guy is a jerk. I agree with him about some aspects. you can ask people
about questions like OO and bits. but asking a candidate via phone to read out code line by line without syntax error is definitely a jerk's behavior. with today's
IDE, code syntax errors can be avoid easily. it is not DOS century. about regex. how the heck people can remember those long options with regex? what is the point of man page? in this blog, he doesn't test algorithm that can demonstrate a person's real capability. in short,steve yegge is a jerk, fortunately I never interviewed by him.
when he interview people , he suppose he is at a super position to check candidates. in fact, CS is a complicate subject. he can be dead if I test him with tough questions. I guess what he needs is a skilled coder. he don't need a person who can solve problems and be creative. I found the same interview style from amazon.

http://placementsindia.blogspot.com/2007/10/sorting-quick-sort.html

all kinds of interview questions posted daily and discussed
http://discuss.joelonsoftware.com/default.asp?pg=pgDiscussTopics&ixDiscussGroup=11
http://www.gowrikumar.com/

basic interview tech questions with answers
http://vijay.techi.googlepages.com/interview
http://vijayinterviewquestions.blogspot.com/2007_07_01_archive.html

good site
http://cracktheinterview.in/
http://technical-interview.com/default.aspx
http://discuss.techinterview.org/default.asp?interview.11.438205.13
3)
C++ FAQ http://www.parashift.com/c++-faq-lite/virtual-functions.html
C FAQ http://c-faq.com/questions.html

@@

x & 0 = 0
0 & x = 0
x & 1 = 1
1 & x = x

0 | x = x
x | 0 = x
1 | x = 1
x | 1 = 1

0 ^ x = x
x ^ 0 = x
1 ^ x = ~x
x ^ 1 = ~x

x -> y = ~x | y
x <-> y = ~(x ^ y)

void *aligned_malloc( size_t nbytes, unsigned char align ) {

void *p; /* pointer returned */
unsigned char r; /* p % align */
unsigned char incr; /* actual increment to p */
unsigned char *ptr2;

p = malloc( nbytes + align );

r = (unsigned char) ( p % align );

incr = align - r;

p += incr;

/* bookkeeping: write the increment at { the address just before the return address } */
ptr2 = (unsigned char *)p - 1;
*(ptr-1) = incr;

return p;
}

void aligned_free(void *ptr) {

int *ptr2=(int *)ptr - 1;
ptr -= *ptr2;
free(ptr);
}

What will be the output of the following program?
#include <stdio.h>

class Base {
public:
virtual void f(int j = 10)
{ printf("Base %d ",j);}
};

class Derive:public Base {
public:
void f(int b = 20)
{ printf("Derive %d ",b);}
};

main()
{
Base *b = new Derive; <—- the line
b->f();
delete b;
}

Base *b = new Derive; output is : Derive 10

Base *b = new Base; then output is : Base 10
Drive *b = new Drive; then output is : Drive 20
Drive *b = (Drive *)(new Base); then output is : Base 20

reason:
default arguments are statically bounded.while the object function is dynamically bounded

Technical interview questions
Here's a list of questions I was asked over the last two months, in the course of my job search. No solutions, nor a comment on the quality of questions, will be provided. So, don't bother asking.

Microsoft (on campus):

* Reverse a linked list.
* Given an array (positive and negative integers), find the contiguous subarray with the maximum sum.

* Find the minimum number of colors required to color a dodecahedron. Now, write an algorithm that does so.

NetApp (phone screen):

* When would you prefer hashing as your dictionary implementation?

* What is secondary hashing?

- Hash-based system and method with primary and secondary hash functions for rapidly
identifying the existence and location of an item in a file.

A system and method for rapidly identifying the existence and location of an item in a
file using an improved hash table architecture.

A hash table is constructed having a plurality of hash buckets, each identified by a primary hash key.
Each hash entry in each hash bucket contains a pointer to a record in a master file, as well as a
secondary hash key independent of the primary hash key.

A search for a particular item is performed by identifying the appropriate hash bucket by obtaining
a primary hash key for the search term.

Individual hash entries within the hash bucket are checked for matches by comparing the stored
secondary keys with the secondary key for the search term.

Potentially matching records can be identified or ruled out without necessitating repeated reads
of the master file. The improved hash table system and method is employed in a contextual text
searching application for determining the intersection of a text search with a hierarchical
categorization scheme.

* Perfect hashing/universal hashing…

define a hash function h that maps keys into numbers from 0…M-1.
to store our dictionary, we will allocate an array A of size M and use the power of indirect addressing.
We'll store (key, object) in A[h(key)].

universal hasing:
if H is universal, then for any set S in U of size N, and any x in S, the *expected* number of
collisions x has is <= (N-1)/M where M is (0,1,2,…M-1)

Perfect hashing : no collision at all.
really bad hash function: h maps everything in S to the same place.
Really good hash function: S gets evenly spread through range.

* How is the open() system call implemented in UNIX?

Caliber Consulting (phone):

* Implement strlen(), strcat()…
* What is the complexity of strcat() ?
* How would you change strcat(), given the following scenario:

char src[VERYBIGNUMBER]; /* NULL initially */
char *s1, *s2, …, *sn;

You need to place the strings s1, s2,…, sn into src using strcat(). Assume that src can accomodate all these strings. Note that normally, a single execution of strcat() takes O(l + m), where the lengths of the two strings are l and m. With that complexity, the above cascade of strcat()'s takes time proportional to:

n*strlen(s1) + (n - 1) * strlen(s2) + … + strlen(sn).

Can you change the complexity to:

strlen(s1) + strlen(s2) + … + strlen(sn) ?

* Given that you had only upto the IP stack implemented on two machines. How would you go about establishing a session between them? Note - you obviously can't just use TCP! Also, no error correction, sequencing etc. are required, so you don't *need* to use TCP.
* With the same scenario as in the previous question, how would you implement a messaging client?
* What are virtual functions in C++?
* How would you implement virtual functions in a compiler?

Random Walk (pre-interview - on campus):

* Implement the factorial function.
* What is polymorphism?
* What are virtual functions?
* Talk about inner classes in Java.
* Difference between a button and a JButton
* 57 cents worth of money in 7 coins. How many of each do I have: 1c, 5c, 10c, 25c ?

Neuco (phone screen)

* What are virtual functions in C++?
* How does a typical C++ compiler implement virtual functions?
* How would you reproduce/simulate the object system of C++ in C?
* Given a C++ object and its method, how would you simulate with a C function, the calling of the C++ method?
* Suppose you are given a pointer to a function that takes a double between 0 and 1, and
returns a double between 0 and 1. The function is continuous, and is zero at some point(s) in the
interval. Write a procedure to find those zero-points. What is the complexity of the function, as a function of (a) precision, (b) accuracy ?

Random Walk (phone interview)

* What is the difference between the procedural and the object oriented approaches to programming?
* Elucidate the cornerstones of OOP.
* Suppose you had a Shape class. Its an abstract class that subclasses into concrete classes like
a Point, Triangle, Square etc. How would you handle render()'ing a Shape instance…?
* Suppose an application program wants to render birds on the screen. Different birds are to have
different functionalities (Ducks can quack(), Crows can fly() etc). Suggest a good design pattern to
provide these functionalities to different instances, that repsects the paradigms: cohesion and
loose coupling.
* What is the most prominent characteristic about multi-threaded programming? And why does multi-threaded
prog have this characteristic?

@@

DB


pessimistic locking, and optimistic locking

There are two mechanisms for locking data in a database: pessimistic locking, and optimistic locking. Pessimistic locking is where a record or page is locked immediately when the lock is requested, while an optimistic lock is where a record or page is only locked when the changes made to that record are updated. The latter situation is only appropriate when there is less chance of someone needing to access the record while it is locked; otherwise it cannot be certain that the update will succeed because the attempt to update the record will fail if another user updates the record first. With pessimistic locking it is guaranteed that the record will be updated.

caching: Read-Through, Write-Through, Refresh-Ahead and Write-Behind caching.

In the Refresh-Ahead scenario, Coherence allows a developer to configure the cache to automatically and asynchronously reload (refresh) any recently accessed cache entry from the cache loader prior to its expiration.

In the Write-Behind scenario, modified cache entries are asynchronously written to the datasource after a configurable delay, whether after 10 seconds, 20 minutes, a day or even a week or longer.

Read-Through/Write-Through vs cache-aside
There are two common approaches to the cache-aside pattern in a clustered environment. One involves checking for a cache miss, then querying the database, populating the cache, and continuing application processing. This can result in multiple database hits if different application threads perform this processing at the same time.

Refresh-Ahead vs Read-Through
Refresh-ahead offers reduced latency compared to read-through, but only if the cache can accurately predict which cache items are likely to be needed in the future. With full accuracy in these predictions, refresh-ahead will offer reduced latency and no added overhead. The higher the rate of misprediction, the greater the impact will be on throughput (as more unnecessary requests will be sent to the database) – potentially even having a negative impact on latency should the database start to fall behind on request processing.

Write-Behind vs Write-Through
If the requirements for write-behind caching can be satisfied, write-behind caching may deliver considerably higher throughput and reduced latency compared to write-through caching. Additionally write-behind caching lowers the load on the database (fewer writes), and on the cache server (reduced cache value deserialization).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License