程序员有趣的面试智力题(An interesting interview question for programmers)
程序员有趣的面试智力题(An interesting interview question for
programmers)
1, consider a double play. The game takes place on a round table. Each player has enough coins. They need to take coins placed on the table, when necessary and can only be placed in a coin, the coin placed entirely within the requirements desktop (not part of a hanging on the table outside, and not let go) and the original coin overlap. Whoever has no place to put new coins will lose. Does the pioneer or the stalker have a winning strategy? What is this strategy?
Answer: the forerunner placed a coin at the center of the table, and the coin later placed in the position relative to the place where the walker had just put it. In this way, as long as the rear runner can release, the forerunner must also have place to put. The forerunner will prevail.
2, with linear time and constant additional space will be an article of words (not characters) in reverse order.
Answer: first, reverse all the characters in the whole text (exchange the relative characters from the two ends), and then reverse the characters inside each word in the same way. In this way, the word order of the whole article is reversed, but the word itself is turned back.
3, add a space with linear time and constant to move a m bit to the left of the string of length n. For example, "ABCDEFG" moves 3 bits and becomes "defgabc".
Answer: cut the string into two halves of M and N-M. Divide the two parts in reverse order, and then reverse the whole string.
4, a rectangular cake, the cake has a rectangular hole inside. How do you cut the cake into two equal pieces with only one knife?
Answer: notice that the lines that share the rectangular area pass through the center of the rectangle. The line between the larger rectangle and the hollow rectangle draws a line that clearly divides the two rectangles into half, and their differences are, of course, equal.
5, a rectangular chocolate, at the beginning by N, x, M small pieces. Each time you can only break a bar of chocolate into two small rectangles. How many times do you need to break them into small chocolate pieces of N x M 1x1?
Answer: N, x, M - 1 times is obviously enough. This number is also necessary, because every time after the breaking of chocolate can only add a number of N x M, put the chocolate into pieces of N x M requires at least 1 times - breaking.
6, how to quickly find a 32 bit integer binary expression, how many "1"? With the linear time of the number of "1"?
Answer (1 digits on the linear): for (n=0; B; b = 1) and if (B & n++ 1);
Answer 2 (the number of "1" linear): for (n=0; B; n++) B B-1 &=;
7, a size of N array, all numbers are not more than N-1 positive integer. Use the O (N) time to find the number of repetitions (assuming only one). An array of N sizes, all of which are positive integers no more than N+1. Use the time of O (N) to find the number that does not appear (assuming only one).
Answer: calculate the sum of all the numbers in the array, and then calculate the sum of all the numbers from 1 to N-1. The difference between the two is the number of repetitions. Calculate the sum of all the numbers in the array, and then calculate the sum of all the numbers from 1 to N+1, the difference between them is the missing number.
8, give a line of C language expressions to determine whether a given integer is a power of 2.
Answer: ((B & B-1)) = = 0
9 how many points on earth make it a mile south from that point, a mile east, and a mile north, and then just back to the starting point?
Answer: the north pole is a traditional answer, but there are other answers to the question. In fact, there are infinitely many points to satisfy the requirement. All from South Pole 1 + 1/ (2 n) miles are to meet the requirements, go to the South after the arrival of a mile from the South Pole 1/ (2 pi) place, walk to the East after a mile, just around the circle of latitude for a week, and then go to the North back to the starting point. In fact, this is still not the whole point of meeting the
requirements. The distance from South Pole 1 + 1/ (2k PI) is OK, in which K can be any positive integer.
10, A, B two people on two islands respectively. B is sick. A has the medicine that B needs. C has a small boat and a lockable box. C is willing to transport things between A and B, but things can only be put in boxes. As long as the box is not locked, C steals everything in the box, no matter what is in the box. If A and B each have a lock and a key that can only open their own locks, how should A safely deliver things to B?
Answer: A put the medicine in the box and locked the case with its own lock. When B gets the box, add another lock to the case. When the box is shipped back to A, A takes its own lock. When the box was shipped to B, B took his lock and got the medicine.
11, a couple invited N-1 to the couple's Party (so there was a total of 2N people at the party). Everyone shook hands with all the people he didn't know. Then the host asked the rest of them (2N-1 people each) to hold hands several times and all the answers were different. Suppose each person knows his spouse, how many times does the hostess hold her hand?
Answer: the number of handshakes is only 2N-1 from 0 to 2N-2. Apart from the male host, there were 2N-1 individuals, so each number happened exactly once. One of them (0) did not shake hands, and one of them (2N-2) shook hands with all the other couples. The two must be a couple, or the latter will shake hands with the former (so that the number of handshakes is no longer 0). Remove the couple, a man (1) and (2N-2) shook hands, a man (2N-3) and (0) in addition to other couples outside all shook
hands. The two must be a couple, or the latter will shake hands with the former (so that the number of handshakes is no longer 1). And so on, until the person who has held the N-2 hand and those who have held the N hand have a pair. At this point, all the men except the host and his spouse have been paired. According to the rule of exclusion, the last remaining person with a handshake number of N-1 is the hostess.
12, two robots, initially located at different locations on the number axis. Enter the same program for the two robots so that the two robots are guaranteed to meet. Program can only include "left shift n units", "right shift n units", conditional judgment statement "If",
The loop statement while, and two functions that return the Boolean value, "at their own starting point" and "at the starting point of the other party"". You cannot use other variables and counters.
Answer: at the same time, the two robots begin to move right at unit speed until a robot moves to the starting point of another robot. The robot then chases the other team at double speed. Procedures are as follows.
While ({at_other_robots_start) {
Move_right 1
}
While (true) {
Move_right 2
}
13, if you are asked to choose one of the two games, which one do you prefer? Why?
A. write down a sentence. If that's true, you'll get $10; if that's false, you'll get less than $10 or more than $10 (but not exactly $10).
B. write down a sentence. True or false, you'll get more than 10 dollars.
Answer: choose the first game and write "I won't get $10, and I won't get $10000000."".
14, you are in a 100 storey building, there are 21 wires, thread marked with digital 1..21. The wires extend all the way to the top of the building with the letters' A..U 'at the end of the building. You don't know the corresponding relationship between the following numbers and the letters above. You have a battery, a light bulb, and a lot of very short wires. How can you determine the corresponding relationship of the wires and cables only when you go up and down?
Answer: in the following 2,3 put together, put 4 to 6 of the company together, put 7 to 10 of the company together, etc.,
In this way, you divide the wires into 6 equivalent classes,
sizes 1, 2, 3, 4, 5, 6, respectively. Then go to the roof and figure out which line is not connected to all the other wires, which lines are connected to the other, which lines are connected with the other two, and so on, so as to determine which equivalence class the letter A..U belongs to. Now, the first letter in each equivalence class together, form a new equivalence class size is 6; the 5 equivalence classes in second letters together to form a new equivalence class size is 5 and so on. Go back downstairs and distinguish the new equivalence classes. Then you'll see how each number corresponds to the first letter of the original equivalence class, thus solving the problem.
15, some prescription requirements are very strict, you need to take A, B, two tablets each at one time, can not be more and less. This medicine is very expensive. You don't want any waste. One day, you opened the bottle of medicine containing A, poured a tablet into your palm, and opened another bottle of medicine, but accidentally poured two tablets. Now, you have a tablet on your palm, A, two tablets, B, and you can't tell which is A and which is B. How can you strictly follow the prescription, take the pills, and do not have any waste?
Answer: three pieces of Medicine on the handle are cut into halves and divided into two piles. Take another pill, A, cut it in half, and add a half slice of A to each pile. Now, each tablet contains exactly 2.5 slices of A and 2.5 slices of B. Take one of them a day.
16, you're on a spaceship,
The computer on the ship has n processors. Suddenly, the spacecraft was attacked by an alien laser weapon, and some of the processors were damaged. You know, more than half of the processors are still good. You can ask a processor whether the other processor is good or bad. A good processor always tells the truth, and a bad processor always tells lies. Ask n-2 times to find a good processor.
Answer: label the processor from 1 to n. Using symbolic a->b to indicate a processor marked to a, ask whether processor B is good. First ask 1->2, and if 1 says no, remove both of them (remove one good and one bad, leave the good half of the rest of the processor), and then start asking questions from 3->4. If 1 says 2 is good, go on asking 2->3, 3->4,...... Until a certain time j said j+1 is bad, the J and j+1 removed, and then ask the J-1 - > j+2 - > j+3; or from the j+2 start asking questions, if there is no J-1 (before the front has been removed after). Notice that you always maintain such a chain, and each processor in front of you says that the latter is good. All the processors in this chain are either good or bad. As this chain grows longer and fewer processors are left, there is always a time when the chain is more than half of the rest of the processor, and then you can be sure that all the processors in this chain are good. Or, as more and more processors are removed, the chain length is still 0, and only one or two processors are left behind, and they must be all right.
Also noted that the first processor has never been asked to think carefully, you will find the last processor is not likely to be asked (once the chain length exceeds the remaining half of the processor, or the last is not removed only this one, you
would not ask so). Ask the number of not more than n-2.
17, a disc was painted black and white two colors, two colors each accounted for a semicircle. The disk rotates at an unknown speed and in an unknown direction. You have a special camera that allows you to instantly see the color of a point on the circle. How many cameras do you need to determine the direction of the disk rotation?
Answer: you can put two cameras on two points near the disk, and then watch which points change first. In fact, just one camera would be enough. Control the camera moving clockwise around the center of the disk, observe how often the color changes, and then let the camera move counterclockwise around the center of the disk at the same speed, again to see the frequency of discoloration. It can be concluded that the rotation direction of the camera is the same as that of the disc at a slower color change.
18, there are 25 horses, the speed is different, but the speed of each horse is fixed. Now there are only 5 tracks that can't be timed, that is, at each game, you can only know the relative speed of 5 horses. Ask at least a few races to find the fastest 3 of the 25 horses (Baidu 2008 interview questions)
Every horse has at least one chance to enter the race, so the 25 horses are divided into 5 groups, and the first 5 races are unavoidable. Next, it's easy to find a champion,
Each group of champions will play one game (sixth games). The last one is to find second and third. We ranked them in groups,
B, C, D, E in the first 5 games, in accordance with the rankings obtained in the sixth games. Namely: A group champion is first place in sixth games, B group champion is sixth games second...... Each group has 5 horses according to their race out results from fast to slow:
Group A: 1, 2, 3, 4, 5
Group B: 1, 2, 3, 4, 5
Group C: 1, 2, 3, 4, 5
Group D: 1, 2, 3, 4, 5
Group E: 1, 2, 3, 4, 5
From what we have now, we can know which horses have been excluded from the 3 place. As long as has been able to identify 3 horsepower or more than 3 over the horse quickly, then it has been eliminated. As you can see, the 5 horses with only the bold ones in the upper table are likely to be 2 or 3. Namely: 2 and 3 in group A; 1 in group B; 2 in group C; first in group A. Take the 5 horses for seventh games, and the first two of the seventh races are 2, 3, and 25. So there are at least 7 games.
There are some variations on this one, such as 64 horses looking for the top 4. The method is the same. After you reach the first place, you can find a candidate for the latter 3.
本文档为【程序员有趣的面试智力题(An interesting interview question for programmers)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。