Data Structure: Interview Experience Part 7(Microsoft)

Searching and Sorting

Data Structure: Interview Experience Part 7(Microsoft)

Searching and Sorting

1. Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Example 1: 

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2: 

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

  • 1 <= schedule.length , schedule[i].length <= 50
  • 0 <= schedule[i].start < schedule[i].end <= 10^8

Practise: https://leetcode.com/problems/employee-free-time/

2. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1: 

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

Practise: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

3. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example: 

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
Output: [1,2,2,3,5,6]

Constraints:

  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1.length == m + n
  • nums2.length == n

Practise: https://leetcode.com/problems/merge-sorted-array/

4. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example: 

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2's.
  • Could you come up with a one-pass algorithm using only constant space?

Practise: https://leetcode.com/problems/sort-colors/

5. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1: 

Input: [3,4,5,1,2] 
Output: 1

Example 2: 

Input: [4,5,6,7,0,1,2]
Output: 0

Practise: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 

One might notice that we are calculating the pivot with the formula of pivot = low + (high-low)/2, rather than the more intuitive term pivot = (high+low)/2.

Actually, this is done intentionally to prevent the numeric overflow issue, since the sum of two integers could exceed the limit of the integer number.

6. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1: 

Input: [1,3,5]
Output: 1

Example 2: 

Input: [2,2,2,0,1]
Output: 0

Note:

Practise: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 

Complexity Analysis
Time complexity: on average O(log⁡2N) where N is the length of the array, since in general it is a binary search algorithm. However, in the worst case where the array contains identical elements (i.e.case #3 nums[pivot]==nums[high]), the algorithm would deteriorate to iterating each element, as a result, the time complexity becomes O(N).
Space complexity : O(1), it’s a constant space solution.

7. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1: 

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2: 

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Practise: https://leetcode.com/problems/search-in-rotated-sorted-array/

8. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1: 

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Practise: https://leetcode.com/problems/search-a-2d-matrix/

9.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix: 

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Practise: https://leetcode.com/problems/search-a-2d-matrix-ii/

Complexity Analysis

  • Time complexity : O(n+m)
  • The key to the time complexity analysis is noticing that, on every iteration (during which we do not return true) either row or col is is decremented/incremented exactly once. Because row can only be decremented m times and col can only be incremented n times before causing the while loop to terminate, the loop cannot run for more than n+m iterations. Because all other work is constant, the overall time complexity is linear in the sum of the dimensions of the matrix.
  • Space complexity : O(1)

10. 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)).

You may assume nums1 and nums2 cannot be both empty.

Example 1: 

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2: 

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Practise: https://leetcode.com/problems/median-of-two-sorted-arrays/

Hope this article is useful for people looking to learn and practice Data structure & Algorithm in swift, Please ❤️ to recommend this post to others 😊. Let me know your feedback. :)