CareerCup

To get the next palindrome of a number, the number should be greater than that number and it should be a palindrome. In the below approach,
I. we first make the number palindrome
II.Increment the numbers in the palindrome to make the number bigger than this number.

1) Make the number as a String and ultimately make it to char array for easy manupulations (lets call this char array "ch").
2) Take 2 variables i=0 and j=n-1 and start with ch[i] and ch[j] (where n is the length of the char array) and start copying the left half to the right half to make the number palindrome (remember I above.)
3) See if ch[i]>ch[j]. If it is true, then we don't need to increment anything to make the number bigger(remember II above.). Just copying the left half to the right will be sufficient.
4) However, if ch[i]<ch[j], we need to do some increments to the left half of the array. To be strict, we need to increment the left half of the array only when the middle elements of the array satisfy this condition. (because, even if other elements have ch[i]<ch[j] and for middle elements ch[i]>ch[j], just copying the elements to the right half will be sufficient to make the number bigger).
5) Now, there may be some cases when the element is 9 and it has to be incremented for step II. so, it should be made 0 and 1 is to be carried over to its left element. It may also be 9 and again 1 has to be carried to its left element. So we keep track of this using:

boolean is9Present=false;
            while(i>=0&&ch[i]=='9'){
                is9Present=true;
                ch[i--]='0';
                ch[j++]='0';
            }
            if(is9Present){
                i--;
                j++;

}
6) And then increment the numbers at places i and j and return this array in integer form.

Whole code is displayed below:

public static int getNextImmediatePalindrome(int number) {
        if(number>=0 && number<9)return number+1;
        if(number==9)return 11;
        String num=number+"";
        int n=num.length();
        boolean all9s=false;
        for(int i=0;i<num.length();i++){
            all9s=true;
            if(num.charAt(i)=='9')all9s&=true;
            else{
                all9s=false;
                break;
            }
        }
        if(all9s){
            StringBuilder res=new StringBuilder("");
            res.append(1);
            for(int i=0;i<n-1;i++){
                res.append(0);
            }
            res.append(1);
            return Integer.parseInt(res.toString());
        }
        boolean b=false;
        char ch[]=num.toCharArray();
        int i=0;
        int j=n-1;
        while(i<j){
            if(ch[i]>ch[j]) b=true;
            else if(ch[i]<ch[j]) b=false;

            ch[j--]=ch[i++];
        }
        if(b==false){
            if(n%2==1){
                if(ch[i]=='9') {
                    ch[i] = '0';
                    i--;
                    j++;
                }
            }
            boolean is9Present=false;
            while(i>=0&&ch[i]=='9'){
                is9Present=true;
                ch[i--]='0';
                ch[j++]='0';
            }
            if(is9Present){
                i--;
                j++;
            }
            if(i>=0){
                ch[i]++;
                if(i!=j) ch[j]++;
            }
            else{
                ch[n-1]='1';
            }
        }
        int result=Integer.parseInt(new String(ch));
        return result;

}

This can be done in O(n/2) i.e O(n) time.

My Algo is as follows:

1) Lets say the 0th element is 'a'
2) 1st element can have 'a+1' or 'a-1'
3) 2nd element can have '(a+1)+1','(a+1)-1','(a-1)+1','(a-1)-1'. So 'a+2','a','a-2'
4) Likewise nth element can have 'a-n','a-n-2'..'a+n-2',a+n'.
5) Now lets say the element we want to search is 'x'. So the difference between 'x' and 'a' will be 'x-a'
6) As the difference is 'x-a', x should be in a position where it can fall under the series containing 'a+(x-a)'.
7) 'a+(x-a)' starts from 'x-a'th position.
8) Also note that elements will be even/odd alternatively based on the series above.
9) So we will do a linear search from 'x-a'th position and increment the index by 2.

int findElement(int[] arr,int x){
        int n=arr.length;
        int a=arr[0];
        for (int i = Math.abs(x-a); i < n; i+=2) {
           if(arr[i]==x)return i;
        }
        return -1;
    }

@thelineofcode your thinking is wrong. at 6:00 its is 180 deg but at 6:55, its not 150 deg as the MINUTES hand is less by 5 min(its not HOUR's hand). And you will also have an offset there as the hour's hand wont be pointing at 7 exactly..it will be very close to 7 but not 7. Please watch your clock more carefully

No..if the stream ends,my answer is O(1) because, we would have got the answer already before stream ends..and no need to modify it as more characters are not there

This is very simple!

1. Take a boolean[] ascii=new boolean[256];
2. For each character in stream,make ascii[ascii value of that character]=true;
3. if a new character comes, if(ascii[ascii value of that character]==false) return that character;
else {
ascii[ascii value of that character]=true;
go to next character;
}
Note:- We don't have to store the characters coming in the stream..its just sufficient to check which character is 1st non repeating character

Time Complexity: O(n)
Space Complexity: O(1)

This can be done in a better mathematical way like this:
Input:
1.We are given a Point
2.We are given a triangle with 3 points

First compute the equations of the 3 lines using 2 point formula i.e if two points (x1,y1), (x2,y2) are there,the equation of line passing through them is (x-x1)/(x2-x1)=(y-y1)/(y2-y1)

a.Now we have 3 equations..take any of those 3 equations and let f(x,y)=ax+by+c be that equation(for simplicity..u can substitute the values of a,b,c here).
To find the point (x4,y4) lies on the triangle or not,if u find f(x4,y4)=0 for any equation,that point lies on triangle..otherwise not.
If the point doesn't lie on triangle,then:
To know whether the point lies inside or outside the triangle:
1.The point should lie to the left of one line of triangle and to the right of another line of that triangle.To get this:
b.Now take origin i.e (0,0) and substitute and calculate f(x,y)..so now f(0,0)=0*x+0*y+c=c(c can be +ve or -ve) .If c is +ve,it means origin is right side of that line and if its -ve ,it means origin is left side of that line
c.Now calculate f(x4,y4) where (x4,y4) is the given point .if sign(f(x4,y4))==sign(c)..then they both are on the same side of the line..so if f(x4,y4) and c are both +ve..tehy are on right..if both -ve,they are on left,if c +ve and f(x4,y4) -ve,the point is on the left...
d.if u find the point is left/right of this line,then do this for other 2 lines also
e.if u find the same point is on right/left(respectively) of another line..then its inside the Triangle otherwise its outside the triangle

Thank you avenger ...this is my highest rated answer in Careercup . Thanks for the upvote :)

no..there is no point of missing number in this question..bcoz there will always be n elements from 1..n and an extra number in the range 1..n..so no missing number cases here..

this question assumes that u have all the numbers from 1..n and a repeated number which makes the no.of elements n+1..so ur example is wrong...u might take 1,2,3,3,5,4..(one number is added at end to make no.of elements n+1)..then my algorithm works :)

no..this solution works for duplicate number also..lets say we have numbers 2,3,4,1,4,5 with 4 duplicated and the range is from 1..5 .so after xoring all these numbers with 1..5 we get xor=(2^3^4^1^4^5)^(1^2^3^4^5)=4 which is required :)

The best possible answer is this:

As 1..n numbers are there in which one number is repeated, XOR all the numbers with 1..n which cancels out all the numbers from 1..n and gives the repeated number

public int repeated(int[] arr,int n){
	int xor=0;
	for(int i=0;i<arr.length;i++){
		xor^=arr[i];
	}
	for(int i=1;i<=n;i++){
		xor^=i;
	}
	return xor;
}
       
}

Time Complexity: O(n)

public static int[] populateArray(int[] arr,int n){
int sum=0;
for(int i=1;i<=n;i++){
sum+=i*i;
arr[i-1]=sum;
}
return arr;
}

if this is just finding number of ways,then here is the answer :
1.This is equivalent to x1+x2+x3+...+xn=S where 1<=x1,x2,x3,..xn<=A where x1,x2,..xn are variables whose values are specified on each dice respectively
2.so now let t1=x1-1,t2=x2-1,t3=x3-1,...so now we have (x1-1)+(x2-1)+..+(xn-1)=S-(1+1+..1)=S-n
3.so now we have t1+t2+t3+..+tn=S-n where 0<=t1,t2,..tn<=A-1
4.The number of ways of forming x1+x2+..xr=n where x1,is (n+r-1)C(r-1)(there is a proof :))
5.so now the number of ways = (S-n+n-1)C(n-1)=(S-1)C(n-1) (where nCr=n!/(n-r)!(r!) )

public static int multiple64(int n){
	int mask=1<<31,pos=0;
	int i=0;
	for(i=0;i<32;i++){
		if(mask&n>0)break;
	}
	pos=32-i;
	return (pos>6)?1<<(pos+1):64;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

import java.lang.Math;
public static boolean compute(int A,int n){
	int x=0,y=0,count=0;
	for(x=0;x<pow(A,1/3);x++){
		for(y=0;y<pow(A,1/3),y++){
			if(pow(x,3)+pow(y,3)==A)count++;
		}
	}
	return (count==n)?true:false;
}

This can be done using the method as follows:
1.take an array of sqrt(n)(assuming n is the total # of elements): int[] arr=new arr[sqrt(n)]
2.initially fill it with all the elements of array with the last element of each row
i.e for each x in arr do x=last element of each row in matrix
3.now take int largest=findLargest(arr) where findLargest(arr) computes largest element in the array(this can be done using a max heap and takes O(log(sqrt(N))) and replace the largest element in that array with its previous element in the matrix(i.e if its a[i][j] ,replace it with a[i][j-1])
4.now repeat step 3 "k" times..which gives the Kth Largest element
Time Complexity: O(k*log(sqrt(n)))

iteration or recursion can be used as long as the time complexity of the problem doesn't change..its also not hard to implement recursion ...

public static void joinLL(LL ll1,LL ll2){
		joinLL(ll1.first,ll2.first);
}
public static void joinLL(Node first1,Node first2){
		if(first1==null || first2==null)return;
		Node temp1=first1.next;
		Node temp2=first2.next;
		first1.next=first2;
		if(temp1!=null)first2.next=temp1;
		joinLL(temp1,temp2);	
}

As the question is to find the maximum value..
1.if the vertex value is either 0 or 1 use '+'
2.else use '*' operator..
3.for example if the vertices values are in order 0,4,1,3,2,5..then the max result is ((0+4)+1)*3*2*5
code is as follows:

int result=0;
  for each vertex in polygon P:
        if(vertex.data==0 || vertex.data==1)res+=vertex.data; //considering vertex as a node 
        else res*=vertex.data;
  return res;

@jaydee can u explain how did u get the number of BSTs formed is (2n)!/n!(n+1)! ?

@AAA see my answer above :)

This is a problem of constructing Best Fit line through all the points(so that the line passes through maximum number of points) using Least Squares Method in regression analysis.So that constructed line is the required line through which we can find the slope and y-intercept easily :)

ya and how to calculate probability of a word and output it in programming?

@eugene.yarovoi but how to ensure that the probability of a random number to be selected is 1/k??

Do inOrder Traversal of both the BSTs and u'll get 2 sorted arrays (and elements are unique)..so merge these 2 sorted arrays using Merge Sort and there u go :)

import java.util.Scanner;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author suryakarthik.v
 */
public class Division {
   static  int count=1;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count=1;
        System.out.println("give the dividend");
        double m=sc.nextDouble();
        System.out.println("Give the divisor");
        double n=sc.nextDouble();
        System.out.println("The quotient is "+quotient(m,n));
        System.out.println("The remainder is "+rem(m,n));
        ;
    }
  
    public static int quotient(double m,double n){
        
        double N=n;
        if(m<n)return 0;
        else if(m==n)return 1;
        else{
            for (;n<m-N; n=n+N) {
                count++;
            }
        }
        return count;
    }
    public static double rem(double m,double n){
        return m-n*count;
    }
}

hash table relies on the hash function so that hash function should ensure the uniformity of all the keys into all the hash positions...

This code doesn't ensure that k "should" be in the middle ..if k is greater than all the other numbers,then both k's will be at last which is not required

Sort the string with 3 way quicksort and find duplicate if the value of the current one is equal to the previous one and delete the current one

y/x+x/x(which is ofcourse y/x+1)

Use a Min Priority Queue of n elements..when the stream of integers are coming in,first store the n elements and after it,if (n+1)th element comes,remove the min element from the priority queue and add this new (n+1)th element..so at last we'll have the first top n elements :)

Thanks shyam :)

no..i think the question is to find combinations which equals to one number IN the array..the key=11 above is not valid

whats wrong in directly returning i instead of copying i to j and returning j?

it is sufficient to find the Minimum element of the array as its position tells how many times array is rotated...the code is following

public int rotate(int[] arr){
	int min=arr[0];
	int i;
	for(i=0;i<arr.length;i++){
		if(arr[i]<min){
			min=arr[i];			
		}
	}
	return i;
}