### Microsoft Aptitude Test - Sample Questions

Hope You will find this useful!

----------------------------------

Implement an algorithm to reverse a linked list. Now do it without recursion.

Implement a linked list. Why did you pick the method you did?

Compare two strings using O(n) time with constant space.

Describe advantages and disadvantages of the various stock sorting algorithms.

Implement strstr() (or some other string library function).

What’s the difference between a linked list and an array?

Implement an algorithm to insert a node into a circular linked list without traversing it.

Write routines to manage a heap using an existing array.

Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.

Implement an algorithm to do wild card string matching.

Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up.

Now test it.

Multiple by 8 without using multiplication or addition. Now do the same with 7.

Count the number of set bits in a number. Now optimize for speed. Now optimize for size.

Reverse a string. Optimize for speed. Optimize for space.

Implement an algorithm to take an array and return one with only unique elements in it.

Reverse the words in a sentence, i.e. “My name is Chris” becomes “Chris is name My.” Optimize for speed. Optimize for space.

Write routines to read and write a bounded buffer.

Implement an algorithm to sort an array. Why did you pick the method you did?

Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.

Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

Find a substring. Optimize for speed. Optimize for space.

Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2

Implement an algorithm to print out all files below a given root node.

How would you find a cycle in a linked list?