Alternative earnings through internet.

Modern day students need not depend on their parents or elders for the pocket money. With the widespread use of internet there are lot of opportunities available for making money online. There are couple of online survey sites based in india which are providing reward points for filling up simple surveys ( http://xcel-onlinesurveys.com?sid=1&rid=AF24257&aid=0).
Lot of online work portals like rentacoder.com etc.. which provides works ranging from homework help to large industrial automation projects in the field of IT.

microsoft livesearch win rewards

Live.com microsoft's search initiative introduced a new feature which enables users to play the video search results with mouseover. This is one of the scoring points for Live.com apart from host of incentives you get by searching with Windows Live search engine.

Microsoft has comeup with free talktime offer to popularize there search. Click on the below link to find out more.
http://winwithsearch.com

Their searchperks program where you can win gifts based on the reward points in still on. Last date to register is 31st December,2008. Below link have the details.

http://www.getsearchperks.com/
I don't know whether it helps in popularizing their search , but certainly helps users in winning prizes.

There are 25 horses and only 5 tracks. No of matches to find top 3 horses.

Problem:
There are 25 horses and only 5 tracks. So only 5 horses can run the race at a time. How many minimum no of races should be conducted to find the 3 best horses?
Sol: The answer is 7.
Round 1: Take 5 horses at a time. 5 winners of each race will go to round2.
Round 2: Winner of this will be top most horse.(call it W1)
Round 3: Final race comprises of following 5 horses.
h1: 2nd horse of round2
h2:3rd horse of round2
h3:2nd horse of W1's group during round 1
h4:3rd horse of W1's group during round1
h5:2nd horse of h1's group during round1

Hat color problem--most asked question in interviews..

http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle

Two tribes one always tells true other false....

There were 2 tribes living on an island. The east tribal people always tell a lie. The west tribal people always tell the truth. Alan and Bryan came from the same tribe. However, we do not know which tribe they came from. When they were asked the marital status, Alan said: “Both of us are married.” But Bryan said: “I am not married”. Are they really married?


Ans:

Both are from same tribe. It means either both of them will lie or both will tell true. If we look at the statements both of them contradicts about Bryan's marital status. It means one of them is not telling truth, as they are from same tribe it concludes that they are from east tribe. It means Bryan is married and Alan's status is unclear.

Design a stack which have O(1) time complexity for finding the minimum element?

We can think of two different solutions -
Sol 1:
With additional memory where time complexity of findmin(),Push(),Pop() is O(1) but space complexity is O(n). Along with pushing the elements push the current minimum on to the stack. For pop operation pop 2 elements instead of 1 , it is still O(1).
For ex: Let us assume the following numbers which are pushed on to the stack.
4 2 9 3 6 1
Stack state will be something like below
4 4 2 2 9 2 3 2 6 2 1 1.
POP(x) = pop(), pop().
Where POP(x) is modified stack pop operation. pop() is standard pop() operation.
FINDMIN(x)=pop()
PUSH(x)=push() and push( MIN(pop(),elem)).
Where PUSH(x) is modified stack push operation. push() is standard push() operation.
Here storage needed for stack is 2n where n is number of elements in the stack.

There is another optimal solution which i will post later.

Difference Between Composition and Aggregation in Object Oriented Programming?

Both are one way of extending a class.

In a composition relationship, the whole has sole responsibility for the disposition of its parts, or as you put it above, the whole "controls the lifetime of" the part. In order for the whole
to have "sole disposition" or "control the lifetime" of its parts, the whole must be the only object that knows of the parts existence.

C++ Code Example:

class Whole {
Part* part;
public:
Whole(): part( 0 ) { }
~Whole() { delete part; }
};
Part is created inside Whole class constructor and it is destroyed when whole is destroyed.

Real Life Example:
University and Departments have a composition relationship. When University is created all the departments are created with it. When University is removed departments will not have the existance of their own.


In aggregation relationship, the part object reference can be re-used. Usually creation of part object is not the responsibility of the ‘whole ‘ object. It would have been created somewhere else, and passed to the ‘whole’ object as a method argument. Whole object will not have control on the lifetime of the part object.

class Whole {
Part* part;
public:
Whole() { }
~Whole() { }
};

Real Life Example:

University and Professors are in aggregation relationship. When University is formed professors will come and join the University. But, when University is removed Professors will still exists and they can work in other Universities.

Given a singly linked list, determine whether it contains a loop or not.

1. Start reversing the list. If you reach the head, then there is a loop.
But this changes the list. So, reverse the list again.
2. Second solution is called Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment first pointer by one and
second pointer by 2. After each increment comapre if they are equal. They will meet if there is a loop.

p1 = p2 = head;
do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);

3. Hash all seen nodes and compare the next node with the nodes in the hash. If a node is already present in the hash then there is a loop.

Under what circumstances can one delete an element from a singly linked list in constant time?

If the list is circular and there are no references to the nodes in the list from anywhere else! Just copy the contents of the next node and delete the next node. If the list is not circular, we can delete any but the last node using this idea. In that case, mark the last node as dummy!

Remove duplicates from a linked list ?

NODE *DupRem(NODE *head)
{
NODE *p1 = head, *p2, *resultList = NULL, *temp = NULL;
while(p1 != NULL)
{
p2 = p1->link;
while(p2 != NULL)
{
if(p1->data == p2->data)
{
break;
}

else
{
p2 = p2->link;
}
}

if(p1->data==p2->data)
{
p1 = p1->link;
}else
{
if(resultList == NULL)
{
resultList = p1;
temp = p1;
p1 = p1->link;
}else
{
temp->link = p1;
temp = temp->link;
p1 = p1->link;
}
}
}
return resultList;
}

Given two sorted linked lists, write a function to merge them into one?

list* merge(LIST* list1, LIST* list2){
LIST *it1, *it2, *head;
if(!list1) return list2;
if(!list2) return list1;
head = (list1->value <= list2->value) ? list1 : list2;
if(head == list1)
{ it1 = list1; it2 = list2;
}
else{
it1 = list2;
it2 = list1;
}
while(it1->next && it2){
if(it1->next->value >= it2->value){
list *temp = it1->next;
it1->next = it2;
it2 = it2->next;
it1->next->next = temp;
}
else{
it1 = it1->next;
}
}

if(it2)
it1->next = it2;
return head;
}

Given a single linked list write a function to swap each pair of nodes by manipulating with pointers (not values).?

Sol:
Original list: head->1->2->3->4->5->NIL should be transformed to head->2->1->4->3->5-> NIL

int reverse_pairs(LLIST ** head)
{
LLIST * temp = ULL;
LLIST* current_pair = *head;
LLIST** previouspair = head;
while((current_pair != NULL) && (current_pair->next != NULL))
{
temp = current_pair;
current_pair = current_pair->next;
temp->next = current_pair->next;
current_pair->next = temp;
*previouspair = current_pair;
current_pair = temp->next;
previouspair = &temp->next;
}
return 0;
}

Reverse each individual word in sentence?

void reversestr(char* str, char* strend)
{
char tmp;
while(strend>str)
{
tmp = *strend;
*strend = *str;
*str = tmp;
str++;
strend--;
}
return;
}
void reverseSen(char *sentence)
{
char *wordstart=sentence, *wordstop=sentence;
char *pSend=sentence,*pSstart =sentence ;
int size=0;
while(*pSend != '\0'){
pSend++;
size++;
}
pSend--;
// reverese stentence
reversestr(pSstart,pSend);

while(wordstop < pSend)
{
//find the word
while((*wordstop!='\0')&&(*wordstop!=' ')) wordstop++;
wordstop--;
//reverese the word
reversestr(wordstart,wordstop);
wordstart = wordstop +2;
wordstop = wordstart;
}
}

Find out if a string is a palindrome?

bool Palindrome(char *str)

{
int end = strlen(str)-1;
for (int i = 0; i <>
if (*(str+i) != *(str+end))
return false;
return true;
}

Find a repeated integer in array of size n?

int DuplicatedNumber(int *a, int size)
{
map hash;
bool founddup = false;
for(int i=0; i 0)
{
founddup= true;
break;
}
else
hash[a[i]]++;
}

return founddup ? a[i] : -1; // return the duplicated value or -1 if not found
}

Giving Two Strings, Find out whether they are Anagrams(made up of same chars) or not?

If(strlen(Str1)!=strlen(Str2)) return FALSE;
sort both Str1,Str2.
If(str1==str2) return TRUE;
else
return FALSE;

Game of Russian roulette!!

You are tied to a chair and can,t get up.Here is the gun , six chambers all empty. Now I put two bullets in the gun and I put these bullets in the adjecent chambers. I close the barrel and spin it. I put the gun to your head and pull the trigger. Clik and the slot was empty. Now before we start the interview I want to pull the trigger one more time , which one do you prefer , that I spon the barrel first or that I just pull the trigger ?

X being a bullet, _ being and empty chamber. The gun rotates from 1 to 6, and the bullets are in adjacent chambers.

The setup: _ X X _ _ _
1 2 3 4 5 6

The interviewer just got a blank, so the current position must be 1,4,5, or 6. If it’s 1, the next one is a bullet. If it’s 4-6, the next one is empty. So if the interviewer just fires again, you have a 1/4 chance of getting shot.

If, on the other hand, the interviewer spins again, you’re back to the initial 2/6 or 1/3 chance of getting shot.

I’ll take the 1/4 chance, myself.

WAP to reverse a linked list?

void reverse(NODE **head) {
if (!*head) return;
NODE *cur = *head;
NODE *prev = NULL;
NODE *next = NULL;
while (cur) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head = prev;
return;

}

Recusive way call with original = list, parent = NULL

Node* reverselinkedlist(Node* original, Node*parent)
{
Node* reverse;

if(original == NULL)
{
reverse = parent;

}
else
{
reverse = reverselinkedlist(original->link,original);
original->link = parent;
}

return reverse;

}

How would you find the nth to last element in a linked list?

Sol: Have 2 pointers at the beginning of the linked list. Move ptr1 by n locations. Then start moving ptr2(which is at beginning of the list) parallel with ptr1. By the time ptr1 reaches the end of linked list, ptr2 will be at the nth last element.

Code:
void nth_last_elment(NODE *ln, int N)
{
NODE *nelement = ln, *node = ln;int i = 0 ;

while(i < N && node != NULL){
i++;
node = node->next;

}
if(i != N)
{
printf("\n Lesser than N elements in list %d \n ",N);
return ;
}
else
{
while(node != NULL)
{
node = node->next;
nelement = nelement->next;
}
}
printf("\n %dth element of link list from end is : %d " ,N,nelement->info);
}

Swap 2 values with XOR ?

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

Swap 2 values with subtraction and addition?

#define SWAP(a, b) ((&(a) == &(b)) || \

                    (((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))

If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

fill cup5 , pour it in cup3, cup5 left with 2quarters.
pour out cup3, pour cup5 into cup3, cup3 has 2quarters.
fill cup5, pour it in cup3 until cup3 fills
now cup5 has 4quarters.