Microsoft visited my university, and I gave them my resume.

They spoke with me briefly there and then sent me an email inviting me for an interview.

The interview was in a hotel next to the subway station, so it was easy to get there. The interviewer was extremely nice and gave me the opportunity to ask many questions about the job and the company.

I had to write some simple algorithms, such as reversing a linked list.

Next, I received an email asking me to travel to another city for the final interview day. They purchased my plane tickets and booked a nice hotel.

I had three interviews there:

• On two of them, I had to write algorithms to solve problems with strings.
• On the other one, I had to create a test plan for a software.

The interviewers were extremely nice, except for one. We had to solve all the problems on the whiteboard, and there were some puzzles during the interviews.

Write the algorithm for this:

If you have a string like aaabbc, the output should be a3b2c1. For the string aabcc, the output should be a2b1c2, and so on.

You should not allocate memory for a new string and can achieve this by reading each character only once.

Note: If the result is larger than the original string (e.g., abc -> a1b1c1), return null or a message that makes this clear.