谷歌onsite的一道题

Job Hunting Interview
, , ,
1

求解法！

Given 2x4 matrix it contains numbers in the range 1-8.
For eg :
[4,2,6,5
1,8,7,3]

You have 3 operations:

  1. Rotate : Middle 4 numbers rotate in clockwise manner.
    [4,2,6,5
    1,8,7,3]
    becomes
    [4, 8,2 ,5
    1, 7,6 ,3]
  2. Swap : swaps the two arrays
    [4,2,6,5
    1,8,7,3]
    becomes
    [1,8,7,3
    4,2,6,5]
  3. Shift (right) :
    [4,2,6,5
    1,8,7,3]
    becomes
    [ 5 ,4,2,6,
    3 ,1,8,7]

Your goal is to reach following state and return how many minimum operations would it take to reach that state.
[1,2,3,4
5,6,7,8]

感觉很像 https://leetcode.com/problems/sliding-puzzle/description/

2

报个面经：

5 轮

  1. Given an array of intergers divide them into n subsets such that difference between sum of each subset is minimum.
    Example : input [1,1,4,2,8] and n=2 ; output = [1,1,4,2] and [8]
    input [1,1,4,2,8] and n=3 ; output = [1,1,2] and [4] and [8]
  2. A frog is at starting index of array of length having n. Some indexes of array has obstacles. Frog can either move 1 step or jump m steps only when there is obstacle. Write a program to tell if frog can reach last index of array.
  3. Check if the given node exists in a complete tree