## Adobe Interview Question for Member Technical Staffs

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 3 vote

It "feels" like there is a better way. This might seem borderline brute forcish..

Let N be the largest such number you want.

``````MinHeap<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);

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

Comment hidden because of low score. Click to expand.
0
of 0 votes

``````#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,arr,...,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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

How will we avoid to add duplicate entries in Heap

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````/* 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 = 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;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 votes

can you explain the theory of your code?

Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 for variable naming.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it's using an approach similar to that of the Sieve of Eratosthenes in that it uses the multiples of previously found Ugly Numbers to test the next ones.

Comment hidden because of low score. Click to expand.
0
of 2 vote

the numbers which are multiples of 30(30,60,90,.....) will always have the factors in (2,3 &5)

Comment hidden because of low score. Click to expand.
0
of 0 votes

I too thought the same . Is it that simple?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If only the factors 2,3,5 are to be used then there is a solution in thread
question?id=6260011781062656

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Oops, the LINQ part:

``Enumerable.Range(0, int.MaxValue).Where(n => IsUgly(n));``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

This is a famous problem, known as the ugly numbers problem.

The heap solution by Soundwave is good, but there are better solutions.

Comment hidden because of low score. Click to expand.
1
of 1 vote

care to share?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More