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;

How many points are there on the globe where, by walking one mile south, one mile east, and one mile north, you reach the place where you started?

In normal scenario if you think immediate answer will be zero as moving above directions will form 3 sides of a square. But here is the trick. Answer is not zero.
But precisely at north pole every direction is south only. At this point walking south one mile will place u at 1 mile to the south. For there if u walk east then you will form a circlular path centered at north pole. from there if you walk 1 mile north then again you will reach the point where you started. This journey looks like a wedge of pie. Samething holds good at south pole. But here you need to start little more than 1 mile away from south pole as you cannot go to south from the south pole. Then from this point u go 1 mile south. There walk east to form a full circle of 1 mile circumference and then walk 1 mile north. You will reach where u started. on circumference you can do this on infinite number of points. Similarly you can start little bit away from pole from where if you walk closer to pole one mile you will form a circle of circumference 1/2 mile(2 revolutions while walking east), 1/3 mile etc.....
So there are infinite number of points where you can do this.

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.

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. The opposite holds for the South Pole, where every direction is north

codechef

Introduction to CodeChef
CodeChef.com is India’s first, non-commercial, multi-platform online programming competition. CodeChef features monthly contests, practice problems and discussion boards, all geared towards helping students and professionals improve their software development skills. Our judging system accepts solutions in over 35 different programming languages (like Haskell, Ruby, Python, PHP, Perl, C, C++, C#, Java, Pascal… ) allowing users to test their skills against their peers as well as experiment with new technologies.

About CodeChef

CodeChef was created by Directi as a way to continuously challenge and engage the developer community. The site’s goals are to provide a platform for practice, competition and improvement, as well as enable developers to benchmark their skills against their peers. The first online contest begins March 1^st through March 15^th, and prizes include an Asus Eee PC, a Nokia 5800 and an iPod Touch.

The CodeChef Community

Despite launching only a month ago, CodeChef has over 1200 registered users, who submit hundreds of solutions each day. We’re able to stay connected with the developer community through our Blog, Forums, Twitter and our newly created Facebook Group. We have also announced a set of unique initiatives: CodeChef Campus Chapters and the User group outreach program. We have some exciting new features in the works including a comprehensive ranking system and Facebook Connect integration.

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.

Free domain+disk space offer from one.com

Today i have seen a good webhosting offer from one.com for indian customers.
They are giving 3000M diskspace + domain name for free for first 12 months.
We need to pay only 13.8 USD. I think there is some moneyback offer for 15 days if you are not satisfied with their service. Here is the link http://www.one.com/en_US/.

I have talked to their customer care executive about this offer.
Here is the excerpt of the same. Arjun is their customer care executive.

you: i want to know about free domain + hosting offer
Arjun: hI
Arjun: As a promotion in India, we are offering domain name and 3000MB web space absolutely free for the first year. So all you need to pay is a minimal setup fee of 13.8 USD
you: how long this offer will be active
you: when is the last day to apply
Arjun: there is no end date announced yet
you: ok
Arjun: Is there anything else I could assist you with?
you: can i put the adsense
you: on the site hosted with this offer
Arjun: yes
you: any site templates available from one.com
you: is it possible to put forums on this site
Arjun: yes
Arjun: we offer templates and yes you can install a forum
you: thanks
you: is there any offline payment option available in india
Arjun: unfortunately, no

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