Microsoft Software Development Engineer interview questions

1. How to design a cache data structure for a certain search use case 2. String comparison/manipulation, and non-binary tree traversal and try to find a root-based path qualifying a certain requirement. 3. Search an element from a matrix. 4. String reversing with some special characters to check. BinaryTree level by level traversal. 5. What are you expecting to be in 5 years? Talk about previous working experience.

Q: Given a linked list with a pointer to next and a pointer to random, create a copy of this list. Q: Check of two strings are anagrams of each other. Q: string to int