Alg-Code: Interview Q

Array

How would you detect a repeated element in an integer array?
Design an algorithm and write code to find two numbers in an array whose sum equals a given value.
Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
Given an array containing both positive and negative integers and required to find the sub-array with the largest sum in O(N)
Given an array [100] which contains numbers between 1..99. Find the duplicate value.
Write a function to find the K biggest elements in the array, and return the sum. Do both in O(n) time.
Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
A "rotated array" is an array of integers in ascending order, after which for every element i, it has been moved to element (i + n) mod sizeOfList. Write a function that takes a rotated array and, in less-than-linear time, returns n (the amount of rotation).
Find an Item in a Sorted Array with Shifted Elements
Rotate/Shift an array: Given a char array and n (number by which to shift), the array characters had to be circular shifted by n . For example ABCDEF becomes DEFABC
design a technique to initialize an entry of a vector to zero the first time it is accessed.
Problem: Write code for implementing 2 stacks in 1 array *
You're given an array which contains the numbers from 1 to n, in random order, except there is one missing. Write a function to return the missing number.
Write code to sort an array. Why did you chose your method? What are its pros and cons?
Write a program to copy strings A and B. Last 10 characters of A overlap the first 10 characring B.
Given an array of integers. The sum of the elements of the array is known to be less than the max integer. Compute the sum. What if we know that integers are in 2's complement form?
Write code for extracting unique elements from a sorted list of array
Given array of 1001 integers. All the integers are between 1 and 1000 (inclusive). Also, each integer can appear only once in the array except for one which occurs twice. Give an algorithm to find the repeated number. Assume that you can access each element of the array only once and try to solve it without using extra storage.
Given two fixed length buffers padded with nulls/ Swap and reverse them, not swapping and reversing nulls.
Write a program to compact an array (remove duplicates).
Write a program to merge two arrays while removing duplicate elements
Write a program to merge two sorted arrays. First array has extra space at the end to accommodate the second array.
Array: Find the number with odd number of occurrences
Function to perform Binary Search on a Sorted Array
array of random numbers. Find the duplicate numbers.o(sqr(n)), O(nlogn), O(n)
the first n cells of an array contain integers sorted in increasing order. The remaining cells all contain some very large integer tht we may think of as MAXINT. The array is arbitarily large (you may thnk infinite) and you donot know n. Give an algorithm to find the position of a given integer x (x < MAXINT) in the array. What is worst case running time of your algorithm ? Make your algorithm efficient. (Hint the problem can be solved in log n) time.

String

You are given a C string. Design a function to remove duplicate characters. i.e. "aaabbbccc" → "abc", "abc abc abc" → "abc"
Problem: Given an array of strings (char * a[100]). Each string is a word from the dictionary. Devise a way to determine and display all of the anagrams in the array. *
Given two strings return a string that consists of intersection of the characters in the two strings
Implement an algorithm to do string matching with wildcards
Reverse a string in place *
Reverse words in a sentence *
Find a substring.
Implement strstr() (or some other string library function).
String compare
Given a set of pointers to very long strings. Find the pointer to the lexicographically smallest and largest strings.
Given strings A and B, delete from B all characters present in A.
Implement strpbak
Given a set of strings, write code to print the strings that are anagrams.
Write a program to find acronyms ("Interview Question" becomes "I.Q.")
String: Permutations Using Recursion *
Convert Integer to String itoa *
Convert String To Integer atoi *
Find First Non-Repeated Character *
String: Palindrome Check *
Write a function to count the number of characters, number of words in a paragraph
Given a sequence of characters. How will you convert the lower case characters to upper case characters. ( Try using bit vector solutions given in the C lib -typec.h)

Matrix

Given an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
Write code to print a 2 dimensional matrix in spiral sequence
What is the time complexity of matrix multiplication ?

Linked List

Implement a linked list
You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don't know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
Sort a linked list in. Can you do it in O(n)?
Write code for reversing a doubly linked list
Reverse a singly linked list using recurssion and iteration
Given a linked list find the center of the linked list. *
Get the data stored in the nth position of a linked list
Pop for linked list
Count the number of times a given number occurs in a linked list.
Insert a new node at nth index
SortedInsert in a linked list
Sort a linked list. It should use SortedInsert method from above question
Append on linked list to another
Given a linked list, split it into two lists one for the front half and, one for the last half. If odd number of elements are present the extra node should go to the front list
Remove duplicates from a linked list
Write a function to divide the nodes in a lists in an alternate fashion
Merge Sort a list using FrontBackSplit and SortedMerge
SortedMerge takes two sorted lists and merges them.
SortedIntersect: Given two sorted linked lists, create and return a new linked list that represents the intersection of the two.
Reverse and recursive reverse a linked list *
Write code to reverse a linked list.
Write a program to insert a new node in a circular linked list without traversing it.
Find nth element in the linked list from back
Merged List Problem
Given are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join.
Given a singly linked list, determine whether it contains a loop or not.
Under what circumstances can one delete an element from a singly linked list in constant time?

Trees

Write a program that performs a breadth first traversal of a binary tree.*
Write a program that finds the depth of a binary tree.
You must serialize and deserialize a binary tree. Design two functions such that: char *f(Node *); Node *g(char *); tree = g(f(tree);
Write a function to reconstruct a binary tree from its preorder traversal and inorder traversal. Take into account that the traversals could be invalid.
You are given two nodes in a tree. Write a program to find the common root of the nodes. *
How do you represent an n-ary tree. Write a program to perform an breadth first traversal of this n-ary tree.
What is a balanced tree?
Print data in a binary tree, level by level, starting at the top. Breath First Traversal/Search. *
Write code to traverse a binary tree and set the parent node for all the nodes.
Given a binary tree with nodes, print out the values in pre-order/in-order/post-order without using any extra space.
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
What are the advantages and disadvantages of B-star trees over Binary trees?

Sorting

How to implement a Merge Sort on disk
How to sort 10 million 7 digit unique phone numbers with ~ 1 MB memory?
Implement quick sort
Compare and contrast the sorting algorithms you know

Sets

Given two sets, Write a function to provide the union of them.
Given a fixed list of numbers A. compare with another list B to find out if an element in A exists in B

Numbers

Given a number, describe an algorithm to find the next number which is prime.
Write a program to print the Fibonacci sequence.
Convert a decimal number to a roman numeral given a set of numerals

Data Structures

Propose a good data structure that can hold 'n' queues in a finite memory segment. you are allowed to have some datastructure separate for each queue.Try to consume at least 90% of the memory space.
Implement a trie (http://en.wikipedia.org/wiki/Trie) data structure. Write a function add, which takes a word, and a trie, and adds the word to the trie. Write another function lookup, which takes a prefix and a trie, and returns all the words in the trie that start with that prefix.
Difference between a linked list and an array
Write a function to manage a heap using an existing array
How do you optimize symbol table storage
Write a hashing function for a hashtable that can contain 1 million rows.
Implement a queue using 2 stacks
Implement a Queue using an Array
What's the big-O for growing a vector?
Describe one simple rehashing policy.(Asked by Motorola people)
Describe Stacks and name a couple of places where stacks are useful. (Asked by Microsoft)
What is the major advantage of a hash table? (Asked by Silicon Magic Corp. people)
What are the techniques that you use to handle the collisions in hash tables?(Asked by Silicon Magic Corp. people)

A10:

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.

Language/OOPS

What is a virtual function in C++
What is a default constructor? : A default constructor is a constructor that either has no parameters, or if it has parameters, all the parameters have default values.
What is a conversion constructor?
What is a copy constructor? A copy constructor is a special constructor in the C++ programming language used to create a new object as a copy of an existing object. The first argument of such a constructor is a reference to an object of the same type as is being constructed (const or non-const), which might be followed by parameters of any type (all having default values).
What is an explicit constructor? C++ constructors that have just one parameter automatically perform implicit type conversion. For example, if you pass an int when the constructor expects a string pointer parameter, the compiler will add the code it must have to convert the int to a string pointer. However, you might not always want this automatic behavior.
You can add explicit to the constructor declaration to prevent implicit conversions. This forces the code to either use a parameter of the correct type, or cast the parameter to the correct type. That is, if the cast is not visibly expressed in code, an error will result.

The explicit keyword can only be applied to in-class constructor declarations to explicitly construct an object.
What is the difference between a copy constructor and an overloaded assignment operator?

The assignment operator is used to copy the values from one object to another already existing object. The key words here are "already existing". Consider the following example:

            1      Cents cMark(5); // calls Cents constructor   
            2      Cents cNancy; // calls Cents default constructor   
            3      cNancy = cMark; // calls Cents assignment operator   

In this case, cNancy has already been created by the time the assignment is executed. Consequently, the Cents assignment operator is called. The assignment operator must be overloaded as a member function.

What happens if the object being copied into does not already exist? To understand what happens in that case, we need to talk about the copy constructor.

The copy constructor

Consider the following example:

            1      Cents cMark(5); // calls Cents constructor   
            2      Cents cNancy = cMark; // calls Cents copy constructor!   

Because the second statement uses an equals symbol in it, you might expect that it calls the assignment operator. However, it doesn't! It actually calls a special type of constructor called a copy constructor. A copy constructor is a special constructor that initializes a new object from an existing object.

The purpose of the copy constructor and the assignment operator are almost equivalent — both copy one object to another. However, the assignment operator copies to existing objects, and the copy constructor copies to newly created objects.

The difference between the copy constructor and the assignment operator causes a lot of confusion for new programmers, but it's really not all that difficult. Summarizing:

If a new object has to be created before the copying can occur, the copy constructor is used.
If a new object does not have to be created before the copying can occur, the assignment operator is used.

what happens if there is an error in constructor destructor?
What is the difference between an abstract class and an interface?
What is the difference between malloc(), calloc(), and realloc()? *

malloc, calloc, and realloc are functions used for memory allocation in C/C++ languages. There are some fundamental differences on how the above functions work.
realloc()
First of all realloc() is actually a reallocation function. It is used to resize a previously allocated (using malloc(), calloc(), or realloc()) block of memory to the desired size. Depending on whether the new size if less or more than the original size the block may be moved to new location.

Usage and example of realloc()

Function Prototype for realloc():
void *realloc(void *pointer, size_t size);

malloc() vs calloc()

There two basic difference between malloc() and calloc() functions:
1. malloc() allocates memory in bytes. So the programmer specifies how many bytes of memory malloc should allocate and malloc will allocate that many bytes (if possible) and return the address of the newly allocated chunk of memory.

Function prototype for malloc():

void *malloc(size_t size); //size is the number of bytes to allocate

On the other hand calloc() allocates a chunk of memory specified by a block/element size and the number of blocks/elements.

Function prototype for calloc():
void *calloc(size_t nelements, size_t elementSize);

2. malloc() does not initialize memory after it allocates it. It just returns the pointer back to the calling code and the calling code is responsible for initialization or resetting of the memory, most probably by using the memset() function. On the other hand calloc() initializes the allocated memory to 0. calloc() is obviously slower than malloc() since it has the overhead of initialization, so it may not be the best way to allocate memory if you don't care about initializing the allocated memory to 0.

Side note: Don't forget to free your allocated memory when you are done with it using the free() function.

- malloc function allocates a specified number of bytes of memory. The initial value of the memory is indeterminate.

- calloc funtion allocates space for a specified number of objects of a specified size. The space is initialized to all 0 bits.

- realloc function increases or decreases the size of a previously allocated area. When the size increases, it may involve moving the previously allocated area somewhere else, to provide the additional room at the end. Also, when the size increases, the initial value of the space between the old contents and the end of the new area is indeterminate.

What are the advantages of OOPL?
Basic concepts, like is-a vs. has-a (with examples), overloading vs. overriding, class vs. object, method vs. function, virtual vs.pure virtual, base class vs. derived class, inheritance, encapsulation, delegation, aggregation
What's the difference between pointers and references in C++?
What's a static variable?
What's the heap?
What's the difference between call-by-reference and call-by-value?
Do they understand the scope of variables and how the stack is used?
What is polymorphism?
Why is polymorphism better than simple collection of source files with subroutines and data structures?
What's a virtual function and how do they work?

In object-oriented programming, a virtual function or virtual method is a function or method whose behaviour can be overridden within an inheriting class by a function with the same signature. This concept is a very important part of the polymorphism portion of object-oriented programming (OOP).

  class Animal:     """Define an Animal base class"""     def eat(self):         """Class function (method) to show how an Animal eats."""         print "I eat like a generic Animal."   class Wolf(Animal):     """Define a Wolf class (derived from Animal)"""     def eat(self):         """Class function (method) to show how a Wolf eats."""         print "I eat like a wolf!"   class Fish(Animal):     """Define a Fish class (derived from Animal)"""     def eat(self):         """Class function (method) to show how a Fish eats."""         print "I eat like a fish!"

When should you use multiple inheritance?
What is a virtual destructor? when assigne the derived class to the base class:

when destructing, only the base destructor will be called, but not the derived class, Base *Var = new Derived();

Thus we need to deaclaer the virtual for the base destructor, then both destructor will be called

virtual ~Base(){ cout<<"Destructor : Base"<<endl;}

~Derived(){ cout<<"Destructor : Derived"<<endl;}

What is a mutable member?
c++: Describe run-time type identification.
What problem does the namespace feature solve?
What is a Make file?
In C++, what is the difference between method overloading and method overwriting?

Method overloading means having two or more methods with the same name but different signatures in the same scope. These twomethods may exist in the same class or anoter one in base class and another in derived class.

Calling Overloaded Methods.

Person(); // as a constructor and call method without parameter

Person(userFirstName); // as a constructor and call method with one parameter(like User's first Name)

Person(userFirstName,userLastName); // as a constructor and call method with one parameter(like User's first Name)

When to use Method Overloading?

Generally, you should consider overloading a method when you have required same reason that take different signatures, but conceptually do the same thing.

Method overriding means having a different implementation of the same method in the inherited class. These two methods would have the same signature, but different implementation. One of these would exist in the base class and another in the derived class. These cannot exist in the same class.

In a derived class, if you include a method definition that has the same name and exactly the same number and types of parameters as amethod already defined in the base class, this new definition replaces the old definition of the method.

Explanation

A subclass inherits methods from a superclass. Sometimes, it is necessary for the subclass to modify the methods defined in the superclass. This is referred to as method overriding. The following example demonstrates method overridin

Example code

This is the code to instantiate the above two classes

Circle myCircle;
myCircle = new Circle(1.20);
Cylinder myCylinder;
myCylinder = new Cylinder(1.20,2.50);

In the derived class, which data member of the base class are visible?

Access specifiers in the base classprivateprotectedpublicprivate inheritanceThe member is inaccessible.The member is private.The member is private.protected inheritanceThe member is inaccessible.The member is protected.The member is protected.public inheritanceThe member is inaccessible.The member is protected.The member is public.

Design Problems:

Implement a thread-safe class that will read/write to/from a buffer
Write an algorithm for Soduku puzzle
Solve the mouse in a maze problem
Wire Routing Problem using Queues.
How could you generate a file of k unique random integers between 0 and n-1 in random order?
Write a function to smooth out stock fluctuations.
Write a small lexical analyzer. it should be able to parse simple expressions like a*b
What is the solution to the reader-writers problem
Implement a multiple-reader-single-writer lock given a compare-and-swap instruction. Readers cannot overtake waiting writers.
Write an efficient algorithm and C code to shuffle a pack of cards. The cards are stored in an array of integers.
Order the following runtimes in order of their asymptotic performance O(2^n), O(n^y), O( 10^100), O(n!), O(n^n)
Implement malloc or write the code for malloc memory allocation function.
Given a square with side length of 1 unit, describe all points inside square that are closer to the center of the square than to the edge of the square.
You are given a list of Ball objects. Each Ball is either Red or Blue. Write a function that partitions these balls so that all of the balls of each color are contiguous. Return the index of the first ball of the second color (your result can be Red balls, then Blue balls, or the other way around). In haskell, you'll probably want to return a ([Ball],Int).
Live Search is a search engine. Suppose it was to be tied into an online store. Now you're given two lists. One is a [(SessionId, NormalizedQuery)]. That is, when a particular user performs a query, it is turned into some consistent format, based on their apparent intent, and stored in this logfile. The second list is a [(SessionId, ProductId)]. This indicates the product bought by a particular user. Now, you want to take these two (potentially very long) lists, and return some structure that will make it easy to take a query and return a list of the most popular resulting purchases. That is, of people who have run this query in the past, what are the most common products they've wound up buying? The interviewer said that this is an instance of a well-known problem, but I didn't catch the name of it.
You have a [(WeatherStationId, Latitude, Longitude)]. Similar to #3, write a function which will, off-line, turn this into a data structure from which you can easily determine the nearest Weather Station, given an arbitrary Latitude and Longitude.
Write a function for scoring a mastermind guess. That is, in a game of mastermind (http://en.wikipedia.org/wiki/Mastermind_(board_game)), given a guess, and the actual answer, determine the number correct, the number wrong,and the number out of place.
Write an algorithm to shuffle a deck of cards. Now write a function to perform some kind of evaluation of "how shuffled" a deck of cards is.
Space-time trade off: You are given a 5x5 grid where each cell has a weight associated to it, and a scale with the ability to give the total weight of any arbitrary selection of cells. In this grid, four of the five rows contain only one pound weights. One of the five rows contains only two pound weights. What is the minimum number of times you must use the scale, and in what configuration, to find the row with the two pound weights.
Write code to read and write from a bounded buffer
Function to select the eight strongest radio stations in a radio
Design and implement a self managing Thread Pool class
Write a function to draw a circle. (x**2 + y**2 = r** 2). You cannot use any floating point computations.
Write a routine putlong() that prints out an unsigned long in decimal numbering system. You are allowed to use only putchar (no sprintf, itoa, etc)
In the game of tic tac toe, write a program to generate moves by a computer. This should be fast.
How would you go about finding out where to find a book in a library ( You dont know before hand how exactly the books are organized).
Given a tree control in a Windows User Interface. How would you read information from a database and display it in the tree control. The tree has arbitrary levels and each level can contain arbitrary number of items in it.
DNA Sequence Pattern Match/ String Search Problem
Given a stream of numbers, suggest a data structure to store the numbers in the stream along with their number of occurrences.
Write a function that adds 30 days to a given date.
How would you design a restaurant reservation system, parking lot, elevator, vending machine (gen question). (test an elevator, vending machine, online shopping cart)
Find the angle of a clock at a particular time
You, a designer want to measure disk traffic i.e. get a histogram showing the relative frequency of I/O/second for each disk block. The buffer pool has b buffers and uses LRU replacement policy. The disk block size and buffer pool block sizes are the same. You are given a routine int lru_block_in_position (int i) which returns the block_id of the block in the i-th position in the list of blocks managed by LRU. Assume position 0 is the hottest. You can repeatedly call this routine. How would you get the histogram you desire?
Write a function to check if two rectangles defined as below overlap or not. struct rect { int top, bot, left, right; } r1, r2;
Write a SetPixel(x, y) function, given a pointer to the bitmap. Each pixel is represented by 1 bit. There are 640 pixels per row. In each byte, while the bits are numbered right to left, pixels are numbered left to right. Avoid multiplications and divisions to improve performance.
A character set has 1 and 2 byte characters. One byte characters have 0 as the first bit. You just keep accumulating the characters in a buffer. Suppose at some point the user types a backspace, how can you remove the character efficiently. (Note: You cant store the last character typed because the user can type in arbitrarily many backspaces)
Write the 'tr' program of UNIX. Invoked as tr -str1 -str2. It reads stdin and prints it out to stdout, replacing every occurance of str1[i] with str2[i].
First some definitions for this problem: a) An ASCII character is one byte long and the most significant bit in the byte is always '0'. b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is '1'. Now you are given an array of a characters (both ASCII and Kanji) and, an index into the array. The index points to the start of some character. Now you need to write a function to do a backspace (i.e. delete the character before the given index).

Low level/Machine specific Stuff

Write a program to find if a machine is big-endian or little-endian.
How do you test if a number if power of 2.
Write a function to figure out if a computer's stack grows up or down.
How can you align a pointer to a 4 byte boundary in an efficient way.
How do you find if the sum of two unsigned integers has resulted in an overflow?
reverse all the bits in the byte
count the number of set bits in a number. Optimize for speed and time.
multiply a number by 8 without using the * or + operators. Can you multiply with 7?
Add numbers in base n (not any of 10,16,8, or 2) -2 charles simonyi
Exchange two numbers without using a temporary say a = 8 and b = 10
a = a+b b = a-b a = a-b
array of 0's and 1's. Give an efficient algorithm to count the number of 0's and 1's
What are the logical operations? (AND, OR, NOT, XOR.)
What's the difference between logical-AND and bitwise-AND?
What is 36 expressed in hexadecimal?
Write an if-statement that tests whether the high order bit is set in a byte.
Reverse the bits of an unsigned integer.
Compute the number of ones in an unsigned integer.
Compute the discrete log of an unsigned integer.
How do we test most simply if an unsigned integer is a power of two?
Set the highest significant bit of an unsigned integer to zero.
Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
What is a volatile variable?

OS/Systems Programming

What is a deadlock?
What is a Semaphore?
How does the race condition occur?
What are mutex and semaphore? What is the difference between them?
What are the disadvantages of using threads?
Describe synchronization in respect to multithreading.
What is Virtual Memory?
What is multiprogramming?
Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.

Database

What is Boyce Codd Normal form?
Write a query to find the zip codes for all the orders within the last 24 hours. (to see if one can write basic queries to join 2 tables)
Write a SQL Query to find first day of month?
Why there is a performance difference between two similar queries that uses UNION and UNION ALL?
How to choose between a Clustered Index and a Non-Clustered Index?
How you can minimize the deadlock situation?
When you should use low fill factor?
Explain Third normalization form with an example?
What is a Cartesian product? What causes it?
What is an advantage to using a stored procedure as opposed to passing an SQL query from an application.
What is the difference of a LEFT JOIN and an INNER JOIN statement?
When a query is sent to the database and an index is not being used, what type of execution is taking place?
What are the pros and cons of using triggers?
What are the pros and cons of using stored procedures. When would you use them?
What are the pros and cons of using cursors? When would you use them?

Networks and Security

What is the difference between TCP and UDP?
How do you use RSA for both authentication and secrecy?
What is ARP and how does it work?
What's the difference between a switch and a router?
Name of seven layers in Open System Interconnection model.
Name some routing protocols? (RIP,OSPF etc..)
Give 4 examples which belongs application layer in TCP/IP architecture? (from CISCO )
How do you do authentication with message digest(MD5)? (Usually MD is used for finding tampering of data)
How do you implement a packet filter that distinguishes following cases and selects first case and rejects second case.
i) A host inside the corporate n/w makes a ftp request to outside host and the outside host sends reply.
ii) A host outside the network sends a ftp request to host inside. for the packet filter in
both cases the source and destination feilds will look the same.
How does traceroute works? Now how does traceroute makes sure that the packet follows the same path that a previous (with ttl 1) probe packet went in?
Explain Kerberos Protocol?
What are digital signatures and smart cards?
Difference between discretionary access control and mandatory access control?
What is the goal of the shortest distance algorithm ?

Personal

Tell me the courses you liked and why did you like them.
Give an instance in your life in which u were faced with a problem and you tackled it successfully
What is your ideal working environment. ( They usually to hear that u can work in group also.)
Why do u think u are smart.
Questions on the projects listed on the Resume.
Do you want to know any thing about the company.( Try to ask some relevant and interesting questions)
How long do u want to stay in USA and why?
What are your geographical preference?
What are your expectations from the job.
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.

Software Development Lifecycle (SDLC)

Trade off between time spent in testing a product and getting into the market first.
What to test for given that there isn't enough time to test everything you want to.

Puzzles

Fly plane around the world half fuel puzzle *
Classic: If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear. ANS. The color of the bear is trivial. The possible solutions to it are interesting. In addition to the trivial north pole and circle near north pole solutions, there is an additional circle near south pole solution. Think it out.
Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife? ANS. Join the centers of the original and the removed rectangle. It works for cuboids too!
There are 3 baskets. one of them have apples, one has oranges only and the other has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn't have oranges only,it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets. HINT. There are only two combinations of distributions in which ALL the baskets have wrong labels. By picking a fruit from the one labeled MIXTURE, it is possible to tell what the other two baskets have.
You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighings how do you find the defective one?
Why is a manhole cover round?
How many cars are there in the USA? (A popular variant is "How many gas stations are there in the USA?")
How many manhole covers are there in the USA?
You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?
Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?
You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?
Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no 'prime triples.'
There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.
Suppose you had 8 billiard balls, and one of them was slightly heavier, but the only way to tell was by putting it on a scale against another. What's the fewest number of times you'd have to use the scale to find the heavier ball?
Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement? Try for 5 too.
The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long: 1. How many possible solutions are there? 2. What if we know which 5 letters are being used? 3. Develop an algorithm to solve the word.
There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace. Woman 1: 1 minute to cross Woman 2: 2 minutes to cross Woman 3: 5 minutes to cross Woman 4: 10 minutes to cross For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what's the other way?
If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.
A version of the "There are three persons X Y Z, one of which always lies".. etc..
There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don't collide.
Which way should the key turn in a car door to unlock it?
If you could remove any of the 50 states, which state would it be and why?
There are four dogs/ants/people at four corners of a square of unit distance. At the same instant all of them start running with unit speed towards the person on their clockwise direction and will always run towards that target. How long does it take for them to meet and where? HINT. They will meet in the centre and the distance covered by them is independent of the path they actually take (a spiral).
(from Tara Hovel) A helicopter drops two trains, each on a parachute, onto a straight infinite railway line. There is an undefined distance between the two trains. Each faces the same direction, and upon landing, the parachute attached to each train falls to the ground next to the train and detaches. Each train has a microchip that controls its motion. The chips are identical. There is no way for the trains to know where they are. You need to write the code in the chip to make the trains bump into each other. Each line of code takes a single clock cycle to execute. You can use the following commands (and only these); MF moves the train forward MB moves the train backward IF (P) conditional that's satisfied if the train is next to a parachute. There is no "then" to this IF statement.

.NET

C#/.NET

Reference/value type, stack vs heap, garbage collectpr
boxing vs unboxing
const vs readonly
delegates vs events
generics
partial classes - what is and what problem is solved
nullable types
config relatinships: app.config, web.config, machine.config

ASP.NET

Controls and Pafe Life Cycle

Order these in the correct order

Static constructor
class constructor
PreInit
Init
InitComplete
PreLoad
Load
LoadComplete
Validation
Event Handling
PreRender
PreRenderComplete
Render
Unload
DataBinding (can happen anytime between Init and PreRender)

State

Compare these in terms of scope, life cyle, pros/cons

Application (system.web.HttpApplicationState)
Cache(system.web.Caching.Cache)
Items (System.Web.httpContext.Items)
Sessions (system.web.UI.HttpSessionState)
Profile (System.Web/HttpContext.Profile) ASP.NET 2.0
ViewState (system.Web.UI.COntrol.ViewState)
ControlState (System.Web.UI.Control.ControlState) ASP.NET 2.0
Cookies (System.Web.HttpRequest.Cookies)
Query String Paramters (System.Web.HttpRequest.QueryString)
Hidden Input Fields (System.Web.UI.ClientScriptManager.RegisterHiddenField(....))

Page Intrinsics

Discuss the purpose and usage of these:

Request (System.Web.HttpRequest)
Response
Context System.Web.HttpContext
Server System.Web.HttpServerUtility
ClientScript System.Web.UI.CLientScriptManager
Trace System.Web.TraceContext
Browser System.Web.ttpBrowserCapabilities

Controls

Compare and contrast

Server Controls (webControls, HtmlComtrols, Composite Controls, Custom Controls)
Templates Controls (UserControls, Page)
Web Parts - .NET 2.0 or Sharepoint 2.0

Conceptual Questions

Compare Server.Transfer(...) vs Request.Redirect(...)
Describe how ASP.NET builds and renders pages
How are master pages implemented
How do you add javascript to an asp.net page

IIS Administration

AppPool vs Website vs Virtual Directory
Posts or Host geaders for multiple roots

XHTML 1.0/1.1

Difference from HTML 4.01? How to get valid xhtml?
Which browser classes should you code/test for?
Describe building complex or columnar layouts without nested tables

CSS 2.1

Give syntax for each select and explain what each sleector matches

Any element: "*"
Class ".className"
Element: "ElementName" e.g. "div"
ID: "#ElementID" e.g. "#ctrl01_myDiv"
PseudoClass "Selector:PseudoClass" e.g. "A:hover"

Box model

Draw a diagram of how each of these porperties exists within the box model: margin, padding, border, width, height, left, top

Positioning

Describe usage and values for "float"
Describe usage and values for "position"
contract methods for hiding elements

Media Types

Explain how to target a set of styles to a specific media type (e.g. printing with white background)

Advanced Techniques

Describe effects and usages of setting a negative margin on a block
describe and discuss image replacement technique

javascript

What is the syntax for declaring variables?
Contrast with C# or java

Object oriented javascript

descibr classes in javascript
describe usage of prototype keyword

DOM familiarity

find an element via id
find an element via tag
show a message box
ask the user for permission
get input from the user

XSLT

Contrast xsl:stylesheet vs xsl:template
what is match="..." in xsl:template
calling templates vs applying templates
Flow control?
XPath expression

XML in .NET

Name some methods for generating xml in .NET

XmlWriter
XmlDocument
Serialization
DataSet.WriteXml()
XpathDocument using external XSLT
How do you control/customize serialization

using serializable attribute
Decorate class members with atributes to rename/ignore/specify types
Implement ISerializable and manually control via another method

Threading and Synchronization

Mutex corss process
sybc() {} for critical sections
ReaderWriter lock
Semaphores

WebService

C# attribute for decorating as webservice
Webservices base class: what value if can decorate with attributes
Design considerations vs. remoting or sharing libraries?

Design patterns in .NET
C# iterators

Alg-Code

Pages

Welcome~~~

Monday, April 18, 2011

Interview Q

2 comments: