CareerCup

static void Main(string[] args)
        {
            int[] a = new int[26];
            int count = 0, min = 0, max=0;
            string s = "hello";
            for (int i = 0; i < 26; i++)
                a[i] = -1;
            for (int i = 0; i < s.Length; i++)
                if (a[s[i]-97] < min)
                {
                    a[s[i] - 97] = i;
                    count++;
                    if (count > max)
                        max = count;
                }
                else
                {
                    count -= a[s[i] - 97];
                    min = a[s[i] - 97] + 1;
                }
            Console.WriteLine(max);
            Console.ReadLine();
        }

Recursion is overkill. would have been better if you had used an array to memoize

int Sq(int n){
		int i=n, sq=0, count=1;
		if((i&1) == 1)
			sq += n;
		i >>= 1;
		while(i>0){
			if((i&1) == 1)
				sq += n<<count;
			i >>= 1;
			count++;
		}
		return sq;
	}

for convenience i took denominations as boolean array

Split(int amount, bool[] denominations){
  int[,] dp = new int[amount + 1, denominations.Length];
  for (int i = 0; i < denominations.Length; i++)
    dp[0, i] = 1;
  for (int i = 1; i <= amount; i++)
    for (int j = 1; j < denominations.Length; j++){
      dp[i, j] = dp[i, j - 1];
      if (denominations[j] && i>=j)
        dp[i, j] += dp[i - j, j];
    }
  return dp[amount, denominations.Length-1];
}

doesn't work

@Anonymous:I recommend u to draw a stack diagram for the remove method.It ll be big but its worth it

@Algoseeker:yes duplicates can be either in left subtree or right.but for instance during insertion if left or right is decided based on a random number for a duplicate then it ll be lil more complicated to remove.but it can also be done with a small modification to the method i gave above

heres de code

class Node{
  int data;
  Node left;
  Node right;
	
  Node(int data){
    this.data=data;
    left=null;
    right=null;
  }	
}
class BST{
  Node head;
  
  Node insert(Node node,int data){
    if(node==null)
      return new Node(data);
    if(data<=node.data)
      node.left=insert(node.left,data);
    else
      node.right=insert(node.right,data);
    return node;
  }
	
  public static void main(String args[]){
	new BST().go();
  }
  
  void go(){
    int[] a=new int[]{80,150,70,80,70,70,140,110,110};//test case
	for(int i:a)
	  head=insert(head,i); 
	inorder(head);
	remove(head,-1);//I need an element which cant be in the bst for a neat recursion so i use -1
	System.out.println();
	inorder(head);
  }
  
  void inorder(Node n){
    if(n==null)
	  return;
	inorder(n.left);
	System.out.print(n.data+" ");
	inorder(n.right);
  }
  
  boolean remove(Node n,int d){
    if(n==null)
      return false;
    if(remove(n.left,n.data))
      n.left=n.left.left;
    if(n.data==d)
      return true;
    if(remove(n.right,d))
      n.right=n.right.left;
    return false;
  }
}

ok...my code is based on 1 assumption. A duplicate is always in the left subtree.I mean all values of n.left subtree is <=n.data...Now u can observe that a duplicate can have no right child also if an element 'e' is not a duplicate then the duplicates of all the elements above 'e' will fall in the right subtree of 'e'...try to imagine my algorithm based on these observations...I will give u a working code in java in my following post

class count{
  int leaves;
  int nonleaves;
}

count go(node n){
  count c=new count();
  if(n==null)
    return c;
  if(n.left==null && n.right==null){
    c.leaves=1;
    return c;
  }
  count cl=go(n.left);
  count cr=go(n.right);
  c.leaves=cl.leaves+cr.leaves;
  c.nonleaves=cl.nonleaves+cr.nonleaves+1;
  return c;
}

ya...that sounds good...btw i read only the quote at first

Wow dint think so far!

@Tulley:R u sure what u did is correct?i dont think so...for instance how can leftHight - rightHight > 1 happen? cos return value is 0 for any subtree

boolean isBalanced(Node n){
  if(isBalancedHelp(n)==-1)
    return false;
  return true;
}
isBalancedHelp(Node n){
  if(n is null)
    return 0;
  left=isBalancedHelp(n.left);
  right=isBalancedHelp(n.right);
  if(left==-1 || right==-1)
    return -1;
  if(left-right>=-1 && left-right<=1)
    return 1+max(left,right);
  return -1;
}

my bad plz ignore above

Heres the approach
if i and j are the 2 numbers...count the number of continuous ones at the front and back of i and j...let them ifrnt,iback,jfrnt,jback...
if(iback+jfrnt)>(jback+ifrnt)
i should come before j
else
j should come before i

eg:12315,123--->123 is 1111011--->front=4,back=2
12315 is 11000000011011--->front=2,back=2...so 12315 should come before 123

@ Kishore:
Just a sample...what if i have a number in the list which has the maximum no: of digits an int can hold?I mean 31st bit of that number set to 1 if int size is 32 bits.

Kishore's claim is so obvious and shopno take a careful look at the question again..."Given an integer array...

dude...it meant any prime can be represented as 6n+1 or 6n-1 and not that any number which has this form is prime.Any way i think he made a mistake saying"So set all 6*n+(1|5) as a prime."

@blueskin:
how did u get the ans?did u jus work it out for 5 a complete cycle and concluded for any number?just curious...

Node temp=root,trash;
while(root){
  while(root.right!=null)
    temp=root.right;
  if(root==temp){
    trash=root;
    root=root.left;
    temp=root;
    free(trash);
    continue;
  }
  temp.right=root.left;
  trash=root;
  root=root.right;  
  free(trash)
}

U can do it with single array...Call Perm(a,0).a has the integers 1 to n

Perm(int[] a,int start){
  if(start==a.length){
    Print a
    return;
  }
  int temp;
  for(int i=start;i<a.length;i++){
    swap(a[start],a[i])
    Perm(a,start+1)
    swap(a[start],a[i])
  }
}

for(int start=0;start<st.length;start++){
  prev=start;next=start
  while(prev>=0 && next<st.length && st[prev]==st[next])
        prev--;next++
  if(found string > Max)
      //save string
  if(start<st.length-1)
    if(st[start]==st[start+1]){
      prev=start-1;next=start+2
      while(prev>=0 && next<st.length && st[prev]==st[next])
        prev--;next++
      if(found string > Max)
        //save string
    }  
}

doesnt work with ur own eg..put k=2..b[6] shud be 3 but 5 in ur eg

@Anonymous
The internal nodes automatically get 3 children.This way the leaves are already inserted when 'i' is encountered.Try the test case by urself it should work.

@XYZ:
If a given array is random.The probability of what u saying is 1/n! do u think it is really worth to maintain the 2nd and 3rd maxs coz they wud be of no use if 1st max is defeated...

N=new Node();
Construct(N,0);
Construct(Node n,int i){
	if(a[i]=='i')
		n.left=new Node();n.middle=new Node();n.right=new Node();
		return Construct(n.right,(Construct(n.middle,Construct(n.left,i+1)));
	else
		return i+1;
}

@asetech:What r u doing?if u r trying to find max of 3 try this
a>b?(a>c?a:c):(b>c?b:c)

this is good
but there shud be i--, before while loop and it shud be while(i>=0) isn't it?

if ur more concerned abt no: ifs in while loop use below

void go(){
  int start=0,end=k-1,k;//k is input
  start=findMax(start,end);
  System.out.println(a[start]+" ");
  end++;
  while(end<a.length){
    if(end-start==k){
      start=findMax(start+1,end);
      System.out.println(a[start]+" ");
      end++;
    }
    else if(a[start]>a[end]){
      System.out.println(a[start]+" ");	
      end++;
    }
    else{
      System.out.println(a[end]+" ");
      start=end;
      end++;
    }
  }
}

this is the best i can come up with.

go(){
  int start=0,end=k-1,k;//k is de input
  while(end<a.length){
    if(end-start==k-1){
      start=findMax(start,end);
      System.out.println(a[start]+" ");
      end++;
    }
    else if(end-start==k)
      start++;
    else if(a[start]>a[end]){
      System.out.println(a[start]+" ");	
      end++;
    }
    else{
      System.out.println(a[end]+" ");
      start=end;
      end++;
    }
  }
}
int findMax(int start,int end){
  int max=start++;
  for(;start<=end;start++)
    if(a[start]>a[max])
      max=start;
  return max;
}

What u mean by 'each stage'?can u explain a bit more?