Longest path between two nodes in a graph Amazon Problem : C code

Finding longest path between two nodes in a graph

Problem Statement 

Write algorithm/code to find longest path between any two cities. 4X4 matrix was given. If there is no connectivity between two cities then the distance between them was given as -1. Its cyclic graph.

Solution

Finding longest path between two nodes in a graph is an NP Hard problem. So, we should not try to find a polynomial solution to this problem. As you can see the given problem is of very small size. So even brute force is acceptable.

#include<stdio.h>

int longestPath(int node);

int matrix[4][4] = {{0,1,2,3},{1,0,1,1},{2,1,0,5},{3,4,3,0}};

int main()
{
printf("%d",longestPath(0));
}

int longestPath(int node) {

int dist=0,max=0,i;
for(i=node+1;i<4;i++) {
    dist=0;
    if(matrix[node][i]>0) {
        dist+=matrix[node][i];
        dist+=longestPath(node+1);
    }
    if(max<dist)
        max=dist;
}
printf("%d\t",max);
return max;
}

 

Time Complexity 

Let there be n cities. Given starting city as S and destination city as D. We are left with n-2 cities.
There are approximately 2^(n-2) * (n-2)! ways for reaching D from S.
Find length of all these ways and choose the smallest one.



The other problem of finding longest path is "Find longest path between any two nodes of a tree". Click any where on this line to see the problem.

 

 

 If you find this blog somewhat helpful, please share & Keep Visiting...:)

Interviewstreet CouponDunia GetEqualSumSubString Problem

Longest Contiguous Equal Sum Substring of length 2N

Interview Question (April 2012)

Problem Statement

Complete the function getEqualSumSubstring, which takes a single argument. 

The single argument is a string s, which contains only non-zero digits. 

This function should print the length of longest contiguous substring of s, 

such that the length of the substring is 2*N digits and the sum of the 

leftmost N digits is equal to the sum of the rightmost N digits.If there 

is no such string, your function should print 0.

Sample Test Cases:

Input #00:
123231

Output #00:
6

Explanation:
1 + 2 + 3 = 2 + 3 + 1.
The length of the longest substring = 6 where the sum of 1st half = 2nd half

Input #01:
986561517416921217551395112859219257312

Output #01:
36

Solution

int getEqualSumSubString(char s[], int n)

{

int sum[N];

sum[0]=s[0];
for(int i=1;i<N;i++)
{
sum[i]=sum[i-1]+s[i];
}

int max=0;
int si=0;
for(int i=1;i<N;i++)
{
for(int j=0;j<i;j++)
{
if((i-j+1)%2==0)
{
int left;
if(j==0)
left=sum[(i-j+1)/2+j-1];
else
left=sum[(i-j+1)/2+j-1]-sum[j-1];
int right=sum[i]-sum[(i-j+1)/2+j-1];

if(left==right)
{
if((i-j+1)>max)
max=(i-j+1);

}
}

}

}

return max;
}

Time Complexity: O(n2)



// If you find this blog somewhat helpful, please share it and Keep visiting..:)

Interviewstreet CouponDunia Palindrome Problem

Interviewstreet CouponDunia Palindrome Problem

Problem Statement

Given a string, determine whether it is palindrome or not. Output 1 for palindrome, and output 0 for not a palindrome.

A palindrome is a string that when reversed is equivalent to its original. Assume case is insensitive and then all non letters are ignored in calculating whether the string is palindrome.

Sample Input:
Dad
Sample Output:
1

Sample Input:
A man, a plan, a canal - Panama!
Sample Output:
1

Solution

#include<iostream>

#define MAX 1000
using namespace std;


int main()
{
 char s[MAX];
 cin>>s;
 int n=strlen(s);

 int i=0,j=n-1;
    while(i<j)
    {

              if(tolower(s[i])!=tolower(s[j]))
              break;
              i++;
              while(tolower(s[i])==s[i]&&(toupper(s[i])==s[i]))
              i++;
              j--;
              while((tolower(s[j])==s[j])&&(toupper(s[j])==s[j]))
              j--;

    }
    if(i>=j)
    cout<<1;
    else
    cout<<0;

}

Time Complexity: O(n)

InterviewStreet CouponDunia Count Pairs Problem: C++ code

CouponDunia Count Pairs Problem

Problem Statement

Given N numbers , [N<=10^5] we need to count the total pairs of numbers 

that have a difference of K. [K>0 and K<1e9]

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured 

to be distinct. 

Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:
3 

Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635
491595254 879792181 1069262793

Sample Output #01:
0 

Solution

#include<iostream>
#include<algorithm>

using namespace std;
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
int n,k;

cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

qsort(a,n,sizeof(int),compare);

int seq=0;
for(int i=0;i<n;i++)
{
int key=a[i]+k;
if(((int*)bsearch(&key,a+i+1,n-i-1,sizeof(int),compare))!=NULL)
seq++;
} 

cout<<seq;

}

Time Complexity : O(nlogn) 

Interviewstreet Unbxd CodeSprint Covering Cities : C++ code

Unbxd CodeSprint Covering Cities 

Unbxd Interview Question

Problem Statement

The country of Maryland is very strange. This country has only one very long straight road and all the cities are located on this road itself. Concretely you can assume the road to be X-axis and and cities as points. So each city i is located at some integer distance xi from the beginning of road.

To provide wireless connection in each of the city, it is required to install some antennas at some point on the road. All the antennas currently available have same coverage range say R, so if an antenna is installed at a point x then it covers all cities that lie in the closed interval [x-R, x+R].

Given the position of all cities on the road, your task is to find the minimum number of antennas required to cover all the cities.

Input Format
First line of input contains two space-separated integers, N and K. N is the number of cities and K is the coverage of any antenna as described in the problem statement. Next line contains a space-separated list of the positions of cities on road.

Output Format
Print an integer which is the required answer for this task.

Sample Input                                                                                

3 1
1 2 3

Sample Output

1

Sample Input

6 2

1 5 4 7 11 8

Sample Output

2                         

Explanation

In the first sample testcase installing just one antenna at point 2 will have coverage of [2-1, 2+1] = [1, 3]. So this will cover all the cities. So just one antenna is sufficient in this case.

Constraints

1 <= N,K <= 1000,000

0 <= x <= 1000,000

All cities are at integer distances.

Antennas can be installed at non-integer distances like 2.5.

Solution Code:

#include<iostream>
#include<set>
using namespace std;

int main()
{

int n,t;
cin>>n>>t;
int r= 2*t;
set<int> s;
set<int>::iterator it;
for(int i=0;i<n;i++)
{

cin>>t;
s.insert(t);

}
it=s.begin();

int count =1;
int f=*it+r+1;

while(s.lower_bound(f)!=s.end())
{
count++;
f=*(s.lower_bound(f))+r+1;

}

cout<<count;

}

Time Complexity: O(n) 


// If you find this blog somewhat helpful, please share it.......&.......Keep visiting..:)

Binary Search Tree : Insert and Search, C code

Implement a Binary Search Tree

// Binary Search Tree - O(logn) for search and insert operation.

// For more info. BST - en.wikipedia.org/wiki/Binary_search_tree 

 

#include<stdio.h>
#include<stdlib.h>
typedef struct treetype
    {
    int value;
    struct tree *right;
    struct tree *left;
    }tree;
tree *root;
int rootvalue;
void insert(tree *node,int x);
void display(tree *node);
void search(tree *node,int x);
int main()
{
int y,x,z;
printf("Enter root value\n");
scanf("%d",&rootvalue);
root=(tree *)malloc(sizeof(tree));
root->value=rootvalue;
root->left=NULL;
root->right=NULL;

while(y!=4)
{
printf("Enter your choice\n");
printf("1.Insert\n2.Display\n3.Search\n4.Exit\n");
scanf("%d",&y);
switch(y)
{
case 1:
printf("Enter the element value\n");
scanf("%d",&x);
insert(root,x);
break;
case 2:
display(root);
break;
case 3:
printf("Which number are u looking for\n");
scanf("%d",&z);
search(root,z);
break;
}
}
}

void insert(tree *node,int x)
{
tree *new;
if(x>node->value)
{
    if(node->right==NULL)
    {
    new=(tree *)malloc(sizeof(tree));
    new->value=x;
    new->left=NULL;
    new->right=NULL;
    node->right=new;
    }
    else
    {
    insert(node->right,x);
    }
}

else
if(x<node->value)
{
    if(node->left==NULL)
    {
    new=(tree *)malloc(sizeof(node));
    new->value=x;
    new->left=NULL;
    new->right=NULL;
    node->left=new;
    }
    else
    {
    insert(node->left,x);
    }
}
else
{
printf("Enter discrete number\n");
}
}

// In-order traversal
void display(tree *node)
{
if(node!=NULL)
{
display(node->left);
printf("%d\t",node->value);
display(node->right);
}
}

// O(logn) approach
void search(tree *node,int x)
{
if(node->value==x)
{
printf("Yes,%d is present in BST\n",x);
}
else if((x>node->value) && (node->right!=NULL))
{
search(node->right,x);
}
else if((x<node->value) && (node->left!=NULL))
{
search(node->left,x);
}
else
{
printf("%d Not found\n ",x);
}
}

Time Complexity 

1. Insertion - O(logn)
2. Search - O(logn)

Queue Implementation : C code

Write all the functions for queue implementation using link-list.

// Queue is based on FIFO(first in first out) order. 
// Time complexity for insertion as well as deletion is O(1).

#include<stdio.h>
#include<stdlib.h>

typedef struct nodetype
    {
    int data;
    struct nodetype *next;
    } node;

typedef struct qtype{
    node *r;
    node *f;
    } qtype ;
qtype *q;
 

qtype *create(struct qtype *q);
qtype *insert(struct qtype *q,int info);
qtype *delete(struct qtype *q);
void display(struct qtype *q);

main()
{
int x,info;
while(x!=5)
{
printf("Enter your choice in formation of queue\n");
printf("1.Create\n2.Insert\n3.Delete\n4.Display\n5.Exit\n");
scanf("%d",&x);
switch(x)
{
case 1:
q=create(q);
break;
case 2:
printf("Enter the element\t");
scanf("%d",&info);
q=insert(q,info);
break;
case 3:
q=delete(q);
break;
case 4:
display(q);
}
}
}



qtype *create(struct qtype *q)
{
q=(struct qtype *)malloc(sizeof(struct qtype));
q->r=NULL;
q->f=NULL;
return(q);
}


qtype *insert(struct qtype *q,int info)
{
struct nodetype *temp;
temp=(node *)malloc(sizeof(node));
temp->data=info;
temp->next=NULL;
if((q->r==NULL) && (q->f==NULL))
{
q->r=q->f=temp;
}
else
{
q->r->next=temp;
q->r=temp;
}
printf("\n%d\n",q->f->data);
printf("%d\n",q->r->data);
return(q);
}


qtype *delete(struct qtype *q)
{
node *t;
t=q->f;
if(q->r==q->f)
{
printf("%d\n",q->f->data);
free(q->f);
//q->f=q->r=NULL;
}
else
{
printf("%d\n",q->f->data);
q->f=q->f->next;
free(t);
}
return(q);
}


void display(struct qtype *q)
{
node *t;
t=q->f;
if(t!=q->r)
{
while(t!=q->r)
{
printf("%d\t",t->data);
t=t->next;
}
printf("%d",t->data);
}
else
{
printf("%d\t",t->data);
}
printf("\n\n");
}

Time Complexity

1.  Insertion - O(1)
2.  Deletion  - O(1)

Find Longest Palindrome in a string : O(n*n) C code

  Given a string S, find the longest palindromic substring in S.

For example,
S = “caba".

The longest palindromic substring is “aba”.

Algorithm:

1. Palindrome mirrors around center and there are 2N-1 such centers in string. The reason is center of palindrome can be in between two letters(for even length string) or the letter itself (for odd length string).
2. Expand a palindrome around its center in both direction and look for maximum possible palindrome (O(n) time).
3. If the length of string is odd, the center would be letter, therefore repeat the step 2 for each letter and update maximum palindrome on the way.
   
4. If the length of string is even, the center would be between two letters, therefore repeat the step 2 for each such center and update the maximum palindrome on the way.
5. Since there are O(N) such centers, time complexity would be O(n²).

// O(n*n) time complexity and O(1) space algorithm
#include<stdio.h>
#include<string.h>

void longestpalindrome(char *str);

int main()
{
char *str = "abacba";
int i;
longestpalindrome(str);
scanf("%d", &i);
}

void longestpalindrome(char *str) {

int length = strlen(str);
printf("%d\n", length);
int i,j,k;
int start,end,max=0,curr;

if(length == 0) {printf("string null"); return;}

if(length%2!=0) { //if string is of odd length
    for(i=0;i<length-1;i++) {
        j=k=i;
        while(j>0 && k<length-1 && str[--j]==str[++k]); 
        curr = k-j+1;
        if(curr > max) {
           max = curr;
           start = j;
           end = k;
        }
    }
    for(i=start;i<=end;i++) printf("%c", str[i]);
    printf("\n");
}
else { //if string is of even length
    for(i=0;i<length-1;i++) {
        if(str[i]==str[i+1]) {
            j=i;
            k=i+1;
            while(j>=0 && k<=length-1 && str[j--]==str[k++]);
                    curr = k-j-1;
                    if(max < curr) {
                       max = curr;
                       start = j+1;
                       end = k-1;
                    }
        }
        for(i=start;i<=end;i++) printf("%c", str[i]);
        printf("\n");
    }
}
}
  
                         
           

// Time Complexity: O(n²)

// Space Complexity: O(1)