Labels

Sunday, September 12, 2010

2 Egg Problem

Q.

* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

ANS:


The maximum drops is 14.
take it as n(n+1)/2 is just greater than or equal to 100.so n=14.
Algo:
i=14,j=13
1.drop the egg from ith floor
if egg breaks then
drop egg from (i-j)th floor and then go one floor up and keep droping(until req floor is found)
else
i=i+j
j--
if(j>=1)
goto step 1.



EXPLANATION:

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Saturday, August 21, 2010

Reverse string by words in c

That is, given a sentence like this


Sachin is a good boy


The in place reverse would be


boy good a is Sachin



Method1

First reverse the whole string and then individually reverse the words


Sachin is a good boy
<------------->

yob doog a si nihcaS
<-> <--> <-> <-> <->

boy good a is Sachin



Here is some C code to do the same ....


/*
Algorithm..

1. Reverse whole sentence first.
2. Reverse each word individually.

All the reversing happens in-place.
*/

#include

void rev(char *l, char *r);


int main(int argc, char *argv[])
{
char buf[] = "the world will go on forever";
char *end, *x, *y;

// Reverse the whole sentence first..
for(end=buf; *end; end++);
rev(buf,end-1);


// Now swap each word within sentence...
x = buf-1;
y = buf;

while(x++ <>
{
if(*x == '\0' || *x == ' ')
{
rev(y,x-1);
y = x+1;
}
}

// Now print the final string....
printf("%s\n",buf);

return(0);
}


// Function to reverse a string in place...
void rev(char *l,char *r)
{
char t;
while(l <>
{
t = *l;
*l++ = *r;
*r-- = t;
}
}





Method2
Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------


Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.


Method3

Create a linked list like



| I | -> | <> | -> | am | -> | <> | -> | a | -> | <> | -> | good | -> | <> | -> | boy | -> | NULL |



Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.

#include "stdio"
#include "stdlib"

#include "string"

/* reverse a string in place, return str */
static char* reverse(char* str)
{
char* left = str;
char* right = left + strlen(str) - 1;
char tmp;
while (left < style="color: rgb(0, 51, 0);"> tmp = *left;
*left++ = *right;
*right-- = tmp;
}
return str;
}

static int reverseWords(
const char* instr, /* in: string of words */
char* outstr) /* out: reversed words */
/* (caller must ensure big enough) */
{int k;
char* p;
char* buf;
*outstr = '\0';
if ((buf = (char*)malloc(strlen(instr)+1)) == NULL) {
fprintf(stderr, "oops, out of memory\n");
return -1;
}
strcpy(buf, instr);
reverse(buf);
if ((p = strtok(buf, " \t")) == NULL) {
free(buf);
return 0;
}

strcpy(outstr, reverse(p));
outstr += strlen(p);
while ((p = strtok(NULL, " \t")) != NULL) {
*outstr++ = ' ';

strcpy(outstr, reverse(p));
outstr += strlen(p);
}
free(buf);
return 0;
}

int main()
{
char instr[256];
char outstr[256];
printf("\n enter a string:");
gets(instr);
reverseWords(instr, outstr);
printf("in='%s' out='%s'\n", instr, outstr);
return 0;
}





:::::::::::::::::::::::::::::::::::::::
#include"stdio.h"

/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);

/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */

/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */

/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}

/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end )
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}

/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}

Saturday, August 7, 2010

binary tree in c

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
Node *current = this->root;

while ( current != NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}

return false;
}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.

Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like

static Node* Leaf;

bool BinaryTree::Search (int data )
{
Node *current = this->root;

Leaf->data = data;

while ( current->data != lead->data )
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}

return (current != Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.

Saturday, July 24, 2010

Reverse a single linked list using single pointer iteratively and recursively

(Recursive)
struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;

if ( head == NULL)
return NULL;
if ( head->next == NULL )
return head;

temp = reverse_ll ( head->next );
head->next -> next = head;
head->next = NULL;
return temp;
}

int main()
{
...
head = reverse_ll(head);
...
}
____________________________________________________________________
(Iterative)

#define pointer_swap( a, b) ((int)(a))^=((int)(b))^=((int)(a))^=((int)(b))

struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;
if (head && head->next) {
temp = head->next;
head->next = NULL;
} else {
return head;
}
while (temp->next) {
pointer_swap(head, temp->next);
pointer_swap(head,temp);
}
temp->next = head;
//head = temp;
return temp;
}
____________________________________________________________________



. Minimized version of my code.
#define pointer_swap(a,b) ((int)(a)) ^= ((int)(b)) ^= ((int)(a)) ^= ((int)(b))

struct list * reverse_ll(struct list * head)
{
struct list * temp = NULL;

while(head) {
pointer_swap(temp,head->next);
pointer_swap(temp,head);
}
return temp;
}

Friday, July 16, 2010

Find the two repeating elements in a given array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Method 1 (Basic)
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.

This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.

#include
#include
void printRepeating(int arr[], int size)
{
int i, j;
printf(" Repeating elements are ");
for(i = 0; i <>
for(j = i+1; j <>
if(arr[i] == arr[j])
printf(" %d ", arr[i]);
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method 2 (Use Count array)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.

This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.

#include
#include
void printRepeating(int arr[], int size)
{
int *count = (int *)calloc(sizeof(int), (size - 2));
int i;
printf(" Repeating elements are ");
for(i = 0; i <>
{
if(count[arr[i]] == 1)
printf(" %d ", arr[i]);
else
count[arr[i]]++;
}
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 (Make two equations)
We have to find two numbers, so to unknowns. We know the sum of n numbers is n(n+1)/2 and product is n!. Make two equations using these sum and product formulas, and get values of two unknowns using the two equations.

Let summation of all numbers in array be S and product be P

Let the numbers which are being repeated are X and Y.

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6

XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2
X + Y = 6
X – Y = 2

Thanks to geek4u for suggesting this method. As pointed by Beginer , there can be addition and multiplication overflow problem with this approach. The methods 3 and 4 use all useful information given in the question :)

#include
#include
#include
/* function to get factorial of n */
int fact(int n);
void printRepeating(int arr[], int size)
{
int S = 0; /* S is for sum of elements in arr[] */
int P = 1; /* P is for product of elements in arr[] */
int x, y; /* x and y are two repeating elements */
int D; /* D is for difference of x and y, i.e., x-y*/
int n = size - 2, i;
/* Calculate Sum and Product of all elements in arr[] */
for(i = 0; i <>
{
S = S + arr[i];
P = P*arr[i];
}
S = S - n*(n+1)/2; /* S is x + y now */
P = P/fact(n); /* P is x*y now */
D = sqrt(S*S - 4*P); /* D is x - y now */
x = (D + S)/2;
y = (S - D)/2;
printf("The two Repeating elements are %d & %d", x, y);
}
int fact(int n)
{
return (n == 0)? 1 : n*fact(n-1);
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 4 (Use XOR)
Thanks to neophyte for suggesting this method.
The approach used here is similar to method 2 of this post.
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.
The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

void printRepeating(int arr[], int size)
{
int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
int n = size - 2;
int x = 0, y = 0;
/* Get the xor of all elements in arr[] and {1, 2 .. n} */
for(i = 0; i <>
xor ^= arr[i];
for(i = 1; i <= n; i++)
xor ^= i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i <>
{
if(arr[i] & set_bit_no)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
for(i = 1; i <= n; i++)
{
if(i & set_bit_no)
x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
else
y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
}
printf("\n The two repeating elements are %d & %d ", x, y);
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Method 5 (Use array elements as index)
Thanks to Manish K. Aasawat for suggesting this method.

traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition,
now list is {-1,1,2,3,2}

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated
now list becomes {-1,-1,-2,3,2}

i=4 ;
and A[4]=3 is not repeated

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition,

This method modifies the original array.

#include
#include
void printRepeating(int arr[], int size)
{
int i;
printf("\n The repeating elements are");
for(i = 0; i <>
{
if(arr[abs(arr[i])] > 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}
int main()
{
int arr[] = {1, 3, 2, 2, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}
The problem can be solved in linear time using other method also

Reverse a Linked List in groups of given size


Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */

#include
#include
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* Reverses the linked list in groups of size k and returns the pointer to the new head node */
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;
/*reverse first k nodes of the linked list */
while (current != NULL && count <>
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(next != NULL)
{ head->next = reverse(next, k); }
/* prev is new head of the input list */
return prev;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;
/* Created Linked list is 1->2->3->4->5->6->7->8 */
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("\n Given linked list \n");
printList(head);
head = reverse(head, 3);
printf("\n Reversed Linked list \n");
printList(head);
getchar();
}
return(0);

Time Complexity: O(n) where n is the number of nodes in the given list.

Friday, June 25, 2010

Check whether a given Binary tree is BST

*

A program to check if a binary tree is BST or not

A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.

BST


METHOD 1 (Simple but Wrong)
Following is a simple program. For each node, check if left node of it is smaller than the node and right node of it is greater than the node.
view source
print?
int isBST(struct node* node)
{
if (node == NULL)
return 1;

/* false if left is > than node */
if (node->left != NULL && node->left->data > node->data)
return 0;

/* false if right is <>right != NULL && node->right->data <= node->data)
return 0;

/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
return 0;

/* passing all that, it's a BST */
return 1;
}

This approach is wrong as this will return true for below binary tree (and below tree is not a BST because 4 is in left subtree of 3)

tree_bst




METHOD 2 (Correct but not efficient)
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.
view source
print?
/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
if (node == NULL)
return(false);

/* false if the max of the left is > than us */
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);

/* false if the min of the right is <= than us */ if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);

/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
return(false);

/* passing all that, it's a BST */
return(true);
}

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree


METHOD 3 (Correct and Efficient)
Method 2 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

/* Returns true if the given tree is a binary search tree
(efficient version). */
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
values are >= min and <= max. */ int isBSTUtil(struct node* node, int min, int max) Implementation: view source print? #include
#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree
(efficient version). */
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
values are >= min and <= max. */ int isBSTUtil(struct node* node, int min, int max) { /* an empty tree is BST */ if (node==NULL) return 1; /* false if this node violates the min/max constraint */ if (node->data <>data > max)
return 0;

/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);

if(isBST(root))
printf("Is BST");
else
printf("Not a BST");

getchar();
return 0;
}

Time Complexity: O(n)
Space Complexity: O(1) if Function Call Stack size is not considered, otherwise O(n)

METHOD 4(Using In-Order Traversal)

Thanks to LJW489 for suggesting this method.
1) Do In-Order Traversal of the given tree and store the result in a temp array.
3) Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Time Complexity: O(n)
Space Complexity: O(n)

Sources:
http://en.wikipedia.org/wiki/Binary_search_tree
http://cslibrary.stanford.edu/110/BinaryTrees.html

Memory Leak and Memory Corruption

Memory leakage is memory lost. You can't use the leaked portion of memory during the course of execution. For example:

int * p = new int[10];
p++;
delete []p;

Here memory is leaked as we are not deleting the first location of array of integer.

On the other side memory corruption is like over deleting the same memory location.

For example:

int *p = new int;
delete p;
delete p; //dont use delete twice, it may corrupt the heap(memory)

Or we can do like this to avoid the corruption:

int *p = new int;
delete p;
p = NULL;
delete p; // this delete will not harmful for heap

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

There are two forms of Linux Memory accessible to the programmer:

  1. User's virtual memory space in which application is run.
  2. Register memory.

The most obvious memory errors result in a "Segmentation violation" message. This may alert the programmer to the location of the memory error when the program is run in gdb. The following errors discussed are the not so obvious errors.

Memory errors:

  • Heap memory errors:
    • Attempting to free memory already freed.
    • Freeing memory that was not allocated.
    • Attempting to write to memory already freed.
    • Attempting to write to memory which was never allocated.
    • Memory allocation error.
    • Reading/writing to memory out of the bounds of a dynamically allocated array

  • stack (local variables) memory errors:
    • Reading/writing to memory out of the bounds of a static array. (array index overflow - index too large/underflow - negative index)
    • Function pointer corruption: Invalid passing of function pointer and thus a bad call to a function.


Memory Leaks:

Memory leak description: Memory is allocated but not released causing an application to consume memory reducing the available memory for other applications and eventually causing the system to page virtual memory to the hard drive slowing the application or crashing the application when than the computer memory resource limits are reached. The system may stop working as these limits are approached.


Many C library functions malloc's memory which MUST be freed: i.e.: strdup(),

01#include
02#include
03
04...
05
06char *oldString = "Old String";
07char newStrig = strdup(oldString);
08if(newString == ENOMEM) ... // Fail!!!!
09
10...
11
12free(newString);
Note: You can NOT use the C++ delete call. The strdup() function is part of the C library and you must use free().

Any routine which is supplied by the C libraries or ones written within an application which allocate memory must have the memory freed. Comments on this need should be included in the include file to make users of the function aware of their duties to free the memory and the mechanism by which it is to be freed (free() or delete).


Programmer must free() malloc()'ed memory:

Also for calloc(), malloc() and realloc();

1#include
2
3char *textString = malloc(128*sizeof(char));
4if(textString == ENOMEM) ... // Fail!!!!
5...
6free(textString); // Don't free if allocation failed

Check for memory allocation errors. Can't free it if it didn't get allocated.


Programmer must delete new'ed memory:

using namespace std;

ClassTypeA *ptr = new ClassTypeA;

...

delete ptr;
New/delete is preferred to malloc()/free() because it can initialize the memory and it invokes the constructor for new objects. New/delete also point to the correct memory type. Note on mixing source code containing new/delete and malloc()/free(). This is not a problem with the GNU C++ compiler but this is not guaranteed for all C++ compilers.


Inheritance, polymorphism and the wrong delete:

1BaseClass* obj_ptr = new DerivedClass; // Allowed due to polymorphism.
2...
3delete obj_ptr; // this will call the destructor ~Parent() and NOT ~Child()

If you are counting on the destructor to delete memory allocated in the constructor beware of this mistake as it will cause a memory leak. Use a virtual destructor to avoid this problem. The ~BaseClass() destructor is called and then the destructor ~DerivedClass() is chosen and called at run time because it is a virtual destructor. If it is not declared virtual then only the ~BaseClass() destructor is called leaving any allocated memory from the DerivedClass to persist and leak. This assumes that the DerivedClass has extra memory allocated above and beyond that of the BaseClass which must be freed.

The same ill effect can be achieved with a C style cast to a class of less scope which will dumb down the destructor to that which may not execute all the freeing of the original class. A C++ style dynamic cast may prevent this error as it will recognize the loss of translation and not allow the cast to take place resulting in a traceable crash rather a tough to find memory leak.


Pointer re-assignment error leads to dangling pointer:

If the pointer is re-assigned a new value before being freed, it will lead to a "dangling pointer" and memory leak.

Example:

1char *a = malloc(128*sizeof(char));
2char *b = malloc(128*sizeof(char));
3b = a;
4free(a);
5free(b); // will not free the pointer to the original allocated memory.


Default copy constructor may not give correct results:

Memory allocated by copy constructors for pointer duplication. Check in destructor and delete if necessary. Memory allocated in passing class by value which invokes copy constructor. Also beware, the default copy constructor may not give you the results you want especially when dealing with pointers as the default copy constructor has no knowledge of how to copy the contents of what the pointer points to. To prohibit the use of the default copy constructor define a null assignment operator.

1ClassA& operator=(const ClassA& right_hand_side);


Good practice: Use assert to check pointers before freeing or using:

1assert(ptr !=0)


Memory Corruption:

Memory Corruption: Memory when altered without an explicit assignment due to the inadvertent and unexpected altering of data held in memory or the altering of a pointer to a specific place in memory.


Buffer overflow:

Example 1:
Overwrite beyond allocated length - overflow.

1char *a = malloc(128*sizeof(char));
2memcpy(a, data, dataLen); // Error if dataLen too long.

Example 2:
Index of array out of bounds: (array index overflow - index too large/underflow - negative index)

1ptr = (char *) malloc(strlen(string_A)); // Should be (string_A + 1) to account for null termination.
2strcpy(ptr, string_A); // Copies memory from string_A which is one byte longer than its destination ptr.
Overflow by one byte.


Using an address before memory is allocated and set:

1struct *ABC_ptr;
2x = ABC_ptr->name;
In this case the memory location is NULL or random.


Using a pointer which is already freed:

01char *a = malloc(128*sizeof(char));
02..
03..
04free(a);
05
06cout <<>// This will probably work but dangerous.
07
08... Do stuff. Probable overwriting of freed memory.
09
10cout <<>// No longer the same contents. Memory overwritten by new stuff.


Freeing memory which has already been freed. Also applies to delete.

Freeing a pointer twice:

1char *a = malloc(128*sizeof(char));
2free(a);
3... Do stuff
4free(a); // A check for NULL would indicate nothing.
5 // This memory space may be reallocated and thus we may be freeing
6 // memory we do not intend to free or portions of another block of
7 // memory. The size of the block of memory allocated is often held
8 // just before the memory block itself..

Freeing memory which was not dynamically allocated:

1struct ABC abc;
2struct ABC *abc_ptr = &abc;
3...
4free(abc_ptr);


Incorrect use of delete: The delete must match the use of new.

The pairing is new/delete and new [] / delete[]

1ClassABC *abc_ptr = new ClassABC[100];
2...
3delete [] abc_ptr;
Use of "delete abc_ptr" is an error.

Do not use malloc()/free() with a C++ class as it will not call the constructor or destructor. Also malloc()/free() can not be mixed with new/delete. i.e. Free() can not be used to free memory allocated with new and delete can not be used to free memory allocated with malloc().


Exception Errors:

Freeing memory never allocated. If you use a constructor to allocate memory but an exception is thrown before all is allocated, the destructor needs to be aware that fact or else it may try to free memory which was never allocated.

Also the converse is true. If the destructor throws an exception, subsequent steps which free memory may not be executed. This applies to the destructor and all nested destructors which handle/re-throw the exception while the stack unwinds.


Pointer persistence:

Function returning a pointer from the stack which can get overwritten by the calling function (in this case main()):

01int *get_ii()
02{
03 int ii; // Local stack variable
04 ii = 2;
05 return
06}
07main()
08{
09 int *ii;
10 ii = get_ii(); // After this call the stack is given up by the routine
11 // get_ii() and its values are no longer safe.
12
13 ... Do stuff
14 .. ii may be corrupt by this point.
15}
This is also true for a local variable within the scope of only { and } as well as for the scope of a function.


Incorrect passing of a function argument:

If the pointer is passed around as an argument and does not get passed correctly, one may try to free the incorrect pointer.


Mixing the object base class and derived class:

If mixing the object base class and derived class when passing an object by value as a function parameter, make sure that you understand what may be lost.

1function_A(BaseClass baseClass_ptr)
2{
3...
4}
5
6// Call to function
7function_A(derivedClass_ptr); // Note that much of the information contained
8 // in the derived class will not be passed into
9 // the function including virtual destructors.


Copying an object:

Don't use memcpy() or any bit for bit copy function to copy an object. It will not execute the class constructor. What kind of person would do this?? Passing an object in a va_arg() list will result in a bit for bit copy and will not use the default copy constructor.