A friend of mine forwarded me this nice little problem he got asked in some interview.

Write code to reverse a string such that the words are reversed as in "We apologise for the inconvenience" becomes "inconvenience the for apologise We".

Obviously (is there fun otherwise?) the problem had to be solved for a memory constraint device (constant space).

I thought I'd share the solution as its kind of neat.

The solution is to do it in two passes. In the first pass the whole string is reversed and in the second each word is reversed again.

After reversing the whole string: "ecneinevnocni eht rof esigolopa eW"
Reversing word at a time:           "inconvenience eht rof esigolopa eW"
...
Finally:                                         "inconvenience the for apologise We"

A simple version of code (non-Unicode and considering only space as an word separator) doing this is as follows

// reverses text in between two pointers
void Reverse(char *c1, char *c2)
{
    while(c1 < c2) {
        char ch = *c1;
        *c1++ = *c2;
        *c2-- = ch;
    }
}



// reverses the complete string
void Reverse(char *str)
{
    if (!str) return;
    printf("'%s' ===> ", str);

    if(strlen(str) > 0) {
        // get the complete string reversed in pass 1
        Reverse(str, str + strlen(str) - 1);
        
        char *c1 = str, *c2 = str + 1;
        do {
            // find word boundary
            for(;*c2 != ' ' && *c2; c2++);


            // reverse each word
            Reverse(c1, c2 - 1);
            if (!*c2) break; // reached end of string
            c1 = ++c2;
        }while(*c2);
    }
    printf("'%s'\n", str);
    return;
}

Here's another problem which was given to me by Amit. I had lots of fun solving this :) 

Consider two link list as shown above which are joined at some point. The problem statement is as follows

"Given pointers to two single-linked list, find out if they are joined and at which node they are joined. Use constant space to solve this and assume that the nodes cannot be modified."

From the experience of the previous similar problem I posted let me first explain what is meant by constant space . Constant space means that the algorithm should use constant amount of space and its memory allocation should NOT increase as the length of the list increases. This means ironing out every byte allocation is a NOT a goal (constant space doesn't mean least amount of space). Just ensure that the allocation doesn't increase with the length.

Non-Solution 

The above two constrains rules out the two most common brute force algorithms that come to mind

1. Add another bool/bit field to the nodes and while traversing the list mark the node by setting this field. Check out while traveling in second pass through the other pointer whether any node has this field set which would give the common node. There are some possible optimization over this like traversing the two lists in parallel so that not all the nodes be touched in the first pass.
2. Create list/hash-tables of the nodes for look up later

My-Solution

I call this my solution because I'm sure there are better solutions to this :). This is O(n) solution.

The pseudo-code

1. Traverse the first list looking for the last node and compute the list's length (say len1)
2. Traverse the second list looking for the last node and compute it's length (say len2)
3. The last nodes of the two list has to be the same if they have joined anywhere in the middle. If not then the lists are not joined and hence return NULL
4. Find whichever is the longer list (using len1 and len2) and increment the root pointer of that list by abs(len1 - len2). This would ensure that both the pointers are equidistant from joined node.
5. Make another pass through the list by incrementing both the pointers and at every step ensure if they point to the same node. Since both are equidistant from the joined node (see step 4) this check will succeed and return the joined node.

The C++ code looks something as follows

// Data-structure for the node
typedef struct Node
{
    Node(int pVal) {
        val = pVal;
        p = NULL;
    }

    int val;
    Node *p;
} *PNODE;

PNODE GetJoinedNode(PNODE LL1, PNODE LL2)
{
    // handle null lists
    if(LL1 == NULL || LL2 == NULL) return NULL;

    PNODE t1 = LL1, t2 = LL2;
    int len1 = 1, len2 = 1;

    // Find first list's length and it's last node
    for(;t1->p != NULL; t1 = t1->p)
        ++len1;

    // find second list's length and it's last node
    for(;t2->p != NULL; t2 = t2->p)
        ++len2;

    // last node not same means no joins in the middle
    if (t1 != t2) return NULL;

    // Advance the longer list by the difference in length so that
    // the pointers are equidistant from the join
    PNODE* t = len1 > len2 ? &LL1 : &LL2;
    AdvanceBy(t, abs(len1 - len2));
    
    // last pass to find the join.
    for(;LL1 != LL2; LL1 = LL1->p, LL2 = LL2->p);

    return LL1;
}

void AdvanceBy(PNODE *pNode, int val) {
    for(int i = 0; i < val; ++i)
        (*pNode) = (*pNode)->p;
}

On an internal DL someone asked a question about how folks share enums between C++ and C# code when required (e.g. common error codes for a large project that use both native code and C#).

There was a very interesting answer given by one person. He simply asked why don't you define it in a .cs file and #include that file in your C++ code. I initially thought what the hell is he talking about and then it struck me that C++ and C# is not just similar but in some context they are exactly the same. Consider the following enum definition in a .cs files

// File Enum.cs
namespace EnumShare
{
    enum MyEnum
    {
        a = 1,
        b = 2,
        c = 3,
    };
}

This can be simply included in a C# project to be built normally. However, it can also be pulled into C++ code as follows

#include "..\EnumShare\Enum.cs"

using namespace EnumShare;

int Foo()
{
    cout << a << endl;

}

Note that I could directly pull in the C# code because the syntax matches that of C++ :)

I thought that this was a rather interesting usage.

I have always been a fan of dark UI-backgrounds, especially for code-editors. I used dark schemes like darkblue for gvim and custom dark color-scheme for VisualStudio. I always thought they are good for the eyes (less radiation) and saves power.

Looks like I'm no longer right in the days of LCD displays. Check out the details here. However, I did like the idea of http://www.blackle.com/.

If you follow other VSTS blogs, I'm sure you are already aware of the first ever CTP of Microsoft® Visual Studio® Team System code name “Rosario”. For me this is extra cool because this is the first VSTS CTP on which I've worked. As I had mentioned earlier I moved into VSTS team from my earlier TFS (Team Foundation Server) team over a year ago.

We have been working on a lot of cool stuff and you can see the first sneak preview in this CTP. You can download the VPC from here and learn more about it from the whitepaper here. You can also check out the overview of the release in Jeff Beehhler's blog.