Technical Interview

Home
Added Recently
Data Structures
Puzzles
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Algorithms
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Links
Contact Us
Submit Question/Answer


Question:

Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).


This Question is from the Book Cracking the Coding Interview













          

Answer:

The Approach:

What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q



More Questions and Answers @ Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)

Delivered instantly as a PDF via email. For Software Engineers & SDETs      

·         150 programming interview questions and answers

·         5 proven approaches to crack algorithm questions

·         10 mistakes candidates make, and how to avoid them.

·         How to prepare for technical and behavioral questions without wasting your time!

30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!
 

More Info