6 Jan 10

Gold for 7 Days of Work

Question: You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)

Answer: The trick is not to try and how to cut in such a way to make 7 equal pieces but rather to make transactions with the worker. Make two cuts on the gold bar such that you have the following sizes of bars.

1/7, 2/7 and 4/7. For convenience sake, I would just refer to the bars as 1, 2 and 4.

At the end of Day 1: Give Bar 1 (You- 2 and 4, Worker- 1)

At the end of Day 2: Give Bar 2, Take back Bar 1 (You- 1 and 4, Worker- 2)

At the end of Day 3: Give Bar 1 (You- 4, Worker- 1 and 2)

At the end of Day 4: Give Bar 4, Take back Bar 1 and Bar 2 (You- 1 and 2, Worker- 4)

At the end of Day 5: Give Bar 1 (You- 2, Worker- 1 and 4)

At the end of Day 6: Give Bar 2, Take back Bar 1 (You- 1, Worker- 2 and 4)

At the end of Day 7: Give Bar 1 (You- Empty, Worker- 1, 2 and 4)

That should take care of everything.

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.

Get a free subscription to Oracle magazine published by Oracle Corp.
 Powered by Max Banner Ads 
8 Comments
Filed in Puzzles
  Posted by admin
Tagged , , , , , ,
5 Jan 10

Reverse the Order of Words in a String

Question: Reverse the order of words in a string in C using as little additional memory as possible.

Answer: The solution for this questions uses the solution of Reverse a String. I am going to make a small change to that solution by adding a length parameter. It will probably be better for you to read through that question before proceeding further with this one. Note that a space is being used to delimit the words in the sentence. Let’s look at an example before we dive into the code.

Original Sentence: My car is very fast

Modifies Sentence: fast very is car My

void reverseWords( char * str )
{
    int i = 0, j = 0;
    reverseString( str, strlen(str) ); // tsaf yrev si rac yM
    while( 1 ) // Loop forever
    {
        if( *(str+j) == ' ' || *(str+j) == '\0') // Found a word or reached the end of sentence
        {
            reverseString( str+i, j-i );
            i = j+1;
        }
        if( *(str+j) == '\0')
        {
            break;
        }
        j++;
    }
}
void reverseString(char* str, int len)
{
    int i, j;
    char temp;
    i=j=temp=0;

    j=len-1;
    for (i=0; i<j; i++, j--)
    {
        temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
}

I did not have time to test this a lot so if there are any mistakes, please let me know.

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.

4 Comments
Filed in String Manipulation
  Posted by admin
Tagged , , , ,
5 Jan 10

Reverse a String

Question: Reverse a string in C using as little additional memory as possible.

Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.

void reverseString(char* str)
{
    int i, j;
    char temp;
    i=j=temp=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
}

The second solution is slightly better than the first as it does not need the char space. It uses bitmanipulation (XOR in this case) to swap the chars in place.

void reverseStringBetter(char* str)
{
    int i, j;
    i=j=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        str[i] ^= str[j] ;
        str[j] ^= str[i] ;
        str[i] ^= str[j] ;
    }
}


Even though the second solution uses less space, the first one is probably a better solution in terms of readability and maintainability. The compilers are very advanced now and are able to reduce the swap instructions in the first solution into a single execution step. However, the same might not happen for the second solution so in real life situations, it is better to use the first solution although the second solution seems smarter and better theoretically.

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.

5 Comments
Filed in Bit Manipulation, String Manipulation
  Posted by admin
Tagged , , , , ,
4 Jan 10

Power of 2

Question: How do you find out if an unsigned integer is a power of 2?

Answer: The trick here is to know that an unsigned integer which is a power of 2 has only one of its bits as 1. So a simple solution would be to loop through the bits and count the number of 1s.

There is another solution which uses bit manipulation.

isPower = (x !=0 && !(x & (x-1)))

x & (x-1) will always give you a 0 if x is a power of 2. !(x & (x-1)) should give us what we want but there is one corner case. If x is 0, then the second term alone would return true when the answer should be false. We need the check to make sure x is not 0.

Most interviewers would be happy with the first solution. The second solution might be quite hard to come up with on the spot unless of course you are a genius or you have read the solution before.

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.

0 Comments
Filed in Bit Manipulation
  Posted by admin
Tagged , , , , ,

My Tech Interviews is powered by WordPress using theme Tribune