Pages
Welcome~~~
It is easier to write an incorrect program than understand a correct one.
Thursday, April 28, 2011
Java sorting  comparable v comparator
java.lang.Comparable  java.util.Comparator 
int objOne.compareTO(objTwo) – A Comparable interfaced class must contain a method called compareTo to compare two objects (one being the object on which it is called and the other being passed as a paramater)  int compare(objOne, objTwo) – A Comparator is a class in its own right, which implements the Comparator interface; that means it must contain a method called compare (two objects as parameters) 
Return Values  negative – if objOne < objTwo zero – if objOne = objTwo positive – if objOne > objTwo  Return Value  same as Comparable 
Only one sort sequence can be created  Many sort sequences can be created 
You must modify the class whose instances you want to sort  You build a separate class from the class whose instances you want to sort 
Implemented frequently in the API by : String, Wrapper Classes, Date, Calendar  Meant to be implemented to sort instances of thirdparty classes 
If you want to sort a collection using its comparable interface, you simply call the static Collections.sort method on it … so if we had an ArrayList called Animal which implemented Comparable, we could write:Collections.sort(Animal);  To sort a collection using a Comparator class, you need to pass an extra parameter into the Collections.sortmethod – that parameter being an instance of a Comparator object. Thus:Collections.sort(Animal, new ByBreed()); 
Monday, April 25, 2011
Sunday, April 24, 2011
Saturday, April 23, 2011
Java Source Code / Java DocumentationJava Source Code and Java Documentation
MatrixpackageforPython
http://sourceforge.net/projects/matpy/
Description:
MatPy is a Python package for numerical linear algebra and plotting with a MatLablike interface. It currently consists of wrappers around Numeric and Gnuplot packages, but eventually may be implemented directly in C/C++, or as interface to Octave.
PyGoogle
URL:  http://sourceforge.net/projects/pygoogle/ 
Description:  A Python wrapper for the Google web API. Allows you to do Google searches, retrieve pages from the Google cache, and ask Google for spelling suggestions 
Python Open Source
Python Open Source  

Friday, April 22, 2011
Thursday, April 21, 2011
Wednesday, April 20, 2011
Monday, April 18, 2011
Printing expressions from Tree
http://www.daniweb.com/forums/thread323976.html
http://www.careercup.com/question?id=7473670
http://wordaligned.org/articles/pythonsurprisemehttp://openbookproject.net/thinkcs/python/english2e/ch21.html
http://stackoverflow.com/questions/1894846/printingbfsbinarytreeinlevelorderwithspecificformatting
http://codinggeeks.blogspot.com/2010/04/serializinganddeserializingbinary.html
http://ponywma.spaces.live.com/blog/cns!3757DF93DF1F3015!334.entry
def printexp(tree):
sVal=""
if tree:
sVal='( ' + printexp(tree.getLeft())
sVal=sVal+str(tree.getRootValue())
sVal= sVal+printexp(tree.getRight()) +' )'
return sVal
Here is the source code and the text file format:
Note that the text file is created "by hand" and only read function is implemented in the code. Implementing write function should be straight forward.
==============================================
#include <stdio.h>
typedef struct tree_struct
{
int data;
int nchildren;
struct tree_struct *children;
}tree_t;
tree_t * create_new()
{
return ((tree_t *) malloc(sizeof(tree_t)));
}
int populate_tree(tree_t *root, FILE *fp)
{
fscanf(fp,"%d",&(root>nchildren));
root>children = NULL;
if(root>nchildren)
{
root>children = (tree_t *) malloc(root>nchildren * sizeof(tree_t));
for(int i=0; i<root>nchildren; i++)
fscanf(fp,"%d",&(root>children[i].data));
for(int i=0; i<root>nchildren; i++)
populate_tree(&root>children[i],fp);
}
else
return 0;
}
int print_tree(tree_t *root)
{
static int count = 0;
if(root)
{
if(!count++)
printf("%d\n",root>data);
if(root>nchildren)
{
for(int i=0; i<root>nchildren; i++)
printf("%d ",root>children[i].data);
printf("\n");
for(int i=0; i<root>nchildren; i++)
print_tree(&(root>children[i]));
}
return 0;
}
else
return 1;
}
int main(int argc, char *argv[])
{
char *filename = argv[1];
FILE *fp = fopen(filename,"r");
tree_t *root = create_new();
fscanf(fp, "%d", &(root>data));
populate_tree(root,fp);
print_tree(root);
}
==============================================
The tree taken for illustration purpose is:
5 >3(1(4,19),7(20),2(25)), 10(11,17), 2(99,8)
The file format used is as follows:
<example.tree>
5
3 3 10 2
3 1 7 2
2 4 19
0
0
1 20
0
1 25
0
2 11 17
0
0
2 99 8
0
0
==============================================
To compile (on linux):
gcc std=c99 g main.c o treeio
==============================================
Usage:
./treeio example.tree
Output:
5
3 10 2
1 7 2
4 19
20
25
11 17
99 8
==============================================
 http://www.pythonforum.org/pythonforum/viewtopic.php?f=14&t=5842
Some OOP websites
It also has a subweb site for the algorithms:http://www.oopweb.com/Algorithms/Files/Algorithms.html
Find the longest palindromes
the most naive solution would be to exhaustively examine all n (n + 1) / 2 substrings of the givennlength string, test each one if it's a palindrome, and keep track of the longest one seen so far. This has worstcase complexity O(n^{3}), but we can easily do better by realizing that a palindrome is centered on either a letter (for oddlength palindromes) or a space between letters (for evenlength palindromes). Therefore we can examine all 2n + 1 possible centers and find the longest palindrome for that center, keeping track of the overall longest palindrome. This has worstcase complexity O(n^{2}).
est data used is HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
public static string GetPalindromeString(string theInputString)
{ int j = 0;
int k = 0; string aPalindrome = string.Empty; string aLongestPalindrome = string.Empty ; for (int i = 1; i < theInputString.Length; i++) { k = i + 1; j = i  1; while (j >= 0 && k < theInputString.Length) { if (theInputString[j] != theInputString[k]) { break; } else { j; k++; } aPalindrome = theInputString.Substring(j + 1, k  j  1); if (aPalindrome.Length > aLongestPalindrome.Length) { aLongestPalindrome = aPalindrome; } } } return aLongestPalindrome; }
Notes on Path Finding problem
astar c
.)matrix[u][v] = 1
denotes an edge between u and v, and matrix[u][v] = 0
denotes no edge between u and v. Then (matrix)^3
(just simple matrix exponentiation) is 'magically' the path matrix of exactly length 3. An efficient implementation of Dijkstra's algorithm takes O(Elog V) time for a graph with E edges and V vertices.
 Hosam Aly's "flood fill" is a breadth first search, which is O(V). This can be thought of as a special case of Dijkstra's algorithm in which no vertex can have its distance estimate revised.
 The FloydWarshall algorithm takes O(V^3) time, is very easy to code, and is still the fastest for dense graphs (those graphs where vertices are typically connected to many other vertices). But it'snot the right choice for the OP's task, which involves very sparse graphs.
Raimund Seidel gives a simple method using matrix multiplication to compute the allpairs distance matrix on an unweighted, undirected graph (which is exactly what you want) in the first section of his paper On the AllPairsShortestPath Problem in Unweighted Undirected Graphs [pdf].
(This is not exactly the problem that I have, but it's isomorphic, and I think that this explanation will be easiest for others to understand.)
Suppose that I have a set of points in an ndimensional space. Using 3 dimensions for example:
A : [1,2,3] B : [4,5,6] C : [7,8,9]
I also have a set of vectors that describe possible movements in this space:
V1 : [+1,0,1] V2 : [+2,0,0]
Now, given a point dest, I need to find a starting point p and a set of vectors moves that will bring me todest in the most efficient manner. Efficiency is defined as "fewest number of moves", not necessarily "least linear distance": it's permissible to select a p that's further from dest than other candidates if the move set is such that you can get there in fewer moves. The vectors in moves must be a strict subset of the available vectors; you can't use the same vector more than once unless it appears more than once in the input set.
My input contains ~100 starting points and maybe ~10 vectors, and my number of dimensions is ~20. The starting points and available vectors will be fixed for the lifetime of the app, but I'll be finding paths for many, many different dest points. I want to optimize for speed, not memory. It's acceptable for the algorithm to fail (to find no possible paths to dest).
Update w/ Accepted Solution
I adopted a solution very similar to the one marked below as "accepted". I iterate over all points and vectors and build a list of all reachable points with the routes to reach them. I convert this list into a hash of <dest, p+vectors>, selecting the shortest set of vectors for each destination point. (There is also a little bit of optimization for hash size, which isn't relevant here.) Subsequent dest lookups happen in constant time.
Minimum Spaning Tree

Some Notes

Counting sort
Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A).
Counting sort is a stable sort and has a running time of Î˜(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.
Latex
About the latex size: http://en.wikibooks.org/wiki/LaTeX/Formatting#Font_Styles
Interview Q
 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 subarray 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 lessthanlinear 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 NonRepeated 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 submatrix 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 nary tree. Write a program to perform an breadth first traversal of this nary 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 preorder/inorder/postorder without using any extra space.
 How do you traverse a Btree in Backward inorder? Process the node in the right subtree> Process the root >Process the node in the left subtree
 What are the advantages and disadvantages of Bstar 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 bigO 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)
 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 nonconst), 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 inclass 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()? *
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. What are the advantages of OOPL?
 Basic concepts, like isa vs. hasa (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 callbyreference and callbyvalue?
 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?
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:
 What is a mutable member?
 c++: Describe runtime 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?
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.
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?
 Implement a threadsafe 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 n1 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 readerwriters problem
 Implement a multiplereadersinglewriter lock given a compareandswap 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 wellknown problem, but I didn't catch the name of it.
 You have a [(WeatherStationId, Latitude, Longitude)]. Similar to #3, write a function which will, offline, 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.
 Spacetime 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 ith 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).
 Write a program to find if a machine is bigendian or littleendian.
 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 = ab a = ab
 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 logicalAND and bitwiseAND?
 What is 36 expressed in hexadecimal?
 Write an ifstatement 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 yth number in the increasing sequence of nonnegative 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?
 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.
 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 NonClustered 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?
 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 3bit sequence number is used in the selectivereject ARQ, what is the maximum number of frames that could be transmitted at a time? (Asked by Cisco) A5 If a 3bit 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.
 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.
 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.
 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