#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 = '\\0';
}
int main() {
char s\[64\];
scanf("%\[^\\n\]c", s);
trimspace(s);
printf("%s\\n", s);
}
Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order
Given a binary tree. Find the sum( inclusive of the root ) of sub-tree rooted at each node. Print the sum in in-order.
E.g.
3
/ \\
2 4
/ / \\
2 2 -1
Output: 2, 4, 12, 2, 5, -1.
Solution
#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;
}
Leveling sectors in a circle
Problem : How to make the surface of the circular plot level in minimum number of moves
Detail:
The circular plot is divided into sectors. Each of these sectors has a level which is indicated by an integer. The sector can be either above the earth surface, in which case the integer is positive, or below the earth surface, when it will be negative. She can choose two consecutive sectors and increase the level of both the sectors by 1 at a time, which will be counted as one move.
[Read More]
To find the longest substring with unique characters in a given string
#include <stdio.h> #include <string.h> typedef struct { const char \*start; size\_t len; }Substring; Substring longestSubstring(const char \*s){ Substring ret = {s, 1}; Substring cur = {s, 1}; size\_t i, len = strlen(s); const char \*p = NULL; for(i = 1; i < len; ++i){ p = memchr(cur.start, s\[i\], cur.len); if(p){ if(cur.len > ret.len) ret = cur; cur.len -= (p - cur.start) + 1; cur.start = p + 1; } cur.len++; } if(cur.
[Read More]
Reverse the words in a sentence in place
Problem Given a sentence you have to reverse it word by word.
Example
That is, given a sentence like this :
I am a good boy
The in place reverse would be:
boy good a am I
Solutions Method1 - Reverse the sentence first and then words again
First reverse the whole string and then individually reverse the words
I am a good boy
<————->
yob doog a ma I
[Read More]
Check if singly linked list is Palindrome
There are couple of solution to it :
Method 1 - Using the stack
A simple solution is to use a stack of list nodes. This mainly involves three steps.
Traverse the given list from head to tail and push every visited node to stack. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node. If all nodes matched, then return true, else false.
[Read More]
Spiral printing of a two dimensional array
Given a 2D array, print it in spiral form.
Examples
See the following examples.
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is :
[Read More]
Sum of two long positive numbers (each represented by linked lists)
Code :
#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);
[Read More]
Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order
Code :
#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;
}