M Cube insvestment Software Pvt. Ltd. (Questions asked)

The first company that visited our campus did leave me with an unforgettable experience. M Cube is a very different kind of company from the scratch. Why?
1. Their aptitude test has no mathematics or logic or the other standard sections that you find in other papers
2. Only 2 questions, 1 hour time to solve
3. Both the questions will be algorithmic puzzle expected to test your analytic reasoning.
4. The interviewers question on linked lists, FIFO, circular linked lists, trees, and all other data structure concepts you can possibly think of.
5. They worry a lot on space and time complexity.

The 2 questions that we got :
1. Consider a string. Devise an algorithm to find all possible circular rotations of the string.
Eg:



RotateString("gorilla","gorilla") returns 1
RotateString("gorilla","illagor") returns 1
RotateString("gorilla","illarog") returns 0

You may use a function strstr, that works as:
strstr("arch","search"); returns 2
strstr("ill","gorilla"); returns 3
strstr("ten","gorilla"); returns -1

Condition:

You may use strstr() ONLY ONCE !

Solution:

All possible combinations of gorilla are
gorilla
agorill
lagoril
llagori
illagor
rillago
orillag

The next circular shift repeats with gorilla

Consider the string gorillagorilla (i .e the same string taken twice)
Every valid circular shift is a substring of this. Use strstr wisely to do the rest

2. An array has only elements of 0s and 1s. Devise the MOST FASTEST ALGORITHM to sort the elements in ascending order.

Solution:
We know that the array has only 0s and 1s. So find the number of 0s. Make the rest of the elements 1.

int [] Sort(int *a,int n)
{
   int count=0,i;
   for(i=0;i
      if(a[i]==0) count++;

  for(i=0;i
  for(i=count;i
  return a;
}

A few technical interview questions that I remember:
1. Devise an algorithm that differentiates circular linked list from regular linked list
2. Devise an algorithm to find all possible permutations of 3 boolean variables
3. What is your favorite algorithm/program. Mention a few algorithms that you've devised.

Be prepared with questions on all data structure topics and ADA.

All the Best !! :)

(To read whether I got the job after I cleared apti, check my next post)