I met with the Microsoft representatives at the school's career fair and secured an on-campus interview a month later. It was quite simple. The technical question was to remove duplicates from a sorted linked list, along with some behavioral questions. About a week later, I received an invitation for an on-site interview, which consisted of four rounds.

The questions I recall are:

• Turn a string like "sdasd..." into all possible strings where each character can be replaced by its corresponding uppercase letter.
• Write a thread-safe singleton class, suitable for multi-threaded environments, and also answer some brain teaser problems.
• Given a sorted array where all elements appear twice except for one, find that unique element (the optimal solution should be O(log n)).
• This final round's interviewer was terrible and asked some meaningless problems.

Find the element that appears only once in a sorted array where all other elements appear twice. The best solution should have a time complexity of O(log n).