#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
unsigned char c;
struct Node *next;
}Node;
typedef Node *slist;
slist reverse(slist);
Node *makeNode(unsigned char);
/*
*/
slist Sum(slist left, slist right) {
if(!left || !right) {
return left ? left : right;
}
left = reverse(left);
right = reverse(right);
unsigned char carry = left->c + right->c;
slist ret = makeNode(carry % 10);
carry /= 10;
Node *p = left->next;
Node *q = right->next;
Node *r = ret;
while(p || q) {
carry += (p? p->c : 0) + (q ? q->c : 0);
r->next = makeNode(carry % 10);
carry /= 10;
r = r->next;
p = p ? p->next : NULL;
q = q ? q->next : NULL;
}
if(carry)
r->next = makeNode(1);
reverse(left);
reverse(right);
return reverse(ret);
}
/*
utilities
*/
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(unsigned char c) {
Node * tmp = calloc(sizeof(Node), 1);
tmp->c = c;
return tmp;
}
void print(slist s) {
if(s == NULL) {
printf("\n");
return;
}
printf("%c", s->c + '0');
print(s->next);
}
slist listFromString(const unsigned char *s) {
if(!s || !*s) return NULL;
slist ret = makeNode(*s++ - '0');
Node *tmp = ret;
unsigned char c;
while((c = *s++)) {
tmp->next = makeNode(c - '0');
tmp = tmp->next;
}
return ret;
}
int main()
{
slist left = listFromString("99");
slist right = listFromString("233823");
slist sum = Sum(left, right);
print(sum);
return 0;
}
Monthly Archives: February 2011
Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order
Problem
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
struct TreeNode *left, *right;
int data;
}TreeNode;
typedef TreeNode * Tree;
/*
Two passes with constant space
*/
int printSum(Tree t, int toPrint)
{
if(t == NULL)
return 0;
int lsum = printSum(t->left, toPrint);
int rsum = printSum(t->right, 0);
int sum = lsum + t->data + rsum;
if(toPrint)
printf("%d ", sum);
printSum(t->right, toPrint);
return sum;
}
/*
One pass with n space
*/
int printSum2(Tree t, int a[], int *pos)
{
if(t == NULL)
return 0;
int lsum = printSum2(t->left, a, pos);
(*pos)++;
int p = *pos;
int rsum = printSum2(t->right,a, pos);
return a[p] = lsum + t->data + rsum;
}
/*Utilities*/
inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;
return n;
}
int main()
{
/*level 0*/
Tree t = makeTreeNode(3);
/*level 1*/
t->left = makeTreeNode(2);
t->right = makeTreeNode(4);
/*level 2*/
t->left->left = makeTreeNode(2);
t->right->left = makeTreeNode(2);
t->right->right = makeTreeNode(-1);
/*print sum*/
printSum(t, 1);
printf("\n");
int a[100];
int pos = -1;
printSum2(t, a, &pos);
int i;
for(i = 0; i <= pos; ++i) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
Given set of words, find an area of the text where these words are close
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
struct Word {
string word;
const char *pos;
bool operator == (const string & str) {
return word == str;
}
Word(const string &w, const char *p) : word(w), pos(p){}
};
typedef list<Word> Window;
typedef list<string> Words;
string textarea(const Words &words, const char *str) {
string result;
if(!str || !*str) return result;
const char *p = str;
Window window;
string word;
while(1) {
if(*p == ' ' || *p == '') { //end of word
word = string(str, p - str);
//find the word in words
if(find(words.begin(), words.end(), word) != words.end()) {
//find the word in window
Window::iterator wit = find(window.begin(), window.end(), word);
//if word is there, reduce the window till the next word in window
if(wit != window.end()) {
window.erase(window.begin(), ++wit);
}
//place the current word in window
window.push_back(Word(word, str));
//if the size of the window is same as size of words
if(window.size() == words.size()) {
//starting of the window is the pos of the first word
const char* start = window.front().pos;
string temp(start, p - start);
if( result.empty() || result.size() > temp.size() )
result = temp;
}
}
str = p + 1;
}
if(*p == '') break;
p++;
};
return result;
}
int main() {
Words l;
l.push_back("bat");
l.push_back("cat");
l.push_back("mat");
cout<<textarea(l, "bat stop the mat blah blah cat by mat bat ss cat t mat bat")<<endl;
return 0;
}
to eliminate the two same chars adjacent to each other recursively
.comment { color: #999999; font-style: italic; } .pre { color: #000099; } .string { color: #009900; } .char { color: #009900; } .float { color: #996600; } .int { color: #999900; } .bool { color: #000000; font-weight: bold; } .type { color: #FF6633; } .flow { color: #FF0000; } .keyword { color: #990000; } .operator { color: #663300; font-weight: bold; } .operator { color: #663300; font-weight: bold; }
#include <stdio.h>
void removeSpace(char *s) {
char *p = s;
char c;
while((c = *s++)) {
if(c != '\n' && c != '\t' && c != ' ')
*p++ = c;
}
*p = '';
}
void removeCouple(char *str) {
char *p = str;
char *q;
while(*p) {
//find couple
while(*p && *p != *(p + 1)) p++;
if(!*p) break;
q = p - 1;
//replace couple with space
*p++ = ' ';
*p++ = ' ';
while(q >= str && *p) { //go backward
if(*q == ' ') {
--q; continue;
}else if(*q == *p) { //now q && p are couple, replace them with space
*q-- = *p++ = ' ';
} else
break;
}
}
//finally remove space
removeSpace(str);
}
int main() {
char str[]= "BBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRGBBGBGRRBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGBGB";
printf("%s\n", str);
removeCouple(str);
printf("\n\n%s\n", str);
}
Duplicate removal in Binary Search Tree
#include <stdio.h>
class BinarySearchTree
{
private:
int data;
BinarySearchTree *left, *right;
public:
BinarySearchTree(const int d):data(d), left(NULL), right(NULL){}
~BinarySearchTree()
{
if(left != NULL)
{
delete left;
}
if(right != NULL)
{
delete right;
}
}
//remove duplicates
void removeDup()
{
if(left)
{
left->removeDup();
left->remove(data, this);
}
if(right)
right->removeDup();
}
void remove(int value, BinarySearchTree *parent)
{
if(value < data && left)
{
left->remove(value, this);
}
else if(value > data && right)
{
right->remove(value, this);
}
else
remove(parent);
}
void remove(BinarySearchTree *parent) //remove this node
{
if(left == NULL && right == NULL) //leaf
{
((parent->left == this) ? parent->left : parent->right) = NULL;
}
else
{
if (left != NULL && right != NULL) //two child
{
right->removeMin(this);
return;
}
else //one child
{
((parent->left == this) ? parent->left : parent->right) = (left != NULL) ? left : right;
}
}
delete this;
}
void removeMin(BinarySearchTree *root)
{
BinarySearchTree *p = this, *parent = root;
while(p->left)
{
parent = p;
p = p->left;
}
root->data = p->data;
p->remove(parent); //remove p
}
//constructs bst from an array
void construct(const int a[], const int n, const int i)
{
int j;
for(j= i; j < n; ++j)
{
insert(a[j]);
}
}
void inorder() const
{
if(left)
left->inorder();
printf("%d ", data);
if(right)
right->inorder();
}
void insert(const int el)
{
if(el <= data) //same element insert in left
{
if(left)
left->insert(el);
else
{
left = new BinarySearchTree(el);
}
}
else
{
if(right)
right->insert(el);
else
{
right = new BinarySearchTree(el);
}
}
}
};
int main()
{
int n;
scanf("%d", &n);
int i;
int a[n];
for(i = 0; i <n; ++i)
scanf("%d", a + i);
BinarySearchTree *t = new BinarySearchTree(a[0]);
t->construct(a, n, 1);
BinarySearchTree *prev = NULL;
t->inorder();
printf("\n");
t->removeDup();
t->inorder();
printf("\n");
return 0;
}
recursive mkdir
/*
Recursively creates the given path, with the given mode
Returns: 0 on success and -1 on error
*/
int mkdirp(const char *dir, mode_t mode)
{
const char *p = dir + 1;
while(*p)
{
if(*p == '/')
{
*((char*)p) = '';
if(mkdir(dir, mode) == -1 && errno != EEXIST)
return -1;
*((char*)p) = '/';
}
p++;
}
if(*(p-1) != '/')
if(mkdir(dir, mode) == -1 && errno != EEXIST)
return -1;
return 0;
}
printing pascal triangle
#include <stdio.h>
unsigned long ncr(int n, int r) {
static unsigned long table[256][256] = {0};
if(r == 0 || n == r) {
return table[n][r] = 1;
}
if(r == 1) {
return table[n][r] = n;
}
if(r > n / 2) {
return table[n][r] = ncr(n, n - r);
}
return table[n][r] = table[n - 1][r - 1] + table[n - 1][r];
}
void printPascal(int n) {
int numSpaces = n;
int i, j;
for(i = 0; i <= n; ++i) {
for(j = 0; j < numSpaces; ++j)
printf(" ");
for(j = 0; j <= i; ++j)
printf("%lu ", ncr(i, j));
printf("\n");
numSpaces--;
}
}
int main() {
int n;
scanf("%d", &n);
printPascal(n);
return 0;
}
Effective Programming 