Category Archives: Algorithm

Triangle Puzzle

Problem: By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

        5
      9   6
    4   6   8
  0   7   1   5

I.e. 5 + 9 + 6 + 7 = 27.
Write a program to find the maximum total from top to bottom by reading the triangle from text file. File would look like:

5
9 6
4 6 8
0 7 1 5

Solution: time complexity is O(n)
1. Read integers from file into an one-dimensional array.
2. From last level to second level and from leftmost integer to next-to-last integer in each level
3. Pick the larger one among current integer and its right neighbour, and add it up to the left adjacent integer on the row above.
4. Return array[0] (root) as maximum total

For above example:
Level 4: compare 0 and 7, add 7 to 4; compare 7 and 1, add 7 to 6; compare 1 and 5, add 5 to 8.
then level 3 would be: 11 13 13
Level 3: compare 11 and 13, add 13 to 9; compare 13 and 13, add 13 to 6.
then level 2 would be: 22 19
Level 2: compare 22 and 19, add 22 to 5.
then level 1 would be: 27
stop and return 27 as solution.

C/C++ code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    //assuming that we know there are 100 levels in the file
    long *array = (long long*)malloc(sizeof(long)*6000);
    
    FILE *file = fopen("triangle.txt","r");
    
    if (file == 0) {
        printf("cannot open\n");
    }
    int i = 0;
    
    while (EOF != fscanf(file, "%ld", &array[i])) {
        i++;
    }
    
    //assuming that we know there are 100 levels in the file
    for(int j = 99; j > 0; j--)
    {
        for (int k = 0; k < j; k++) {
            if(array[j*(j+1)/2+k] > array[j*(j+1)/2+k+1])
            {
                array[j*(j+1)/2+k - j] += array[j*(j+1)/2+k];
            }
            else
            {
                array[j*(j+1)/2+k - j] += array[j*(j+1)/2+k+1];
            }
        }
    }
    printf("%ld\n",array[0]);
    
    return 0;
}

Link: from yodle’s website http://www.yodlecareers.com/puzzles/triangle.html

Verify a binary tree is a binary search tree

Algorithm: In-order traversal the binary tree and examine that the visited node’s data are in sorted order, then the binary tree is BST.

Here is source code:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

struct node{
   int data;
   node* leftchild;
   node* rightchild;
   node(int d):data(d), leftchild(NULL),rightchild(NULL){}
};

bool isBST(node* ptr)
{
   static node* prv_node = new node(INT_MIN);
   
   if(ptr)
   {
      if(!isBST(ptr->leftchild)) return false;
      
      if(prv_node->data >= ptr->data) return false;
      
      prv_node = ptr;
      
      if(!isBST(ptr->rightchild)) return false;
   }
   
   return true;
} 

int main()
{
   /*input: a binary tree
               5
              / \
             3   6
            / \ 
           2   4
   */
   node* root = new node(1);
   root->leftchild = new node(3);
   root->rightchild = new node(6);
   root->leftchild->leftchild = new node(2);
   root->leftchild->rightchild = new node(4);

   if(isBST(root)) printf("is BST\n");
   else printf("not BST\n");
   
   /*output:
     is BST
   */
}

Root-to-leaf path sum equle to given number in tree

#include <stdlib.h>
#include <stdio.h>

struct node{
   int data;
   node* leftchild;
   node* rightchild;
   node(int d):data(d), leftchild(NULL),rightchild(NULL){}
};

void print_path(int* path, int length)
{
   int i;
   for( i = 0;i < length; i++)
   {
      printf("%d ", path[i]);
   }
   printf("\n");
}

int path_sum(int* path, int length)
{
   int i,sum = 0;
   for( i = 0;i < length; i++)
   {
      sum +=path[i];
   }
   return sum;
}

bool is_leaf(node* ptr)
{
   if(ptr->leftchild == NULL && ptr->rightchild == NULL)
   {
      return true;
   }
   else return false;
}

void match_path_sum(node* ptr,int* path,int length,int sum)
{
   if(NULL == ptr) return;
   
   path[length] = ptr->data;
   
   if(is_leaf(ptr) && path_sum(path, length + 1) == sum)
   {
      print_path(path, length + 1);
   }
   
   match_path_sum(ptr->leftchild, path, length + 1, sum);
   match_path_sum(ptr->rightchild, path, length + 1, sum);
   
}

int main()
{
   /*input: sum = 9
               3
              / \
             2   6
            / \ 
           5   4
   */
   node* root = new node(3);
   root->leftchild = new node(2);
   root->rightchild = new node(6);
   root->leftchild->leftchild = new node(5);
   root->leftchild->rightchild = new node(4);
   
   int* path = new int[100];
   
   match_path_sum(root, path, 0, 9);
   
   delete path;
   
   /*output:
     3 2 4
     3 6
   */
}

Reverse singly linked list: recursive and non-recursive

#include <stdlib.h>
#include <stdio.h>

struct node{
   int data;
   node* next;
   node(int a, node* b):data(a),next(b){}
};

class list{
   public:
      node* head;
      list():head(NULL){}
      list(int n){
         head = new node(0,NULL);
         node* prv = head;
         node* ptr = NULL;
         for(int i=1;i<n;i++)
         {
            ptr = new node(i,NULL);
            prv->next = ptr;
            prv = ptr;
         }
      }
      ~list(){
         node* ptr = head;
         while(ptr)
         {
            node* tmp = ptr;
            ptr = ptr->next;
            delete tmp;
         }
      }
      void printlist(){
         node* ptr = head;
         while(ptr)
         {
            printf("%d ", ptr->data);
            ptr = ptr->next;
         }
         printf("\n");
      } 
};

//non-recursive
void reverse(node* &head)
{
   node* prv = NULL;
   node* ptr = head;
   while(ptr)
   {
      node* tmp = ptr->next;
      ptr->next = prv;
      prv = ptr;
      ptr = tmp;
   }
   head = prv;
}

//recursive
node* r_reverse(node* ptr, node* prv)
{   
   if(ptr == NULL) return prv;
   node* tmp = ptr->next;
   ptr->next = prv;
   prv = ptr;
   return r_reverse(tmp, prv);
}

int main()
{
   list s(5);
   s.printlist();
   reverse(s.head);
   s.printlist();
   s.head = r_reverse(s.head,NULL);
   s.printlist();
   return 0;

   //output is:
   // 0 1 2 3 4
   // 4 3 2 1 0
   // 0 1 2 3 4
}

Reverse integer

Problem:

Reverse a signed integer.
For example, reverse 123 to 321, reverse -456 to -654, reverse -120 to -21

Solution(C/C++):

#include <stdio.h>

int reverse(int x) {
    int sign,rev;

    rev = 0;
    sign = (x > 0) ? 1:-1;

    x = x * sign;

    while(x > 0)
    {
        rev = rev * 10 + x % 10;
        x = x / 10;
    }

    return sign * rev;
}

int main()
{   
    printf("%d\n",reverse(-120));
    return 0;
}

Find “bing”

Problem:

Assuming that one string only contain chars ‘b’,’i’,’n’,’g’, please count the number of combinations of ‘bing’
For example, given string “iinbinbing” and the index of chars begins from 1, then there are 4 combinations:
(4,5,6,10) (4,5,9,10),(4,8,9,10) and (7,8,9,10).
The maximum length of string is 10000. Please return [count%(10^9+7)] because the result might be very large.

Solution(C/C++):

#include "stdio.h"
int howmany (char* s)
{
    int length = strlen(s);
    int i;
    long long num_b    = 0;
    long long num_bi   = 0;
    long long num_bin  = 0;
    long long num_bing = 0;

    for(i = 0; i &lt; length; i++ )
    {
        switch(s[i])
        {
            case 'b':
                num_b++;
                break;
            case 'i':
                num_bi += num_b;
                break;
            case 'n':
                num_bin += num_bi;
                break;
            case 'g':
                num_bing += num_bin;
                break;
        }
    }
    return num_bing%1000000007;
}
int main()
{
    printf("%d",howmany("iinbinbing"));
}