面试常问问题大全
面试常问问题大全
面试时最经常被问到的问题（Frenquently asked interview questions）之Analytical, puzzles, and brain-teasers篇
Analytical, puzzles, and brain-teasers Questions & Answers
1．If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
2．If you could remove any of the 50 states, which state would it be and why?
--I would not remove any of them, (provided the definition of state is the
--I will ask the interviewer for the definition of "remove" first.
If ( the answer is dig a hole, let water bubble up)
{
I would say I "remove" a state lack of water supply.
}
else if ( the answer is give it up or give it away to other countries )
{
I would say it's some state with the biggest area of desert. And I would definitely trade sth. back from whom want it
} else // default,
{
I will keep it for possible future usage
}
3．If you are on a boat and you throw out a suitcase, will the level of water increase?
-- The answer is: it depends on the density of the briefcase. While the briefcase is in the boat, it will displace it's weight in water.
If the briefcase floats after you toss it out, then it still displaces its weight in water, and there is no change.
However, if the briefcase is heavier than water it will displace its volume, not its weight. The amount of displaced water will be less (which is why it sank) and the water level will decrease.
-- The other question is whether or not the suitcase is thrown in the water. If it is thrown on to a dock or land, then the level will decrease due to less weight in the boat.
4．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?
--- 1. Let's mark the corners of the triangle as A,B,C.
2. There are only two cases under which the ants won't collide : A->B, B->C, C->A and A->C, C->B and B->A
3. Therefore, probability of ants not colliding : 2/8 = 1/4.
---This assumes that ants move in a straight line, as we know they don't. They move all over the place, in random directions, eventually ending up in their final destinations. Although Microsoft asked me this question and was looking for the answer mentioned by other posters, they gave extra credit for what I explained.
--- You are all wrong! You have made not one but three obvious assumptions!
1) They move in straight lines.
2) They start within the confines of the triangle.
3) They stay within the confines of the triangle.
Moral: Think out of the triangle!!
5、Three men were renting a motel figuring the room cost 30 dollars they would pitch in ten a piece. The room was only 25 so they each gave the bell boy ten,(tip)the bellboy didn"t think that would be fair so he gave them each back 1 dollar and kept 2 for himself. What happened to the other dollar? ( sent by MACsabastion@webtv.net )
Oh after giving it some thought actually I was right, there isn't any missing dollar.
If you go backwards you come up to this:
9x3 = 27
27+2 = 29
so it had to be 30$ in order to be correct right?
No, because you have to add 3$ and not 2. You think it would be right if you add 2$ because the tip is that amount. But the tip is already included in the multiplication.
So the maths aren't right, it should be 9x3+3 and not 9x3+2.
6．"You have b boxes and n dollars. If I want any amount of money from 0 to n dollars, you must be able to hand me 0 to b boxes so that I get exactly what I request." The two questions were " What are the restrictions on b and n, and how is money distributed among the boxes?"
The trick is of Binary Numbers
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
....
...
2^7=128
...
The formula is [log n to base 2] + 1 = b
where [] denote integral part of the log base 2 of n
Example
So if we want 0 to 15 dollars
[log of 15 to base 2] + 1 = [3.90] + 1 = 3 + 1 = 4 boxes
we need to have 4 boxes each having 1,2,4,8, dollars respectively.Now we know from binary numbers that any amount from 0 to 15 can be formed with this boxes.
For 0 to 6 dollars
[log of 7 to base 2] + 1 = [2.58] + 1 = 2 + 1 = 3 boxes
we need to have 3 boxes each having 1,2,4, dollars respectively
For 0 to 100 dollars
[log of 100 to base 2] + 1 = [6.64] + 1 = 6 + 1 = 7 boxes
we need to have 7 boxes each having 1,2,4,8,16,32,64 dollars respectively
-Ameya Vaidya
7．What is the sum of the numbers from 1 to 1000?
Depends what NUMBER means here:
If means integer, that's 100*(100+1)/2=5050;
If not, that's infinity.
8、You are an employer. You have ten employees. Each month, each one of your ten employees gives you ten bags of gold. Each bag of gold has ten pieces of gold in it. Each piece of gold weighs one pound. One of your employees is cheating you by only putting nine pieces of gold in each of his ten bags of gold. You have a scale (not a balance, a scale), and you can only take one measurement from the scale, only one (1) reading. How can you tell which of the ten employees is cheating you by using this scale and only taking one measurement?
---When your employees come to pay you at the end of the month, take one bag from employee number one's pile and set it aside. Take two bags from employee number two's pile and add it to the one from employee number one. Take three from employee three, four from employee four, etc...
Once you have now compiled a pile of bags, you should have 55 bags (one from one, two from two, etc). Set the whole pile (all 55 bags) on the scale and take a reading. If all the bags were honest, you would have 550 pounds on the scale.
If employee one is cheating you, then the reading would be 549, since you only have one bag from employee one. Likewise, if the measurement is 547, then 3 pounds are missing, and employee three is the thief.
--- I think we are given a scale not a balance. So we can’t tell the exact weight of the bags. So how do we find out whether its 549, 547 etc.?
--- Why does he need to weigh? Can't he just count?
9、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.
--At the North Pole, The South Pole wouldn't quite work, since you can only go north from the South Pole.
--Both answers (North Pole, and all points on the circle 1 mile north of the circle having circumference of 1 mile around the South Pole) are right.
10、How would go about finding out where to look for a book in a library? (You do not know how the books are organized beforehand)
-- I would go and ask a person in charge of arranging the books instead of wasting my time in searching all of them
-- This question is open ended , though Microsoft might be testing fundamentals on Binary search , Indexing etc by asking this.
The approach I would take is , check out the index cards and find the shelf where the book is located. Then do an alphabetical search by physically going to that shelf. You can also say that you would start on the top of the shelf or the bottom depending on the "letter" name of the book etc.
-- I would leave the library, drive to the exact location of the person who wrote this question, and slap them.
11、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?
-- It's mainly because man himself is "left-right" symetric but not "up-down" symetric.
-- This is not a Physics issue... this is a matter of perception.
When you stand in front of the mirror and raise YOUR LEFT HAND, the reflection is of YOUR LEFT HAND.
By referring to "what appears to be his right hand" the question has essentially asked you to envision yourself rotated 180 degrees about a vertical axis, thus subtly introducing the apparent conflict between left and right.
Why it works: Since humans are relatively symmetric along a vertical axis you are able to envision YOUR LEFT HAND as a suitable RIGHT HAND for your reflection.
Humans are not generally symmetric along a horizontal axis (hey, I've never seen it, but that doesn't mean some freak isn't out there...), so it's much harder to envision feet as a suitable head and vice versa.
12、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?
If you select 4 Jelly beans you are guaranteed that you will have 2 that are the same color.
13、You are given a scale which you are to use to measure eight balls. Seven of these balls have the same weight: the eight ball is heavier than the rest. What is the minimum number of weighs you could perform to find the heaviest of the eight balls?. Remember it's a scale not a balance. (i.e. It can just tell you if one side is heavier than the other it can't give you the exact weight).
!..Umm. You can do this in 2 weighs. Put three balls on each side of the scale. That's a total of six balls you're weighing. If the three balls on each side weigh equally, you know that one of the two remaining balls is the heaviest. Weigh those two balls to determine which one is heaviest. If, however, one of the three ball combinations weighs most, remove all balls from the scale, then weigh just two of the three "heavier" balls. If those two balls are equal weight, the third, unweighed ball is the heaviest; otherwise the scale will indicate which of the two balls on the scale is the heavier one.
So, what’s the difference between a balance and a scale?
14．How would you design a toaster?
1. Find out Voltage to be supported
2. '' '' 2-pin/3 pin plug ?
3. '' '' How many slots for bread?
4. '' '' what size bread ?
5. Automatic pop-up
6. Easily accessible for cleaning and maintenance
7. Easily operable
8. Compact and good looking
9. Design a simple circuit that uses components that are easily available.
10. Internet enabled ?
11(?). Provide a place to keep the stack of bread slices, a settable counter, place to keep the plate, toaster automatically picks up bread from the stack, "toasts" it and places it on the plate.
12. Also could provide a butter holder that melts the butter and sprinkles it on the toast, once done.
13. Optional alarm that rings after the job is done (entire stack is toasted)
14. Optical sensor to sense the actual browning of the bread (different settings for wheat and white bread)
.. And so on.... :))
15．How would you design an universal remote control?
16．How would you design a clock for a blind person?
I would design a clock with Brail Code, Self talk and vibration and with capabilities for disabling any of those features depending on the requirement. Since vibration is very difficult to design, they can be set aside in another version of the clock.
17．How many miles of road are there in the US?
-- This series of questions is called Guesstimates, and tests
-- actually this questions is like that : how many cars in USA u can answer any number u want and argue later: ask the interviewer to count them for u, if he finds more cars than , more cars have been bought since he last counted ..., if less then a lot of cars have been scrapped...
the same thing applies to road also, enjoy
-- I guess this is funny!! I would rather say, 0.625 times the number of kms in
18．There are n couples attending a party. Each one shakes hands with the persons he doesn't know. (Assuming each person knows his/her partner) Mary and John are a couple. John asked the rest of the party-attenders how many times he has shaken hands. Each one gives a unique answer. How many times does Mary shake hands?
面试时最经常被问到的问题（Frenquently asked interview questions）之Algorithms & Coding篇
Algorithms & Coding Questions & Answers
1、Write a function to print the Fibonacci numbers.
-- int fib ( int n ){
if (n == 0) return 1;
else return fib(n-1) + fib(n-2);
}
-- int fibo (int n)
{
int i, current, one_back, two_back;
if (n <= 1)
return 1;
else {
one_back = 1;
two_back = 1;
for ( i = 2; i <= n; i++) {
current = one_back + two_back;
one_back = two_back;
two_back = current;
} /* end for loop */
} /* end else block */
return current;
}
-- There are better ways to find a solution to this problem instead of using Recursion. Recursion is a disaster as someone has already mentioned. Try giving 20 or more elements in your series and your program will take awful lot of time to compute. For every element in series you're finding the element before using recursion though you theoretically you would have computed it before!!!
2．Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
-- if (x > 0 && (x & (x-1)) == 0)
-- I think all the answers here are either wrong completely, partially, or too complex. The best answer so far, by jinaljhaveri, was if(!(x&(x-1))), which I believe works for all powers of 2, but also for 0, which is not a power of 2.
Basically, an integer which is the power of 2 will have one and only one bit set in its binary representation. If you subtract 1 from that, you will get all bits set (equal to 1) before the original 1 bit, and the rest are 0. Taking advantage of this, the answer is
if ((x << 1) == 1 + (x | (x - 1))) {}
The term x | (x - 1) makes an integer with all bits set starting from the original set bit. Adding 1 will set the next bit and clear all the previous bits, effectively doubling x, which is the same as x << 1.
It’s a pity that the second solutions work for 0 too, which is just what he/she wants to avoid.
3．Implement an algorithm to sort a linked list.
直接插入排序、直接选择排序、归并排序。
如果可以使用的额外的内存空间，会比较的简单；否则，则需要一点思考了。
4．Reverse a string.
void str_rev(char s[])
{
int len = strlen(s);
int i;
char temp;
for(i=0; i<len/2; i++)
{
temp = s[i];
s[i] = s[(len-1) - i];
s[(len-1) - i] = temp;
}
}
5．Given a linked list which is sorted, how will you insert in sorted way.
U have already very familiar with it if you did question 3 (sort a linked list) by direct insertion sort.
6．Implement an algorithm to insert in a sorted list.
7．Delete an element from a doubly linked list.
void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}
8．Implement an algorithm to sort an array.
An array can be sorted using any of the classic algorithms like quicksort , heapsort and the inefficient bubblesort.
9．Given a sequence of characters, how will you convert the lower case characters to upper case characters?
void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S>='a' && *S<='z')?(*S-'a'+'A'):*S;
S++;
}
}
10．Write a routine that prints out a 2-D array in spiral order.
int NumbersPerTime = SIZE; // 绕圈的边长
int tInit = 0; // 绕圈的起始值
for(int i = 0 ; i < (SIZE+1)/2; i++)
{
int t = tInit;
for(int j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t += SIZE;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t += 1;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t -= SIZE;
}
for(j = 0; j < NumbersPerTime-1; j++)
{
// out here
printData(t);
t -= 1;
}
NumbersPerTime -= 2;
tInit += SIZE + 1;
}
11．Give a fast way to multiply a number by 7.
int num = (n<<3) – n;
12．Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
int str2int(const char *str)
{
int value = 0;
int sign = (str[0] == '-')?-1:1;
int i = (str[0] == '-')?1:0;
char ch;
while(ch = str[i++])
{
if ((ch >= '0')&&(ch <= '9'))
value = value*10 + (ch - '0');
else
return 0; // return 0 denotes error occurs
}
return value*sign;
}
13．How would you print out the data in a binary tree, level by level, starting at the top?
1) Put the root node into a queue;
2) while the queue is not empty, do as follows;
3) Get a node from the queue, print its value, and put its children into the queue;
14．Write a routine to draw a circle given a center coordinate (x, y) and a radius (r) without making use of any floating point computations.
In order to avoid floating point calculations, we can do two things:
1) Instead of fixing one co-ordinate and looking for another via the equation, search the whole co-ordinate space from x +- r and y +- r. Plot the point that is close. But this is a costly N*N algo.
2) To go for an efficient workhorse, go for Bresenham's circle drawing algo, found in any of the good graphics textbooks.
15．You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
#include<stdio.h>
#include<string.h>
main() {
char str1[5] = "abcd";
char str2[3] = "bc";
int len = strlen(str1);
int i =0;
char newstr[len];
int cntr = 0;
for ( i = 0; i<len; i++ ) {
if ( strchr(str2,str1[i]) == NULL ) {
newstr[cntr++] = str1[i];
}
}
newstr[cntr] = '/0';
printf("%s%s%s", "The new str is ", newstr, "/n");
}
16．Write a small lexical analyzer for expressions like "a*b" etc.
bool is_astarb(char* s)
{
if (*s++ != 'a') return false;
while(*s++);
if (*--s != 'b') return false;
return true;
}
17．Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
-- Traverse array to compute sum, subtract 99*100/2, the sum of integers between 1 and 99.
-- Create a new array of b[100], elements initialized all to 0
int b[100];
for ( i=0;i<100;i++)
b[i]=0;
int tm;
for ( i=0;i<100;i++)
{
tm=t[i] ;
if b[tm]== 1;
return(tm); // return the duplicate number
else b[tm]=1;
}
printf(" there is no duplication");
return 0; // 0 indicates no duplication
O(n square ) ... just sort all numbers and check if two consecutive numbers are same by traversing the sorted array..
18．Write efficient code for extracting unique elements from a sorted list of array.
#include <stdio.h>
main()
{
int a[10] = {0,4,4,4,5,6,6,8,9,9};
int i;
for(i=0; i<10; i++)
{
if(a[i] == a[i+1] )
{
while(a[i] == a[i+1]) i++;
}
else
printf("%d ", a[i]);
}
printf("/n");
}
We do print the ununiqued numbers out, but we do not extract them!
19．Print an integer using only putchar. Try doing it without using extra storage.
1) void printInt(int a);
int b = a;
char *str;
int i = 1;
int len = 0;
while (b) {
b /= 10;
i *= 10;
len++;
}
i /= 10;
while (i > 0) {
putchar(a/i + 48);
a = a%i;
i /= 10;
}
}
2) This can be done by recursion. Since the number of recursive calls is not significant, it does not affect the performance much.