Problem: Create a data structure and functions that can insert into the structure and then output the largest element and whether an element is a member
void insert (int elem, struct node * dataStruct) {...}
int largest (struct node * dataStruct) {...}
int isMember(int elem, struct node * dataStruct) {...}
Solution: At its core, this is a fairly straight-forward problem. We need to do three common operations in data structure: insert, determine membership and determine the largest value.
First, we need to figure out what data structure to use. Let's go through a few common ones and talk about the trade-offs, efficiency and maintenance required for each data structure.
One common data structure we could use is an array. This has the advantage of being fairly simple. We could just add elements to the end of the array. This would be an O(1) step. Then, we could lookup any element by iterating through the array O(n) and could determine the max value in O(1) time. Also, there is virtually no data structure overhead in this case.
Well, this is a possible solution. If we will do lots of inserts and very few lookups and largest calls -- and we just want something simple; maybe this could work.
But, there are a few possible optimizations. First, we could keep the list ordered. This has the advantage of making lookup an O(log n) operation, which is much faster, and making the largest function an O(1) time operation as we simply return the last element. The downside here is that insert takes much longer. We may frequently have to shift values in the array down to make room, so insert could be as long as an O(n) function, which seems pretty long to build up the data structure.
So, let's look another structure. How about a binary tree? Well, a tree has insertion in O(log n), but would occasionally have to be rebalanced, usually an O(n) operation. Lookup is O(log n), as is finding the max element (follow the right branch to the bottom). Also, there is the overhead of the pointers to maintain the tree structure. So, this could be a good solution if we were doing a good amount of lookups, insertions and finding the max value repeatedly.
Let's think about the ideal characteristics of this data structure. It would have constant time insert and constant time lookup and constant time max value.
Well, a hashtable could do the first two. We can create a hashtable that would allow us to insert and lookup in constant time, but getting the max value would normally be O(n).
But, does it have to be? What if simply modified the data structure to be a hashtable as well as a value representing the max value. During the insertion step, we could do a comparison to always track the max value. This would then make returning the max value an O(1) step (in theory -- we could to this addition to any data structure, but a hashtable is still fastest for lookup and insertion). There is some hashtable overhead, but this seems manageable given the efficiency of this structure.
So, the ideal data structure is a modified hashtable which tracks its max value during the insertion step. This makes all of the functions we need to implement constant time functions.
Tomorrow's problem is to implement these.
/* Please let me know if you find any bugs or alternative solutions. Thank you, Noah */
Thursday, March 22, 2012
Wednesday, March 21, 2012
Brainteaser: Turn a 6-sided dice into 5-sided dice
Problem: Use a fair, six-sided die to play a game requiring a five-sided die.
Solution: So, we're given one die as shown in the picture below.
Solution: So, we're given one die as shown in the picture below.
There is nothing terribly special about this die; it's the standard type that is used in casino board games, etc, and we can assume that it's a fair die for this problem (not shaved, weighted to bias a number, etc.).
Unfortunately, when we roll it, it give us numbers from 1-6, not 1-5 as the problem requires. What algorithm can we use that can allow us to generate random numbers?
Let's start by thinking about fairly obvious algorithms to transfer the range of numbers.
Some algorithms jump out immediately as fairly obvious. One thing we could do is half the numbers and round up. So, 1 and 2 could be 1. 3 and 4 could be 2. 5 and 6 could be 3. This would give us numbers from 1-3 in a fair way. Similarly, we can generate numbers from 1-2 by mapping numbers to range.
Unfortunately, there is no obvious way that we can map numbers and get to 5.
One other possibility is to roll multiple times. For example, if we did two rolls, we would get a range between 2 and 12, though not an even range. We could look at ways to divide the outputs of the dies (either the sum, or the sequence) and then slice it into fifths. Perhaps we could even roll more than once until we found a distribution that could be sliced into fifths. This could work, but the math very quickly gets tough and we end up with lots and lots of rolls.
Let's look again at the numbers that we can generate a range in so far:
2, 3 and 6.
Let's look at the 2, what does this mean:
Well, first, we generate this by assigning 1-3 to 1, and 4-6 to 2.
Seem familiar? This is essentially a bit generator where we can generate a random bit each time where the range 1-3 produces the bit 0, and 4-6 the bit 1.
Now, how can we use a bit generator to generate a random number between 1-5?
Well, if you have a background in cryptography, this is easy. If not, it's actually quite hard to see how this is helpful (though you can generate any range you want from this algorithm by making a big number and taking it % 5). There is an easier way though.
So, let's go back to the die. What else can we do when we roll it? We looked at assigning ranges and adding, but what else can you do? Do you need to use ever result of the die, or can you fairly ignore some?
How about ignoring a number? Why not the number 6?
And there is the answer. Roll the die like normal, and if you get a six, just re-roll. There's your range, 1-5.
This is a good example of a class of brainteaser problems that appear to be complicated math, and in fact can be solved like that, but are actually quite simple. When you get to seemingly really hard math, it's worth going back to your assumptions. Your interviewer will generally comment that you're on the right path or not as well, so you can read the cluse.
/* Please let me know if you find alternative solutions or bugs. Thanks, Noah */
Tuesday, March 20, 2012
Super Simple Reverse Sorting
Problem: Implement Reverse Super Simple Sort -- a sorting algorithm which works by repeatedly finding the largest remaining element and swapping that with its order in the array.
void reverseSuperSimpleSort(int a[]) {
...
}
Solution: Let's make sure that we understand this algorithm before we start implementing it.
So, assume we have a sample array with the numbers:
10 8 -5 20 9
To sort this array, we would start in the first position and find the biggest number, 20 in this case. We would then swap 20 with the first number 10, to get:
20 8 -5 10 9
We then move up our iterator and find the largest of the remaining four numbers. This is 10. Then, we swap 10 and 8 and get
20 10 -5 8 9
We continue in this way until we get:
20 10 9 8 -5
This is a very simple sorting algorithm, but let's implement it. We'll write a helper function first which can do the first part of this function -- find the index of the largest element in an array of a known size:
int indexOfLargest (int a[], int arraySize) {
int indexLargest, maxSoFar, i;
/*Check the error case */
if (arraySize <= 0) return ERROR;
/* initialize maxSoFar and its index to the first element */
maxSoFar = a[0];
indexLargest = 0;
for (i = 1; i < arraySize; i++) {
if (a[i] > maxSoFar) {
maxSoFar = a[i];
indexLargest = i;
}
}
return indexLargest;
}
/*Now, we can write the function which does the sorting */
void reverseSuperSimpleSort(int a[]) {
int i, swapIndex, temp;
for (i = 0; i < a.size -1; i++) {
swapIndex = indexOflargest(a + i * sizeof(int), a.size - i);
temp = a[i];
a[i] = a[i + swapIndex];
a[i + swapIndex] = temp;
}
}
That's it!
Let's check this on our original array. Go through the numbers, and yup, it works.
So, this is a correct solution. What is the run time?
Well, the first function, indexOfLargest(), iterates through the entire array that it is given. So this function goes: n + (n-1) + (n-1)...
This is an O(n^2) function. It's not a super fast sorting algorithm, but it's pretty simple and intuitive.
/* Please let me know if you find any bugs or alternative solutions. Thanks, Noah */
void reverseSuperSimpleSort(int a[]) {
...
}
Solution: Let's make sure that we understand this algorithm before we start implementing it.
So, assume we have a sample array with the numbers:
10 8 -5 20 9
To sort this array, we would start in the first position and find the biggest number, 20 in this case. We would then swap 20 with the first number 10, to get:
20 8 -5 10 9
We then move up our iterator and find the largest of the remaining four numbers. This is 10. Then, we swap 10 and 8 and get
20 10 -5 8 9
We continue in this way until we get:
20 10 9 8 -5
This is a very simple sorting algorithm, but let's implement it. We'll write a helper function first which can do the first part of this function -- find the index of the largest element in an array of a known size:
int indexOfLargest (int a[], int arraySize) {
int indexLargest, maxSoFar, i;
/*Check the error case */
if (arraySize <= 0) return ERROR;
/* initialize maxSoFar and its index to the first element */
maxSoFar = a[0];
indexLargest = 0;
for (i = 1; i < arraySize; i++) {
if (a[i] > maxSoFar) {
maxSoFar = a[i];
indexLargest = i;
}
}
return indexLargest;
}
/*Now, we can write the function which does the sorting */
void reverseSuperSimpleSort(int a[]) {
int i, swapIndex, temp;
for (i = 0; i < a.size -1; i++) {
swapIndex = indexOflargest(a + i * sizeof(int), a.size - i);
temp = a[i];
a[i] = a[i + swapIndex];
a[i + swapIndex] = temp;
}
}
That's it!
Let's check this on our original array. Go through the numbers, and yup, it works.
So, this is a correct solution. What is the run time?
Well, the first function, indexOfLargest(), iterates through the entire array that it is given. So this function goes: n + (n-1) + (n-1)...
This is an O(n^2) function. It's not a super fast sorting algorithm, but it's pretty simple and intuitive.
/* Please let me know if you find any bugs or alternative solutions. Thanks, Noah */
Monday, March 19, 2012
Pi. Yum.
Problem: Write a function that calculates π.
double calculatePi(void) {
...
}
Solution: The core of the problem is straight forward -- output a numerical value for π . And yes, you can't simply return a constant like many languages allow (that would be too easy, though it's worth mentioning this to the interviewer). Also, as π is irrational, we can only approximate it with a numerical value.
Instead, the interviewer will explain a way to do this using a Gregory-Leibniz series. This is a mathematical sum that calculates pi at infinity. The proof behind this is quite complicated (and truthfully, I don't understand it, but it works). This series is shown below which sums up to pi.
Also, this is a very slow converging function. At k=150, we only have two decimal points of precision, but well, we can go much further than this!
So, coding this up should be fairly straight-forward. If we choose a big k (say 20,000), we can get a nice value for π.
Let's also put the constraint on that we can't use a power. This is also not too bad, as the (-1)^k only determines parity, so we can use an if statement letting us know that if k is even, we should pe positive, else negative.
Putting this all together, we can code it up:
double calculatePi(void) {
int i;
double pi = 0;
for (i = 0; i < 20,000; i++){
/* determine parity */
if (i%2 == 0) /* even and positive */
pi += 4 / (2*i + 1);
else
pi -= 4 / (2*i +1);
}
return pi;
}
It's worth doing a few examples here (0, 1, 2) which yield (4/1) - (4/3) + (4/5) . . .
Pretty neat. Try this, and you'll notice that you can very nice value for pi.
Also, the run-time of this function is O(20,000), which is constant, and actually quite fast as the multiply by 2 is a very fast function.
There are some optimizations possible, but this is good.
This was written on pi day (3/14). So, happy pi day!
/* Please let me know if you find errors or alternate solutions. Thank you. Noah */
double calculatePi(void) {
...
}
Solution: The core of the problem is straight forward -- output a numerical value for π . And yes, you can't simply return a constant like many languages allow (that would be too easy, though it's worth mentioning this to the interviewer). Also, as π is irrational, we can only approximate it with a numerical value.
Instead, the interviewer will explain a way to do this using a Gregory-Leibniz series. This is a mathematical sum that calculates pi at infinity. The proof behind this is quite complicated (and truthfully, I don't understand it, but it works). This series is shown below which sums up to pi.
Also, this is a very slow converging function. At k=150, we only have two decimal points of precision, but well, we can go much further than this!
So, coding this up should be fairly straight-forward. If we choose a big k (say 20,000), we can get a nice value for π.
Let's also put the constraint on that we can't use a power. This is also not too bad, as the (-1)^k only determines parity, so we can use an if statement letting us know that if k is even, we should pe positive, else negative.
Putting this all together, we can code it up:
double calculatePi(void) {
int i;
double pi = 0;
for (i = 0; i < 20,000; i++){
/* determine parity */
if (i%2 == 0) /* even and positive */
pi += 4 / (2*i + 1);
else
pi -= 4 / (2*i +1);
}
return pi;
}
It's worth doing a few examples here (0, 1, 2) which yield (4/1) - (4/3) + (4/5) . . .
Pretty neat. Try this, and you'll notice that you can very nice value for pi.
Also, the run-time of this function is O(20,000), which is constant, and actually quite fast as the multiply by 2 is a very fast function.
There are some optimizations possible, but this is good.
This was written on pi day (3/14). So, happy pi day!
/* Please let me know if you find errors or alternate solutions. Thank you. Noah */
Friday, March 16, 2012
Brainteaser: The two paths
Problem: A traveler comes to a fork in the road. One path leads to the land of L, where people always lie, the other path to the land of T, where people always tell the truth. At the fork is a man, but the traveler does not know if the man is from L or T. We can ask him only one question.
What question should the traveler ask to ensure he gets to T?
Solution: Let's draw a picture, as this often helps find the solution.
Pic 1 shows the problem, where we have encountered a man from L or T and we are trying to find the correct path to T.
If the man is from L, he will always lie. If he is from T, he will always tell the truth. We have to determine a question, which will allow us to know which way to go, irrespective of whether he is from L or T.
It's better not to just start randomly guessing (unless you immediately see the solution), so let's try to think structurally about what we are trying to get out of the question:
1. The question must allow us to choose the correct path
2. The answer must be definitive
3. The answer must not depend on whether the person is from L or T. It must be definitive irrespective of the person's home.
Most obvious questions fail this test, e.g.,:
- Which path takes me to T? -- fails because we do no know from the answer where to go
- Which path takes me to L? --If we could get this answer, we could do the opposite, but again, fails
--Are you from L or T?-- They both say T in this answer, and we don't know where to go?
Let's think about a two question combination that could work. This is in fact trivial.
ny question that uniquely determines where the person is from, e.g.,:
What is 2+2? to determine if the person is from L or T, then
Which path goes to T?
Unfortunately, we don't have two questions (and we can't put both in one question). One thought here is to try to ask a question that reveals both the person and answers something about the path, like: What path is the best path? But again, this doesn't work either.
At this point, let's look at the two question combination? Is there anything that we don't need in there? Well, one thing is that we actually figured out too much -- we don't actually need to know what city the man is from.
So, with this insight, we simply need to know the right path, and we have essentially a true and a false. We can use these to cancel each other out.
For example, we can ask the man, "What path would the other person say goes to T?" Hence, each will give the path to F." Then, we can take the opposite.
There is nothing terribly tricky about this problem. The important thing is to be structured, not just start guessing and to try to glean insights of what is needed and not needed. Some people find truth tables helpful in this problem, but I never have.
Also, there are other questions, but they typically involve negating either with someone from 'your town' or 'the other town', e.g., "What path leads to your town (negating with yourself)?"
/* Please let me know if you find bugs or alternate solutions. Thx, Noah */
What question should the traveler ask to ensure he gets to T?
Solution: Let's draw a picture, as this often helps find the solution.
Pic 1 shows the problem, where we have encountered a man from L or T and we are trying to find the correct path to T.
If the man is from L, he will always lie. If he is from T, he will always tell the truth. We have to determine a question, which will allow us to know which way to go, irrespective of whether he is from L or T.
It's better not to just start randomly guessing (unless you immediately see the solution), so let's try to think structurally about what we are trying to get out of the question:
1. The question must allow us to choose the correct path
2. The answer must be definitive
3. The answer must not depend on whether the person is from L or T. It must be definitive irrespective of the person's home.
Most obvious questions fail this test, e.g.,:
- Which path takes me to T? -- fails because we do no know from the answer where to go
- Which path takes me to L? --If we could get this answer, we could do the opposite, but again, fails
--Are you from L or T?-- They both say T in this answer, and we don't know where to go?
Let's think about a two question combination that could work. This is in fact trivial.
ny question that uniquely determines where the person is from, e.g.,:
What is 2+2? to determine if the person is from L or T, then
Which path goes to T?
Unfortunately, we don't have two questions (and we can't put both in one question). One thought here is to try to ask a question that reveals both the person and answers something about the path, like: What path is the best path? But again, this doesn't work either.
At this point, let's look at the two question combination? Is there anything that we don't need in there? Well, one thing is that we actually figured out too much -- we don't actually need to know what city the man is from.
So, with this insight, we simply need to know the right path, and we have essentially a true and a false. We can use these to cancel each other out.
For example, we can ask the man, "What path would the other person say goes to T?" Hence, each will give the path to F." Then, we can take the opposite.
There is nothing terribly tricky about this problem. The important thing is to be structured, not just start guessing and to try to glean insights of what is needed and not needed. Some people find truth tables helpful in this problem, but I never have.
Also, there are other questions, but they typically involve negating either with someone from 'your town' or 'the other town', e.g., "What path leads to your town (negating with yourself)?"
/* Please let me know if you find bugs or alternate solutions. Thx, Noah */
Thursday, March 15, 2012
Why are manhole covers round?
Problem: Why are manhole covers round?
Solution: This is canonical with Microsoft, so it has to be asked. Also, I was asked this at a Microsoft interview, so it's real!
There are lots of reasons that probably pop into your head, but let's not start by just randomly pushing out answers. The place to start here is by examining, what is a manhole cover and what does it do?
Well, a manhole cover is a cover for an opening that provides a person access to an underground area (like a sewer or storm drain). It is used so that people, objects, water and such do not fall in -- and so it can be removed when someone needs access.
So, a manhole cover would need to meet the requirements of:
1. It is able to cover a manhole to prevent people/objects/water from entering
2. It can be removed to provide access
3. It is durable and strong as it may be outside and used aggressively (e.g., trucks may drive over it)
4. It can be manufactured and made easily
5. It should use the minimal amount of material needed to keep cost down
6. It should take up the least space possible as it likely intrusive aesthetically and functionally (e.g., different surface than a road)
Well, let's now design the product that meets this. Clearly, to meet the first requirement, it must be the same shape or bigger than the manhole. And, since we want to keep meet requirements 4, 5, and 6, it makes no sense to make it any shape other than the cover itself. So, manhole covers are round because they cover manholes which are round -- and this shape allows the cover to meet the requirements in the optimal manner.
There is a follow-up question here too -- why are most manholes round (thus creating their round covers). Again, to answer this question, you would look at the requirements of a manhole:
1. Allow a man to enter
2. Cheap/easy to manufacture and maintain
3. Of minimal required size as manhole creates constraints/weaknesses within their structure and are aesthetically ugly
4. Durable/strong
Many shapes could meet some of the requirements, but round is often optimal as a round pipe is cheap/easy to manufacture and maximizes volume for a given amount of material. Also, humans, with their arms in front as is often required to go down a latter -- fit well in a circular pipe.
So, manhole covers are round because it is the optimal shape to cover an optimally designed manhole.
The trick to this question is to realize that it is not a trick question, but a product design question at its core. A wrong answer to this is starting to spout out true, but unorganized answers, (e.g., the manhole pipe is round, it's a good shape, etc.). Questions like this are designed primarily to see if a candidate is organized, hard to fluster and able to think in a structured manner.
As an aside, not all manhole covers are round -- as sometimes the manhole cover is not round, usually due to constraints on the manhole. Also, the round shape of a manhole contrasts it with the triangular shape of electrical covers, allowing people to know that a triangle means electricity, even if color or words have faded.
/* Please let me know if you find any bugs or alternative solutions. Thank you, Noah */
Solution: This is canonical with Microsoft, so it has to be asked. Also, I was asked this at a Microsoft interview, so it's real!
There are lots of reasons that probably pop into your head, but let's not start by just randomly pushing out answers. The place to start here is by examining, what is a manhole cover and what does it do?
Well, a manhole cover is a cover for an opening that provides a person access to an underground area (like a sewer or storm drain). It is used so that people, objects, water and such do not fall in -- and so it can be removed when someone needs access.
So, a manhole cover would need to meet the requirements of:
1. It is able to cover a manhole to prevent people/objects/water from entering
2. It can be removed to provide access
3. It is durable and strong as it may be outside and used aggressively (e.g., trucks may drive over it)
4. It can be manufactured and made easily
5. It should use the minimal amount of material needed to keep cost down
6. It should take up the least space possible as it likely intrusive aesthetically and functionally (e.g., different surface than a road)
Well, let's now design the product that meets this. Clearly, to meet the first requirement, it must be the same shape or bigger than the manhole. And, since we want to keep meet requirements 4, 5, and 6, it makes no sense to make it any shape other than the cover itself. So, manhole covers are round because they cover manholes which are round -- and this shape allows the cover to meet the requirements in the optimal manner.
There is a follow-up question here too -- why are most manholes round (thus creating their round covers). Again, to answer this question, you would look at the requirements of a manhole:
1. Allow a man to enter
2. Cheap/easy to manufacture and maintain
3. Of minimal required size as manhole creates constraints/weaknesses within their structure and are aesthetically ugly
4. Durable/strong
Many shapes could meet some of the requirements, but round is often optimal as a round pipe is cheap/easy to manufacture and maximizes volume for a given amount of material. Also, humans, with their arms in front as is often required to go down a latter -- fit well in a circular pipe.
So, manhole covers are round because it is the optimal shape to cover an optimally designed manhole.
The trick to this question is to realize that it is not a trick question, but a product design question at its core. A wrong answer to this is starting to spout out true, but unorganized answers, (e.g., the manhole pipe is round, it's a good shape, etc.). Questions like this are designed primarily to see if a candidate is organized, hard to fluster and able to think in a structured manner.
As an aside, not all manhole covers are round -- as sometimes the manhole cover is not round, usually due to constraints on the manhole. Also, the round shape of a manhole contrasts it with the triangular shape of electrical covers, allowing people to know that a triangle means electricity, even if color or words have faded.
/* Please let me know if you find any bugs or alternative solutions. Thank you, Noah */
Wednesday, March 14, 2012
Ceasar Cipher
Problem: Implement a Caesar cipher to encrypt and decrypt a string
char * caesarEncrypt(char * a, int key) {
...
}
char * caesarDecrypt(char * a, int key) {
...
}
Solution: It's useful to know what a Caesar cipher is. It is one of the earliest ciphers where The contents of a character set are shifted by a certain amount to create cipher text.
For example, the string:
"cat in the hat" shifted with a key of 2 becomes: "ecv kp jcv"
Let's also assume that we'll use only the 128 characters in ASCII.
For the encrypt function, at its core this seems simple. We can simply increment each character by the key value. The only potential issue here is what do we do if we reach the end? In this case, we want to roll over, which we can do with the mod operator.
Let's also assume that we will make a copy of the string to return the cipher text. Putting this together, we get:
char * caesarEncrypt(char * a, int key) {
char * cipher;
int i;
cipher = strcpy(a);
if (cipher == null) return ERROR;
for (i = 0; i < cipher.length; i++) {
cipher[i] = (cipher[i] + key ) % 128;
}
return cipher;
}
Now, how to decrypt? Well, it would seem that we could do the same thing in reverse -- simply reduce the value of each element by the key. This almost works, but consider what happens when we go below 0. We get negative, which doesn't really make sense in this char set.
There are lots of ways that we can deal with this with if statement, by consider how we can do something similar to the increment. If we add 128 to each element and then take the % 128, we are guaranteed a positive number -- and it's elegant without lots of if statements.
Putting this together, we get:
char * caesarDecrypt(char * a, int key) {
char * plain;
int i;
plain = strcpy(a);
if (plain == null) return ERROR;
for (i = 0; i < plain.length; i++) {
plain[i] = (plain[i] - key + 128) % 128;
}
return plain;
}
This works too. The algorithmic run time of both is O(n) since we have to look at each element in the string once.
Well, is this a good cipher? Not at all! It's simple, which is about all that you can say for it. Julius Caesar supposedly used it in his private communications -- and it is well understood. Truthfully, it's probably better to use no cipher than this one, as this has the appearance of security, with truly none.
/* Please let me know if you find any errors or alternate solutions. Thank you, Noah */
char * caesarEncrypt(char * a, int key) {
...
}
char * caesarDecrypt(char * a, int key) {
...
}
Solution: It's useful to know what a Caesar cipher is. It is one of the earliest ciphers where The contents of a character set are shifted by a certain amount to create cipher text.
For example, the string:
"cat in the hat" shifted with a key of 2 becomes: "ecv kp jcv"
Let's also assume that we'll use only the 128 characters in ASCII.
For the encrypt function, at its core this seems simple. We can simply increment each character by the key value. The only potential issue here is what do we do if we reach the end? In this case, we want to roll over, which we can do with the mod operator.
Let's also assume that we will make a copy of the string to return the cipher text. Putting this together, we get:
char * caesarEncrypt(char * a, int key) {
char * cipher;
int i;
cipher = strcpy(a);
if (cipher == null) return ERROR;
for (i = 0; i < cipher.length; i++) {
cipher[i] = (cipher[i] + key ) % 128;
}
return cipher;
}
Now, how to decrypt? Well, it would seem that we could do the same thing in reverse -- simply reduce the value of each element by the key. This almost works, but consider what happens when we go below 0. We get negative, which doesn't really make sense in this char set.
There are lots of ways that we can deal with this with if statement, by consider how we can do something similar to the increment. If we add 128 to each element and then take the % 128, we are guaranteed a positive number -- and it's elegant without lots of if statements.
Putting this together, we get:
char * caesarDecrypt(char * a, int key) {
char * plain;
int i;
plain = strcpy(a);
if (plain == null) return ERROR;
for (i = 0; i < plain.length; i++) {
plain[i] = (plain[i] - key + 128) % 128;
}
return plain;
}
This works too. The algorithmic run time of both is O(n) since we have to look at each element in the string once.
Well, is this a good cipher? Not at all! It's simple, which is about all that you can say for it. Julius Caesar supposedly used it in his private communications -- and it is well understood. Truthfully, it's probably better to use no cipher than this one, as this has the appearance of security, with truly none.
/* Please let me know if you find any errors or alternate solutions. Thank you, Noah */
Tuesday, March 13, 2012
Max Sum
Problem: Write a function that returns the max sum of two numbers from an array of integers
int maxSumofTwoNums(int a[]){
...
}
Solution: Let's start off with a picture.
Pic 1 shows the array a. In this case, we can see that the correct answer 17, which we get when we add 9 and 8.
One initially obvious way to solve this is to add up all sums, and then output the largest one at the end. We can do this by starting to iterate with the first number, and then iterate through every other number and keep a biggestSum until we get to the end.
The code for this solution is:
int maxSumofTwoNums(int a[]){
int i, j, biggestSum;
/* Check the error case of needing at least two elements */
if (a.size < 2) return ERROR;
/* Initialize biggestSum */
biggestSum = a[0] + a[1];
for (i = 0; i < a.size; i++) {
for ( j = i+1; j < a.size; i++) {
if (a[i] + a[j] > biggestSum)
biggestSum = a[i] + a[j];
}
}
return biggestSum;
}
Let's check this with the sample array in pic 1. In this example, biggestSum is initialized to 4. It then increases to 17 quickly when the 9 and 8 are added, and no sum is bigger. Also, all possible sums are checked, so it works in this case. We have a correct solution.
Also, let's check error cases. We have checked when there are fewer than two elements, so we should be pretty set here. We have not checked when the sum is more than the int range, but let's address that later.
So now, what is the run time of this function? Well, we check n + (n-1) + (n-2)...2. This is an O(n^2) function. Can we do better?
At first, it appears potentially not. We need to check every sum, and this does it. We have essentially developed an NP solution and treated this problem as if it is NP hard (if this sentence does not make sense, just ignore it; NP and P are not necessary to solve this).
One other thought is to sort the array. This could be done in O(n log n) time -- and then you could return the sum of the first two elements. This is faster, but requires sorting (and you may not want to change the order).
However, look at the example array again. Try to see how you knew that 9 and 8 were the biggest number. Look at how this is determined intuitively.
You probably didn't add up all the sums and return the greatest, as above. When I did it, I saw that 9 and 8 were the biggest elements and summed them. This is a key insight. Essentially, this problem can be reduced to -- "find the two biggest elements in the array." And, finding each one of these elements is an O(n) solution, which can make the entire solution O(n).
Now, with this, write the code to:
1. Find the biggest element
2. Find the second largest element (handle the case of the largest repeated)
3. Return the sum
Let's also deal with our error case where the sum exceeds the int range by returning a long instead of an int.
long maxSumofTwoNums(int a[]){
int i, j;
int biggest, secondBiggest;
int bigPlace;
/* Check the error case of needing at least two elements */
if (a.size < 2) return ERROR;
/* Initialize biggest and secondBiggest and bigPlace */
biggestSum = a[0];
secondBiggest = a[0];
bigPlace = 0;
/* Find the biggest num */
for (i = 1; i < a.size; i++) {
if (a[i] > biggest)
biggest = a[i];
bigPlace = i;
}
}
/* make sure if the first elem is the biggest, second
* cannot be in that location */
if (bigPlace == 0) secondBiggest = a[1];
/* Find the second biggest num */
for (j = 0; j < a.size; j++) {
if (bigPlace != j && a[j] > secondBiggest)
secondBiggest = a[j];
}
}
return (biggest + secondBiggest);
}
This is an O(n) solution now as we iterate through the array a constant number of times (2x). We also have solved the error case of exceeding the int range.
This is a good example of where we were able to come up with a better solution by looking at how we intuitively solved a problem, and doing that, instead of thinking about the obvious way for a computer to solve the problem. And, we got a much better solution this way.
/* Please let me know if you find bugs, or there are alternative solutions. Thank you, Noah */
int maxSumofTwoNums(int a[]){
...
}
Solution: Let's start off with a picture.
Pic 1 shows the array a. In this case, we can see that the correct answer 17, which we get when we add 9 and 8.
One initially obvious way to solve this is to add up all sums, and then output the largest one at the end. We can do this by starting to iterate with the first number, and then iterate through every other number and keep a biggestSum until we get to the end.
The code for this solution is:
int maxSumofTwoNums(int a[]){
int i, j, biggestSum;
/* Check the error case of needing at least two elements */
if (a.size < 2) return ERROR;
/* Initialize biggestSum */
biggestSum = a[0] + a[1];
for (i = 0; i < a.size; i++) {
for ( j = i+1; j < a.size; i++) {
if (a[i] + a[j] > biggestSum)
biggestSum = a[i] + a[j];
}
}
return biggestSum;
}
Let's check this with the sample array in pic 1. In this example, biggestSum is initialized to 4. It then increases to 17 quickly when the 9 and 8 are added, and no sum is bigger. Also, all possible sums are checked, so it works in this case. We have a correct solution.
Also, let's check error cases. We have checked when there are fewer than two elements, so we should be pretty set here. We have not checked when the sum is more than the int range, but let's address that later.
So now, what is the run time of this function? Well, we check n + (n-1) + (n-2)...2. This is an O(n^2) function. Can we do better?
At first, it appears potentially not. We need to check every sum, and this does it. We have essentially developed an NP solution and treated this problem as if it is NP hard (if this sentence does not make sense, just ignore it; NP and P are not necessary to solve this).
One other thought is to sort the array. This could be done in O(n log n) time -- and then you could return the sum of the first two elements. This is faster, but requires sorting (and you may not want to change the order).
However, look at the example array again. Try to see how you knew that 9 and 8 were the biggest number. Look at how this is determined intuitively.
You probably didn't add up all the sums and return the greatest, as above. When I did it, I saw that 9 and 8 were the biggest elements and summed them. This is a key insight. Essentially, this problem can be reduced to -- "find the two biggest elements in the array." And, finding each one of these elements is an O(n) solution, which can make the entire solution O(n).
Now, with this, write the code to:
1. Find the biggest element
2. Find the second largest element (handle the case of the largest repeated)
3. Return the sum
Let's also deal with our error case where the sum exceeds the int range by returning a long instead of an int.
long maxSumofTwoNums(int a[]){
int i, j;
int biggest, secondBiggest;
int bigPlace;
/* Check the error case of needing at least two elements */
if (a.size < 2) return ERROR;
/* Initialize biggest and secondBiggest and bigPlace */
biggestSum = a[0];
secondBiggest = a[0];
bigPlace = 0;
/* Find the biggest num */
for (i = 1; i < a.size; i++) {
if (a[i] > biggest)
biggest = a[i];
bigPlace = i;
}
}
/* make sure if the first elem is the biggest, second
* cannot be in that location */
if (bigPlace == 0) secondBiggest = a[1];
/* Find the second biggest num */
for (j = 0; j < a.size; j++) {
if (bigPlace != j && a[j] > secondBiggest)
secondBiggest = a[j];
}
}
return (biggest + secondBiggest);
}
This is an O(n) solution now as we iterate through the array a constant number of times (2x). We also have solved the error case of exceeding the int range.
This is a good example of where we were able to come up with a better solution by looking at how we intuitively solved a problem, and doing that, instead of thinking about the obvious way for a computer to solve the problem. And, we got a much better solution this way.
/* Please let me know if you find bugs, or there are alternative solutions. Thank you, Noah */
Monday, March 12, 2012
An array, a binary search tree and a guy walk into a bar...
Problem: Write a function that determines if an element is in a binary search tree and an unordered array.
bool inBoth(int elem, int a[], struct node * root) {
...
}
Solution: This seems really simple at first. We can write a lookup for the array and a lookup for the binary search tree and call both. Let's do this to show that we can get a functional answer.
As algorithms, we can very simply iterate through the array, and follow the binary search tree to get the answer.
/* Implement standard lookup in an unordered array */
bool arrayLookup(int elem, int a[]){
int i;
for (i=0; i < a.length; i++) {
if (elem == a[i]) return (true);
}
return (false);
}
/* Implement standard lookup in a binary search tree */
bool bstLookup(int elem, struct node * root) {
/* Recursive base case of reaching null being false */
if (root == null) return (false);
/* True if our current node has the correct element */
if (root->value == elem) return (true);
/* Otherwise, follow the correct branch of the current node*/
if (root->value < elem)
return (bstLookup(elem, root->left));
else
return (bstLookup(elem, root->right));
}
/* Use the two functions to implement inBoth() */
bool inBoth(int elem, int a[], struct node * root) {
return (arrayLookup(elem, a) && bstLookup(elem, root));
}
What is the algorithmic run time of this function? The Array lookup checks every element, so it is O(n) and the bst lookup checks only one branch, which is O(log n). So, overall, this function is O(n).
Is this good?
It could be, but are there any very quick optimizations to make?
Look at the return line in inBoth.
What happens first and and what happens second? Well, arrayLookup is called, and then bstLookup is called. Since we know that arrayLookup is faster, one very simple optimiation is to change the order of the functions in that line so we do the bstLookup first. This could be a huge optimization if we rarely hit in either the bst or the array, so we do not have to frequently iterate through the entire array.
Also, if this function were rarely called and the binary search tree and the array were changing rapidly, it could make sense to implement the function like this.
But, let's now assume that the array does not change very much. How could the function become more efficient?
One likely solution is to sort the array. This could be done in O(n log n) and then any lookup could be in O(log n) time. So, by taking the overhead of one sort operation, we can then make lookup an O(log n) instead of O(n) function.
But, this comes with tradeoffs of: 1) sorting the array, and 2) needing to maintain the sorted array.
Another option is to use a different data structure. Lookup can be very fast with a hash table. So, one option is to create a hashtable, O(n) operation, which then looks up as O(1). This has the overhead of the memory and the maintenance of the hashtable, but this can reduce the worst case run-time of the function from O(n) to O(log n) -- with the constraint being the binary search tree.
It is also an option now to but the bst in a hash table, but this could be done easier -- since we already have a hash table. We can go through the bst and indicate on each element whether it already exists (and return true) or whether it does not already exist (and false).
This is also an O(n) operation. Once we create this lookup+boolean hash table, we can then in constant time do a lookup, and it only takes O(n) to build this structure, though it does take memory and overhead to maintain. Depending on likely uses, this could be a good choice.
This is an example of where in an interview it is important to first implement a clean solution, then look at easy implementations (like changing the order of the function calls) and then talk through even more optimizations and cases where they would make sense/not make sense.
/* Please let me know if you find any bugs or alternate solutions. Thank you, Noah */
bool inBoth(int elem, int a[], struct node * root) {
...
}
Solution: This seems really simple at first. We can write a lookup for the array and a lookup for the binary search tree and call both. Let's do this to show that we can get a functional answer.
As algorithms, we can very simply iterate through the array, and follow the binary search tree to get the answer.
/* Implement standard lookup in an unordered array */
bool arrayLookup(int elem, int a[]){
int i;
for (i=0; i < a.length; i++) {
if (elem == a[i]) return (true);
}
return (false);
}
/* Implement standard lookup in a binary search tree */
bool bstLookup(int elem, struct node * root) {
/* Recursive base case of reaching null being false */
if (root == null) return (false);
/* True if our current node has the correct element */
if (root->value == elem) return (true);
/* Otherwise, follow the correct branch of the current node*/
if (root->value < elem)
return (bstLookup(elem, root->left));
else
return (bstLookup(elem, root->right));
}
/* Use the two functions to implement inBoth() */
bool inBoth(int elem, int a[], struct node * root) {
return (arrayLookup(elem, a) && bstLookup(elem, root));
}
What is the algorithmic run time of this function? The Array lookup checks every element, so it is O(n) and the bst lookup checks only one branch, which is O(log n). So, overall, this function is O(n).
Is this good?
It could be, but are there any very quick optimizations to make?
Look at the return line in inBoth.
What happens first and and what happens second? Well, arrayLookup is called, and then bstLookup is called. Since we know that arrayLookup is faster, one very simple optimiation is to change the order of the functions in that line so we do the bstLookup first. This could be a huge optimization if we rarely hit in either the bst or the array, so we do not have to frequently iterate through the entire array.
Also, if this function were rarely called and the binary search tree and the array were changing rapidly, it could make sense to implement the function like this.
But, let's now assume that the array does not change very much. How could the function become more efficient?
One likely solution is to sort the array. This could be done in O(n log n) and then any lookup could be in O(log n) time. So, by taking the overhead of one sort operation, we can then make lookup an O(log n) instead of O(n) function.
But, this comes with tradeoffs of: 1) sorting the array, and 2) needing to maintain the sorted array.
Another option is to use a different data structure. Lookup can be very fast with a hash table. So, one option is to create a hashtable, O(n) operation, which then looks up as O(1). This has the overhead of the memory and the maintenance of the hashtable, but this can reduce the worst case run-time of the function from O(n) to O(log n) -- with the constraint being the binary search tree.
It is also an option now to but the bst in a hash table, but this could be done easier -- since we already have a hash table. We can go through the bst and indicate on each element whether it already exists (and return true) or whether it does not already exist (and false).
This is also an O(n) operation. Once we create this lookup+boolean hash table, we can then in constant time do a lookup, and it only takes O(n) to build this structure, though it does take memory and overhead to maintain. Depending on likely uses, this could be a good choice.
This is an example of where in an interview it is important to first implement a clean solution, then look at easy implementations (like changing the order of the function calls) and then talk through even more optimizations and cases where they would make sense/not make sense.
/* Please let me know if you find any bugs or alternate solutions. Thank you, Noah */
Friday, March 9, 2012
The expert arrow shooter (or not)
Problem: A prince comes across a barn with an arrow right in the middle of bull's-eye painted on the side. He asks who shot these arrows and a young boy comes forward and says he did from 100 paces and can repeat the outcome. He does and the prince walks away disgusted. What happened?
Solution: Let's start by thinking about the obvious answer. Let's say that the young archer hits the middle of bull's eye targets. It is highly unlikely the prince would be disgusted, so this probably isn't the solution.
Let's draw a picture, as this often helps of the scenario -- shown in pic 1.
You might add that the young archer insulted the prince or wore another prince's colors, etc., but this isn't a terribly likely scenario, and it isn't the answer.
Well, then, why would the prince be upset? It is hard to imagine a scenario where the archer walks back 100 paces and hits the bull's-eye and the prince gets disgusted. The prince would naturally be excited.
So, what could have happened? Let's assume that the boy 'cheated' somehow. How could he have cheated.
This actually reduces the question to, "How did the boy cheat?" which is an important reduction from the original problem, and not immediately obvious.
Well, let's think of some ways of cheating. He could have had someone else shoot -- but that is not shown in the question. He could have lied initially, but that is also not stated in the question.
Maybe he did something else like have a contraption with a string that steers the arrow to the target, but this too seems a bit far fetched.
Well, let's look at pic 1 (and the question) closer to see if anything comes to mind. Is anything odd about the picture? One thing that seems a little odd is the choice of a barn. The questions states that the arrows are "right in the middle of a bull's-eye painted on the side [of the barn.]"
This is an unusually specific scenario. It is not 'in the center of a target.' as we might expect. How can we use this information? Well, since it is the side of a barn, we know that the barn probably has a big size. And the target is specifically painted on it, which is also unusual.
Well, this starts to hint at the likely cheat. The target could have been painted at any time, even after the arrow is shot.
So, the answer become apparent -- the boy hits the side of the barn (an easy shot) and then paints the target around the arrow. Disgusting!
This is a good example of a problem which is pretty challenging because the answer involves thinking non-logically (painting the arrows after the shot), but it shows that the trick to brainteasers is often: 1) challenging assumption (e.g., target is painted first), 2) listening very closely to all information, even that which seems extraneous, and especially information which is a little odd or overly specific, and 3) pictures can help even in a question where it doesn't appear that it will.
/* Please let me know if there are any errors or alternative solutions. Thank you, Noah */
Solution: Let's start by thinking about the obvious answer. Let's say that the young archer hits the middle of bull's eye targets. It is highly unlikely the prince would be disgusted, so this probably isn't the solution.
Let's draw a picture, as this often helps of the scenario -- shown in pic 1.
You might add that the young archer insulted the prince or wore another prince's colors, etc., but this isn't a terribly likely scenario, and it isn't the answer.
Well, then, why would the prince be upset? It is hard to imagine a scenario where the archer walks back 100 paces and hits the bull's-eye and the prince gets disgusted. The prince would naturally be excited.
So, what could have happened? Let's assume that the boy 'cheated' somehow. How could he have cheated.
This actually reduces the question to, "How did the boy cheat?" which is an important reduction from the original problem, and not immediately obvious.
Well, let's think of some ways of cheating. He could have had someone else shoot -- but that is not shown in the question. He could have lied initially, but that is also not stated in the question.
Maybe he did something else like have a contraption with a string that steers the arrow to the target, but this too seems a bit far fetched.
Well, let's look at pic 1 (and the question) closer to see if anything comes to mind. Is anything odd about the picture? One thing that seems a little odd is the choice of a barn. The questions states that the arrows are "right in the middle of a bull's-eye painted on the side [of the barn.]"
This is an unusually specific scenario. It is not 'in the center of a target.' as we might expect. How can we use this information? Well, since it is the side of a barn, we know that the barn probably has a big size. And the target is specifically painted on it, which is also unusual.
Well, this starts to hint at the likely cheat. The target could have been painted at any time, even after the arrow is shot.
So, the answer become apparent -- the boy hits the side of the barn (an easy shot) and then paints the target around the arrow. Disgusting!
This is a good example of a problem which is pretty challenging because the answer involves thinking non-logically (painting the arrows after the shot), but it shows that the trick to brainteasers is often: 1) challenging assumption (e.g., target is painted first), 2) listening very closely to all information, even that which seems extraneous, and especially information which is a little odd or overly specific, and 3) pictures can help even in a question where it doesn't appear that it will.
/* Please let me know if there are any errors or alternative solutions. Thank you, Noah */
Thursday, March 8, 2012
Intersecting Line Segments (part 3)
Problem: Determine if two line segments, defined by their end points, intersect.
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
...
}
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
...
}
So, yesterday we had:
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
long m1, m2, b1, b2, xi, yi;
// Determine slopes
m1 = (end1->y - start1->y) / (end1->x - start1x);
m2 = (end2->y - start2->y) / (end2->x - start2x);
// If not parallel
if (m1 != m2) {
b1 = start1->y - (m1 * start1->x);
b2 = start2->y - (m2 * start2->x);
xi = (b2-b1)/(m1-m2);
yi = m1*xi + b1;
// Now we check if (xi, yi) is on segment 1
if (((start1->x <= xi && end1->y >= xi)&&
start1->y <= yi && end1->y >= yi))||
(start1->x >= xi && end1->y <= xi)&&
start1->y >= yi && end1->y <= yi))&&
//now we check if (xi, yi is on segment 2
((start2->x <= xi && end2->y >= xi)&&
start2->y <= yi && end2->y >= yi))||
(start2->x >= xi && end2->y <= xi)&&
start2->y >= yi && end2->y <= yi)))
return(true);
else
return (false);
} else { // if parallel
// We'll do this part tomorrow.
}
}
Now, let's finalize this to get the parallel part. First, if the two line segments are parallel, they must be the same line to intersect, which we can determine by checking the 'b' value as we did above. Then, if either end point (x or y) falls within the range of the other, they must intersect.
Coded, the full solution (minus the two caveats is):
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
long m1, m2, b1, b2, xi, yi;
// Determine slopes
m1 = (end1->y - start1->y) / (end1->x - start1x);
m2 = (end2->y - start2->y) / (end2->x - start2x);
// If not parallel
if (m1 != m2) {
b1 = start1->y - (m1 * start1->x);
b2 = start2->y - (m2 * start2->x);
xi = (b2-b1)/(m1-m2);
yi = m1*xi + b1;
// Now we check if (xi, yi) is on segment 1
if (((start1->x <= xi && end1->y >= xi)&&
start1->y <= yi && end1->y >= yi))||
(start1->x >= xi && end1->y <= xi)&&
start1->y >= yi && end1->y <= yi))&&
//now we check if (xi, yi is on segment 2
((start2->x <= xi && end2->y >= xi)&&
start2->y <= yi && end2->y >= yi))||
(start2->x >= xi && end2->y <= xi)&&
start2->y >= yi && end2->y <= yi)))
return(true);
else
return (false);
} else { // if parallel
// if the b values are not the same, cannot intersect
if (b1 != b2) return (false);
/* if they are the same, see if the x value of the
* first line segment falls inside that of the second */
return ((start1->x >= start2->x && start1->x <= end2->x)
|| (start1->x <= start2->x && start1->x >= end2->x));
}
}
Now, except for the two caveats of: 1) comparing longs, which should be done with epsilon comparison, and 2) not dividing by zero, we're in good shape. If you would like, add the error conditions -- and you always should in an interview.
In fact, this is an example of a particularly tricky problem. The first solution in part 1 did not get us anywhere and we had to start over -- which is fairly common in interviews. Then, when we figured out how to do the problem, the math was fairly involved. Coding turned out to be relatively simple, but long with many places to slip up. And, there are lots of error conditions to check too.
/* Please let me know if you find any bugs or have alternate solutions. Thank you, Noah */
Subscribe to:
Posts (Atom)