When I was a college student, Microsoft first came to my campus to interview me. They asked a challenging programming logic question, and I passed. Microsoft then flew me to Seattle for an on-site interview. Over the course of a day, I had four interviews, all similar to my on-campus one. At each interview, I was asked a technical question. From what I heard, it seemed only about one out of every four people flown to Seattle received an offer.

You have a list of red and blue objects. You must sort them using swaps in at most N time.

Given an inorder and preorder traversal of a binary tree, reassemble the tree.

Given a set of people, one of them is a celebrity. You have a 2D array that describes who knows whom. [N, M] is true if N knows M. The celebrity will not know anyone (except themselves), and everyone will know the celebrity. Find an O(N) algorithm to find the celebrity.

You have a list of numbers that are sorted but shifted. For example, [5, 6, 1, 2, 3] or [15, 17, 20, 25, 2, 8] is given. Find the most efficient way to search for a number in this type of list.