Adobe Interview Question
Technical Support EngineersCountry: United States
This is ugly number problem. Please find the below code
void getNthUglyNo(unsigned n)
{
int ugly = new int[n];
int i2 = 0, i3 = 0, i4 = 0, i7=0;
int i;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_4 = 4;
int next_multiple_of_7 = 7;
int next_ugly_no = 1;
ugly[0] = 1;
for(i=1; i<n; i++)
{
next_ugly_no = Math.min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_4,
next_multiple_of_7);
ugly[i] = next_ugly_no;
if(next_ugly_no == next_multiple_of_2)
{
i2 = i2+1;
next_multiple_of_2 = ugly[i2]*2;
}
if(next_ugly_no == next_multiple_of_3)
{
i3 = i3+1;
next_multiple_of_3 = ugly[i3]*3;
}
if(next_ugly_no == next_multiple_of_4)
{
I4 = i4+1;
next_multiple_of_4 = ugly[i4]*4;
}
if(next_ugly_no == next_multiple_of_7)
{
i7 = i7+1;
next_multiple_of_7 = ugly[i7]*7;
}
} /*End of for loop (i=1; i<n; i++) */
return next_ugly_no;
}
35 is multiple of 7 and is not generated,reason is that we multiply given factors with generated numbers,and 5 is not generated so 35 is not generated,that why i am multiply numbers by i=1,2,3,4...... in my approach.
and for handle duplicates we can take an hash array.
My question is how to handle duplicates without extra space.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
class pair{
int key;
int value;
pair(int key,int value){
this.key=key;
this.value=value;
}
}
class pairComp implements Comparator<pair>{
public int compare(pair o1, pair o2) {
return o1.value-o2.value;
}
}
public class NumberOfVariables {
public static void main(String args[]){
int[] k={2,3,4,7};
int n=100;
ArrayList<pair> al= new ArrayList<>();
for(int i=0;i<k.length;i++){
pair temp = new pair(k[i],k[i]);
al.add(temp);
}
int[] ans=generate(al,n);
System.out.println(Arrays.toString(ans));
}
private static int[] generate(ArrayList<pair> k, int n) {
Collections.sort(k,new pairComp());
for(int j=0;j<n;j++){
}
int[] ans=new int[n];
int prev=-1;
for(int i=0;i<n;i++){
pair temp=k.get(0);
if(prev!=temp.value)
{
ans[i]=temp.value;
prev=ans[i];
}
else{
i--;
}
temp.value+=temp.key;
Collections.sort(k,new pairComp());
}
return ans;
}
}
It is simple.
Just do the modulus for each number starting from 6 with the numbers in the set. If its 0 then, we can print that number else we check with other number in the given set.
As the set completes we move on to the next integer. It is same as the first solution, but with lesser complexity.
private static void giveTheFactors(int[] arr, int n) {
// TODO Auto-generated method stub
int numberToPrint_Not = 6;
for(;numberToPrint_Not<=n;numberToPrint_Not++)
{
for(int i=0; i<arr.length;i++)
{
if(numberToPrint_Not%arr[i] == 0)
{
System.out.println(numberToPrint_Not);
break;
}
}
}
}}
Keep k variables. Each variable represents a factor. Each iteration, output the min variable then increment it by the respective factor. If a variable is equal to the currently output value, increment it (to avoid duplicates). When you've outputed n numbers, you are done.
O(kn) time, O(k) space
- SK July 07, 2015