Permutations of a String 

void permutate( char[] str, int index )
{
    int i = 0;
    static lastChar = 0;
    if( index == strlen(str) )
    { // We have a permutation so print it
        printf(str);
        return;
    }
    // Permutate once without any swaps.
    permutate( str, index + 1 );
    lastChar = str[index];
    for( i = index + 1; i < strlen(str); i++ )
    {
        if( lastChar == str[i] ) {
            continue;
        } else {
            lastChar = str[i];
        }
        swap( str[index], str[i] ); // It doesn't matter how you swap.
        permutate( str, index + 1 );
        swap( str[index], str[i] );
    }
}

permutate( sort("Hello World"), 0 );

Comments

Post a Comment

Popular posts from this blog

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 functio...
Read more

Boxes of Money

Question:  You are given  b  boxes and  n  dollar bills. The money has to be sealed in the  b  boxes in a way such that without thereafter opening a box, you can give someone a requested whole amount of dollars from 0 to  n . How should  b  be related to  n  for this to happen? Answer:  Stumped? Let’s think of an example to approach this problem. Say we have $100. A good approach to distributing $100 would be the binary number system. So you’d have $1, $2, $4, $8, $16, $32 in the first six boxes. We can’t fill the next box with $64 dollars because we are only left with $37 dollars (from a total of $100). So we’d have to put $37 in the seventh box. To supply any requested amount, we’d have to use a combination of these boxes. To find out the restrictions on the values of b and n, we have to think of different scenarios. For instance, with a million dollars and just one box, we would never be able to dispense any req...
Read more

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. Theoretical...
Read more