Common multiple

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

A:

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

Nice Book for your Interview

Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)

How do you do dynamic memory allocation in C applications? List advantages and disadvantages of dynamic memory allocation vs. static memory allocation.

How do you do dynamic memory allocation in C applications? List advantages and disadvantages of dynamic memory allocation vs. static memory allocation.

Answer:


In C, malloc, calloc and realloc are used to allocate memory dynamically. In C++, new(), is usually used to allocate objects. Some advantages and disadvantages of dynamic memory allocation are:

Advantages:

• Memory is allocated on an as-needed basis. This helps remove the inefficiencies inherent to static memory allocation (when the amount of memory needed is not known at compile time and one has to make a guess).

Disadvantages:

• Dynamic memory allocation is slower than static memory allocation. This is because dynamic memory allocation happens in the heap area.
• Dynamic memory needs to be carefully deleted after use. They are created in non-contiguous area of memory segment.
• Dynamic memory allocation causes contention between threads, so it degrades performance when it happens in a thread.
• Memory fragmentation.