Classify the Hashing Functions based on the various methods by which the key value is found

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.

What are references in C++? Why do you need them when you have pointers?

What are references in C++? Why do you need them when you have pointers?

Answer:


A reference variable is actually just a pointer that reduces syntactical clumsiness related with pointers in C (reference variables are internally implemented as a pointer; it’s just that programmers can't use it the way they use pointers).

As a side note, a reference must refer to some object at all times, but a pointer can point to NULL. In this way, references can be more efficient when you know that you'll always have an object to point to, because you don't have to check against NULL:
void func(MyClass &obj)
{

obj.Foo();

}
Is better than:
void func(MyClass *obj)
{

if (obj) obj->Foo();

}

What leads to code-bloating in C++?

What leads to code-bloating in C++?




Answer:

Inline functions and templates, if not used properly, may lead to code bloating. Multiple Inheritance may also lead to code bloating (this is because the sub classes will end up getting members from all the base classes even if only few members will suffice). Techniques to avoid code blot are discussed in “Effective C++ programming”.

how to write delay code in c

how to write delay code in c?

Ans

To perform an efficient delay you need to use a non standard function provided by the operating system for example sleep(...) in Linux or Sleep(...) in Windows.

There is no standard way of efficiently delaying without using processor cycles.

Detect merged linked list

Given the pointers to 2 linked list, how will we find out if they are merged? i.e. at some point they point to the same address.

Ans

Pick one of the lists and traverse it from head to tail. For each node encountered, compare it to the head pointer of the other list. If you find a match then the second list is embedded within the first list.

If you don't find a match, then repeat the procedure by traversing the second list.

Linked list

How does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n)

Ans

One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there's a loop.

Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?

Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.

What is the difference between an external iterator and an internal iterator? Describe an advantage of an external iterator.

Ans

An internal iterator is implemented with member functions of the class that has items to step through. .An external iterator is implemented as a separate class that can be "attach" to the object that has items to step through. .An external iterator has the advantage that many difference iterators can be active simultaneously on the same object.

What are the advantages and disadvantages of B-star trees over Binary trees?

Ans
A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.

Google Puzzle

You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?

Ans
ou simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people.

Euclidean algorithm

Write an algorithm for finding the greatest common divisor of two integers.

Ans
function gcd( a,b : Integer ) returns Integer
{
if ( b != 0 )
return gcd( b, a mod b )
return abs(a)
}

Majority element

Given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible. A majority element in an array of size N is any element which is present more than N/2 times.

Ans
Naive approach:

Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!

One needn't ponder much on the complexity of this bruteforce approach.

This requires O(N) additional space and O(N) time.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

let AL , AR be the first and second halves of A

ML = majority(AL ) and MR = majority(AR )

if neither half has a majority:

return ‘‘no majority’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

Divide a = a1a2 · · · aN by d using long division

Solution

B1 <-- a1 {Bi is what we divide d into in step i}
i <-- 1
while i <= N do
qi <-- largest integer such that d × qi <= Bi; {qi is the ith digit of the quotient q}
if i <= N − 1 then
Bi+1 <-- 10 × (Bi − d × qi) + ai+1
end if
i <-- i + 1;
end while
r <-- BN − d × qN {r is the remainder}

Algorithm Sum N numbers in a list (or array) named values

Solution
sum <-- 0;
index <-- 1;
while index <= N do
sum <-- sum + values[index ];
index <-- index + 1;
end while
print sum;

Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

Q:

Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

A:

public Node Insert(Node head, int value)
{
if (head == null || value < head.value)
return new Node(value, head);
else
{
head.next = Insert(head.next, value);
return head;
}
}

Write a function which will test whether or not there is a cycle in a single linked list

Q:

Write a function which will test whether or not there is a cycle in a single linked list

A:

public bool hasLoop(Node head)
{
Node first = head;
Node second = head;
while (first && second &&
first.Next && second.Next &&
second.Next.Next)
{
first = first.Next;
second = second.Next.Next;
if (first == second)
{
// Found loop
return true;
}
}
return false;
}

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used

Q:

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used”

A:

public void PrintInReverseOrder (Node head)
{
if (head != null)
{
PrintInReverseOrder(head.next);
Console.WriteLine(head.value);
};
}