Wednesday, June 11, 2008

Swap two pointers

Our task is to two pointers which is pointing to two objects. The problem is very simple and remember to use pointer to pointer concept. Without that it is just a pass by value to the function.


#include<stdio.h&gt;
void swap(int **firstPtr, int **secondPtr)
{
int *temp = *firstPtr;
*firstPtr = *secondPtr;
*secondPtr = temp;

return;
}

int main()
{
int a = 10;
int b = 20;

int *aPtr = &a;
int *bPtr = &b;

printf("Before Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
swap(&aPtr, &bPtr);
printf("After Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
}

If you compile and see the result, the pointers would be swapped ..

Tuesday, June 10, 2008

Write your own tail -n implementation

This is one of the question asked in Adobe to my friend. You need to implement your own tail function. read the man page for more information about tail command.

I could able to think of two ways to solve the problem. [tail -n 10 filename ]

Solution 1:

Keep 2 pointers, 1st points to the start of the file, the 2nd points to the n+1 th line :

if the file is not big enough [ less than n ] then dump the content of the file from the beginning to the end of the file and return
else move the second pointer by one line and move the 1st pointer by one until the second reaches EOF. One the 2nd pointer reaches the end of the file, dump the content from where the 1st pointer currently pointing till the end of the file.

This is one of the solution me and Arun discussed when I was there in Hyderabad. But there are lot of improvements that we can do in this and the companies expect such kind of answers (just for the interview sake)

Problem: One of the biggest problem with the above solution is the performance. Both the pointers are reading the same content (2 times reading the same content). Since disk I/O is costly this is a real performance issue.


Solution 2 :

The next solution is instead of reading from the file twice, create a buffer to hold the content, read the file from the end of the file and dump it into the buffer, also keep track of the no of lines read so far from the end. Once the required no of lines read, print the content of the buffer from the end.


My Implementation :


#include <stdio.h&gt;
#include <stdlib.h&gt;
#include <string.h&gt;
#include <sys types.h>
#include <sys stat.h>
#include <fcntl.h&gt;

void tail(int lines, char *file_name)
{
struct stat file;
int size = 0;
char *ch = NULL;
char *buf = NULL;

FILE *fd = fopen(file_name, "r");

if(fd == NULL)
{
printf("Not able to open the file : %s\n", file_name);
return;
}

// Set the pointer to the end
fseek(fd, 0, SEEK_END);

// Find the size of the file
size = ftell(fd);
--size;

// Allocate the buffer to hold the content
ch = (char *)malloc(2);
buf = (char *)malloc(80 * lines);
memset(buf, 0, 80 * lines);

char * start = buf;
*buf++ = '\0';

// Copy the file content from the end of the file in the reverse order into the buffer
// Use fseek --> SEEK_SET to navigate the file from the back

while(size && lines)
{
--size;
fseek(fd, size , SEEK_SET);
fread(ch, 1, 1, fd);
*buf++ = *ch;
if(*ch == '\n')
lines--;


}
close(fd);

// Print the content of the buffer
while( start != buf)
printf("%c", *buf--);

printf("\n");
return;
}
int main(int argc, char **argv)
{
if(argc != 3)
{
printf("Run exe file_name no_of_lines\n");
return (-1);
}

char *file = argv[1];
tail(atoi(argv[2]), file);

return 0;
}


input file :cat ganesh
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

Output:

# ./a ganesh 2

4 Arun
5 Jerome

# ./a ganesh 4

2 Vishnu
3 Ramak
4 Arun
5 Jerome

./a ganesh 10
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

PS : Guys don't get envy that I wrote a big program for myself. I struggled a lot to make this program to work :-)

Reverse the bits in a number

The problem is to reverse the bits in a number.
Example : 1011 should be reversed as 1101


#include <stdio.h>
void bit_form(unsigned int value)
{
while(value)
{
printf("%d", value & 0x01);
value = value >>1;
}
printf("\n");
return;
}
int main()
{
unsigned int value = 0;
scanf("%d", &value);
unsigned int return_value = value;
int loop = sizeof(value) * CHAR_BIT - 1;

bit_form(value);

for(value >>= 1; value; value >>= 1)
{
return_value <<= 1;
return_value |= value & 1;
loop--;
}

return_value <<= loop;
bit_form(return_value);
return 0;
}

Fast Exponentation

We need to compute the value of a^n, for some reasonable large value of n.

The simplest algorithm that we know is computing axaxax ... xa (up to n times). However we can do this better by observing that n = [n/2] * [n/2]. If n is even, then a^n = [a^n/2]^2. If n is odd, then a^n = a * [a^n/2]^2. In either case we have halved the size of our computation. so O(log n) multiplications suffice to compute the final value.

Code :



#include <stdio.h>
int power(int n, int e)
{
int res;

if(n == 0)
return 0;
if(e == 0)
return 1;

res = power(n, e/2);

if( e%2 ) // ODD
{
return n * res * res;
}
else // Even
return res * res;

}
int main()
{
int number;
int expon;
int result;

printf("Enter the number :");
scanf("%d", &number);

printf("Enter the exponent :");
scanf("%d", &expon);
result = power(number, expon);

printf("%d ^ %d is : %d\n", number, expon, result);
return 0;
}

I am working hard to make my syntax highlighter to work .. this is yet another shot ..



#include <iostream.h>

int main()
{
return 0;
}


Yeah !! It worked at last ..

Monday, June 09, 2008

Implement your own tail functionality

This is one of the question asked in Adobe to my friend. You need to implement your own tail function. read the man page for more information about tail command.

I could able to think of two ways to solve the problem. [tail -n 10 filename ]

Solution 1:

Keep 2 pointers, 1st points to the start of the file, the 2nd points to the n+1 th line :

if the file is not big enough [ less than n ] then dump the content of the file from the beginning to the end of the file and return
else move the second pointer by one line and move the 1st pointer by one until the second reaches EOF. One the 2nd pointer reaches the end of the file, dump the content from where the 1st pointer currently pointing till the end of the file.

This is one of the solution me and Arun discussed when I was there in Hyderabad. But there are lot of improvements that we can do in this and the companies expect such kind of answers (just for the interview sake)

Problem: One of the biggest problem with the above solution is the performance. Both the pointers are reading the same content (2 times reading the same content). Since disk I/O is costly this is a real performance issue.


Solution 2 :

The next solution is instead of reading from the file twice, create a buffer to hold the content, read the file from the end of the file and dump it into the buffer, also keep track of the no of lines read so far from the end. Once the required no of lines read, print the content of the buffer from the end.


My Implementation :


#include <stdio.h&gt;
#include<stdlib.h&gt;
#include<string.h&gt;
#include<sys/types.h&gt;
#include<sys/stat.h&gt;
#include<fcntl.h&gt;

void tail(int lines, char *file_name)
{
struct stat file;
int size = 0;
char *ch = NULL;
char *buf = NULL;

FILE *fd = fopen(file_name, "r");

if(fd == NULL)
{
printf("Not able to open the file : %s\n", file_name);
return;
}

// Set the pointer to the end
fseek(fd, 0, SEEK_END);

// Find the size of the file
size = ftell(fd);
--size;

// Allocate the buffer to hold the content
ch = (char *)malloc(2);
buf = (char *)malloc(80 * lines);
memset(buf, 0, 80 * lines);

char * start = buf;
*buf++ = '\0';

// Copy the file content from the end of the file in the reverse order into the buffer
// Use fseek --> SEEK_SET to navigate the file from the back

while(size && lines)
{
--size;
fseek(fd, size , SEEK_SET);
fread(ch, 1, 1, fd);
*buf++ = *ch;
if(*ch == '\n')
lines--;


}
close(fd);

// Print the content of the buffer
while( start != buf)
printf("%c", *buf--);

printf("\n");
return;
}
int main(int argc, char **argv)
{
if(argc != 3)
{
printf("Run exe file_name no_of_lines\n");
return (-1);
}

char *file = argv[1];
tail(atoi(argv[2]), file);

return 0;
}



input file :cat ganesh
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

Output:

# ./a ganesh 2

4 Arun
5 Jerome

# ./a ganesh 4

2 Vishnu
3 Ramak
4 Arun
5 Jerome

./a ganesh 10
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

PS : Guys don't get envy that I wrote a big program for myself. I struggled a lot to make this program to work :-)

Monday, June 02, 2008

Aiyoo Aiyoo ..

One of the Ultimate comedies of TR :