Anagrams in an Array of Strings

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters.

Answer: The brute force solution would be to take each string and compare it to every other string in the array one character at a time ( O(n^4) solution, assuming there are n strings with maximum n characters each). This will surely give you the answer but almost certainly not the job unless you improve it. If you have no idea what the O(?) notation is, this might be a good time to read up on it (wikipedia).

Let’s use this example to improve on the solution {“abc”, “albert”, “cat”, “gate”, “cab”, “grow”, “act”}

One way we can quicken the string comparison process is by pre-sorting each string alphabetically (any sorting would be fine actually). Pre-sorting helps you avoid comparing each character in a string to each character in another string. You only need to compare every character to the character in the corresponding position of the other string. This reduces the order of the solution ( O(n^2 log n (sorting n strings with n characters each) + n^3 (n^2 comparisons of n characters each)) = O(n^3)) assuming the sorting algorithm is O(n log n)). However, this increases memory usage since you now need to store the original strings so you can print them out later.

After sorting the characters in the string, the array would look like this {“abc”, “abelrt”, “act”, “aegt”, “abc”, “gorw”, “act”}.

Currently, we are comparing each string with every other string. That seems inefficient. How about in addition to sorting the characters in each string, we sort each string in the array alphabetically (again any other sorting will do). Sorting the strings in the array means you do not have to compare each string to every other string, you only have to compare it to the next string in line. If they happen to be the same (i.e. found an anagram), then you can compare with the one after that. Whichever the case is, the order of comparison in this case will be of the order O(n) instead of O(n^2). This sorting will reduce the order to ( O(n^2 log n (sorting characters) + n^2 log n (sorting strings) + n^2 (n comparisons of n characters each)) = O(n^2 log n) assuming the sorting algorithm is O(n log n)). Make sure you also move the strings from the original array in order to maintain the mapping of the sorted array to the original array.

After sorting the strings, the array would look like {“abc”, “abc”, ”abelrt”, “act”, “act”, “aegt”, “gorw”}.

There is an alternate solution using hashing. You can first sort the characters in the string ( O(n log n) ) and then put each string in a hash table ( O(n) ). If the spot in the hash table is already taken, then that is an anagram. The order for this solution is ( O(n^2 log n (sorting n strings with n characters each) + n^2 (hashing n strings) + n (n insertions into hash table) = O(n^2 log n) assuming hashing each string is O(n) ).

As you can see, both the solutions have the same order of execution. Do you prefer one over the other? Why? Post as a comment.

As usual, if there is something wrong with this solution, feel free to ping me. Any improvements are always welcome. Cheers!

Pick a Random Byte

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.

Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?

Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.

When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.

Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.

Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.

If you have suggestions or comments, they are always welcome.

Like this post? Please Digg it or Stumble it.

C Keywords – Review

Static

Static keyword can be used for both variables and functions.

By default, functions and global variables defined in a file are available for use in other files. However, if the static keyword is used, they are restricted to the current file only. They will not be available in other files even if the extern keyword is used.

Local variables by default will be unavailable once the program leaves the scope in which it was defined. If the static keyword is used with a local variable, the local variable is preserved even when the program leaves the scope in which it was defined. This is commonly used to preserve local variable values between successive function calls. Static variables are initialized during compile time.

volatile

Volatile indicates that the variable can be changed in unpredictable ways. A volatile variable has to be retrieved from memory each time it is used rather using a copy if it is available in a register or cache.

int itr_rx; // Interrupt Address
...
while( !itr_rx ) {
    // Do something
}

In this case, if the optimization is turned on, the compiler will convert this to an infinite while loop since the value of itr_rx could not have changed due to the program flow. The compiler doesn’t know that the variable is an interrupt address so it will treat it like a normal variable. We don’t want that, do we?

volatile int itr_rx; // Interrupt Address
...
while( !itr_rx ) {
    // Do something
}

If the variable is declared as volatile, it will be reloaded from memory each time. It will not be optimized into an infinite while loop. It can be used for peripheral addresses and variables which are used to synchronize multiple threads.

const

const int a;

The value of a can not be changed. It will generate a compile error if you try to do it. However, there is a way you can change it but it is not recommended.

*(int *) &a = 123;
const int * b;

The address to which the pointer is pointing to can not be changed however the value in that address can be changed.

int * const b;

The value in the address, b is pointing to, can not be changed.

0 Comments

9 Minutes

Hourglass

Question: You are given two hourglasses. One measures 4 minutes and one measures 7 minutes. How would you measure exactly 9 minutes?

Answer: This question is similar to 4 Quarts of Water. With water, we were able to fill and pour out the pail multiple times. We can use the same logic and easily come up solutions which start measuring 9 minutes somewhere in the middle of the procedure but those will not be ideal. If possible, we want to measure the 9 minutes right from the start.

Step Time 4 minute timer 7 minute timer
1 0 min Start Start
2 4 mins Flip 3 minutes left
3 7 mins 1 minute left Flip
4 8 mins Stop Flip (1 minute left)
5 9 mins Stop

If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.

3 Comments

Singly Linked List – Delete Node

Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do?

We can easily get away by moving the data from the next node into the current node and then deleting the next node.  This solution has O(1) runtime. Here’s some code to illustrate this simple logic.

void deleteNode( Node * node )
{
    Node * temp = node->next;
    node->data = node->next->data;
    node->next = temp->next;
    free(temp);
}

Some things to consider. This method could pose potential problems. For instance, let’s consider we have a linked list A -> B -> C -> D and we are given a pointer to B to delete it. Theoretically, you would expect B to be deleted and all pointers which were pointing to B to become invalid. However, if we use this function to delete B, all pointers which were pointing to B will still be valid. Furthermore, node B now will contain the value C and node C will be invalid. Any previous pointers to C will become invalid, which may not be expected behavior in general. This is not a problem if there are no external links to any of the items in the linked list. But this would definitely be something you should consider asking your interviewer to show your thinking process.

Simple enough? Try more linked list questions.

If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.

Chess Squares

Question: How many squares are on a chess board?

Answer: If you thought the answer was 64, think again! How about all the squares that are formed by combining smaller squares on the chess board (2×2, 3×3, 4×4 squares and so on)?

A 1×1 square can be placed on the chess board in 8 horizontal and 8 vertical positions, thus making a total of 8 x 8 = 64 squares. Let’s consider a 2×2 square. There are 7 horizontal positions and 7 vertical positions in which a 2×2 square can be placed. Why? Because picking 2 adjacent squares from a total of 8 squares on a side can only be done in 7 ways. So we have 7 x 7 = 49 2×2 squares. Similarly, for the 3×3 squares, we have 6 x 6 = 36 possible squares. So here’s a break down.

1×1     8 x 8 = 64 squares
2×2     7 x 7 =  49 squares
3×3     6 x 6 = 36 squares
4×4     5 x 5 = 25 squares
5×5     4 x 4 = 16 squares
6×6     3 x 3 = 9 squares
7×7     2 x 2 = 4 squares
8×8     1×1 = 1 square

Total = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204 squares

2 Comments

6 Pirates Fight for 1 Gold Coin

Question: Six pirates discover a chest containing 1 gold coin. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 6, where Pirate 6 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, the most experienced pirate is thrown off the ship and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 6 devises a plan which he knows will keep him alive. What is his plan?

This question was taken from pirates revisited.

Solution: This question is a more complex version of “5 Pirates Fight for 100 Gold Coins”. If you have not read through question, please do so. I am going to explain this solution assuming you know the other solution.

If there is only one pirate, he takes the coin. If there are 2 pirates, pirate 2 takes the coin leaving pirate 1 with nothing.

If there are 3 pirates, pirate 3 needs one more vote. There is no way we can convince pirate 2 since he benefits if pirate 3 dies. Pirate 3 gives the gold coin to pirate 1 to get his vote so he survives.

If there are 4 pirates, pirate 4 needs one more vote. He can’t give it to pirate 1 since pirate 1 will get the gold coin even if pirate 4 dies. He can give it either to pirate 2 or 3 which will get him another vote to ensure his survival.

If there are 5 pirates, pirate 5 needs two more votes. There is no way he can get two more votes since there is only one gold coin to bribe with. Pirate 5 dies regardless of his proposal.

If there are 6 pirates, pirate 6 needs two more votes. He will surely get pirate 5′s vote since pirate 5 will die if pirate 6 dies. If pirate 6 and pirate 5 die, pirate 4 will survive but will not get the gold coin. Pirate 6 can bribe pirate 4 with the gold coin and get his vote. That makes a total of 3 votes allowing pirate 6 to survive. He can also give the gold coin to pirate 1, 2 or 3 although giving it to pirate 2 or 3 is a little confusing since either of them could get the gold coin in the case of 4 pirates.

If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it. VF6HD4EH987D

4 Comments

How Strong is an Egg?

Question: You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 –  20
15 –  20
16 –  21

So picking any one of the intervals with 19 maximum tries would be fine.

Update: Thanks to RiderOfGiraffes for this solution.

Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.

79 Comments

Reverse a Linked-List

Question: Reverse a Linked-list. Write code in C.

Answer: There are multiple ways to go about this. Let’s first look at a recursive solution.

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);

Now for a non-recursive solution.

Node * reverse( Node * ptr )
{
    Node * temp;
    Node * previous = NULL;
    while(ptr != NULL) {
        temp = ptr->next;
        ptr->next = previous;
        previous = ptr;
        ptr = temp;
    }
    return previous;
}

I personally prefer the non-recursive solution but it is always good to know both of them.

If anyone has any modifications or a better methods, please post it up. Comments are always welcome.

Boys and Girls

Question: In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same)

Answer: This is a very simple probability question in a software interview. This question might be a little old to be ever asked again but it is a good warm up.

Assume there are C number of couples so there would be C boys. The number of girls can be calculated by the following method.

Number of girls = 0*(Probability of 0 girls) + 1*(Probability of 1 girl) + 2*(Probability of 2 girls) + …
Number of girls = 0*(C*1/2) + 1*(C*1/2*1/2) + 2*(C*1/2*1/2*1/2) + …
Number of girls = 0 + C/4 + 2*C/8 + 3*C/16 + …
Number of girls = C
(using mathematical formulas; it becomes apparent if you just sum up the first 4-5 terms)

The proportion of boys to girls is 1 : 1.

Challenge yourself with more probability questions or interview puzzles.

If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.