program to squeeze all multiple spaces in a string into one space

#include <stdio.h>

void trimspace(char *dst) {

const char *src = dst;

int tocopy = 1;

char c;

while((c = *src++)) {

if(tocopy)
*dst++ = c;

tocopy = (c != ' ') || (*src != ' ');
}

*dst = '';
}


int main() {
char s[64];

scanf("%[^\n]c", s);

trimspace(s);

printf("%s\n", s);
}
Advertisements

Palindrome in singly linked list

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

typedef struct Node
{
char c;

struct Node *next;

}Node;


typedef Node *slist;


slist reverse(slist s)
{
if(s->next == NULL)
return s;

Node *ret = reverse(s->next);

s->next->next = s;
s->next = NULL;

return ret;
}


Node *makeNode(char c)
{
Node * tmp = calloc(sizeof(Node), 1);

tmp->c = c;

return tmp;
}


void print(slist s)
{
if(s == NULL)
return;

printf("%c", s->c);

print(s->next);
}

/*
Divede the list into two halves using slowfast algo..

reverse the second part

now compare both the parts

incase odd number of elements in the list, second part is the big one
*/


int palindrome(slist s)
{
Node *prevslow = NULL;
Node *slow = s;

Node *fast = s;

//divide into two parts
while(fast)
{
if(fast->next)
fast = fast->next->next;
else
break;

prevslow = slow;
slow = slow->next;
}

prevslow->next = NULL;

//reverse the second part
fast = reverse(slow);

//to retain the list
slow = fast;

//compare two parts
while(s && fast->c == s->c)
{
fast = fast->next;
s = s->next;
}

if((fast == NULL || fast->next == NULL) && s == NULL)
printf("Plaindrome\n");
else
printf("Not Plaindrome\n");


//retain the list back
prevslow->next = reverse(slow);
}


int main()
{
slist s = makeNode('s');
s->next = makeNode('a');
s->next->next = makeNode('a');
s->next->next->next = makeNode('a');
s->next->next->next->next = makeNode('s');

palindrome(s);

return 0;
}

Populating Siblings in a binary tree

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

/*Data structures*/
typedef struct TreeNode
{
struct TreeNode *left, *right, *sibling;

int data;
}TreeNode;


typedef TreeNode * Tree;

/*
For each level there will be one list node, which has prev pointer pointing to TreeNode for which sibling has to populate in that level
*/

typedef struct ListNode
{
TreeNode *prev;
struct ListNode *next;

}ListNode;

typedef ListNode *List;

/*End of data structures*/

/*
*Function which populates siblings
*/
void PopulateSibling(Tree t, ListNode *prevLevel) //preorder traversal
{
if(t == NULL)
return;

ListNode *node = prevLevel->next;

if(node == NULL) //allocate node to the current level, if not yet allocated
{
node = calloc(sizeof(ListNode), 1);
prevLevel->next = node;
}
else if(node->prev) //if prev is there in this level, populate sibling
node->prev->sibling = t->left ? t->left : t->right;


if(t->left)
{
if(t->right) //sibling of left is right if there, else populate node->prev
{
node->prev = t->left->sibling = t->right;

}
else
node->prev = t->left;

PopulateSibling(t->left, node);
}

PopulateSibling(t->right, node);
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}

/* prints if left most is the first node in sibling list*/
inline void printSibling(Tree t)
{
TreeNode *sibling;

while(t)
{
printf("%d ", t->data);

sibling = t->sibling;

while(sibling)
{
printf("%d ", sibling->data);

sibling = sibling->sibling;
}

printf("\n");
t = t->left;
}
}

int main()
{
/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);

/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*Empty List head*/
ListNode head = {NULL, 0};

PopulateSibling(t, &head);

printSibling(t);

return 0;
}

spiral printing of a two dimensional array

#include <stdio.h>

void spiralPrint(int m, int n, int a[][n])
{

int i, k = 0, l = 0;

m--, n--;

/*
        k - min row
        m - max row
        l - min column
        n - max column

        i - iterator
    */

while(k <= m && l <= n){

for(i = l; i <= n; ++i) {
printf("%d ", a[k][i]);
}

k++;

for(i = k; i <= m; ++i) {
printf("%d ", a[i][n]);
}

n--;

if(m >= k) {

for(i = n; i >= l; --i) {
printf("%d ", a[m][i]);
}

m--;
}

for(i = m; i >= k; --i) {
printf("%d ", a[i][l]);
}

l++;
}


printf("\n");
}

int main()
{
printf("1, 2, 3, 4, 5, 6\n");
printf("7, 8, 9, 10, 11, 12\n");
printf("13, 14, 15, 16, 17, 18\n");
printf("19, 20, 21, 22, 23, 24\n");
printf("25, 26, 27, 28, 29, 30\n");
printf("35, 36, 37, 38, 39, 40\n\n");

int a[6][6] = { {1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24},
{25, 26, 27, 28, 29, 30},
{35, 36, 37, 38, 39, 40}
};

spiralPrint(6, 6, a);
}

Color filling in MS-Paint

#include <stdio.h>

typedef struct Pixel
{
/*Pixel coordinates*/
int x, y;

}Pixel;

typedef Pixel Direction;

typedef struct Matrix
{
/*numrows x numcolumns*/
int m, n;

/*flattened two dimensional array*/
int *a;

}Matrix;


void fillcolor(Matrix m, int color, Pixel p)
{
static const Direction directions[8] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1},
{1, 1}, {1, -1}, {-1, 1},{-1, -1}
};

/*flattened index*/
int index = p.x *m.n + p.y;

/*current color of the pixel*/
int val = m.a[index];

/*change the color of the pixel to the given*/
m.a[index] = color;

int i, j, d;

Pixel temp;

/*Fill all the connected pixels*/
for(d = 0; d < 8; d++)
{
i = directions[d].x;
j = directions[d].y;

temp.x = p.x + i;
temp.y = p.y + j;

/*Check boundaries*/
if(temp.x < 0 || temp.x >= m.m) continue;
if(temp.y < 0 || temp.y >= m.n) continue;

/*Check the color of this pixel*/
if(m.a[temp.x * m.n + temp.y] != val) continue;

fillcolor(m, color, temp);
}

}

int main()
{
int a[][4] = {1, 0, 2, 0,
0, 2, 0, 2,
2, 0, 2, 1
};

Matrix m = {3, 4, (int *)a};

Pixel p = {2, 1};

fillcolor(m, 3, p);

int i, j;

for(i = 0 ; i < 3; ++i)
{
for(j = 0; j < 4; ++j)
printf("%d ", a[i][j]);

printf("\n");
}
}

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes

#include <stdio.h>

int equilibrium(int a[], int n)
{
int sum = 0;

int i;

/*Find sum of the array*/

for(i = 0; i < n; ++i)
sum += a[i];


/*find leftsum of an index i
      rightsum = sum - leftsum - a[i];
    */
int leftsum = 0;

for(i = 0; i < n; ++i)
{
sum -= a[i];

if(leftsum == sum)
return i;

leftsum += a[i];
}


return -1;
}


int main()
{
int a[] = {-7, 1, 5, 2, -4, 3, 0};

printf("%d\n", equilibrium(a, 7));
}

Strstr if all characters in pattern are different

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


int Strstr(const char *str, const char *pattern)
{
/*Null pointers or null strings return 0*/
if(!str || !*str || !pattern || !*pattern)
return 0;

/*Compare lengths*/
size_t patlen = strlen(pattern);
size_t len = strlen(str);

if(patlen > len)
return 0;

else if(patlen == len)
return strcmp(str, pattern) == 0;

/*find the position of the first character of the pattern*/
if((str = strchr(str, *pattern)) == NULL)
return 0;

const char *p;


/*find next position of first character of the pattern*/
while(p = strchr(str + 1, *pattern))
{
if((p - str) >= patlen) /*As all characters in the pattern are distinct*/
{
if(strncmp(str, pattern, patlen) == 0)
return 1;
}

str = p;
}

return strncmp(str, pattern, patlen) == 0;
}

int main()
{
char str[64], pat[64];

scanf("%s", str);

scanf("%s", pat);

printf("%d\n", Strstr(str, pat));

return 0;
}