Riddle #923

logicmath

Two words are anagrams if and only if they contain the exact same letters with the exact same frequency (for example, "name" and "mean" are anagrams, but "red" and "deer" are not). Given two strings S1 and S2, which each only contain the lowercase letters a through z, write a program to determine if S1 and S2 are anagrams. The program must have a running time of O(n + m), where n and m are the lengths of S1 and S2, respectively, and it must have O(1) (constant) space usage.
First create an array A of length 26, representing the counts of each letter of the alphabet, with each value initialized to 0. Iterate through each character in S1 and add 1 to the corresponding entry in A. Once this iteration is complete, A will contain the counts for the letters in S1. Then, iterate through each character in S2, and subtract 1 from each corresponding entry in A. Now, if the each entry in A is 0, then S1 and S2 are anagrams; otherwise, S1 and S2 aren't anagrams. Here is pseudocode for the procedure that was described: def areAnagrams(S1, S2) A = new Array(26) A.initializeValues(0) for each character in S1 arrayIndex = mapCharacterToNumber(character) //maps "a" to 0, "b" to 1, "c" to 2, etc... A[arrayIndex] += 1 end for each character in S2 arrayIndex = mapCharacterToNumber(character) A[arrayIndex] -= 1 end for (i = 0; i < 26; i++) if A[i] != 0 return false end end return true end
71.88 %
55 votes

Similar riddles

See also best riddles or new riddles.

logicstorymath

You are standing in a house in the middle of the countryside. There is a small hole in one of the interior walls of the house, through which 100 identical wires are protruding. From this hole, the wires run underground all the way to a small shed exactly 1 mile away from the house, and are protruding from one of the shed's walls so that they are accessible from inside the shed. The ends of the wires coming out of the house wall each have a small tag on them, labeled with each number from 1 to 100 (so one of the wires is labeled "1", one is labeled "2", and so on, all the way through "100"). Your task is to label the ends of the wires protruding from the shed wall with the same number as the other end of the wire from the house (so, for example, the wire with its end labeled "47" in the house should have its other end in the shed labeled "47" as well). To help you label the ends of the wires in the shed, there are an unlimited supply of batteries in the house, and a single lightbulb in the shed. The way it works is that in the house, you can take any two wires and attach them to a single battery. If you then go to the shed and touch those two wires to the lightbulb, it will light up. The lightbulb will only light up if you touch it to two wires that are attached to the same battery. You can use as many of the batteries as you want, but you cannot attach any given wire to more than one battery at a time. Also, you cannot attach more than two wires to a given battery at one time. (Basically, each battery you use will have exactly two wires attached to it). Note that you don't have to attach all of the wires to batteries if you don't want to. Your goal, starting in the house, is to travel as little distance as possible in order to label all of the wires in the shed. You tell a few friends about the task at hand. "That will require you to travel 15 miles!" of of them exclaims. "Pish posh," yells another. "You'll only have to travel 5 miles!" "That's nonsense," a third replies. "You can do it in 3 miles!" Which of your friends is correct? And what strategy would you use to travel that number of miles to label all of the wires in the shed?
Believe it or not, you can do it travelling only 3 miles! The answer is rather elegant. Starting from the house, don't attach wires 1 and 2 to any batteries, but for the remaining wires, attach them in consecutive pairs to batteries (so attach wires 3 and 4 to the same battery, attach wires 5 and 6 to the same battery, and so on all the way through wires 99 and 100). Now travel 1 mile to the shed, and using the lightbulb, find all pairs of wires that light it up. Put a rubberband around each pair or wires that light up the lightbulb. The two wires that don't light up any lightbulbs are wires 1 and 2 (though you don't know yet which one of them is wire 1 and which is wire 2). Put a rubberband around this pair of wires as well, but mark it so you remember that they are wires 1 and 2. Now go 1 mile back to the house, and attach odd-numbered wires to batteries in the following pairs: (1 and 3), (5 and 7), (9 and 11), and so on, all the way through (97 and 99). Similarly, attach even-numbered wires to batteries in the following pairs: (4 and 6), (8 and 10), (12 and 14), and so on, all the way through (96 and 98). Note that in this round, we didn't attach wire 2 or wire 100 to any batteries. Finally, travel 1 mile back to the shed. You're now in a position to label all of the wires here. First, remember we know the pair of wires that are, collectively, wires 1 and 2. So test wires 1 and 2 with all the other wires to see what pair lights up the lightbulb. The wire from wires 1 and 2 that doesn't light up the bulb is wire 2 (which, remember, we didn't connect to a battery), and the other is wire 1, so we can label these as such. Furthermore, the wire that, with wire 1, lights up a lightbulb, is wire 3 (remember how we connected the wires this round). Now, the other wire in the rubber band with wire 3 is wire 4 (we know this from the first round), and the wire that, with wire 4, lights up the lightbulb, is wire 6 (again, because of how we connected the wires to batteries this round). We can continue labeling batteries this way (next we'll label wire 7, which is rubber-banded to wire 6, and then we'll label wire 9, which lights up the lightbulb with wire 7, and so on). At the end, we'll label wire 97, and then wire 99 (which lights up the lightbulb with wire 97), and finally wire 100 (which isn't connected to a battery this round, but is rubber-banded to wire 99). And we're done, having travelled only 3 miles!
78.85 %
57 votes
logicmath

There are 1 million closed school lockers in a row, labeled 1 through 1,000,000. You first go through and flip every locker open. Then you go through and flip every other locker (locker 2, 4, 6, etc...). When you're done, all the even-numbered lockers are closed. You then go through and flip every third locker (3, 6, 9, etc...). "Flipping" mean you open it if it's closed, and close it if it's open. For example, as you go through this time, you close locker 3 (because it was still open after the previous run through), but you open locker 6, since you had closed it in the previous run through. Then you go through and flip every fourth locker (4, 8, 12, etc...), then every fifth locker (5, 10, 15, etc...), then every sixth locker (6, 12, 18, etc...) and so on. At the end, you're going through and flipping every 999,998th locker (which is just locker 999,998), then every 999,999th locker (which is just locker 999,999), and finally, every 1,000,000th locker (which is just locker 1,000,000). At the end of this, is locker 1,000,000 open or closed?
Locker 1,000,000 will be open. If you think about it, the number of times that each locker is flipped is equal to the number of factors it has. For example, locker 12 has factors 1, 2, 3, 4, 6, and 12, and will thus be flipped 6 times (it will end be flipped when you flip every one, every 2nd, every 3rd, every 4th, every 6th, and every 12th locker). It will end up closed, since flipping an even number of times will return it to its starting position. You can see that if a locker number has an even number of factors, it will end up closed. If it has an odd number of factors, it will end up open. As it turns out, the only types of numbers that have an odd number of factors are squares. This is because factors come in pairs, and for squares, one of those pairs is the square root, which is duplicated and thus doesn't count twice as a factor. For example, 12's factors are 1 x 12, 2 x 6, and 3 x 4 (6 total factors). On the other hand, 16's factors are 1 x 16, 2 x 8, and 4 x 4 (5 total factors). So lockers 1, 4, 9, 16, 25, etc... will all be open. Since 1,000,000 is a square number (1000 x 1000), it will be open as well.
78.50 %
79 votes
logicmath

Can you arrange four 9's and use of at most 2 math symbols, make the total be 100?
99 / .99 or 99 + 9/9
78.47 %
50 votes
logicmathstory

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels. What is the most bananas you can bring over to your destination?
First of all, the brute-force approach does not work. If the Camel starts by picking up the 1000 bananas and try to reach point B, then he will eat up all the 1000 bananas on the way and there will be no bananas left for him to return to point A. So we have to take an approach that the Camel drops the bananas in between and then returns to point A to pick up bananas again. Since there are 3000 bananas and the Camel can only carry 1000 bananas, he will have to make 3 trips to carry them all to any point in between. When bananas are reduced to 2000 then the Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward. In the first part, P1, to shift the bananas by 1Km, the Camel will have to Move forward with 1000 bananas – Will eat up 1 banana in the way forward Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana Note: After point 5 the Camel does not need to return to point A again. So to shift 3000 bananas by 1km, the Camel will eat up 5 bananas. After moving to 200 km the Camel would have eaten up 1000 bananas and is now left with 2000 bananas. Now in the Part P2, the Camel needs to do the following to shift the Bananas by 1km. Move forward with 1000 bananas – Will eat up 1 banana in the way forward Leave 998 banana after 1 km and return with 1 banana – will eat up this 1 banana in the way back Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward Note: After point 3 the Camel does not need to return to the starting point of P2. So to shift 2000 bananas by 1km, the Camel will eat up 3 bananas. After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas. The Camel will actually be able to cover 333.33 km, I have ignored the decimal part because it will not make a difference in this example. Hence the length of part P2 is 333 Km. Now, for the last part, P3, the Camel only has to move forward. He has already covered 533 (200+333) out of 1000 km in Parts P1 & P2. Now he has to cover only 467 km and he has 1000 bananas. He will eat up 467 bananas on the way forward, and at point B the Camel will be left with only 533 Bananas.
78.40 %
73 votes
logicmathsimpleclever

We all know that square root of number 121 is 11. But do you know what si the square root of the number "12345678987654321" ?
111111111 Explanation: It's a maths magical square root series as : Square root of number 121 is 11 Square root of number 12321 is 111 Square root of number 1234321 is 1111 Square root of number 123454321 is 11111 Square root of number 12345654321 is 111111 Square root of number 1234567654321 is 1111111 Square root of number 123456787654321 is 11111111 Square root of number 12345678987654321 is 111111111 (answer)
78.31 %
67 votes
logicmathsimple

Two trains are traveling toward each other on the same track, each at 60 miles per hour. When they are exactly 120 miles apart, a fly takes off from the front of one of the trains, flying toward the other train at a constant rate of 100 miles per hour. When the fly reaches the other train, it instantly changes directions and starts flying toward the other train, still at 100 miles per hour. It keeps doing this back and forth until the trains finally collide. If you add up all the distances back and forth that the fly has travelled, how much total distance has the fly travelled when the trains finally collide?
The fly has travelled exactly 100 miles. We can figure this out using some simple math. Becuase the trains are 120 miles apart when the fly takes off, and are travelling at 60 mph each, they will collide in exactly 1 hour. This gives the fly exactly 1 hour of flying time, going at a speed of 100 miles per hour. Thus, the fly will travel 100 miles in this hour.
78.31 %
67 votes
logicmath

There are 5 pirates in a ship. Pirates have hierarchy C1, C2, C3, C4 and C5. C1 designation is the highest and C5 is the lowest. These pirates have three characteristics: a. Every pirate is so greedy that he can even take lives to make more money. b. Every pirate desperately wants to stay alive. c. They are all very intelligent. There are total 100 gold coins on the ship. The person with the highest designation on the deck is expected to make the distribution. If the majority on the deck does not agree to the distribution proposed, the highest designation pirate will be thrown out of the ship (or simply killed). The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan?
To understand the answer,we need to reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted leaving Pirate 1 with nothing. Now let's look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted. If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}. Smart right? Now can you figure out the distribution with 5 pirates? Let's see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.
78.31 %
67 votes
logicmathclever

A grandfather's clock chimes the appropriate number of times to indicate the hour, as well as chiming once at each quarter hour. If you were in another room and hear the clock chime just once, what would be the longest period of time you would have to wait in order to be certain of the correct time?
You would have to wait 90 minutes between 12:15 and 1:45. Once you had heard seven single chimes, you would know that the next chime would be two chimes for 2 o'clock.
78.22 %
61 votes
interviewlogicmath

A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king's guards catch the servant after he has only poisoned one bottle. Alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king, how will he be able to do so?
Think in terms of binary numbers. (now don’t read the solution, give a try). Number the bottles 1 to 1000 and write the number in binary format. bottle 1 = 0000000001 (10 digit binary) bottle 2 = 0000000010 bottle 500 = 0111110100 bottle 1000 = 1111101000 Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc. prisoner = 10 9 8 7 6 5 4 3 2 1 bottle 924 = 1 1 1 0 0 1 1 1 0 0 For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die. After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned. 1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners.
78.11 %
94 votes
logicmath

Think of a number. Double it. Add ten. Half it. Take away the number you started with. What is your number?
Your number is 5.
78.06 %
49 votes