I visited their booth at my university's career fair and then got an on-campus interview about a month and a half later. The on-campus interview was a short, 30-minute session where I was asked questions about linked lists:

• How would you determine if there is a cycle in a linked list?
• How would you find the head of the cycle, i.e., where the cycle starts?
• How would you find the kth element from the end of a linked list?

About two weeks later, I received an invitation for on-site interviews. Approximately three weeks after that, I flew out to Redmond. I had four interviews on-site, which included behavioral questions and coding questions, such as:

• How would you test a phone (your simple, 20-year-old phone)?
• Give test cases for some functions whose implementation is unknown (i.e., black-box testing).

The people there were great, and I really liked their campus.

Given a linked list with three fields: a data field, a next field, and a random pointer field (which points to null or to an element in the linked list), write a function to return a copy of the linked list without destructively modifying the original linked list.