CareerCup

Very simple and clear solution. Get the root and do a DFS using adjacency list as tree data structure.

@oZZz and @Sunny

I didn't say its 2^n - 1 unique words only, i said that there are 2^n-1 subsets. Check my response below to @Epic_coder.

Thus the number of subsets is N = 2^n - 1.
Then the words count = N! + (N-1)! + (N-2)! + ... + 1
Then less the duplicates FF, EE, II, F, I, E
Total Number of Unique words = words count - 6

You are right we have to consider words whose length is less than 9. Thus this is a subset problem but the different subsets should be 2^n - 1 since an empty set is not considered a valid word.

Thus the number of subsets is N = 2^ - 1.
Then the words count = N! + (N-1)! + (N-2)! + ... + 1
Then less the duplicates FF, EE, II, F, I, E
unique words count = words count - 6

I seem to have misunderstood the question. Why would you consider F & F as distinct alphabets if "FFEICIENT" is valid word based on the problem statement. Also, the 9! didn't consider words whose length is less than 9. Thus, this could be (2^n - 1) as @Epic_coder mentioned. Check http://en.wikipedia.org/wiki/Combination#Number_of_k-combinations_for_all_k

CORRECTION:
2^n -1 subsets not unique words. check my response to @Epic_coder

I believe you did not solve the problem. How are you going to get the count on the last second/minute/hour?

Isn't this a simple permutation? So this means it's factorial of length of "EFFICIENT" = 9! = 362880

typedef struct _item {
     item* next;
     void* value;
} item;

void swapKthElem(linkedlist list, int k) {

    item* head = list->head;
    item* kElemFromHead = NULL;
    item* kElemFromTail = NULL;
    int i = k;
   
    // scan the list for the kth element from head and kth element from tail
    while(head!=NULL) {
       
          if( i-- == 0) {
                kElemFromHead = head;
                kElemFromTail = list->head;
          }
       
          if(kElemFromTail!=NULL) {
             kElemFromTail = kElemFromTail->next;
          }
    
          head = head->next;
    }

    // swap only if kth item from head and tail is not the same element
    if( kElemFromHead != NULL && kElemFromTail != NULL && kElemFromHead!=kElemFromTail ) {

          tmp = kElemFromHead->value;
          kElemFromHead->value = kElemFromTail->value; 
          kElemFromTail->value = tmp;

    }
    
}

Here's a simpler code

function item findElemFromTail(LinkedList list, int k) {
   item* p = list->head;   
   item* elem = NULL;
   int i = 0;
   while(p!=null) {
        if(i == k) {
           elem = p;
        }      
        if (item!=null) item = item->next;
        p = p->next;
        i++;
   }

   return elem;
}

This is O(N) and we are only scanning the linked list once.

Requires two scans to the list there is a better way.

function item findElemFromTail(LinkedList list, int k) {
   item* p = list->head;   
   item* elem = NULL;
   int k = ;
   int i = 0;
   while(p!=null) {
        if(i == k) {
           elem = p;
        }      
        if (item!=null) item = item->next;
        p = p->next;
        i++;
   }

   return elem;
}

This is O(N) and we are only scanning the linked list once.

Your equalTrees function already uses 2 stack objects. How is this answering the question?

I believe you can. If both Binary tree implementation is using an adjacency matrix then you can use iteration to traverse the tree. The matrix is NxN multi-dimensional array. So for a Binary Tree with 10 nodes you get a A[10][10] to represent the relationship of the nodes, all nodes with a value (say non-negative value) represents relationship from source node to target node. You also need an array which contains the values say V[N].

Note that my assumption here is the binary tree has already allocated the arrays as a representation of the trees and it node values. The problem we are trying to solve is if our comparison require additional space, and my answer is we don't need additional space as long as its represented this way as a tree. Of course you need the iteration variables.

So for example if you have an entry A[1][2] = 1 and A[1][3] = 1 then Node 1 has two children Node 2 and Node 3. Then lookup the values array say V[1], V[2] and V[3] for the values. Just compare these indexes on both the binary trees. If at least one is not equal then exit your iteration and the trees are not equal.

How are the counters reset if there are no request coming in for that specific second (assuming previously that specific second has a value but the counter value was 1 hour old)? This means there is a possibility that the counter values are incorrect depending on the timing of the requests coming in.

A self referential table would work.

1
/ \
2 3
/ \ \
4 5 6

Example Node Table
| ItemId | ParentId |
| 1 | NULL |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |

To select parent of node 2:
SELECT ParentId FROM Node WHERE ItemId = 2;
To select children of node 2:
SELECT ItemId FROM Node Where ParentId = 2;

Isn't it simpler to just store the timestamps of all requests from current time - hour up to current time in a queue?

You can create the a queue which contains all the timestamps as requests come in.
Then every time interval say every 1millisecond remove all the timestamps in the head which is 1 hour old.

All you have to do to get the count is is peek from the head of the queue up to last the time stamp which is current queue timestamp > current time - hour/minute/seconds.

Or alternatively just create a score array say int score[3] and update every millisecond by reading the queue as described above and update the counters.