Technical Interview

Tips, questions, answers and puzzles at
www.technical-interview.com

Wednesday, August 11, 2010

Nice Book for your Interview

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

Wednesday, June 30, 2010

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

Sunday, May 2, 2010

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.

Saturday, May 1, 2010

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.

Thursday, April 29, 2010

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’’

Tuesday, April 27, 2010

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;

Thursday, April 22, 2010

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

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

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

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

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?

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?

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.

A rectangular plate with length 8 inches

Q:

A rectangular plate with length 8 inches, breadth 11 inches and thickness 2 inches is available. What is the length of the circular rod with diameter 8 inches and equal to the volume of the rectangular plate?

A:

3.5 inches
Explanation: Volume of the circular rod (cylinder) = Volume of the rectangular plate (22/7)*4*4*h = 8*11*2, h = 7/2 = 3.5.

Three cards are drawn

Q:

Three cards are drawn at random from an ordinary pack of cards. Find the probability that they will consist of a king, a queen and an ace.

A:

64/2210

Divide 45 into four parts

Q:

Divide 45 into four parts such that when 2 is added to the first part, 2 is subtracted from the second part, 2 is multiplied by the third part and the fourth part is divided by two, all result in the same number.

A:

8, 12, 5, 20
Explanation: a + b + c + d =45; a+2 = b-2 = 2c = d/2; a=b-4; c = (b-2)/2; d =2(b-2); b-4 + b + (b-2)/2 + 2(b-2) = 45;.

Reverse a Linked-List

Q:

Reverse a Linked-list. Write code in C.

A:

Recursive solution:

Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);

Non-recursive solution:

Node * reverse( Node * ptr )
{
Node * temp;
Node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}

Singly Linked List – Delete Node

Q:

You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

A:

void deleteNode( Node * node )
{
Node * temp = node->next;
node->data = node->next->data;
node->next = temp->next;
free(temp);
}

DeleteList()

Q:

Write a function DeleteList() that takes a list, deallocates all of its memory and sets its
head pointer to NULL (the empty list).

A:

Delete the whole list and set the head pointer to NULL. There is a slight complication
inside the loop, since we need extract the .next pointer before we delete the node, since
after the delete it will be technically unavailable.
void DeleteList(struct node** headRef) {
struct node* current = *headRef; // deref headRef to get the real head
struct node* next;
while (current != NULL) {
next = current->next; // note the next pointer
free(current); // delete the node
current = next; // advance to the next node
}
*headRef = NULL; // Again, deref headRef to affect the real head back
// in the caller.
}

Count()

Q:

Write a Count() function that counts the number of times a given int occurs in a list.

A:
int Count(struct node* head, int searchFor) {
struct node* current = head;
int count = 0;
while (current != NULL) {
if (current->data == searchFor) count++;
current = current->next;
}
return count;
}
Alternately, the iteration may be coded with a for loop instead of a while...
int Count2(struct node* head, int searchFor) {
struct node* current;
int count = 0;
for (current = head; current != NULL; current = current->next) {
if (current->data == searchFor) count++;
}
return count;
}

Sunday, February 28, 2010

Arangement of blocks

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

Friday, February 12, 2010

Moving Circles

Focus on the dot and move your head forward and backward. Can you explain why the circles are moving?

Tuesday, February 9, 2010

Resume Tips

Resume Tips
When you write your resume, think about it as your marketing tool and not only your personal document. Below are some tips and suggestions on how to write an attractive resume.




Use Titles/Headings that match the jobs you are applying for

With employers receiving hundreds of resumes you must make sure that your resume hooks an employer's attention within a 5-second glance. A great way to do this is to use job titles and skill headings that relate to and match the jobs you want.



Use an attractive design

Employers make snap judgments when glancing at your resume. If they see unrelated job titles or skills the likelihood is very high that they will make an immediate assumption that you are not qualified for the job you want.



Mention your skills, knowledge, and experience

Make your statements short, meaningful and focused on what is related to the job you are seeking.



Make a list of your training and education

This is especially true of the ones that are related to the job you are applying for.



Create content that sells

Resume design should get attention but it's really the content of your resume, the descriptions you include of your skills and abilities, that determines how many interviews you generate--as well as the level of salary offers you receive.



Describe your accomplishment

Use simple, powerful statements that emphasize the results which benefit your employers.



Quantify and use power words

Using numbers to describe your achievements and responsibilities can greatly expand and elevate your image. Using numbers and quantifying creates vivid images in our minds when we read them, whereas general statements like the previous examples are easy to skip over or forget. Typically the more specific you can be in describing your duties, the better.



Analyze the job description to identify key words

Learning how to analyze the key words that employers provide in help wanted ads and job descriptions is a key element in creating powerful resumes.



Identify and solve employer's needs

To beat today's heavy competition for jobs, it's important that you identify and anticipate the full range of needs each employer faces and show how you can fulfill those needs.



Tweak and target your resumes and cover letters

You will generate many more interviews by tweaking your resume and cover letter so that they address the specific skills each employer requests.

Reference:
www.technical-interview.com