Microsoft

I was asked to determine the minimum number of swaps needed to sort an array of distinct integers, which I modeled by finding cycle lengths in a permutation graph. The interviewer asked me to find the majority element in a stream of votes that appears strictly more than n/3 times using the Boyer-Moore Voting Algorithm. I was asked to find the convex hull formed by a set of GPS coordinates on a 2D plane using Graham's scan algorithm.