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.