Deleting all your perforce workspaces

p4 clients -u | cut -f2 -d" " | xargs -I {} -t p4 client -d  {}

100 coins dividing into equal heads groups.

Question:
You have 100 coins, 37 of them are heads, rest are tails. Your task is to divide this 100 coins into two groups in which there will be the same number of heads. You are blindfolded and you can flip any number of coins.

Solution:
Pick any 37 coins and flip all of them.

Explanation:
 Lets take a simple case where 5 coins with 3 heads and 2 tails.
HTHHT
Lets take 3 coins randomly. Say first,fouth and fifth lets call it S1. Let remaining coins be S2. So we have 2 groups now
S1(H,H,T) and S2(T,H)
When we flip  the selected set S1 it turns into S1F(T,T,H).  We have only one head in both the sets.

How to select k sample nodes from a unknown sized linked list.?

http://en.wikipedia.org/wiki/Reservoir_sampling can be applied here. Is there any better solution for this problem?

Map reduce implementation of reservoir sampling is discussed in this blog post.
http://had00b.blogspot.in/2013/07/random-subset-in-mapreduce.html

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

This problem can be solved using simple encoding technique. We should use the minimum element to get the next minimum element.Here is a solution which uses O(1) space.PUSH(elem) Operation: In this process we are keeping minimum element on the top of the stack at any given time. And encoding(i.e elem-min) the actual data with minimum and storing. Whenever there is a change in cur minimum data stored in the stack will be negative. This property will be used while poping the elements to find the next minimum. We can define it as shown below. if stack is empty. Store the element twice Else CurMin = POP(); Take difference between elem and Curmin and push it on to stack. Push the least of elem and CurMin on to stack.
POP() Operation: POP process is bit tricky. If minimum is not changing (i.e elements are positive on stack) then return the element + curMin(sitting on stack). If you see a negative stack element then it means there was a shift of curMin (or minimum element is the one which is being popped). In this case we take the current minimum and return it as popped element. We find the new minimum (as current minimum is popped out) by computing curMin-element and push it on top of stack as minimum element. We can summarize it as shown below.curMin = pop();element = pop(); If element is negative then return curMin and push curMin-element on to stack. Else push curMin on to stack and return element + curMin.
FindMin():
This is trivial operation as we are storing minimum element on the top of the stack at any given time. So we pop it and return to the caller. FindMin() steps will be...min=pop();push(min);return min;

Does the sun always rise in the east

This is a bit odd question for testing a s/w engineer. But still people ask these Qs. Here is the most appropriate answer i could get.

At the North Pole, there is no such thing as east. Every direction is south. During the six-month polar "day," the sun rises in the south and sets in the south. Similarly at south pole every direction is north.

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?

(eg given s1 = ABCD and s2 = CDAB, return true)
(given s1 = ABCD, and s2 = ACBD , return false)

Sol:
This is most frequently asked question. It can be solved with simple logic as given below.

1 . Check if both s1, s2 are of same length.
2. if( strstr(strcat(s1,s1), s2) !=NULL) return TRUE
else
return FALSE

Example:
if s1 = ABCD, the concatination will make it ABCDABCD and hence any rotation will fall within the concatenated string. s2 is italicized in conctenized in above concatenated string.

Mathematician daughters age problem?

Problem:
Two old friends(Mathematicians) meet each other after 20 years.Lets call them A,B.
A says to B: “how have you been?”
B says: “Great! I got married and I have three daughters now”
A says: “Really? how old are they?”
B says: “Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”
A says: “I still don’t know”
B says: “The oldest one just started to play the piano”
A says: “my oldest is the same age!”

Solution:

This is simple mathematical problem which can be solved by applying simple logical reasoning in the case of ambiguity.
After first clue A couldn't answer the question just because there might be two sets of three numbers which produce product of 72 and the sum of numbers in both the sets is equal.
After simple calculation we can reduce on two following two sets where sum of numbers is equal.
(8,3,3) & (6,6,2)
In second case two elder kids are of same age, so you cannot pick an “oldest”. Answer is (8,3,3) hence.

Why are manhole covers round rather than square?

This Question was most interviewer's favourite question for years. I hardly find anyone asking it these days. Answer to this question involves some simple maths with commonsense.
All of us know that circle has same diameter in all directions so no matter how you hold it cover cannot be pushed into a circular manhole. Whereas, if it is square, cover can be pushed into manhole via diameter by holding it on edge. Another aspect is, if cover is circular it is easier to roll it so for shorter distances transportation is easy.

Simulate seven sided die using 5 sided die?

This Question is asked in different formats like simulate rand7() using rand5() function.

There is no right answer to this question if interviewer specifies that 7 sided die should have equal probability to al the numbers on it(i.e. 1-7). This is because 5 and 7 are coprime and there is no direct mapping available between coprimes.
There are several solutions which creates a biased 7 sided die.
Sol1:
Throw 5 sided die 7 times. sum will be between 7 and 35, with equal probable numbers. Then take the module 7 of the sum and add 1 to it.
This solution will produce biased die because probability of 1 is higher here.

Sol2:
rand7() = ((ran5() + rand5() + rand5() + rand5() + rand5() - 5) % 7) + 1

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;
}
}