# 谷歌电面 09/27

lc 把武器
lc 把丝丝

Given a 2D grid where each element in the grid can either be a 1 or a 0. You have the ability to choose any element and flip its value. The only condition is that when you choose to flip any element at index (r, c), the 4 neighbors of that element also get flipped. Find the minimum number of flips that you need to do in order to set all the elements in the matrix equal to 0. If it’s not possible, return -1.

Example 1:

Input:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]

Output: 0

Seems like a variant of Word search -1 and word search -2 but I haven’t been able to come up with a better solution than brute force
1- Generate all permutations of the dict.
2 - Apply a generic DFS algorithm on each permutation to see which permutation consumes the max number of words from the dict
3. return the max words consumed from a permutation.

Give two Strings a and b find out if there is any possible to repalce the same frequency character
Input: a = babczzz, b = abbzccc
Output: true
Explanation:
In a string,
a -> 1, b -> 2, c-> 1 , z -> 3
In b string,
a -> 1, b -> 2, c -> 3, z -> 1
a and b are the same frequency.
c and z have same frequency so they can replace to each other.
So return true.

Input: a = x, b = y
Output: false
Explain: Not the same character

Input: a = ii, b = j
Output: false

The frequency of the two letters inside each string can also be interchanged, so this question only needs two strings. Each frequqncy appears the
same number of times. For example, “babzccc” and “bbazzcz” return “true” because z and c can be interchanged. But “babzcccm” and “bbazzczl” are different, because m appeared in the first one, and did not appear in the second.

You are given a 2D integer matrix as input. You always start in the top left corner and have to make your way to the bottom right index by only moving right or downwards. For each possible path to the bottom right corner, there is a maximum integer in the path. Find the minimum of all possible maximum integers for all the paths from the top left to the bottom right.

For example:
You are given the following matrix `[ [1, 7] [5, 3] ]`

The possible paths are (1, 5, 3) and (1, 7, 3). Subsequently, the maximum of the paths are (5, 7). Finally, the minimum of all the maximums is 5 .

Find the shortest substring where all the alphabets (a to z) appear in order. Consider alphabets as case insensitive means ‘a’ and ‘A’ are same.

I started with preprocessing the input string by putting frequency of each character in an array where each position of array holds an array list for all the indexes of the characters.

ArrayList [] map = new ArrayList ;

After this I started with first index of ‘a’ in map and tried to find index of ‘b’ which is greater than index of ‘a’ and so on. At the end I have a substring and I compare the length of substring with minLength variable and update minLength accordingly.

I was able to come up with O(n^2) solution in the given 45 minutes and coded it cleanly.

Can we do it in O(n) time?

Input: str = “… a lot of people, b e something, C algha, d ghala, e dhga, f tu g ga h agha i af j gahalh k qafs l agaga m afag n asfkhgs O gaha pqr hglagha s hlh t hgl u qlgha v agagh w agklha x aghhknmbv y axbvm Z …”

Output: substring which starts with ‘a’ and end with ‘Z’

Generate random candy crush N * N board (using a-f characters) with following conditions

• There is no crush (3 consucative same letter) eg. `"bcaaade"`
• There is at lease one swap (swaping characters result in crush) eg: `"acaafbb"` (swap first two letters)