Archive for Interesting Interview Questions

How to Test a simple Calculator Interview Question

This is a very common interview question and was very much expected when I appeared for my telephonic interview with Microsoft! And as expected I was asked this J “How would you test a calculator that does basic operations like addition, multiplication, division, subtraction and square root.

So here is a reasonable answer to ace this question. Testing formally is divided into two broad categories Functional testing and Non-Functional Testing.  To be very honest interviewer is NOT interested in how much you know about different types of testing rather they want to see how you’re thinking pattern works.

A model answer to this question can be as follows:

“To test a calculator it’s very important that we test both its functional aspects as well as non-functional requirements.  First I would be testing its functional aspects as follows:

a) Perform valid simple arithmetic operations on numbers and compare results with actual results

b) BODMAS: use a long string of different operations on numbers and see if it follows the BODMAS principle and calculates result accurately

c) Try dividing a number by zero and see the output

d) Calculate square root for a negative number and see the result.

e) Perform mathematical operations on very large numbers and see how it handles them.

f) Press and test the back button it should delete the last digit and update screen.

g) Clear button should reset the screen to zero.

h) Use of appropriate error messages.

i) Other aspects such as weight of the calculator should be as such as that it’s easy to carry; display screen should display the numbers big enough for proper visibility and durability of the product.

I hope it helps!

Comments (2)

Print a tree level by level (Level Order Traversal)

Printing a tree level by level

A common interview question in which you would be asked to write a code that would print a binary tree by level. For example the below binary tree when passed to your code should print 7,6,11,3,5,13,12



 

 

 

 

 

This is also known as level order traversal. The level order traversal of a tree is also breadth first traversal of the tree. The concept of level order traversal is to visit the root and then visit all nodes 1 level away, then all nodes 2 levels away and so on. We would need a queue to perform this kind of traversal.

The psuedocode for the program would be as follows:

Create an empty queue “Q”
enqueue the root element of the tree
while queue is NOT empty
dequeue an element from the queue
print element
Get children of the dequeued element
enqueue children

Having written the psuedocode its now very straight forward to convert this into a working C++ code.

 

 

Leave a Comment

Deleting the entire linked list

This is another common interview question. The interviewer wants to see how you tackle the problem and maintain pointers to correctly de allocate all the memory reserved by the linked list.

Suppose you start with the head element and traverse the list and delete elements as you move along…but wait a minute! Do you advance the pointer first or delete the pointer first? Suppose you advance the pointer than how would you delete the previous node? And if you delete the node than you can’t advance as your node contains the address of the next element.  So to perform this function we would need to maintain two pointers one which would hold the current node and one which would hold the next node in the linked list. Here is a sample code in C++

Void Delete (Node ** head)
{

Node* temp = *head;
while (temp) {

Node * temp1 = temp->next;
delete temp;
temp = temp1;
}

*head = NULL;

}

Updated courtesy supergokhan

 

Comments (2)

Detecting a cycle in a linked List (Floyd’s Cycle Detection)

OK here is another very interesting interview problem which I wanted to discuss today. The problem at hand is that you are given a singly linked list and (unfortunately) it contains a cycle i.e. some node points back to an earlier node in the linked list. Your task being a software engineer is to detect if  the linked list contains a cycle.

My initial brainstorming gave me an idea that I should traverse the list and mark nodes on my way so if I reach a node that has already been marked Hurrah !! Got ya !

Lets see how this approach works. So now I need to maintain a status for every node so I updated my Node Structure as follows

Struct Node {
int data;
Node * link;
bool status;
}

Firstly I would have to initialize all nodes with status value equal to “false”

Node * temp = head;
while (temp) {
temp->status = false;
temp = temp->link;

}

Having done that now my job is very simple. I can detect the cycle as follows:

Node * current = head;
bool isCycle = false;

while (current){

if(current->status ==true){
isCycle = true;

}

current->status = true;
current=current->next;

}

The approach seems to be fine but it required us to change our original Node data structure. Supposing the interviewer wants you to come up with a solution that doesn’t change the underlying data structure than you need to figure out some other way. Let’s look at a different algorithm that achieves this.

Most of us would remember the rabbit and turtle story from our childhood where the rabbit was very quick and turtle was very slow during the race. Consider they were racing on a straight track and for sometime assume the rabbit didn’t become complacent and instead kept on running he would have reached the finish line much quicker than the turtle, however consider they were racing in a circular field and there was no finish line the rabbit would have moved ahead quickly and eventually would have crossed the turtle again after some time. Can we use this story for our help? Yes we surely can ! this algorithm is a classical example of Floyd’s Cycle Detection Algorithm or also known as Tortoise and Hare Algorithm. So if we have a cycle in our linked list than some where along the traversal the faster pointer (Hare) would meet the slower pointer (turtle) indicating we have a cycle , else the hare would reach the end of the linked list if there is no cycle. Let’s see how we can code this.

//Hare moves twice the speed of the Turtle so if we have a cycle eventually Hare would meet the turtle again.

bool isCycle(Node *head) {

Node * turtle, * Hare;

turtle=Hare=head;

while (Hare){

if(Hare>link ==turtle->link){

return true;

}

turtle = turtle->link;
Hare= Hare->link->link;

}

return false;

}

Comments (1)

mth from the last element of a singly linked list

Write a program to find the mth from the last element of a singly linked list

Singly Linked List

So for the linked list shown m= 0 would return the node with information field 1203 (tail element) and m = 1 would return node with information field 1202.

Solution:

This is a very common interview question. Let’s look at a very simple solution.

  1. Traverse the list and count the number of nodes.
  2. Calculate the offset of the mth from last element from the start using  offset = (length – m)
  3. Traverse the linked list again (for int i=1 ; i <=offset; i++) and return the current node.

However there must be a better way of approaching this instead of using loops to traverse the list twice.

Another solution can be as follows:

  1. Initialize two pointers p and q both pointing to the head of the linked list.
  2. Now let’s make the distance between p and q equals to m by incrementing the q pointed m times.
  3. Now check if q-> next == NULL (means we have reached the end of the linked list and p is at m positions from the last element so we return node pointed by p) else increment both points p = p-> next and q = q-> next and repeat step 3 again.

Rough implementation in C++ would be as follows:

Node * mthfromLast(Node * head, int m){

if(head==NULL|| m < 0)
{   return NULL;
}

Node * p, *q = head;

for (int i = 0 ; i < m; i++){
if(q->next == NULL)

{ return NULL;
}

q = q-> next;
}
while(q->next!= NULL) {

p = p-> next;

q = q-> next;

}
return p;
}

Singly Linked List Image was taken from : http://www.tech-faq.com/images/singly-linked-list_clip_image002.jpg

Leave a Comment