Maximum sum submatrix

Given a matrix of positive and negative integers, Write a code which find out the sub-matrix with the largest sum.
eg.
0 2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

max sum is : 17
0 2
9 2
-4 1
-1 8












SOLUTION
Thanks to anonymous. My code writing effort got saved coz of him.

int main( void )
{
int N;
int t = 0;
int a[100][100];
int pr[100];
int S = -INF, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;

cin >> N;

for( int i = 0; i < N; i++)
for( j = 0; j - N; j++)
input a[i][j];

for( int z = 0; z - N; z++)
{
for(int i = 0; i - N; i++) pr[i] = 0;

for(int x = z; x-N; x++)
{
t = 0;
s = -INF;
j = 0;
k = 0; l = 0;
for(int i = 0; i - N; i++)
{
pr[i] = pr[i] + a[x][i];
t = t + pr[i];
if( t > s)
{
s = t;
k = i;
l = j;
}
if( t less than 0 )
{
t = 0;
j = i + 1;
}
}
if( s greater than S)
{
S = s;
x1 = x;
y1 = k;
x2 = z;
y2 = l;
}
}
}

print x1 y1 x2 y2
print S;

return 0;
}

Left rotate a BST

A node of binary search tree is given. Write a code which will left rotate the tree about given node.











SOLUTION

void left_rotate ( tree * x){
tree * y = x->right;
tree *z = x->parent;

x->right = y->left;
y->left->parent = x;
y->parent = z;

if ( z == NULL)
root = y;
else {
if ( x == z->left)
z->left = y;
else
z->right = y;
}
y->left = x;
x->parent = y;
}


A palindromic number

Write a code which will check whether the number is palindrome or not.PS: Don not convert a number into string .












SOLUTION

bool IsPalindrome( int n){
int a=n, b=0;
while( n > 0){
b = b*10 + n%10;
n /= 10;
}
if ( a == b)
return true;
return false;
}


Merge 2 sorted LL

Two sorted singly Linked List are given. Write a code to merge them. Your code should be inplace.














SOLUTION

node *merge(node *h1, node *h2){
if ( !h1 && !h2) return NULL;
if( !h1) return h2;
if (!h2) return h1;
if ( h1->data < h2->data ){
h1 ->next = merge(h1->next, h2);
return h1;
}
else {
h2->next = merge(h1,h2->next);
return h2;
}
}

Swap words in sentence

A sentence is given and 2 indexes x and y. Write a code should swap word x with word y in the sentence.
eg. "I love the questions on this blog" x=2,y=6 Ans="I this the questions on love blog"












SOLUTION

char *fun(char *s,int x,int y){
int i=1,l1=0, l2=0;
char *str=s, *p1,*p2;
if ( x greater-than y ) swap (x,y);
//find position of first word
while ( i less-than x){
if ( *str == ' ')
i++;
str++;
}
p1 = str;
//length of first word
while( *str++ != ' ')
l1++;
i += 1;

//find position of second word
while ( i less-than y){
if ( *str == ' ')
i++;
str++;
}
p2 = str;
//find length of second word
while( *str++ != ' ')
l2++;
//end position of 2nd word
p2 = str + l2-1;

int start_pos_of_word1 = p1-s;
int end_pos_of_word2 = p2-s;

rev(s,start_pos_of_word1,end_pos_of_word2);
rev(s,start_pos_of_word1, start_pos_of_word1 + l2);
rev(s,end_pos_of_word2 - l1, end_pos_of_word2);
rev(s,start_pos_of_word1+l2, end_pos_of_word2-l1);
return s

}


BST to CLL

Code which convert Binary search tree to Sorted Single Circular Linked List.










SOLUTION


tree *convert_bst_to_scll(tree *root){
return bst_2_cll(root)->right;
}

tree * bst_2_cll(tree *ptr){
int a;
if (ptr == NULL) return NULL;
node *ltail = bst_2_cll(ptr->left); // return last node of SCLL of left subtree
node *rtail = bst_2_cll(ptr->right); // return last node of SCLL of right subtree

node *lhead=NULL, *rhead=NULL;

ptr->left = NULL;

if ( ltail && rtail) {
lhead = ltail->right;
ltail ->right = ptr;
rhead = rtail->right;
rtail->right = lhead;
ptr->right= rhead;
return rtail;
}

else if ( ltail){
lhead = ltail->right;
ltail ->right = ptr;
ptr->right = lhead;
return ptr;
}
else if ( rtail) {
rhead = rtail->right;
ptr->right= rhead;
rtail->right = ptr;
return rtail;
}
else {
ptr->right = ptr;
return ptr;
}
}


I have been executed 'n' times

Write a code which outputs the number 'n' , which represent no. of times it had been run.
eg. running it for first time it should give 1
for 2nd time it should give 2.






















SOLUTION
#include sys/types.h
#include sys/ipc.h
#include sys/shm.h
#include unistd.h
#include cstdlib
#include cstdio
#define SHMKEY 5678L
using namespace std;

int main()
{
int shmid;
int *no_of_executions;
char *shmptr;



if ( (shmid=shmget(SHMKEY,sizeof(int),IPC_CREAT|IPC_EXCL|0666)) > 0 )
{
if((shmptr =(char*)shmat(shmid,0,0))==(char *)-1)
{
perror("failed to attah shared memory");
exit(-1);
}
no_of_executions=(int*)shmptr;
*no_of_executions=1;
printf("%d\n", *no_of_executions);
}
else
{

if ((shmid=shmget(SHMKEY,sizeof(int),0)) == -1)
{
perror("failed to create shared memory");
exit(-1);
}
if((shmptr =(char*)shmat(shmid,0,0))==(char *)-1)
{
perror("failed to attah shared memory");
exit(-1);
}
no_of_executions=(int*)shmptr;
++*no_of_executions;
printf("%d\n", *no_of_executions);

}


return 0;
}

Maximum Sum with no 2 elements consecutive.

An array on n integers is given. Find out the maximum sum of the elements of array such that no 2 elements are consecutive.
eg.
A[] = {1,2,3,4} Ans= 6
A[] = {1,-2,3,4} Ans=5














SOLUTION

int fun(int *array, int n){
int a=array[0], b=array[1], c=max(max(array[0]+array[2], array[2]), array[0]);
for ( int i=3; n-i;i++){
int temp=max(max( array[i], array[i] +b), array[i]+a);
a = b;
b = c;
c = temp;
}
return max(b,c);
}