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)
for each character in S1
arrayIndex = mapCharacterToNumber(character) //maps "a" to 0, "b" to 1, "c" to 2, etc...
A[arrayIndex] += 1
for each character in S2
arrayIndex = mapCharacterToNumber(character)
A[arrayIndex] -= 1
for (i = 0; i < 26; i++)
if A[i] != 0
A Panda Bear walked into a restaurant. He sat down at a table and ordered some food. When he was finished eating, he took out a gun and shot his waiter. He then left the restaurant.After the police caught up with him, they asked him why he had killed the waiter.He replied, "Look me up in the dictionary." What did the dictionary say?
When they looked up the word "Panda" in the dictionary, it stated, "Panda: Eats shoots and leaves."
You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 13 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck.
Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this.
How can you accomplish this seemingly impossible task?
Take the first 13 cards off the top of the deck and flip them over. This is the first pile. The second pile is just the remaining 39 cards as they started.
This works because if there are N face-up cards in within the first 13 cards, then there will be (13 - N) face up cards in the remaining 39 cards. When you flip those first 13 cards, N of which are face-up, there will now be N cards face-down, and therefore (13 - N) cards face-up, which, as stated, is the same number of face-up cards in the second pile.
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.
A swan sits at the center of a perfectly circular lake. At an edge of the lake stands a ravenous monster waiting to devour the swan. The monster can not enter the water, but it will run around the circumference of the lake to try to catch the swan as soon as it reaches the shore. The monster moves at 4 times the speed of the swan, and it will always move in the direction along the shore that brings it closer to the swan the quickest. Both the swan and the the monster can change directions in an instant.
The swan knows that if it can reach the lake's shore without the monster right on top of it, it can instantly escape into the surrounding forest.
How can the swan succesfully escape?
Assume the radius of the lake is R feet. So the circumference of the lake is (2*pi*R). If the swan swims R/4 feet, (or, put another way, 0.25R feet) straight away from the center of the lake, and then begins swimming in a circle around the center, then it will be able to swim around this circle in the exact same amount of time as the monster will be able to run around the lake's shore (since this inner circle's circumference is 2*pi*(R/4), which is exactly 4 times shorter than the shore's circumference).
From this point, the swan can move a millimeter inward toward the lake's center, and begin swimming around the center in a circle from this distance. It is now going around a very slightly smaller circle than it was a moment ago, and thus will be able to swim around this circle FASTER than the monster can run around the shore.
The swan can keep swimming around this way, pulling further away each second, until finally it is on the opposite side of its inner circle from where the monster is on the shore. At this point, the swan aims directly toward the closest shore and begins swimming that way. At this point, the swan has to swim [0.75R feet + 1 millimeter] to get to shore. Meanwhile, the monster will have to run R*pi feet (half the circumference of the lake) to get to where the swan is headed.
The monster runs four times as fast as the swan, but you can see that it has more than four times as far to run:
[0.75R feet + 1 millimeter] * 4 < R*pi
[This math could actually be incorrect if R were very very small, but in that case we could just say the swan swam inward even less than a millimeter, and make the math work out correctly.]
Because the swan has less than a fourth of the distance to travel as the monster, it will reach the shore before the monster reaches where it is and successfully escape.
While mixing sand, gravel, and cement for the foundation of a house, a worker noticed a small bird hopping along the top of the foundation wall. The bird misjudged a hop and fell down one of the holes between the blocks. The bird was down too far for anyone to reach it and the hole was too small for it to fly out of. Someone suggested using two sticks to reach down into the hole and pull the bird out, but this idea was rejected for fear it would injure the fragile bird. What would be the easiest way to get the bird out of the hole without injuring it?
Since they had plenty of sand available, they could pour a little at a time into the hole. The bird would constantly keep shifting its position so that it stood on the rising sand.
It's 7:00 am. You are asleep and there is a sudden knock on the door.
Behind the door are your parents, who came to have breakfast.
In your fridge: bread, pasteurised milk, juice, and a jar of jam.
What will you open first?
Hussey has been caught stealing goats, and is brought into court for justice. The judge is his ex-wife Amy Hussey, who wants to show him some sympathy, but the law clearly calls for two shots to be taken at Hussey from close range.
To make things a little better for Hussey, Amy Hussey tells him she will place two bullets into a six-chambered revolver in successive order. She will spin the chamber, close it, and take one shot.
If Hussey is still alive, she will then either take another shot, or spin the chamber again before shooting. Hussey is a bit incredulous that his own ex-wife would carry out the punishment, and a bit sad that she was always such a rule follower.
He steels himself as Amy Hussey loads the chambers, spins the revolver, and pulls the trigger. Whew! It was blank. Then Amy Hussey asks, 'Do you want me to pull the trigger again, or should I spin the chamber a second time before pulling the trigger?'
What should Hussey choose?
Hussey should have Amy Hussey pull the trigger again without spinning.
We know that the first chamber Amy Hussey fired was one of the four empty chambers. Since the bullets were placed in consecutive order, one of the empty chambers is followed by a bullet, and the other three empty chambers are followed by another empty chamber. So if Hussey has Amy Hussey pull the trigger again, the probability that a bullet will be fired is 1/4.
If Amy Hussey spins the chamber again, the probability that she shoots Hussey would be 2/6, or 1/3, since there are two possible bullets that would be in firing position out of the six possible chambers that would be in position.
Emily was sitting at her study table, home alone, on a cold and stormy night. Her parents had taken a flight earlier in the morning to Australia as her grandmother had passed away. She had wanted to follow her parents but she had an important English examination the next day which she could not miss. The storm was getting heavier by the minute and the wind was howling outside. All this noise made it very hard for her to concentrate. She was on the verge of dozing off when she was shaken alert by a sudden "THUD!" She dismissed it as a window which had been slammed shut by the wind.
She tried to concentrate on her books when she heard faint footsteps. Emily got out of her room and looked around when suddenly, without warning, she was grabbed by the neck. She tried to scream but it came out as a mere whimper as the intruder was pressing hard against her throat with his arm. She tried to free herself from his grip but to no avail.
"Give me all your money!" growled the man who had grabbed her from behind.
"Th-there is none h-here! Please ll-let me go!" cried Emily.
"Don't LIE TO ME!" screamed the increasingly agitated man. She felt the man strengthen his grip around her neck. She said nothing and a few seconds passed by in silence. Suddenly the phone rang which alerted both of them.
"People will get suspicious if I don't answer the phone," said Emily, with a controlled voice. The intruder let her go.
"Alright, but NO funny business, or ELSE!" said the nervous intruder. Emily walked toward the phone. She took a deep breath and calmed herself. She picked up the phone. "Hey Em! How's the revision going?" said the caller.
"Hey Anna. Thanks for the call. Hey you know those Science notes I lent you last week? Well I really need them back. It would be a great help to me. It's an emergency, so if you could give me them tomorrow it would be great. Please hurry in finding the notes. I need to get back to my books now. Bye," Emily said. She hung up the phone.
"It was wise of you not to say anything," said the intruder, although he was more than a bit confused by her conversation.
"Now TELL ME WHERE THE MONEY IS KEPT!" screamed the thief.
"It...it's...in my dad's room. The first room on the right. Third drawer," said Emily. "SHOW me!" said the man, and removed his grip around her neck. She took a big gulp of air and nearly fell. She swallowed hard and said a silent prayer. She walked slowly, in silence, toward her father's room. All of a sudden, they heard police sirens. The intruder froze in his footsteps. He ran to the nearest window and jumped out of it. Emily ran outside in time to see the intruder being escorted into the car. She saw Anna and she ran toward her and hugged her.
"Smart kids," said the policeman.
What had happened?
Emily had used the mute button during her conversation with Anna so that all Anna heard was: "call...help...emergency...please hurry".
Anna, sensing something was wrong, called the police and told them Emily's address. The police were able to come to Emily's house in time to catch the perpetrator.
You have just purchased a small company called Company X. Company X has N employees, and everyone is either an engineer or a manager. You know for sure that there are more engineers than managers at the company.
Everyone at Company X knows everyone else's position, and you are able to ask any employee about the position of any other employee. For example, you could approach employee A and ask "Is employee B an engineer or a manager?" You can only direct your question to one employee at a time, and can only ask about one other employee at a time. You're allowed to ask the same employee multiple questions if you want.
Your goal is to find at least one engineer to solve a huge problem that has just hit the company's factory. The problem is so urgent that you only have time to ask N-1 total questions.
The major problem with questioning the employees, however, is that while the engineers will always tell you the truth about other employees' roles, the managers may lie to you if they like. You can assume that the managers will do their best to confuse you.
How can you find at least one engineer by asking at most N-1 questions?
You can find at least one engineer using the following process:
Put all of the employees in a conference room. If there happen to be an even number of employees, pick one at random and send him home for the day so that we start with an odd number of employees. Note that there will still be more engineers than managers after we send this employee home.
Then call them out one at a time in any order. You will be forming them into a line as follows:
If there is nobody currently in the line, put the employee you just called out in the line.
Otherwise, if there is anybody in the line, then we do the following. Let's call the employee currently at the front of the line Employee_Front, and call the employee who we just called out of the conference room Employee_Next.
So ask Employee_Front if Employee_Next is a manager or an engineer.
If Employee_Front says "manager", then send both Employee_Front and Employee_Next home for the day.
However, if Employee_Front says "engineer", then put Employee_Next at the front of the line.
Keep doing this until you've called everyone out of the conference room. Notice that at this point, you'll have asked N-1 or less questions (you asked at most one question each time you called an employee out except for the first employee, when you didn't ask a question, so that's at most N-1 questions).
When you're done calling everyone out of the conference room, the person at the front of the line is an engineer. So you've found your engineer!
But the real question: how does this work?
We can prove this works by showing a few things.
First, let's show that if there are any engineers in the line, then they must be in front of any managers.
We'll show this with a proof by contradiction. Assume that there is a manager in front of an engineer somewhere in the line. Then it must have been the case that at some point, that engineer was Employee_Front and that manager was Employee_Next. But then Employee_Front would have said "manager" (since he is an engineer and always tells the truth), and we would have sent them both home. This contradicts their being in the line at all, and thus we know that there can never be a manager in front of an engineer in the line.
So now we know that after the process is done, if there are any engineers in the line, then they will be at the front of the line. That means that all we have to prove now is that there will be at least one engineer in the line at the end of the process, and we'll know that there will be an engineer at the front.
So let's show that there will be at least one engineer in the line. To see why, consider what happens when we ask Employee_Front about Employee_Next, and Employee_Front says "manager". We know for sure that in this case, Employee_Front and Employee_Next are not both engineers, because if this were the case, then Employee_Front would have definitely says "engineer". Put another way, at least one of Employee_Front and Employee_Next is a manager. So by sending them both home, we know we are sending home at least one manager, and thus, we are keeping the balance in the remaining employees that there are more engineers than managers.
Thus, once the process is over, there will be more engineers than managers in the line (this is also sufficient to show that there will be at least one person in the line once the process is over). And so, there must be at least one engineer in the line.
Put altogether, we proved that at the end of the process, there will be at least one engineer in the line and that any engineers in the line must be in front of any managers, and so we know that the person at the front of the line will be an engineer.