Questions

Array

1. How would you detect a repeated element in an integer array?
2. Design an algorithm and write code to find two numbers in an array whose sum equals a given value.
3. 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.
4. Given an array containing both positive and negative integers and required to find the sub-array with the largest sum in O(N)
5. Given an array [100] which contains numbers between 1..99. Find the duplicate value.
6. Write a function to find the K biggest elements in the array, and return the sum. Do both in O(n) time.
7. 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.
8. 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).
9. Find an Item in a Sorted Array with Shifted Elements
10. 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
11. design a technique to initialize an entry of a vector to zero the first time it is accessed.
12. Problem: Write code for implementing 2 stacks in 1 array *
13. 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.
14. Write code to sort an array. Why did you chose your method? What are its pros and cons?
15. Write a program to copy strings A and B. Last 10 characters of A overlap the first 10 characring B.
16. 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?
17. Write code for extracting unique elements from a sorted list of array
18. 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.
19. Given two fixed length buffers padded with nulls/ Swap and reverse them, not swapping and reversing nulls.
20. Write a program to compact an array (remove duplicates).
21. Write a program to merge two arrays while removing duplicate elements
22. Write a program to merge two sorted arrays. First array has extra space at the end to accommodate the second array.
23. Array: Find the number with odd number of occurrences
24. Function to perform Binary Search on a Sorted Array
25. array of random numbers. Find the duplicate numbers.o(sqr(n)), O(nlogn), O(n)
26. 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

1. You are given a C string. Design a function to remove duplicate characters. i.e. "aaabbbccc" → "abc", "abc abc abc" → "abc"
2. 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. *
3. Given two strings return a string that consists of intersection of the characters in the two strings
4. Implement an algorithm to do string matching with wildcards
5. Reverse a string in place *
6. Reverse words in a sentence *
7. Find a substring.
8. Implement strstr() (or some other string library function).
9. String compare
10. Given a set of pointers to very long strings. Find the pointer to the lexicographically smallest and largest strings.
11. Given strings A and B, delete from B all characters present in A.
12. Implement strpbak
13. Given a set of strings, write code to print the strings that are anagrams.
14. Write a program to find acronyms ("Interview Question" becomes "I.Q.")
15. String: Permutations Using Recursion *
16. Convert Integer to String itoa *
17. Convert String To Integer atoi *
18. Find First Non-Repeated Character *
19. String: Palindrome Check *
20. Write a function to count the number of characters, number of words in a paragraph
21. 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

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

Linked List

1. Implement a linked list
2. 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.
3. Sort a linked list in. Can you do it in O(n)?
4. Write code for reversing a doubly linked list
5. Reverse a singly linked list using recurssion and iteration
6. Given a linked list find the center of the linked list. *
7. Get the data stored in the nth position of a linked list
8. Pop for linked list
9. Count the number of times a given number occurs in a linked list.
10. Insert a new node at nth index
11. SortedInsert in a linked list
12. Sort a linked list. It should use SortedInsert method from above question
13. Append on linked list to another
14. 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
15. Remove duplicates from a linked list
16. Write a function to divide the nodes in a lists in an alternate fashion
17. Merge Sort a list using FrontBackSplit and SortedMerge
18. SortedMerge takes two sorted lists and merges them.
19. SortedIntersect: Given two sorted linked lists, create and return a new linked list that represents the intersection of the two.
20. Reverse and recursive reverse a linked list *
21. Write code to reverse a linked list.
22. Write a program to insert a new node in a circular linked list without traversing it.
23. Find nth element in the linked list from back
24. Merged List Problem
25. 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.
26. Given a singly linked list, determine whether it contains a loop or not.
27. Under what circumstances can one delete an element from a singly linked list in constant time?

Trees

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

Sorting

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

Sets

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

Numbers

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

Data Structures

1. 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.
2. 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.
3. Difference between a linked list and an array
4. Write a function to manage a heap using an existing array
5. How do you optimize symbol table storage
6. Write a hashing function for a hashtable that can contain 1 million rows.
7. Implement a queue using 2 stacks
8. Implement a Queue using an Array
9. What's the big-O for growing a vector?
10. Describe one simple rehashing policy.(Asked by Motorola people)
11. Describe Stacks and name a couple of places where stacks are useful. (Asked by Microsoft)
12. What is the major advantage of a hash table? (Asked by Silicon Magic Corp. people)
13. What are the techniques that you use to handle the collisions in hash tables?(Asked by Silicon Magic Corp. people)

Language/OOPS

1. What is a virtual function in C++
2. What is a default constructor?
3. What is a conversion constructor?
4. What is a copy constructor?
5. What is an explicit constructor?
6. What is the difference between a copy constructor and an overloaded assignment operator?
7. what happens if there is an error in constructor destructor?
8. What is the difference between an abstract class and an interface?
9. What is the difference between malloc(), calloc(), and realloc()? *
10. What are the advantages of OOPL?
11. 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
12. What's the difference between pointers and references in C++?
13. What's a static variable?
14. What's the heap?
15. What's the difference between call-by-reference and call-by-value?
16. Do they understand the scope of variables and how the stack is used?
17. What is polymorphism?
18. Why is polymorphism better than simple collection of source files with subroutines and data structures?
19. What's a virtual function and how do they work?
20. When should you use multiple inheritance?
21. What is a virtual destructor?
22. What is a mutable member?
23. c++: Describe run-time type identification.
24. What problem does the namespace feature solve?
25. What is a Make file?
26. In C++, what is the difference between method overloading and method overwriting?
27. In the derived class, which data member of the base class are visible?

Design Problems:

1. Implement a thread-safe class that will read/write to/from a buffer
2. Write an algorithm for Soduku puzzle
3. Solve the mouse in a maze problem
4. Wire Routing Problem using Queues.
5. How could you generate a file of k unique random integers between 0 and n-1 in random order?
6. Write a function to smooth out stock fluctuations.
7. Write a small lexical analyzer. it should be able to parse simple expressions like a*b
8. What is the solution to the reader-writers problem
9. Implement a multiple-reader-single-writer lock given a compare-and-swap instruction. Readers cannot overtake waiting writers.
10. Write an efficient algorithm and C code to shuffle a pack of cards. The cards are stored in an array of integers.
11. Order the following runtimes in order of their asymptotic performance O(2^n), O(n^y), O( 10^100), O(n!), O(n^n)
12. Implement malloc or write the code for malloc memory allocation function.
13. 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.
14. 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).
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. Write code to read and write from a bounded buffer
21. Function to select the eight strongest radio stations in a radio
22. Design and implement a self managing Thread Pool class
23. Write a function to draw a circle. (x**2 + y**2 = r** 2). You cannot use any floating point computations.
24. 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)
25. In the game of tic tac toe, write a program to generate moves by a computer. This should be fast.
26. 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).
27. 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.
28. DNA Sequence Pattern Match/ String Search Problem
29. Given a stream of numbers, suggest a data structure to store the numbers in the stream along with their number of occurrences.
30. Write a function that adds 30 days to a given date.
31. How would you design a restaurant reservation system, parking lot, elevator, vending machine (gen question). (test an elevator, vending machine, online shopping cart)
32. Find the angle of a clock at a particular time
33. 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?
34. Write a function to check if two rectangles defined as below overlap or not. struct rect { int top, bot, left, right; } r1, r2;
35. 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.
36. 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)
37. 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].
38. 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

1. Write a program to find if a machine is big-endian or little-endian.
2. How do you test if a number if power of 2.
3. Write a function to figure out if a computer's stack grows up or down.
4. How can you align a pointer to a 4 byte boundary in an efficient way.
5. How do you find if the sum of two unsigned integers has resulted in an overflow?
6. reverse all the bits in the byte
7. count the number of set bits in a number. Optimize for speed and time.
8. multiply a number by 8 without using the * or + operators. Can you multiply with 7?
9. Add numbers in base n (not any of 10,16,8, or 2) -2 charles simonyi
10. Exchange two numbers without using a temporary say a = 8 and b = 10
11. a = a+b b = a-b a = a-b
12. array of 0's and 1's. Give an efficient algorithm to count the number of 0's and 1's
13. What are the logical operations? (AND, OR, NOT, XOR.)
14. What's the difference between logical-AND and bitwise-AND?
15. What is 36 expressed in hexadecimal?
16. Write an if-statement that tests whether the high order bit is set in a byte.
17. Reverse the bits of an unsigned integer.
18. Compute the number of ones in an unsigned integer.
19. Compute the discrete log of an unsigned integer.
20. How do we test most simply if an unsigned integer is a power of two?
21. Set the highest significant bit of an unsigned integer to zero.
22. 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).
23. What is a volatile variable?

OS/Systems Programming

1. What is  a deadlock?
2. What is a Semaphore?
3. How does the race condition occur?
4. What are mutex and semaphore? What is the difference between them?
5. What are the disadvantages of using threads?
6. Describe synchronization in respect to multithreading.
7. What is Virtual Memory?
8. What is multiprogramming?
9. 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

1. What is Boyce Codd Normal form?
2. 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)
3. Write a SQL Query to find first day of month?
4. Why there is a performance difference between two similar queries that uses UNION and UNION ALL?
5. How to choose between a Clustered Index and a Non-Clustered Index?
6. How you can minimize the deadlock situation?
7. When you should use low fill factor?
8. Explain Third normalization form with an example?
9. What is a Cartesian product? What causes it?
10. What is an advantage to using a stored procedure as opposed to passing an SQL query from an application.
11. What is the difference of a LEFT JOIN and an INNER JOIN statement?
12. When a query is sent to the database and an index is not being used, what type of execution is taking place?
13. What are the pros and cons of using triggers?
14. What are the pros and cons of using stored procedures. When would you use them?
15. What are the pros and cons of using cursors? When would you use them?

Networks and Security

1. What is the difference between TCP and UDP?
2. How do you use RSA for both authentication and secrecy?
3. What is ARP and how does it work?
4. What's the difference between a switch and a router?
5. Name of seven layers in Open System Interconnection model.
6. Name some routing protocols? (RIP,OSPF etc..)
7. Give 4 examples which belongs application layer in TCP/IP architecture? (from CISCO )
8. How do you do authentication with message digest(MD5)? (Usually MD is used for finding tampering of data)
9. How do you implement a packet filter that distinguishes following cases and selects first case and rejects second case.
10. i) A host inside the corporate n/w makes a ftp request to outside host and the outside host sends reply.
11. ii) A host outside the network sends a ftp request to host inside. for the packet filter in
12. both cases the source and destination feilds will look the same.
13. 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?
14. Explain Kerberos Protocol?
15. What are digital signatures and smart cards?
16. Difference between discretionary access control and mandatory access control?
17. What is the goal of the shortest distance algorithm ?

Personal

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

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

Puzzles

1. Fly plane around the world half fuel puzzle *
2. 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.
3. 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!
4. 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.
5. 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?
6. Why is a manhole cover round?
7. How many cars are there in the USA? (A popular variant is "How many gas stations are there in the USA?")
8. How many manhole covers are there in the USA?
9. 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?
10. 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?
11. 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?
12. 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?
13. 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?
14. 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.'
15. 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.
16. 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?
17. 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?
18. 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.
19. 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.
20. 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?
21. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
22. 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?
23. 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.
24. A version of the "There are three persons X Y Z, one of which always lies".. etc..
25. 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.
26. Which way should the key turn in a car door to unlock it?
27. If you could remove any of the 50 states, which state would it be and why?
28. 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).
29. (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

1. C#/.NET
1. Reference/value type, stack vs heap, garbage collectpr
2. boxing vs unboxing
3. const vs readonly
4. delegates vs events
5. generics
6. partial classes - what is and what problem is solved
7. nullable types
8. config relatinships: app.config, web.config,  machine.config
2. ASP.NET
1. Controls and Pafe Life Cycle
1. Order these in the correct order
1. Static constructor
2. class constructor
3. PreInit
4. Init
5. InitComplete
6. PreLoad
7. Load
8. LoadComplete
9. Validation
10. Event Handling
11. PreRender
12. PreRenderComplete
13. Render
14. Unload
15. DataBinding (can happen anytime between Init and PreRender)
2. State
1. Compare these in terms of scope, life cyle, pros/cons
1. Application (system.web.HttpApplicationState)
2. Cache(system.web.Caching.Cache)
3. Items (System.Web.httpContext.Items)
4. Sessions (system.web.UI.HttpSessionState)
5. Profile (System.Web/HttpContext.Profile) ASP.NET 2.0
6. ViewState (system.Web.UI.COntrol.ViewState)
7. ControlState (System.Web.UI.Control.ControlState) ASP.NET 2.0
8. Cookies (System.Web.HttpRequest.Cookies)
9. Query String Paramters (System.Web.HttpRequest.QueryString)
10. Hidden Input Fields (System.Web.UI.ClientScriptManager.RegisterHiddenField(....))
2. Page Intrinsics
1. Discuss the purpose and usage of these:
1. Request (System.Web.HttpRequest)
2. Response
3. Context System.Web.HttpContext
4. Server System.Web.HttpServerUtility
5. ClientScript System.Web.UI.CLientScriptManager
6. Trace System.Web.TraceContext
7. Browser System.Web.ttpBrowserCapabilities
3. Controls
1. Compare and contrast
1. Server Controls (webControls, HtmlComtrols, Composite Controls, Custom Controls)
2. Templates Controls (UserControls, Page)
3. Web Parts - .NET 2.0 or Sharepoint 2.0
4. Conceptual Questions
1. Compare Server.Transfer(...) vs Request.Redirect(...)
2. Describe how ASP.NET builds and renders pages
3. How are master pages implemented
4. How do you add javascript to an asp.net page
5. IIS Administration
1. AppPool vs Website vs Virtual Directory
2. Posts or Host geaders for multiple roots
6. XHTML 1.0/1.1
1. Difference from HTML 4.01? How to get valid xhtml?
2. Which browser classes should you code/test for?
3. Describe building complex or columnar layouts without nested tables
7. CSS 2.1
1. Give syntax for each select and explain what each sleector matches
1. Any element: "*"
2. Class ".className"
3. Element: "ElementName" e.g. "div"
4. ID: "#ElementID" e.g. "#ctrl01_myDiv"
5. PseudoClass "Selector:PseudoClass" e.g. "A:hover"
2. Box model
1. Draw a diagram of how each of these porperties exists within the box model: margin, padding, border, width, height, left, top
3. Positioning
1. Describe usage and values for "float"
2. Describe usage and values for "position"
3. contract methods for hiding elements
4. Media Types
1. Explain how to target a set of styles to a specific media type (e.g. printing with white background)
5. Advanced Techniques
1. Describe effects and usages of setting a negative margin on a block
2. describe and discuss image replacement technique
6. javascript
1. What is the syntax for declaring variables?
2. Contrast with C# or java
7. Object oriented javascript
1. descibr classes in javascript
2. describe usage of prototype keyword
8. DOM familiarity
1. find an element via id
2. find an element via tag
3. show a message box
4. ask the user for permission
5. get input from the user 
9. XSLT
1. Contrast xsl:stylesheet vs xsl:template
2. what is match="..." in xsl:template
3. calling templates vs applying templates
4. Flow control?
5. XPath expression
10. XML in .NET
1. Name some methods for generating xml in .NET
1. XmlWriter
2. XmlDocument
3. Serialization
4. DataSet.WriteXml()
5. XpathDocument using external XSLT
6. How do you control/customize serialization
1. using serializable attribute
2. Decorate class members with atributes to rename/ignore/specify types
3. Implement ISerializable and manually control via another method
2. Threading and Synchronization
1. Mutex corss process
2. sybc() {} for critical sections
3. ReaderWriter lock
4. Semaphores
3. WebService
1. C# attribute for decorating as webservice
2. Webservices base class: what value if can decorate with attributes
3. Design considerations vs. remoting or sharing libraries?
4. Design patterns in .NET
5. C# iterators