微软2016实习生笔试题--Demo Day

题目:Demo Day
描述:You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.
The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.

LeetCode-04 Median of Two Sorted Arrays

题目:Median of Two Sorted Arrays
描述:There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the
median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

  这个题要求“两个有序数组的中位数”,我们可以推广到求“两个有序数组的第k小的数(findKth)”。题目要求算
法的时间复杂度为O(log (m+n)),很明显不能简单地进行归并,这种时间复杂度容易联想到二分查找的思
想。findKth关键思想如下: