Cranky Old ManIt has been long since I posted something here. My only excuse has been that my thinking space has…View Post

Cranky Old Man

It has been long since I posted something here. My only excuse has been that my thinking space has…

View Post

Find missing numbers from a series

NumN:  1, 2, 3, 4, 5
Let's say 3 & 4 are missing  (x and y)
ListN : 1, 2, 5

x + y = 7   -- (1)  // SumOfNumN - SumOfListN
x^2 + y^2 = 25  -- (2) // (sumOf the squares in NumN) - (sumOf the squares in ListN) 

Substitute (1) in (2),

x^2 + (7 - x)^2 = 25

Roots: 3, 4 which are the missing numbers

Shuffle elements of an array : Knuth Shuffle Algorithm

Code :

#include<iostream>
using namespace std;
void Random_List(int n)
{ int a[10000];
	for(int i=1;i<=n;i++)
	{
		a[i] = i;
	}
	cout<<"randlist("<<n<<") :";
	for(int i=n;i>=1;i--)
	{
		int j = rand() % i + 1;
        int swap = a[j];
		a[j] = a[i];
		a[i] = swap;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<" "<<a[i];
	}
}

int main()
{ int n = 0;
	cout<<"n=";cin>>n;
	Random_List(n);	
	cout<<endl;
	return 0;
}

Program in C to read all the characters from standard input and output the reverse when the user presses enter key

Code :

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

struct node_t {
   int c;
   struct node_t *next;
};

struct node_t *create_node(char c) {
    struct node_t* node = (struct node_t*) malloc(sizeof(struct node_t));
    node->c = c;
    node->next = NULL;
    return node;
}

void print(struct node_t *head) {
   struct node_t *p = head;
   while (p != NULL) {
     printf("%c", p->c);
     p = p->next;
   }
   printf("\n");
}

int main() {
   int x;
   struct node_t *head = NULL;   
   struct node_t *node;
   while ( (x = getchar()) != 10 ) {
     node = create_node(x);
     node->next = head;
     head = node;
   }
   print(head);   
 
   return 0;
}

Tags: C

Binary Search tree operations : Insert, Search and Verify if BST or not

Code :

#include<iostream>
using namespace std;
/*
How to check if a binary tree is a binary search tree
*/

typedef struct node_s {
	int value;
	struct node_s *left;
	struct node_s *right;
}BSTNode, *BSTree;

int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
	if(!T) {
		*p = f;
		return 0;
	} else {
		if(T->value == value) {
			*p = T;
			return 1;
		} else if(value < T->value) {
			return tree_search(T->left, value, p, T);
		} else {
			return tree_search(T->right, value, p, T);
		}
	}
}

int tree_insert(BSTree *T, int value) {
	BSTNode *p = NULL;
	if(!tree_search(*T, value, &p, NULL)) {
		BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
		s->value = value;
		s->left = NULL;
		s->right = NULL;
		if(!(*T))
			*T = s;
		else if(value < p->value)
			p->left = s;
		else
			p->right = s;
		return 1;
	}
	return 0;
}

bool is_bst = true;
void check_tree_is_bst(BSTree T) {
	if(T) {
		check_tree_is_bst(T->left);
		if(T->left) {
			if(T->left->value > T->value) {
				is_bst = false;
				return;
			}
		}
		if(T->right) {
			if(T->right->value < T->value) {
				is_bst = false;
				return;
			}
		}
		check_tree_is_bst(T->right);
	}
}

int main(int argc, char *argv[]) {
	int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
	int len = sizeof(a) / sizeof(int);
	int i;
	BSTree T = NULL;
	for(i = 0; i < len; i++)
		tree_insert(&T, a[i]);
	check_tree_is_bst(T);
	if(is_bst)
		cout << "yes" << endl;
	else
		cout << "no" << endl;
	return 0;
}

Code for sprially traversing a 2-D matrix

#include <stdio.h>

#define N 5
#define M 3

int min(int a, int b)
{
    return a < b ? a : b;

}

void spiral(int mat[M][N])
{
    int n = N, d = +1, i = 0, j = -1;
    int s, segl = N + M - 1;
    for (s = 0; s < min(N, M); s++, d = -d, segl -= 2, n—) {
          int c, *ip = &j;
          for (c = 0; c < segl; c++) {
              if (c == n)
                    ip = &i;
              *ip += d;
              printf(“%3d”, mat[i][j]);
          }
    }

}

Max Subcontiguous Sub Sequence Sum Problem

Code :

maxsofar = 0
maxendinghere = 0
for i = [0, n)]    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

Consider 2 integer Arrays A and B. The elements in both arrays are arranged in ascending order. One of the arrays has exact sufficient space at the end to accommodate the other. Write a function to merge both arrays in ascending order and place it in the largest array.

 Code :

void mergeArray(int* arr1, int n1, int* arr2, int n2)
{
	int i, j, k;

	i = n1-1;
	j = n2-1;
	k = n1+n2-1;

	while(i>=0 && j>=0 && k >= 0)
	{
		if(arr1[i] >= arr2[j])
		{
			arr1[k] = arr1[i];
			--k; --i;
		}
		else
		{
			arr1[k] = arr2[j];
			--k; --j;
		}
	}
	while(i>=0)
	{
		arr1[k--] = arr1[i--];
	}
	while(j>=0)
	{
		arr1[k--] = arr2[i--];
	}
}

Reverse the string and reverse the words in it

Code :

main() 
{ 
char s[]=”my name is anthony”; 
revword(s); 
printf(“\nafter rev : %s”,s); 
return 0; 
}

void revword(char *str) 
{ 
         char *end,*x,*y,i; 
        for(end=str;*end;end++){} 
        /*reverse complete sentence */
        rev(str,end-1); 
        /*reverse word in the sentence */

        x=str;
y=str;
       while(x++<end) 
        { 

                   if(*x==” || *x==’/0’)
                  { 
                       rev(y,x-1); 
                       y=x+1; 
                  } 
        } 
}

void rev(char *r,char *l)
{ 
           char temp; 
           while(r<l) 
           { 
               temp=*r; 
               *r=*l; 
               *l=temp; 
                r++; 
                l—; 
          } 
}

Code to find the max array element which exists as a sum of two array elements

Code:
Sort the array using merg sort O(nlogn)

Search the Array : This one has the time complexity O(n3)

<script>
var arr=[“12”,”10”,”9”,”7”,”3”,”1”,”0”];
var arr=[“15”,”10”,”7”,”2”,”2”,”2”,”2”];
var maxSum=maxItemSum(arr);

function maxItemSum(a)
{
var len=a.length;
var i=0,j=0,k=0;
var flag=’notfound’;
  for(i=0;i<len-2;i++)
  {
     for(j=i+1;j<len-1;j++)
     {
       for(k=j+1;k<len;k++)
       {
          if(parseInt(a[i])==parseInt(a[j])+parseInt(a[k]))
           {
             document.write(a[i]+’equals’+a[j]+’plus’+a[k]+’<br/>’);
             flag=’found’;
             break;
           }
        }
        if(flag==’found’)
             break;
     }
     if(flag==’found’)
       break;
  }
}
</script>

A better Optimized version :

<script>
var arr=[“12”,”10”,”9”,”7”,”3”,”2”,”0”];
/*var arr=[“15”,”10”,”7”,”2”,”2”,”2”,”2”];*/
var maxSum=maxItemSum(arr);
document.write(maxSum);
function maxItemSum(a)
{
var lenF=a.length;
var i=0;
var j=0;
var flag=’notfound’;
  for(i=0;i<lenF;i++)
  {
     j=i+1;
     var len=a.length;
     while(j<(len-1) && flag==’notfound’)
     {
     
      if(parseInt(a[i])==parseInt(a[j])+parseInt(a[len-1]))
      {
        flag=’found’;
        break;
      }
      else if(parseInt(a[i])>parseInt(a[j])+ parseInt(a[len-1]))
      {
        len—;

      }
      else if(parseInt(a[i])<parseInt(a[j])+parseInt(a[len-1]))
      {
        j++;
      }
      if(flag==’found’)
      break;
     }
    if(flag!=’found’)
      return flag;
    else
    return a[i];
  }
}
</script>