How to find if two words are anagrams.

The first soln comes to head is sorting them and checking if they are equal.
Takes O(N log N ) complexity.


To make it work in O(N) I know two procedures,
1, Assign a prime number to each & every char. Multiply the prime numbers.
if result is same for both, then they are anagrams. But if the length is more then it overflows.

2, create a char array. For the first string
for(i = 1 to N )
do
char_array[a[i]]++;
for sencond array
for(i = 1 to N )
do
char_array[b[i]]--;
Now check if entire array is zeroes. If yes, those are anagrams.

iterative algorithm for pre-order traversal

This is done by an algormthm called Morris traversal.

void MorrisTraversal(struct Node *root)
 {  struct Node *p,*pre;

 if(root==0) { return; }

 for(p=root;p!=0;)
  {
  if(p->Left==0) { printf(" %d ",p->Data); p=p->Right; continue; }

  for(pre=p->Left;pre->Right!=0 && pre->Right!=p;pre=pre->Right) { }

  if(pre->Right==0)
   { pre->Right=p; p=p->Left; continue; }
  else
   { pre->Right=0; printf(" %d ",p->Data); p=p->Right; continue; }

  
  }
 }

}

Finding next element in inorder traversal of BST

A binary search tree is implemented using an array. You are given the index 'i' of the array. You need to find out the next element after array[i] in the inorder traversal
of BST in O(1).
Suppose the BST is
20
/ \
10 30
/ \ / \
5 15 25 35

Array is 20 10 30 5 15 25 35

Biggest sum subsequence in an array

Given an array of integers. Find the biggest sum subsequence.
For example: a={2, -9, 4,6, 3, -2, 5, 5, -10}
Largest subsequence is 4, 6, 3, -2, 5, 5.

Soln:
http://en.wikipedia.org/wiki/Kadane%27s_Algorithm
WIth this you get where the larges sum ends.
Find the starting point as well.

Nth largest number in the BST

Find the Nth largest number in the binary search tree?

Suppose there are seven elements in the BST as shown below.

    23

   / \

  15 30

 / \ / \

7 18 27 33

Then 5th largest element is 18.