print tree level by level

void LevelReverse(BSTreeNode *pRoot)
{
    if(NULL==pRoot)
        return;
    deque<BSTreeNode *> dataque;
    dataque.push_back(pRoot);
   
    while(deque.size())
    {
        BSTreeNode *node= dataque.front();
        dataque.pop_front();
        cout<<node->data<<" ";
       
        if(node->left)
            dataque.push_back(node->left);
        if(node->right)
            dataque.push_back(node->right);      
    }
}


void LevelReverselevel(BSTreeNode *pRoot)
{
    if(NULL==pRoot)
        return;
    deque<BSTreeNode *> dataque;
    dataque.push_back(pRoot);
    dataque.push_back(NULL);
   
    while(deque.size())
    {
        BSTreeNode *node= dataque.front();
        dataque.pop_front();
       
        if(node)
        {
            cout<<node->data<<" ";
            if(node->left)
                dataque.push_back(node->left);
            if(node->right)
                dataque.push_back(node->right);
        }
        else
        {
            dataque.push_back(NULL);
            cout<<endl;
        }    
             
    }
    cout<<endl;
}

tree depth and balance tree

int Gettreedepth(BinaryTreeNode *pNode)
{
    if(NULL ==pNode)
        return 0;
    if(pNode->left)
        int leftdepth = Gettreedepth(pNode->left);
    if(pNode->right)
        int rightdepth = Gettreedepth(pNode->right);
    return (leftdepth > rightdepth) ? (leftdepth+1) : (rightdepth+1);

}


bool IsBalanced(BinaryTreeNode *pRoot)
{
    if(NULL==pRoot)
        return true;
    if(pRoot->left)
        int ld = Gettreedepth(pRoot->left);
    if(pRoot->right)
        int rd = Gettreedepth(pRoot->right);

    if ((ld-rd)>1 || (ld-rd)< -1)
        return false;
    return (IsBalanced(pRoot->left) && IsBalanced(pRoot->right));

}

verifySquenceOfBST

bool verifySquenceOfBST(int squence[], int length)
{
     if(NULL==squence|| length < 1)
         return false;
     int rvalue = squence[length-1];
   
     for(int i=0;i<length;i++)
     {
         if(squence[i] > rvalue)
             break;
     }
   
     for(int j=i;j<length;j++)
     {
         if(squence[j]<rvalue)
             return false;    
     }
   
     bool left=ture;
     if(i>0)
         left = verifySquenceOfBST(squence, i);
     bool right=ture
     if(i<length-1)
         right = verifySquenceOfBST(squence+i;length-i-1);
   
     return (left&&right);

}

LongestPalindrome

int LongestPalindrome(const char *s, int n)
{
   if(NULL==s || n<1)
       return -1;
   int max=0;
   for(int i=0; i<n; i++)
   {
       for(int j=0; (i-j)>=0&&(i+j)<n;j++)
            if(s[i-j]!=s[i+j]) break;
       if(j*2+1 > max) max = j*2+1;
     
       for(int j=0; (i-j)>=0&&(i+j+1)<n;j++)//even number
            if(s[i-j]!=s[i+j+1]) break;
       if(j*2+2 > max) max = j*2+2;
     
   }
         
   return max;      
}

Very very tired interview

It took me one more hour to finish this interview to discuss the algorithm on phone,  I really feel tired, but another one is waiting tomorrow. It goes well now, hope tomorrow is also going well.

Fighting, fighting~~~~~~~~~~~~~~~~~~~~~~~~!!

phone interview with audible.com

It seems so bad for me in this interview, only talked about 20 minutes, then done. The interviewer asks some questions about java, which is my weak part. I think, he wants to know more about java from me, but for me, allmost c/c++. I need spend more time to review JAVA, DB, UNIX COMMAND, which seems very unfamiliar to me.


Move on, move on, prepare for next interview. I will get it. Fighting～～～！


Update: I passed the first interview and got the second phone interview chance, which is a big surprise to me.

Prepare, prepare, I will get it.

Fighting ～～～～

find all pairs sum to k

void findpairs(int a[], int k)
{
    int n = sizeof(a)/sizeof(a[0]);
    int small = 0;
    int big = n-1;
 
    while(small< big)
    {
        int sum = a[small]+a[big];
        if(sum == k)
        {
            cout<<"("<<small<<","<<big<<")"<<",";
        }
        else if(sum < k)
        {
           small++
        }
        else
        {
            big--;
        }
    }
}

Binary search tree mirror

BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{

   if(NULL == pRoot)
       return NULL;
   BSTreeNode *p = pRoot->left;
   pRoot->left= pRoot->right;
   pRoot->right = p;
 
   if(NULL != pRoot->left)
       Mirror_Solution1(pRoot->left);
   if(NULL != pRoot->right)
       Mirror_Solution1(pRoot->right);
   
}

LevelReverse

void LevelReverse(BSTreeNode *pRoot)
{
    if(NULL == pRoot)
        return;
    queue<BSTreeNode*> treequeue;
   
    treequeue.push(pRoot);
    treequeue.push(NULL);
   
    while(treequeue.size())
    {
        BSTreeNode *node = treequeue.front();
       
        treequeue.pop();
        if(node)
        {
            if(node->left)
                treequeue.push(node->left);
            if(node->right)
                treequeue.push(node->right);
            cout<<node->data<<' ';
        }
        else if(treequeue.size())
        {
            treequeue.push(NULL);
            cout<<endl;  
        }  
    }

}

Reverse List

ListNode* ReverseList(ListNode *pHead)
{
    if(NULL == pHead)
    {
        return NULL;
    }  
    ListNode *cur = pHead;
    ListNode *pre = NULL;
    ListNode *next = NULL;
   
    while(NULL != cur)
    {
        next = cur->next;
       
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    return pre;

}

FirstAppearOnce

char FirstAppearOnce(char *pStr)
{
  int htable[256];
  memset(htable, 0, 256);
 
  char *p = pStr;
 
  while(*p!='\0')
      htable[*p++]++;
  p=pstr;
 
  while(*p!='\0')
  {
     if(htable[*p]==1)
     {
         break;
     }
     else
     {
        p++;
     }
 
  }
  return *p;

}

LeftRotateString n

void reverse(char *pBegin, char *pEnd)
{
    if(NULL==pBegin || NULL == pEnd)
        return;
 
    while(pBegin<pEnd)
    {  
        char temp;
        temp = *pBegin;
        *pBegin =*pEnd;
        *pEnd = temp;
     
        pBegin++;
        pEnd--;
    }
}


void LeftRotateString(char *pSrc, unsigned n)
{
   char *pB1 = pSrc;
   char *pE1 = pSrc+n-1;
   char *pB2 = pSrc+n;
   char *pE2 = pSrc+strlen(pSrc)-1;
 
   reverse(pB1, pE1);
   reverse(pB2, pE2);
   reverse(pB1, PE2);
 }

DeleteSpecialChars

//search create a hash table ,ASII 256, int htable[256]


void DeleteSpecialChars(const char *pSrc, const char *pDel)
{
    if(NULL==pSrc || NULL == pDel)
            return;
           
    int htable[256];
    memset(htable, 0, 256);
   
    while(*pDel!='\0')
    {
        htable[*pDel]++;
        pDel++;
    }
   
    char *pSlow = pSrc;
    char *pFast = pSrc;
   
    while(pFast!='\0')
    {
        if(htable[*pFast]!=1)
        {
            pSlow = pFast;
            pSlow++;
        }
        pFast++;  
    }

    *pSlow='\0';
}

Transfer string to int type

Transfer string to int type

//need consider '+', '-' sign
//need consider overflow
//need consider illege characters

#include <iostream>
#include <limits>

using namespace std;

bool returnflag;

int StrToInt(const char *str)
{
    long long num = 0;
    if(NULL == str)
        returnflag = FALSE;
    if(NULL != str)
    {
       if(*str =='+' || *str=='-')
       {
           int minus=0;
           if(*str=='-')
               minus = 1;  
       }
     
      while(*str!='\0')
      {
           if(*str >= '0' && *str<='9')
           {
               num= num*10+*str-'0';
             
               if(num > numeric_limits<int>::max())
               {
                   break;
                   return 0;
               }
           }
           str++;  
       }
     
       if(*str=='\0')
       {
           returnflag = TRUE;
           if(minus)
               num = 0-num;
       }
               
    }
 
    return static_typecast<int>(num);
}