
1.* Delete loops in a linked list.
(two runners on a track meet at some point if they have different speeds :)

2.* how do you efficiently return nth element from the end of the 
  linked list.(constant space and linear time)
3.* How do you revesre a sinlgy linked list in linear time and constant space?
  (with out stacks or recursion).write code for this.
4.*   if(x & x-1)
	do this
      else 
	do that

if x is a positive natural number, when will I do this and when will I do 
  that??

5. write pseudo code for eliminating blank spaces before lines and empty 
   lines from a stream of text coming one character at a time into a modem.
   ... in linear time and constant space.

   some problem solving questions.
   arrange 10 objects in 5 rows of 4 items each

6.* if you are given two cubes and you were to represent all the days of the 
month using numbers on these cubes, what numbers will you put on them 
(between 0 and 9 only)

7. A rectangular island of 50x70 meters dimensions is surrounded by a water 
canal of 10 metres width.if you have two wooden planks each 7 meters 
in length, how will you enter the island without entering the water.

8. How do you write a filesystem replicator program? how do you maintain 
consistancy and how do you check the correectness of replicator program. 
How will the replicator program be modified if the duplicate file system 
is on a different machine?

some basic c++ fundas and stuff.

I will send you a few more questions soon. These questions, I gathered from 
other guys being interviewed.

-----------------------------

o*You are given a sorted array with duplicate elements. Remove the
  duplicates in linear time, constant space, and return a count of the
  number of elements left.


o* You are given a linked list. Find out if it is circular in linear
  time and constant space.

o There is an unsorted array of positive and negative integers. Find
  the subarray that adds up to the largest sum (in linear time,
  constant space).

o*There is an unsorted array of n integers, each between 1 and
  n-1. Hence, there must be at least one duplicate. Find one in linear
  time, constant space.

o Given a string of characters, break it up into lines, and return an
  array of pointers to the beginnings of the lines. No more than 80
  chars per line, words shouldn't be broken, the array may have
  explicit newlines which must be respected, etc.

o*Given a pointer to a node in a linked list, how do you delete that
  node? 

o*How do you multiply an integer by 3.5 without using floating
   point operations?

o There are a number of disk blocks in a file system. If a file
   is too big for a disk block, the block has a pointer to the
   next block. So basically, you have linked lists of blocks.
   Identify all blocks that are first blocks (or heads of the 
   linked lists). 

o What is Lamport's algorithm for clock synchronization?

o Write a hash class. The user should be allowed to do operations
   like h.insert(x), where h is a hash object, and x is something
   that must be put in a hash table. Its type could be anything:
   int, float, string, etc.

o Write a string class. Overload the type cast operator. Do
   reference counting in the destructor. 


o*Write an efficient program to find the sum of a polynomial.
 S = a_0 x^0 + a_1 x^1 + ...........+ a_n x^n.

o Write a Queue template class.

o Write a Queue class in which each record has only one field(say an id) and
the queue has about a million elements.
(they expect you to implement a circular list of arrays!)

o* A stream of characters is given to you. It has a mixture of two kinds of
characters.
ASCII -  which is a byte long with the Most sig bit 0.
JAPANESE - which is two bytes and has the MSB in the higher byte set.

Given a stream, 
Implement a backspace function which will erase one or two bytes based
on whether it is ASCII or JAPANESE.


o* They might ask you to present any of your projects. It might be a good
idea to have a one page summary of your project with a good diagram.


o* Every time you write a piece of code they expect you to consider ALL 
boundary cases and might ask you to test your program yourself.

o*Program to invert the bits in an integer.

o* PRogram to invert a linked list.

o* GIven a string which has a mixture of carriage returns (ENTER CR) and
returns( ENTER ) in an arbitrary string replace all carriage returns
with returns.

abcde ENTER CR ENTER ENTER qqq ENTER CR 

becomes 

abcde ENTER ENTER ENTER qqq ENTER


o They ask questions about polymorphism, virtual functions, dynamic binding,
and other C++ concepts.


