I went online tonight and saw several test questions from Microsoft, mainly for internship opportunities at Microsoft Student Center. If you are interested in interning at Microsoft, you can consider trying these questions yourself. They may be challenging for beginners. I currently don't have time to write code as I am busy with exams. If you have any ideas, feel free to leave a comment or contact me directly.
Question 1: An integer sequence, where the elements can be any number from 0 to 65535, and the same value will not appear repeatedly. 0 is an exception and can appear multiple times. Please design an algorithm to randomly select 5 values from this sequence and determine if these 5 values are consecutive.
Note:
- The 5 values can be in any order. For example: 8 7 5 0 6
- 0 can be replaced with any value. For example, in 8 7 5 0 6, 0 can be replaced with 9 or 4.
- 0 can appear multiple times.
- If the complexity is O(n^2), no score will be given.
Question 2: Design an algorithm to find the nearest common parent node of any two nodes in a binary tree. If the complexity is O(n^2), no score will be given.
Question 3: Given a sorted binary tree, let f = (maximum value + minimum value) / 2. Design an algorithm to find the node that is closest to and greater than f. If the complexity is O(n^2), no score will be given.
Question 4: An integer sequence, where the elements can be any number from 1 to N (N is a large positive integer), and the same value will not appear repeatedly. Design an algorithm to find the number of pairs in the sequence that satisfy the condition where the sum of the two numbers in the pair is equal to N+1. The complexity should be O(n) for the best score. If the complexity is O(n^2), no score will be given.