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
Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.
You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:
A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.
The first thought most people have it to try to get each robot to go back and forth, centered on their original spot, each time going a little further out in each direction. This won't work.
Another insight is that since you don't know which robot will be on the left or right, it probably doesn't make sense to give them different programs.
The solution to this problem is to just have both robots move consistently in one direction, but not at full speed. Then, have either robot pick up to full speed when it sees oil again (which will only happen for one robot). This robot will eventually catch up to the other robot, causing a collision.Here is a working program, which you will give to both robots. Note that our "move_slowly" section is able to move slowly by moving an extra right and left space.
1 Move Right
2 Move Right
3 Move Left
4 Skip Next Instruction If On Oil
5 GOTO move_slowly
6 Move Right
7 GOTO move_quickly