Questions from/for technical interviews: Part of www.technical-interview.com

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

2011-10-15T05:00:00.001-07:00

Common multiple

2011-09-30T10:08:00.000-07:00

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

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

2010-08-11T14:40:00.001-07:00

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.

2010-06-30T06:18:00.003-07:00

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?

2010-06-30T06:18:00.001-07:00

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++?

2010-06-30T06:17:00.001-07:00

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

2010-05-02T12:54:00.000-07:00

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

2010-05-02T12:50:00.000-07:00

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

2010-05-02T12:42:00.000-07:00

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?

2010-05-01T12:57:00.000-07:00

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.

2010-05-01T12:56:00.001-07:00

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?

2010-05-01T12:55:00.001-07:00

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

2010-04-29T12:54:00.001-07:00

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

2010-04-29T12:51:00.000-07:00

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

2010-04-29T12:48:00.000-07:00

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

2010-04-27T13:34:00.000-07:00

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

2010-04-27T13:32:00.000-07:00

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

2010-04-22T23:51:00.000-07:00

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

2010-04-22T23:49:00.001-07:00

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

2010-04-22T23:48:00.000-07:00

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

Compute the sum of all the values in the nodes of a single linked list

2010-04-22T23:46:00.000-07:00

Q:

Compute the sum of all the values in the nodes of a single linked list

A:

public int getSum(Node head)
{

if (head == null) return 0;
else
return getSum(head.next) + head.value;

}

Calculate length of the linked list

2010-04-22T23:45:00.001-07:00

Q:

Calculate length of the linked list

A:

public int getLength(Node head)
{
if (head == null)
return 0;
else
return length(head.next) + 1;

}

Reverse a Singly Linked List

2010-04-22T23:44:00.000-07:00

Q:
Reverse a Singly Linked List

A:
public Node Reverse(Node head)
{
Node next;
Node current;
current = head;
Node Result = null;
while (current != null)
{
next = current.next;
current.next = result;
result = current;
current = next;
}
return (result);
}

What are the advantages and disadvantages of linked list structure vs. arrays?

2010-04-22T23:43:00.001-07:00

Q:

What are the advantages and disadvantages of linked list structure vs. arrays?

A:

Linked lists allow only sequential access to elements O(n) while arrays allow random access O(1). Linked lists requires an extra storage for references, which often makes them impractical for lists of small data items such as characters or Boolean values. From the over side, size of array is restricted to declaration. Insertion/Deletion of values in arrays are very expensive comparing to linked list and requires memory reallocation. Elements can be inserted into linked lists indefinitely, while an array will eventually.

What is the difference between array and linked list?

2010-04-22T23:42:00.000-07:00

Q:
What is the difference between array and linked list?

A:

The main difference between the linked list and the array is that while the array is a static data structure (with fix number of elements), the linked list - dynamic data structure. In terms of complexity, the linked list is usually more efficient as to the space it uses, however, algorithms for linked lists are usually more complicated that those of the array.