Adobe Interview Question Member Technical Staffs
Country: India
Interview Type: Written Test
This solution works, if they had asked:
Generate all numbers in ascending order which are having "only" factors as 2,3 and 5.
It does not generate numbers which have factors other than 2, 3, and 5. For example: 2*3*5*7 will not be generated.
This is careercup: We have to guess what posters are trying to say and solve based on that interpretation... and move on (otherwise we might end up in infinite loops wasting time).
@Bug the question states to find numbers with factors only as 2,3,5. So we will never have a combination with 7
@ SOUNDWAVE
am not sure this solution will work if the numbers were 2,3,31
#include<iostream>
#include<queue>
#include<set>
using namespace std;
//Utility Function to Print a SET
void printSet(set<int> set1)
{
set<int>::iterator it;
for(it=set1.begin();it!=set1.end();it++)
cout<<*it<<endl;
}
//Compare Function for Min Heap
class compare
{
public:
bool operator()(int&a , int&b)
{
return (a>b);
}
};
//Function to print those numbers whose ONLY factors are arr[0],arr[1],...,arr[n-1]
//Function will print numbers upto K
//Set is used to avoid duplicates
void findFactors(int arr[],int n,int K,set<int>& set1)
{
priority_queue< int, vector<int>, compare > pq1;
pq1.push(1);
int temp=0;
while(!pq1.empty())
{
temp=pq1.top();
pq1.pop();
if(temp>K)
break;
set1.insert(temp);
for(int i=0;i<n;i++)
pq1.push(temp*arr[i]);
}
}
int main()
{
int arr[]={2,3,5};
set<int> set1;
findFactors(arr,3,50,set1);
printSet(set1);
return 0;
}
I don't think your solution is brute force at all, soundwave. I implemented a check for an ugly number below, but it's not very efficient, because it has to factorize each number again and again in order to test it. Your solution avoids that, because it is truly generative, i.e. computes the next ugly number based on the previous.
Also, there are min-heap structures that allow an amortized runtime complexity for both insertion and finding the minimum of constant time, such as Fibonacci heaps.
/* a no which is divisible by only 2,3, or 5 and not any other prime no */
int getNthUglyNo( int n)
{
int *arr = new int[n];
arr[0] = 1;
int i2 =0, i3 = 0, i5 = 0;
int next_i2, next_i3, next_i5;
int next_ugly = 1;
for( int i = 1; i<n; i++)
{
next_i2 = 2*arr[i2];
next_i3 = 3*arr[i3];
next_i5 = 5*arr[i5];
next_ugly = min(next_i2, min(next_i3, next_i5));
arr[i] = next_ugly;
if (next_ugly == next_i2)
i2++;
if (next_ugly == next_i3)
i3++;
if (next_ugly == next_i5)
i5++;
}
return next_ugly;
}
the numbers which are multiples of 30(30,60,90,.....) will always have the factors in (2,3 &5)
Well, English is not my native language, either, but as software engineers I think we should try to be as precise in our written word as much as our code. I totally understand if somebody has not had the amount of exposure to English that requires them to express themselves precisely, but I have often times observed that the apparent amount of effort invested in the use of our spoken languages (that goes beyond English as I have worked in countries of various languages) is inversely proportional to its proximity to code or the Internet ...
That being said, if we interpret the question to mean
In ascending order, list all numbers that have all of and none other than the prime factors two, three, and five.
then I would say you are totally correct in simply iterating from 30 in steps of 30. The question may have been designed to test if a candidate makes the conclusion and realizes that the solution can be greatly simplified in code by arithmetic reasoning.
#include <stdio.h>
#include <string.h>
int maxdivide(int value, int exp)
{
while(value%exp==0)
value = value/exp;
return value;
}
int isUgly(int num)
{
num = maxdivide(num,2);
num = maxdivide(num,3);
num = maxdivide(num,5);
if (num == 1) return 1;
else return 0;
}
int main(void)
{
int val=301;
if (isUgly(val) == 1) printf("%d is a ugly number",val);
else printf("%d is not a ugly number",val);
return 0;
}
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
int ugly(int m);
int main()
{
int n;
bool j;
cout<<" enter range for ugly numbers:\n";
cin>>n;
for(int i=2;i<=n;i++)
{
j=ugly(i);
if(j==true)
cout<<i<<endl;
j=false;
}
return 0;
}
int ugly(int m)
{
int a,x=0,y=0,z=0;
a=m;
while(m%2==0)
{
x++;
m=m/2;
}
while(m%3==0)
{
y++;
m=m/3;
}
while(m%5==0)
{
z++;
m=m/5;
}
if(a==(pow(2,x)*pow(3,y)*pow(5,z)))
return true;
else
return false;
}
So ... I'll be breaking three promises with this single post. First, I promised my partner I would finally go to bed, second I said I would not repost code for the solution to a problem where there are plenty of more efficient solutions readily available on the Internet, and third I said I would quit using LINQ for a day. However, the amount of coffee I have consumed today made it hard for me to sleep and as I was lying in bed a slightly more compact way to write this ugly number test than most other code I have seen on the Internet popped into my head:
private static bool IsUgly(int n)
{
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
return n == 1;
}
void function1(int arr[], int start, int end, int data[], int startD, int endD)
{
if(start<=end+1)
{
if(startD==endD+1)
{
int mul = 1;
for(int i=0;i<=endD;i++)
{
// cout<<" "<<data[i];
mul *= data[i];
}
cout<<" "<<mul<<endl;
return;
}
data[startD] = arr[start];
function1(arr, start+1, end, data, startD+1, endD);
function1(arr, start+1, end, data, startD, endD);
}
}
void function(int arr[], int size)
{
for(int i=0;i<=size;i++)
{
int *data = new int[i+1];
//cout<<" spot 1 "<<i<<endl;
function1(arr, 0, size, data, 0, i);
delete[] data;
}
}
This is a famous problem, known as the ugly numbers problem.
The heap solution by Soundwave is good, but there are better solutions.
Ugly numbers are numbers whose only factors are 2,3 or 5 but here the question demands the number should have factor as 2,3 and 5. so it is not a Ugly number problem.
According to the given question the answer should be just multiple of 30. Please correct me if i am wrong.
@Bharti: You stand corrected. That is a trivial problem (multiples of 30), and unlikely to be the question.
The real question has been lost in translation, as usual.
Hey, there! Not sure what's up with the down votes, but I share your sentiment. The Ugly Number Problem is easy to look up in many places in the literature and there are many ready made implementation on the Internet. I don't think there is much value in duplicating it on this site.
However, since there appears to be an issue in determining the original intention of the question, let me assume another interpretation. Instead of the Ugly Number Problem, let's say that the question meant
"List all numbers in ascending order that have any, but not necessarily all or exclusively, of the prime factors two, three or six."
Then we would obtain the numbers 2, 3, 4, 5, 6, 8, 9, ... This, the other interpretation I posted under the same handle above, and the Ugly Number Problem are the only interpretations I can see right now.
For these particular factors (not necessarily even by their nature of being prime) and this particular interpretation, it is noteworthy that by two being included it means that all even numbers would be contained in the sequence. What about the odd numbers? Instead of trying to arithmetically calculate the next number in the sequence given the current one, we can simply check the odd numbers in order and do so in such a manner that they naturally fall into ascending order:
for (int i = 2; i <= int.MaxValue; i += 2)
{
Console.WriteLine(i);
if ((i + 1) % 3 == 0 || (i + 1) % 5 == 0)
Console.WriteLine(i + 1);
}
It's just one way to write it, but the one with least code I can think of in a C-like language.
Of course, I like to think that they meant to test the Ugly Number Problem as well, since it's a lot more interesting than this sequence.
It "feels" like there is a better way. This might seem borderline brute forcish..
Let N be the largest such number you want.
- S O U N D W A V E March 21, 2014MinHeap<unsigned int> h; h.insert(1); // I consider this as 2^0 * 3^0 * 5^0 int temp; while( ( temp = h.checkMin() ) < N ) { print( temp ); h.extractMin(); insert(temp*2); insert(temp*3); insert(temp*5); }