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