gulusworld1989
BAN USER- 2of 2 votes
AnswersYou are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal. (Imagine that such division is possible for the input array and array size is even)
- gulusworld1989 in United States for Android| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven an integer, find the next highest and next lowest integers, with equal number of 1s in their binary representation as the original number.
- gulusworld1989 in United States for Android| Report Duplicate | Flag | PURGE
Google Intern Algorithm
a few corrections
void nearestRectangle(int n)
{
if(n<0)
return;
int x,y;
x=y=(int)Math.sqrt(n+2);
while(x*y<n || x*y>n+2)
{
if(x*y<n)
y++;
else
x--;
}
System.out.println("x is "+x+" and y is "+y);
}
void nearestRectangle(int n)
{
if(n<=0)
return;
int x,y;
x=y=Math.sqrt(n+2);
while(x*y<n || x*y>n+2)
{
if(x*y<n)
y++;
else
x--;
}
System.out.println("x is "+x+" and y is "+y);
}
@ Tulley
thanks for finding my mistake.
I have understood the problem and corrected it......
Now try this function
static int binarySearch(int[] a,int k)
{
if(a.length==0 || a==null)
return -1;1
int s=0,e=a.length-1;
while(s<=e)
{
int mid=(s+e)/2;
if(a[mid]==k)
return mid;
else if(k>a[mid])
{
if(a[s]>a[mid] && a[s]<=k)
e=mid-1;
else
s=mid+1;
}
else
{
if(a[e]<a[mid] && a[e]>=k)
s=mid+1;
else
e=mid-1;
}
}
return -1;
}
@amartyakhan
Have u run my code. ? If no then u r welcome to run the code and test for sample inputs.
I have tested it and it works for every case.
waiting for ur response ......
Sorry for typo in the time complexity above.
Actually it is O(log n)
Here is the tested working code.
I am doing binary search with complexity of O(nlog n).
Feedback are welcome.
import java.util.*;
class RotatedSearch
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter size of the array");
int n=sc.nextInt();
int a[]=new int[n];
System.out.println("Enter the elements of the sorted but rotated array");
for(int i=0;i<a.length;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter the element to find");
int k=sc.nextInt();
n=binarySearch(a,k);
System.out.println(k+" is present at "+n+"th index of the array");
}
static int binarySearch(int[] a,int k)
{
if(a.length==0 || a==null)
return -1;
int s=0,e=a.length-1;
while(s<=e)
{
int mid=(s+e)/2;
if(a[mid]==k)
return mid;
else if(k>a[mid])
{
if(a[s]>a[mid] && a[s]<k)
e=mid-1;
else
s=mid+1;
}
else
{
if(a[e]<a[mid] && a[e]>k)
s=mid+1;
else
e=mid-1;
}
}
return -1;
}
}
Use partitioning method to find the kth smallest element.
Here is the tested working code.
Any feedback are most welcome.
import java.util.*;
class KthSmallest
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter size of the array");
int n=sc.nextInt();
int a[]=new int[n];
System.out.println("Enter the elements of the array");
for(int i=0;i<a.length;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter the order of smallest element to find");
int k=sc.nextInt()-1;
System.out.println((k+1)+"th smallest element of the array is "+ findK(a,k));
}
static int findK(int a[],int k)
{
if(k>a.length-1 || a==null)
{
System.out.println("Error in input");
return Integer.MAX_VALUE;
}
int start=0,end=a.length-1;
int pivot=-1;
while(pivot!=k)
{
pivot=partition(a,start,end);
if(pivot<k)
start=pivot+1;
else
end=pivot-1;
}
return a[k];
}
static int partition(int a[],int start,int end)
{
int pivot=(start+end)/2;
int sp=start;
swap(a,pivot,end);
for(int i=start;i<end;i++)
{
if(a[i]<a[end])
{
swap(a,sp,i);
sp++;
}
}
swap(a,sp,end);
return sp;
}
static void swap(int a[],int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
}
there were some special cases in the previous post.
This is the correct code which works for every case.
//find next palindrome of a number. eg 125 next palindrome is 131
import java.util.*;
class NextPalindome
{
public static void main(String args[])
{
System.out.println("Enter a number ");
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
int y=nextP(x);
System.out.println("Next Palindrome of "+x+" is "+y);
}
static int nextP(int x)
{
if(x<0)
return -1*nextP(-x);
else if(x<10)
return x;
ArrayList<Integer> a=new ArrayList<Integer>();
boolean inc=false;
while(x>0)
{
a.add(x%10);
x=x/10;
}
int l=0,u=a.size()-1;
while(l<u)
{
if(a.get(u)>a.get(l))
inc=true;
else if(a.get(u)<a.get(l))
inc=false;
a.set(l,a.get(u));
l++;
u--;
}
int b=(a.size()-1)/2,f=a.size()/2;
while(!inc)
{
if(b<0)
return augment(a.size());
int s=a.get(f)+1;
if(s<10)
{
a.set(b,s);
a.set(f,s);
inc=true;
}
else
{
a.set(b,0);
a.set(f,0);
b--;
f++;
}
}
return makeInt(a);
}
static int makeInt(ArrayList<Integer> a)
{
int x=0;
for(int i=a.size()-1;i>=0;i--)
x=x*10+a.get(i);
return x;
}
static int augment(int n)
{
int x=1;
for(int i=0;i<n;i++)
x=x*10;
return x+1;
}
}
Here is the fully working code. It has time and space complexity of O(n) where n is the no. of digits of the number.
//find next palindrome of a number. eg 125 next palindrome is 131
//find next palindrome of a number. eg 125 next palindrome is 131
import java.util.*;
class NextPalindome
{
public static void main(String args[])
{
System.out.println("Enter a number ");
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
int y=nextP(x);
System.out.println("Next Palindrome of "+x+" is "+y);
}
static int nextP(int x)
{
if(x<0)
return -1*nextP(-x);
else if(x<10)
return x;
ArrayList<Integer> a=new ArrayList<Integer>();
boolean inc=false;
while(x>0)
{
a.add(x%10);
x=x/10;
}
int l=0,u=a.size()-1;
while(l<u)
{
if(a.get(u)>a.get(l))
inc=true;
else if(a.get(u)<a.get(l))
inc=false;
a.set(l,a.get(u));
l++;
u--;
}
int b=(a.size()-1)/2,f=a.size()/2;
while(!inc)
{
if(b<0)
return augment(a.size());
int s=a.get(f)+1;
if(s<10)
{
a.set(b,s);
a.set(f,s);
inc=true;
}
else
{
a.set(b,0);
a.set(f,0);
b--;
f++;
}
}
return makeInt(a);
}
static int makeInt(ArrayList<Integer> a)
{
int x=0;
for(int i=a.size()-1;i>=0;i--)
x=x*10+a.get(i);
return x;
}
static int augment(int n)
{
int x=1;
for(int i=0;i<n;i++)
x=x*10;
return x+1;
}
}
Please let me know in case of any problems.
- gulusworld1989 December 14, 2010This is the simple code in java which 100% works
node convert(node n)
{
if((n==null)||(n.left==null && n.right==null))
return n;
node n1=convert(n.left);
node n2=convert(n.right);
node n3=n1;
while(n3.next!=null)
n3=n3.next;
n3.right=n;
n.left=n3;
n.right=n2;
n2.left=n;
return n1;
}
import java.util.*;
class Pale
{
static int st=-1,ed=-1;
public static void main(String args[])
{
Scanner sc= new Scanner(System.in);
sc.useDelimiter("\n");
System.out.println("Enter a string");
String s= sc.next();
char c[]=new char[s.length()];
s.getChars(0,s.length(),c,0);
findMaxPal(c);
}
static void findMaxPal(char[] c)
{
int max=0,s=-1,e=-1;
for(int i=0;i<c.length-2;i++)
{
if(c[i]==c[i+1])
{
int m=findPal(i,i+1,c);
if(m>max)
{
max=m;
s=st;
e=ed;
}
}
if(c[i]==c[i+2])
{
int m=findPal(i,i+2,c);
if(m>max)
{
max=m;
s=st;
e=ed;
}
}
}
if(max!=0)
{
System.out.println("max palendrome is "+max);
for(int i=s;i<=e;i++)
System.out.print(c[i]);
System.out.println();
}
else
{
System.out.println("The string has no palendrome\n");
}
}
static int findPal(int s,int e,char[] c)
{
while(s-1>=0 && e+1<=c.length-1 && c[s-1]==c[e+1])
{
s--;
e++;
}
st=s;
ed=e;
return e-s+1;
}
}
use the method getBytes() of the String class to serialize the string
byte b[]=new String().getBytes();
yes i have tested ...it works awesome
- gulusworld1989 October 28, 2010Can anyone explain me how it is
(m-1 + n-1)C(m-1) OR (m-1 + n-1)C(n-1)
can anyone elaborate the question ?
- gulusworld1989 October 24, 2010I guess it will be (1/10)^9
- gulusworld1989 October 24, 2010Answer is simple.
Let the point be (x3,y3)
Find the equation of the line.
put x=x3 and find y from the equation of the line.
if y3>y
then point is above the line
if y3 < y
point is below
if y3=y
point is on the line
int count=0;
void countNonleaf(node root)
{
if(root.left==null && root.right==null)
return ;
count++;
countcountNonleaf(root.left);
countcountNonleaf(root.right);
}
Here is the BFS approach
int findMinDeapth(node root)
{
Queue<root> q1=new LinkedList<node>();
Queue<root> q2=new LinkedList<node>();
q1.add(root);
int depth=0;
while(!q1.isEmpty() || !q2.isEmpty())
{
while(!q1.isEmpty())
{
node n=q1.remove();
if(n.left == null && n.right == null)
return depth;
q2.add(n.left);
q2.add(n.right);
}
depth++;
while(!q2.isEmpty())
{
node n=q2.remove();
if(n.left == null && n.right == null)
return depth;
q1.add(n.left);
q1.add(n.right);
}
}
}
Here is the recursive implementation.
int min=Integer.MAX_VALUE;
void findMinDeapth(node root,int depth)
{
if(root==null)
{
if(depth<min)
min=depth;
return;
}
findMinDeapth(root.left,depth+1);
findMinDeapth(root.right,depth+1);
}
But i think BFS will be more efficient .
- gulusworld1989 October 21, 2010int delete (node** head,int k)
{
if(*head->val == k)
{
node* temp=*head;
*head=*head->next;
free(temp);
return 0;
}
node **n=head;
while(*n->next->val!=k && *n->next)
{
*n=*n->next;
}
if(*n->next)
{
node* temp=*n->next;
*n->next=*n->next->next;
free(temp);
return 0;
}
return -1;
}
srry previous code was messy . here is the clear code
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.00001)
{
if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;
}
return mid;
}
It's a simple one
Use newton-raphson's method for finding square root.
import java.util.*;
class SQRT
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter a positive no. to find sqrt");
float n=sc.nextFloat();
if(n<0)
{
System.out.println("negative don't have square roots");
System.exit(0);
}
float y=sqrt(n);
System.out.println("sqrt is "+y);
}
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.00001)
{
if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;
}
return mid;
}
}
it works dude
i have called this method in main method as follows
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter a string ");
String s=sc.next();
ArrayList<String> a=subset(s);
Object ss[]=a.toArray();
System.out.println("All the substrings are ");
for(Object o:ss)
System.out.println(o);
}
the following is the output:
Enter a string
abc
All the substrings are
a
b
ab
c
ac
bc
abc
Press any key to continue . . .
how can we do it without using extra space as the space complexity here is O(m*n)
Does anybody have an idea ?
This 100% works.
import java.util.Scanner;
class FindWay
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the x position");
int m=sc.nextInt();
System.out.println("Enter the y position");
int n=sc.nextInt();
int ways=findWays(m,n);
System.out.println("No. of ways are "+ways+"\n");
}
static int findWays(int m,int n)
{
if(m==0 || n==0)
{
if(m==0)
return n;
else
return m;
}
int a[][]=new int[m+1][n+1];
a[0][0]=0;
for(int i=1; i<m+1; i++)
a[i][0]=1;
for(int j=1; j<n+1; j++)
a[0][j]=1;
for(int i=1;i<m+1;i++)
{
for(int j=1;j<n+1;j++)
{
a[i][j]=a[i][j-1]+a[i-1][j];
}
}
return a[m][n];
}
}
class Fibb
{
public static void main(String args[])
{
System.out.println("Enter the rank of fibonacci no. to find ");
int n=new java.util.Scanner(System.in).nextInt();
System.out.println(n+"th fib. no. is "+fibon(n,-1,-1));
}
static int fibon(int n,int s1,int s2)
{
if(n<1)
{
System.out.println("Fib no. does not exist");
return -1;
}
if(s1==-1 && s2==-1)
{
if(n==1)
return 0;
if(n==2)
return 1;
s1=1;
s2=0;
}
if(n==2)
return s1;
else
return fibon(n-1,s1+s2,s1);
}
}
int fibon(int n,int s1,int s2)
{
if(s1==-1 && s2==-1)
{
if(n==1)
return 0;
if(n==2)
return 1;
s1=1;
s2=0;
}
if(n==1)
return s1+s2;
else
return fibon(n-1,s1+s2,s1);
}
suppose i gotta find 5th fibonacci term.
then call this function as fibon(5,-1,-1) and its done.
Here we are using s1 and s2 for backtracking so that we can avoid the recalculation of those terms...
Bandwidth- no. of processes completing exection at unit time.
Latency-The time gap between submission and completion of a process.
For an ideal system bandwidth should be infinity and latency should be zero.
gud work chennavarri
- gulusworld1989 October 19, 2010We can do like this in java
public static ArrayList<String> permutation(String s)
{
if(s==null)
return null;
if(s.length()<=1)
{
ArrayList<String> a=new ArrayList<String>();
a.add(s);
return a;
}
char c=s.charAt(0);
ArrayList<String> a2=permutation(s.substring(1,s.length()));
for(String s2:a2)
{
for(int i=0;i<s2.length()+1;i++)
{
String s3=insert(s2,i,c);
a.add(s3);
}
}
return a;
}
public static String insert(String s,int i,char c)
{
String s1=s.substring(0,i);
String s2=s.substring(i);
String s3=s1+c+s2;
return s3;
}
Dear sushantmax88
Do read the question carefully before commenting.It is clearly mentioned that space should be O(1). But here you are creating a BST which will take O(n) space.
Besides your algo gonna be of time O(n + log n) because first u will make a scan of the array and insert into bst. Scanning wil take O(n) and insertion O(log n).
Does anyone else have soultion ?
public static int getNoAdjMaxSum(int[] a)
{
assert(a.length != 0);
if (a.length == 1)
return a[0];
int sum1=0,sum2=0,i1=-1,i2=-1;
if(a[0]>0)
{
sum1=a[0];
i1=0;
}
for (int i=1; i < a.length; i++) {
if(a[i]>0)
{
if(i-i1 ==1)
{
int add=sum1-a[i1]+a[i];
if(i-i2!=1)
{
sum2+=a[i];
i2=i;
}
if(add>sum2)
{
sum2=add;
i2=i;
}
}
else
{
sum1+=a[i];
i1=i;
}
if(sum2>sum1)
{
int temp=sum1;
sum1=sum2;
sum2=temp;
temp=i1;
i1=i2;
i2=temp;
}
}
}
return sum1;
}
Yeah i understand what u wanna say . But here the time complexity will be O(n log k).
You will traverse the whole list once i.e. O(n) and will put every element in the max heap of size k which is O(log k).
So the overall becomes O(n log k).
public static ArrayList<String> subset(String s)
{
ArrayList<String> a=new ArrayList<String>();
if(s.length()==0||s==null)
return null;
if(s.length()==1)
{
a.add("");
a.add(s);
return a;
}
char c=s.charAt(0);
ArrayList<String> a2=subset(s.substring(1,s.length()));
for(String s2:a2)
{
a.add(s2);
a.add(c+s2);
}
return a;
}
boolean isMirrorImage(node n1,node n2)
{
if(n1==null && n2==null)
return true;
else if(n1==null || n2==null)
return false;
else if(n1.val != n2.val)
return false;
return isMirrorImage(n1.left,n2.right) && isMirrorImage(n1.right,n2.left);
}
@ soron
awesome solution
hats off
8 8 8 + 8 8 + 8 + 8 + 8 = 1000
- gulusworld1989 October 16, 2010node* merge(node* n1,node* n2)
{
node* n;
if(!n1||!n2)
{
if(!n1)
return n2;
else
return n1;
}
if(n1->val < n2->val)
{
n=n1;
n->next = merge(n1->next,n2);
}
else if(n1->val > n2->val)
{
n=n2;
n->next = merge(n1,n2->next);
}
else
{
n=n1;
n->next=n2;
n->next->next = merge(n1->next,n2->next);
}
return n;
}
@nitin It doesn't work. It only returns the first charecter which appears adjacently more than once.
- gulusworld1989 October 16, 2010The following is the easiest perfectly working code
class Missing
{
static void findMissing(int a[],int N)
{
for(int i=0;i<a.length;i++)
a[(a[i]-1)%(N+1)]+=N+1; //array modified
for(int i=0;i<a.length;i++)
{
if(a[i]<N+1)
System.out.println((i+1)+" is missing");
a[i]=a[i]%(N+1); //array restored
}
}
public static void main(String args[])
{
java.util.Scanner sc=new java.util.Scanner(System.in);
int x;
System.out.println("Enter the array size");
x=sc.nextInt();
int[] arr=new int[x];
for(int i=0;i<x;i++)
{
System.out.println("Enter the values");
arr[i]=sc.nextInt();
}
findMissing(arr,arr.length);
}
}
This is an easy one which can be done in O(n) time and O(1) space ...
Suppose the array a is 9 8 7 6 5 7 8 9
maintain a pointer j to the beginning of the array
keep incrementing j until j+2 reaches the end of the array .
when ever signs of a[j]-a[j+1] and a[j+1]-a[j+2] is different then j+1 is the point of inflexion .
so in this case 5 is the point of inflexion as
signs of 6-5 and 5-7 are different ....
can u explain how we can link name and phone no. uniquely
- gulusworld1989 October 15, 2010String is the final class which i believe it should not be
and it is perfectly ok with those classes which are not final ....
Here is my code
- gulusworld1989 February 11, 2011