Friday, 26 October 2012

JAVA VS C++


SPOJ Problem Set (classical)

1163. Java vs C ++

Problem code: JAVAC



Apologists of Java and C++ can argue for hours proving each other that their programming language is the best one. Java people will tell that their programs are clearer and less prone to errors, while C++ people will laugh at their inability to instantiate an array of generics or tell them that their programs are slow and have long source code.


Another issue that Java and C++ people could never agree on is identifier naming. In Java a multiword identifier is constructed in the following manner: the first word is written starting from the small letter, and the following ones are written starting from the capital letter, no separators are used. All other letters are small. Examples of a Java identifier are javaIdentifier, longAndMnemonicIdentifier, name, nEERC.


Unlike them, C++ people use only small letters in their identifiers. To separate words they use underscore character ‘_’. Examples of C++ identifiers are c_identifier, long_and_mnemonic_identifier, name (you see that when there is just one word Java and C++ people agree), n_e_e_r_c.


You are writing a translator that is intended to translate C++ programs to Java and vice versa. Of course, identifiers in the translated program must be formatted due to its language rules — otherwise people will never like your translator.


The first thing you would like to write is an identifier translation routine. Given an identifier, it would detect whether it is Java identifier or C++ identifier and translate it to another dialect. If it is neither, then your routine should report an error. Translation must preserve the order of words and must only change the case of letters and/or add/remove underscores.


Input

The input file consists of several lines that contains an identifier. It consists of letters of the English alphabet and underscores. Its length does not exceed 100.


Output

If the input identifier is Java identifier, output its C++ version. If it is C++ identifier, output its Java version. If it is none, output 'Error!' instead.


Example

Input:
long_and_mnemonic_identifier
anotherExample
i
bad_Style

Output:
longAndMnemonicIdentifier
another_example
i
Error!

NO NEED TO COPY THE SOLUTION :) 
THERE ARE SOME TEST CASES OVER THEM ALL AND GET ACC.
_java =error
java_=error
ja__va=error
Java=error
pnlO_kr=error
name=name
j_aVa ->Error
kI_ng ->Error
heEl_lo ->Error
A=error 
sdf_Add=error

SOLUTION--

#include
#include
int main()
{
    char str[110];
    int i,k,flag=0,d=0;
    while((scanf("%s",str))!=EOF)
    {
        flag=0;
        k=strlen(str);
        d=str[0];
        if(str[0]=='_'||str[k-1]=='_'||(d>=60&&d<=95))
        {
            printf("Error!");
            goto end;
        }
        for(i=0;i
        {
            d=str[i];
            if(str[i]=='_'&&str[i+1]=='_')
            {
                printf("Error!");
                goto end;
            }
            //printf("%d\n",d);
            if(str[i]=='_')
            {
                if(flag==2){
                    printf("Error!");
                    goto end;
                }
                else
                    flag=1;
            }
            if(d>=65&&d<=90)
            {
               // prictf("%c ",str[i]);
                if(flag==1)
                {
                    printf("Error!");
                    goto end;
                }
                else
                flag=2;
            }
        }
        for(i=0;i
        {
            d=str[i];
            //printf("%d \n",d);
            if(d==95)
            {
                i=i+1;
                //d=d;
                d=str[i];
                if(d==95)
                {
                    printf("Error!");
                    goto end;
                }
                else{
                str[i]=d-32;
                printf("%c",str[i]);
                }
            }
            else if(d>=65&&d<=90)
            {
                printf("_");
                //d=d;
                str[i]=d+32;
                printf("%c",str[i]);
            }
            else
            printf("%c",str[i]);
        }
        end :
        printf("\n");
    }
    return 0;
}

Thursday, 25 October 2012

CUBE FREE NUMBERS


SPOJ Problem Set (classical)

9032. Cube Free Numbers

Problem code: CUBEFR

A cube free number is a number who’s none of the divisor is a cube number( A cube number is a cube of a integer like 8(2*2*2) , 27(3*3*3) ). So cube free numbers are 1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18 etc(we will consider 1 as cube free). 8,16,24,27,32 etc are not cube free number. So the position of 1 among the cube free numbers is 1, position of 2 is 2, 3 is 3 and position of 10 is 9. Given a positive number you have to say if its a cube free number and if yes then tell its position among cube free numbers.

Input:

First line of the test case will be the number of test case T(1<=T<=100000) . Then T lines follows. On each line you will find a integer number n(1<=n<=1000000).

Output:

For each input line, print a line containing “Case I: ”, where I is the test case number. Then if it is not a cube free number then print “Not Cube Free”. Otherwise print its position among the cube free numbers.

Sample Input:

10

1

2

3

4

5

6

7

8

9

10

Sample Output:

Case 1: 1

Case 2: 2

Case 3: 3

Case 4: 4

Case 5: 5

Case 6: 6

Case 7: 7

Case 8: Not Cube Free

Case 9: 8

Case 10: 9


SOLUTION---


#include
#define max 1000002
int main()
{
    //calculating non free cude numbers and store in array b //
    static int b[max];
    static int a[max];
    int i,j,k,t,num,p;
    for(i=2;i
    {
        k=i*i*i;
        if(k>max)
        break;
        else{
        for(j=k;j
            b[j]=1;
          }
        }
    }
    j=2,p=0;
    //storing value of cube frre numbers in array a //
    for(i=2;i
    {
        if(b[i]!=1)
        {
            a[j]=i;
            j=j+1;
        }
    }
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d",&num);
        if(num==1)
            printf("Case %d: 1\n",i);
        else if(b[num]==1)
            printf("Case %d: Not Cube Free\n",i);
        else
        {
            int mid,lb=2,ub=j-1; //here j-1 is the total size of array a//
            // binary search of cube free number in array a //
            while(lb<=ub)
            {
                mid=(lb+ub)/2;
                if(a[mid]==num)
                break;
                else if(a[mid] >num)
                ub=mid-1;
                else
                lb=mid+1;

            }
            printf("Case %d: %d\n",i,mid);
        }
    }
    return 0;
}


Monday, 22 October 2012

AMAZON INTERVIEW QUESTIONS


AMAZON INTERVIEW QUESTION--
QUESTION--
You have an array of size n with values ranging from 1 to n. Exactly one number is missed and one number is repeated. Find missing number and Repeated number.

SOLUTION --


#include
int main()
{
    int n,i;
    scanf("%d",&n);
    int arr[n];
    for(i=0;i
        scanf("%d",&arr[i]);
   int sum_of_digit=0;
   int sum_of_sqdigit=0;
    for(i=0;i
    {
        sum_of_digit+=arr[i];
        sum_of_sqdigit+=arr[i]*arr[i];
    }
    int sum_of_digit1=(n*(n+1))/2;
    int sum_of_sqdigit1=(n*(n+1)*(2*n+1))/6;
    int repeat_value=((sum_of_sqdigit-sum_of_sqdigit1)/(sum_of_digit-sum_of_digit1)+(sum_of_digit-sum_of_digit1))/2;
    int miss_value=((sum_of_sqdigit-sum_of_sqdigit1)/(sum_of_digit-sum_of_digit1)-(sum_of_digit-sum_of_digit1))/2;
    printf("repeated valu=%d\nmiss value=%d",repeat_value,miss_value);
    return 0;
}

Saturday, 20 October 2012

TRANSFORM THE EXPRESSION

PROBLEM STATEMENT


Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.
Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*



SOLUTION----



#include
#include

//using char array//
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    char str[500];
    char postfix[500];
    char stack[500];
    scanf("%s",str);
    int k=strlen(str);
    int i,j=0,d,m=-1;
        for(i=0;i
        {
            d=str[i];
            if(d>=97&&d<=122)
            {
                postfix[j]=str[i];
                j=j+1;
            }
            else if(str[i]!=')')
            {
                m=m+1;
                stack[m]=str[i];
           
            }
            else
            {
                while(stack[m]!='(')
                {
                    postfix[j]=stack[m];
                    j=j+1;
                    m=m-1;
                }
                m=m-1;
            }
        }
        for(i=0;i
            printf("%c",postfix[i]);
        printf("\n");
    }
    return 0;
}


STACK AND QUEUE

IMPLEMENTING  STACK

class stack{
             Node top;
             Node pop(){
                        if(top!=null){
                             object item=top.data;
                             top=top.next;
                             return item;
                        }
                        return null;
            }
void push(object item){
                    Node t=new Node(item);
                    t.next=top;
                    top=t;
             }
}

IMPLEMENTING A QUEUE

class Queue{
               Node first,last;
              void enqueue(object item){
                      if(!=first){
                      back=new Node(item);
                       first=back;
                      }
                      else{
                       back.next=new NOde(item);
                       back=back.next;
                       }   
           }

Node dequeue(Node n){
                           if(front!=null)
                           {
                                  object item=front data;
                                   front=front.next;
                                   return next;
                            }
                            return null;
}

Tuesday, 16 October 2012

CIRCULAR LINK LIST DELETION


CIRCULAR LINK LIST DELETION 

#include
#include
int main()
{

    struct node{
        int data;
        struct node *next;
        }*head;
        struct node *temp,*temp1,*temp2;
        head=NULL;
        int num,i,n;
        printf("enter number of nodes in link list=");
        scanf("%d",&num);
        for(i=0;i
        {
            scanf("%d",&n);
            if(head==NULL)
            {
                head=malloc(sizeof(struct node));
                head->data=n;
                temp=head;
            }
            else{
                temp->next=malloc(sizeof(struct node));
                temp->next->data=n;
                temp=temp->next;
            }
        }
        temp->next=head;
        temp=head;

        int pos;
        temp=head;
        printf("enter node no. for deletion=");
        scanf("%d",&pos);
        if(pos==1)
        {
            temp2=head;
            while(temp->next!=head)
            {
                temp=temp->next;
            }
            head=head->next;
            temp->next=temp2->next;
            free(temp2);
        }
        else{
            for(i=1;i
            {
                temp1=temp;
                temp=temp->next;
            }
            temp1->next=temp->next;
            free(temp);
        }
        temp=head;
        // AFTER DELETION//
        for(i=0;i<15 font="font" i="i">
            {
                printf("%d\n",temp->data);
                temp=temp->next;
            }
            return 0;
}

INVERSION COUNT


INVERSION COUNT (6256)


Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

Example

Input:

2

3
3
1
2

5
2
3
8
6
1


Output: 

2
5

SOLUTION----


#include
void mergesort(int i,int j);
void merge(int i,int j);
long long a[200009],b[200009];
long long c;
int main()
{
        int t,n,i;
        scanf("%d",&t);
        printf("\n");
        while(t--) {
                scanf("%d",&n);
                for(i=0;i
                scanf("%lld",&a[i]);
                c=0;
                mergesort(0,n-1);
                printf("%lld\n",c);
                printf("\n");
                }
        return 0;       
}

void mergesort(int i,int j)
{
        if(i>=j) 
                return;
        else {
                int mid=(i+j)/2;
                mergesort(i,mid);
                mergesort(mid+1,j);
                merge(i,j);
                }
        return;
}

void merge(int i,int j)
{
        int mid=(i+j)/2,k=i;
        int l,r;
        l=i;r=mid+1;
        while(l<=mid && r<=j) {
                if(a[l]
                        b[k++]=a[l++];
                else {
                        c=c+mid-l+1;
                        b[k++]=a[r++];
                        }
                }
        if(l>mid)
                while(r<=j)
                        b[k++]=a[r++];
        else if(r>j)
                while(l<=mid)
                        b[k++]=a[l++];
        for(l=i;l<=j;l++)
                a[l]=b[l];
}


AMAZON INTERVIEWS



coding questions amazon 2011
They gave to us (NIT CALICUT) this year
here are the coding ques...

1) if there is a singly linked list the we should reverse the list
upto a certain number passed in agrument.

eg..

Node * reverse_upto_num(Node* head, int k)
is the function.. we had to complete it... such tht first K elements
should get reversed.

this is the sample they gave us
1>2->3->4->5    is the list then for k=3.. output should be
3->2->1->5->4


2) for a string we should be able to find all possible permutations of
characters of certain length passed through the function as argument
in lexicographic order.

Permute_string( string, int k)
{
}
eg. if string is :  AS  and k=2
 then function should give  following as output.

aa
as
sa
ss




amazon paper internship paper 2012
internship paper-------
amazon paper--
1) WAP for finding first unique character in a given string.
2)WAP for finding if the binary tree given is BST or not.

apti-
1) given post order it was asked which of the option is possible inorder
2) FIFO policy is there and 4 pages can remain in main memory...if
pages are scanned from 1 to 100 and then in reverse order ,than no. of
page faults which occur?
3) given 2's complement of a no. .find the 2's complement of 8*(no.)
4) double power(double base,int exponent)
{
if (exponent==0)
return 1;
else if(exponent%2==0)
power(base*base,exponent/2);
else
power(base*base,exponent/2)*
base;
}
how many multiplications happen for power(5.0,12)?
5) int x=1;
int i=1;
while(x>=1000)
do
x=2x;
i=i+1;
end
find value of i after the loop ends.
6)
#define a 20
void main()
{
printf("%d..",a);
foo();
printf("%d",a);
}
foo()
{
#undef a
#define a 50
}
find output.
7)for n players in chess knockout tournament ,how many matches r
required for determining the winner.
8)question of microprocessor ...details about 3 microprocessor where given..
9)two person 20 miles apart move toward each other at speed of 40
miles/hr and 30 miles/hr. find distance b/w them 1 min before they
collide.
10) a plane fires 4 rockets which has probability of hitting the enemy
as 0.7,0.6,0.4,0.5..
find the probability of hitting the enemy when 4 rockets are shot.
11) one question on when hashing is not a good thing to do...answer
was when range query is there...

Friday, 12 October 2012

HUBULULLU





HUBULULLU  SPOJ SOLUTION 

After duelling in quake (a multiplayer game), Airborne and Pagfloyd decide do test themselves out in another game called Hubulullu. The rules of the game are as follows:
N wooden pieces (marked with numbers 1 to N) are placed in a transparent bottle. On his turn the first player takes out some piece (numbered x) and all the pieces numbered by divisors of x that are present in the transparent bottle. The second player picks another number and removes it and its divisors as well. Play continues in an alternating fashion until all pieces have been removed from the bottle. The player who removes the last piece from the bottle wins the game.
Both players play optimally. Given N (the number of wooden pieces in the transparent bottle initially) and thename of the player who starts the game, determine the winner.
Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line containing two integers separated by a single space. The first integer is N (1 <= N <= 2000000000), indicating the number of pieces, and the second integer indicates the player who starts - "0" means Airborne starts the game and "1" means Pagfloyd starts the game (quotes for clarity).
Output

For each test case output one line containing either "Airborne wins." or "Pagfloyd wins."
For each N, it's possible to determine a winner if both players play optimally.
Example

Input:
1
1 0

Output:
Airborne wins.

SOLUTION----


#include
int main()
{
        int t,a,b;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%d %d",&a,&b);
                if(b==0)
                        printf("Airborne wins.\n");
                else
                        printf("Pagfloyd wins.\n");
        }
        return 0;
}
   

DOTA HEROES


DOTA HEROES



Problem Description:

                Defence Of The Ancients(DOTA) is one of the most addictive online multiplayer games. There are n heroes in our team and our motto is to conquer the opponent’s empire. To safeguard their empire the opponents had constructed m towers on the path between them and us. If one or more heroes get into the sight of a tower, then the tower does D amount of damage to one of those heroes at that instant i.e. one of the heroes’ health decreases by D. Any hero will die if his health H <=0.  Once a tower attacks one of the heroes at that instant, all of those at that instant get out of its sight. Find whether all of the heroes in our team can reach the opponent’s empire alive.



Input Specification:

The first line consists of one integer t representing the number of test cases. For each test case, the first line consists of three integers n, m and D, the number of heroes, number of towers and the amount of Damage respectively. The next n lines consist of an integer representing the health of respective hero.

Output Specification:

Just a word “YES” if we can reach the opponent’s empire alive, else “NO”.

Input Constraints:

1<=t<=500

1<=n<=500

1<=m<=n

1<=D,H<=20000


Sample Input:

3

6 3 400

500

500

500

500

500

500



6 5 400

800

800

801

200

200

200



6 3 400

401

401

400

200

400

200



Sample Output:

YES

NO 

NO

SOLUTION-----


#include
#include
using namespace std;
int main()
{
        int t,n,m,D,flag,i,j;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%d %d %d",&n,&m,&D);
                int arr[n];
                for(i=0;i
                {
                        scanf("%d",&arr[i]);
                }
                sort(arr,arr+n);
                i=n-1,flag=0;
                for(j=0;j
                {
                        if(arr[i]>D)
                        {
                                arr[i]=arr[i]-D;
                                while(arr[i]>D)
                                {
                                        arr[i]=arr[i]-D;
                                
                                        j=j+1;
                                }
                        }
                        else
                        {
                                flag=1;
                        }
                        i=i-1;
                }
                if(flag==0)
                        printf("YES\n");
                else
                        printf("NO\n");
        }
        return 0;
}               


Wednesday, 10 October 2012

ARRANGE THE LINK LIST


input linked list is : 1->9->3->8->5->7->7

do you see any pattern in this input ?

odd placed nodes are in increasing order and even placed nodes are in decreasing order.
write a code that gives the the following linkedlist:
output linked list should be 1->3->5->7->7->8->9  

SOLUTION USING DOUBLY LINK LIST--
#include
#include
int main()
{
    struct node
    {
        int data;
        struct node *prev;
        struct node *next;
    }*head;
    struct node *temp,*end,*temp1;
    head=NULL;
    int num,n,i;
    printf("enter nodes n link lis=");
    scanf("%d",&num);
    for(i=1;i<=num;i++)
    {
        scanf("%d",&n);
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=n;
            temp=head;
            temp->prev=NULL;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->prev=temp;
            temp->next->data=n;
            temp=temp->next;
        }
    }
    temp->next=NULL;
    end=temp;
    temp=head;
    i=1;
    while(temp!=NULL)
    {
        if(i%2!=0){
        printf("%d ",temp->data);
        }
        temp=temp->next;
        i=i+1;
    }
    temp1=end;
    i=num;
    while(temp1!=NULL)
    {
        if(i%2==0){
        printf("%d ",temp1->data);
        }
        temp1=temp1->prev;
        i=i-1;
    }
    return 0;
}


USING SINGLE LINK LIST----

 link all odd nodes one after other and reverse all even nodes while traversing for odd nodes. Finally link tha last odd node with the last even node;

Tuesday, 9 October 2012

SWAP THE NODE


Written exam (Amazon, Bangalore)

Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.

Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8


SOLUTION USING DOUBLY LINK LIST


#include
#include
int main()
{
    struct node
    {
        int data;
        struct node *next;
        struct node *prev;
    }*head;
    int num,i,k,c,n;
    struct node *temp,*temp1,*temp2,*temp3,*end;
    printf("enter number of link list");
    scanf("%d",&num);
    scanf("%d",&k);
    head=NULL;
    for(i=1;i<=num;i++)
    {
        scanf("%d",&n);
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=n;
            temp=head;
            temp->prev=NULL;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->prev=temp;
            temp->next->data=n;
            temp=temp->next;
        }
    }
    temp->next=NULL;
    end=temp;
    temp1=end;
    temp=head;
    for(i=1;i<=num;i++)
    {
        if(i==k)
        {
            int c=temp->data;
            temp->data=temp1->data;
            temp1->data=c;
        }
        else
        {
            temp=temp->next;
            temp1=temp1->prev;
        }
    }
    temp=head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    return 0;
}

SOLUTION USING SINGLE LINK LIST


#include  
#include
int main()
{
    struct node
    {
        int data;
        struct node *next;
    }*head;
    head=NULL;
    int i,num,k,n;
    struct node *temp,*temp1,*temp2;
    printf("enter the number=");
    scanf("%d",&num);
    scanf("%d",&k);
    for(i=1;i<=num;i++)
    {
        scanf("%d",&n);
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=n;
            temp=head;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->data=n;
            temp=temp->next;
        }
    }
    temp->next=NULL;
    temp=head;
    i=1;
    while(temp!=NULL)
    {
        if(i==k)
        {
            temp1=temp;
            temp=temp->next;
        }
        else if(i==num-k-1)
        {
            temp2=temp;
            temp=temp->next;
        }
        else
        {
            temp=temp->next;
        }
        i=i+1;
    }
    temp=temp1;
    int c=temp->data;
    temp=temp2;
    int d=temp->data;
    temp=temp1;
    temp->data=d;
    temp=temp2;
    temp->data=c;
    temp=head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    return 0;
}