S1 = S2 S2 S2......n times.

A string is given. Write a code which will determine whether the given string is repetition of any string or not. If yes, find out the repeated string and how many times it has been repeated.
eg. string given = abcabcabcabc
ans : repeated string is abc and it is repeated 4 times.

Square root of a number

Write a code which finds out the square root of a number, w/o sqrt() obviously.










SOLUTION

#define TOLERABLE_LIMIT 0.0000001
double square_root( double n){
double a=n, p=a*a, b;
while(p-n < TOLERABLE_LIMIT){
b = (a+n/a)/2;
a = b;
p = a*a;
}
return a;
}


Copy Linked List

A new type of linked list is given. It's structure has 3 elements, data, next pointer, unknown pointer. data and next pointer are same as in normal linked list. The unknown pointer is pointing to any random node in that linked list. Now, write a code which will copy this linked list.










SOLUTION

node * copy( node * head){
node *p = head, *q=NULL, *NewHead=NULL;
while( p){
node * q = new node;
q->next = p->unknown;
p->unknown = q;
p = p->next;
}

NewHead = head->unknown;
p = head;

while(p){
q = p->unknown;
q->unknown = q->next->unknown;
p = p->next;
}

p = head;

while (p){
q = p->unknown;
p->unknown = q->next;
if (p->next)
q->next = p->next->unknown;
else
q->next = NULL;
p=p->next;
}


return NewHead;
}


Random from infinite stream

An infinite stream of numbers is passing through. Write a code which will select a random number out of it at any given time.










SOLUTION

int select_random(){
int n, our_num
int k=1;
scanf("%d", &n);
our_num=n;
while ( scanf("%d", &n) != 0 ){
float rand = random b/w 0 and 1;
our_num = rand < (float)(1/++k) ? n : our_num;
}
return our_num;
}


Iterative post order

Write a code which will traverse the tree in post-order fashion, iteratively.













SOLUTION

void traverse( tree *root){
Stack st;
while ( !st.empty() && root != NULL){
while( root){
st.push(root);
root = root->left;
}
if ( st.top() ){
st.push(NULL);
root=root->right;
}
else{
st.pop();
print st.top()->data;
st.pop();
root = NULL;
}
}
}


Cycle detection in graph

A graph is given in form of adjacency matrix. Write a code which will check whether cycle is present in the graph or not.












SOLUTION

bool cycle_check( int vertex){
static int visited[n] = {0};
visited[vertex]=1;
for ( int i=0; i-n; i++){
if ( a[vertex][i] == 1){
if ( visited[i] == 1 )
return true;
if ( visited[i] == 0)
return cycle_check(i);
}
}
visited[vertex]=2;
return false;
}


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);
}