I did my summer internship at Microsoft India. The interviews were part of converting the internship to full-time employment.

I had three interviews on different days. My performance in the interviews was not great, but I was given the offer because Microsoft was hiring massively for Bing and the review from my mentor was positive.

(I have listed all the questions from the interviews)

Consider a linked list with two pointers: the first pointer is the normal 'next' pointer, and the second pointer randomly points to some other node in the list. Given such a list as input, clone it.

Find the largest palindrome in a given string. Come up with the best algorithm you can.

There are n petrol bunks arranged in a circle. Each bunk is separated from the next one by a certain distance. You choose a mode of travel which needs 1 liter of petrol to cover 1 km distance. You can't draw any amount of petrol from each bunk, but each bunk has some limited petrol. Find if there is any point in the circle from which you can start. If there is one such point, find the point.

Implement a variation of a stack with push, pop, and getMin operations in O(1) complexity.

Given two sorted arrays: one of size m and another of size m+n. The second array only contains n elements, but has a capacity of m+n. Arrange both sorted arrays in the bigger array. Finally, the bigger array should be sorted.