CareerCup

How to approach that if as the order you mentioned?

@Srishti
Please see comment from zprogd on June 19, 2012
the tree structure, just like that.
using no-recursive method to print it.

it works. Cool!

It works, I think.

child.leafPath(parentPath);

The algo you used is still recursive.

The implementation of solving the problem is a little complex.My idea is

1. according to L, permutation and concat all the strings, e.g.
L: "fooo", "barr", "wing" => L: A="fooo", B="barr", C="wing"
generate: (if the number of strings in L is m, words length is l, the time in this step is O(m!)
ABC = "fooobarrwing"
ACB = "fooowingbarr"
......
then generate "next array" for every string (which will be used to KMP find)
the time is O(m*l)

2. use KMP algo the search every string above in S. (the length of S is n)
kmp time complex is O(m*l + n)

so the whole time complex is O(m! + m*l + n)

C++ code,

// Find the nth non-repeating number given a streams of characters in the range of A-Z
    char FindnthNonRepeatNum(char *str, int k)
    {
        if (!str || 0 == k) return '\0';

        char *p = str;
        std::map<char, int> numMap;
        std::map<char, int>::iterator it;

        std::vector<char> numV; // use the vector to save the order of char occurance
        std::vector<char>::iterator itc;

        while (*p != '\0')
        {
            it = numMap.find(*p);

            if (numMap.end() != it)     // current char has been added to map;
            {
                (*it).second += 1;      // count > 1 mean, the number repeats.
            }
            else
            {
                numMap[*p] = 1;
                numV.push_back(*p);     // not found in map, so add it to vecotr.
            }

            ++p;
        }

        int kth = 0;
        for (itc = numV.begin(); itc != numV.end(); ++itc)
        {
            if (kth != k && 1 == numMap[*itc])  // the char only occur once
            {
                kth++;
                if (kth == k) break;
            }
        }

        if (k != kth)
            return '\0';
        else
            return (*itc);
    }

I think you should use min heap of size 100, NOT max heap.
1. add first 100 data into the heap
2. pick up a data and compare it with the top one of heap, if the data is greater than the top data of the heap, use it replace the top one and adjust the heap. if the data is less than the top data of heap, ignore it.

Sorry, miss the struct RLinkedNode

struct RLinkedNode
{
int data;
RLinkedNode* next;
RLinkedNode* random;
};

My idea is to divide the reverse work into 2 steps
1. reverse "next" node,
2. reverse "random" node

RLinkedNode* ReverseRLinkedNode(struct RLinkedNode* node)
{
    // pre->p->next

    if (!node) 
        return NULL;

    // Divide the reverse work into 2 steps

    // First step, reverse the linked list normally
    RLinkedNode* p = node->next;
    RLinkedNode* pre = node;
    pre->next = NULL;

    while(p)
    {
        RLinkedNode* n = p->next;
        p->next = pre;

        pre = p;
        p = n;
    }

    RLinkedNode* head = pre;

    // Second step, reverse random node
    
    // use a set to contain the nodes which have been accessed/reversed in "random"
    std::set<RLinkedNode*> accessNodes;

    p = head;    // get the head
    while(p)
    {
        // if random is null, 
        // or the current node has been accessed
        // then go to next node
        if (!p->random || accessNodes.find(p) != accessNodes.end())
        {
            p = p->next;
        } 
        else
        {
            // random != null, and the node has not been accessed.
            // reverse random node

            RLinkedNode* r = p->random;
            pre = p;
            pre->random = NULL; 

            // because pre->random is set to null, and (another node)->random may point to this node.
            // so don't add this node to accessNodes.
            // NOTE: and one of the condition is that there are no 2 nodes which will point to (random) the same node.

            while(r)
            {
                RLinkedNode* n = r->random;
                r->random = pre;

                pre = r;
                r = n;
                accessNodes.insert(r);
            }
        }
    }

    return head;
}

I found my issue.
first point to the first element of array
last point to the last element of array
the same array.

You code can't work. could you please take a look at it?
I always got an exception "invalid iterator range"