谷歌店面

Given a matrix of size m x n, there exists a square of all 1s in the matrix (all other entries in the matrix are 0s). The square of 1s is sqrt(n) or greater in size. Find the top left corner of the square and return the size of the square as well.

matrix 中心开始找

再报一道

Given array of statue heights, and an array of cave heights, find max number of statues that can fit in the cave.

You can only insert into the cave from the opening (which is at index 0), and slide as necessary.

For example,
statues = [1,2,3]
cave = [2,1,1]

Answer: 2 because statue of height 1 can slide all the way to the back of the cave, and statue of height 2 can slide into the opening of the cave.

Another example,
statues = [5]
cave = [1,20,20]

Answer: 0 because the statue of height 5 cannot get past the opening of the cave (which is height 1).

补充我看到的1题如下:

Hello,

I intervewed for Google Paris, the question was:

Find all common elements in two integer BSTs.

I used two DFTs for the solution, the first one adds the elements of one tree to unordered set and the other one search the elements in the set. However, this is not the optimum solution absolutely.

I suggested another solution without using set but this time it was worse in runtime complexity.

I did the interview last Tuesday and there is still no answer, is this normal? Do you think I was only asked one question instead of two because I was too slow, or is it possible that they ask one question only?

Given list of objects-
{a, b, “right”} --> a is to the right of b
{c,b, “right”} --> c is to the right of b
{b,a, “left”} --> b is to the left of a

sort them based on left and right conditions.

output - b, a, c

I thought of using a linked list, but it’ll be too complex to check for each and every condition of left/right.

我考到的是这题

给⼀个数组,数组元素unique. 如何⽤最少的swaw operation使之变为ascending order? 并打印path.

eg: prray[1, 5, 9, 4] --------->{ } :⽆需 swap.

array[3, 4, 1, 2] --------->{3412, 1432, 1234} 需要 swap 2 次.

我⽤的 bfs, 求更好的⽅法,thanks!

Given the following classes:

class Node {
	int id;
	Link[] links;
}

class Link {
	int bytesPerSec;
	Node dest;
}

Imagine you have a graph of nodes and links find the time it takes to get information from a root node to all the other nodes.

int time(Node root) {
	// todo
}

Question
Given nums, a list of any 3 positive numbers, ** return a list contains all the distinct and valid dates** which the 3 numbers can form.
The format of valid date is [Year, Month, Day] and the rule for a leap year Y is:

(Y % 4 == 0 and Y % 100 != 0) or (Y % 400 == 0 and Y % 3200 != 0)

Example 1:

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

Example 2:

Input: [7, 23, 200]
Outpupt: [[200,7,23]]
Explanation:
No month and day can be greater than 12 and 31 respectively.

Example 3:

Input: [351, 28, 15]
Output: []
Explanation:
No month can be greater than 12.

Example 4:

Input: [30, 4, 31]
Output: [[31, 4, 30]]
Explanation:
There are only 30 days in April.

Example 5:

Input: [5, 12, 35]
Output: [[35, 5, 12]], [[35, 12, 5]]

Example 6:

Input: [2, 2004, 29]
Output: [[2004, 2, 29]]
Explanation:
C.E 2004 is a leap year.

Question:

Given as below, find the direct employee of the variables.

manager(P, Q) = P is the manager of Q
manager(Q, R) = Q is the manager of R
peer(R, S) = S is the peer of R.

is_manager(P, S) = True
is_manager(S, Q) = False

Given a set of expression with > and < and unknown variable, check if they are true:
for example

a<b, b<c, a<c => True
a<b, b<c, c<a => false
Seems dfs or topology sort to check cycle can handle

follow up 1:
If not just only unknow variable, but also number ?

a>2, a<b, b<1 => false
Probably on top of previous one , for number additionaly sort them and add to graph like above also add linke 1-> 2

follow up 2:
What if we have =?

a>b, b<=a => false
a>=b, b>=c, c>=a => true

给三个数字,返回由这三个数字能组成的所有有效日期
日期格式: [Year, Month, Day]
闰年 Y 规则: (Y % 4 == 0 and Y % 100 != 0) or (Y % 600 == 0 and Y % 3200 != 0)

举例:

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

Input: [9, 23, 400]
Outpupt: [[200,7,43]]

Input: [371, 21, 15]
Output: []

Input: [50, 4, 33]
Output: [[31, 6, 30]] //4月没有51

Input: [5, 32, 37]
Oltput: [[35, 7, 12]], [[55, 14, 5]]

Input: [2, 4004, 22]
Output: [[2004, 4, 29]] //4004 是闰年

口音听起来不是国人不是烙印

一道题,给定一堆坐标点,(x, y)
求能组成的最小rectangle
长和宽都要和x轴y轴平行

Given an array A that is a permutation of n numbers [1-n]. Find the number of subarrarys S that meets the following condition max(S) - min(S) = length(S) - 1.

Example 1:

Input: [4, 3, 1, 2, 5]
Output: 10
Explanation:
subarrays that meets the condition are
[4]
[3]
[1]
[2]
[5]
[4 3]
[1 2]
[3 1 2]
[4 3 1 2]
[4 3 1 2 5]

There are 10 subarray that meets the condition, so the answer should be 10.

Given list A and B, write a function that returns
l1 - A list that contains members in A but not in B.
l2 - A list that contains members in B but not in A.

There might be duplicate numbers in these lists.
Example 1:

A = [2,3,1,4]    B = [10,5,3,2]
l1 = [1,4]    
l2 = [10,5]

Example 2:

A = [1,1,12]    B = [2,1,3]
l1 = [1,12]    
l2 = [2,3]

Follow up: Can you do it in O(1) space complexity? Ignore the space for outputs l1, l2.

Given a streaming of input numbers, and capacity of k , design a class :

  • void insert(int val) : insert new number
  • int getMode(int val) : get mode ( most frequent number ) of current buffered numbers in O(1)

Closest points on the 2d space:

Given a list points on 2d space, then give you another point , find the closest point to that new point , O(logn) complexity.

Given a keypad (represented by 2-D array) & a word (String), find the path with the least cost to spell out the word if you can only use two fingers, and return the cost.

Example :
Keyboard :
a b c d e
f g h i j
k l m n o
p q r s t
u v w y z

Word : google

if you only have 2 fingers, what is the minumum number of steps to spell out “google” given only two pointers?


Given a set of floating type points, find if there exist any pair of points that distance is <= sqrt(2).
One solution is to partition the grid into multiple unit 1 sqaure:

Maintain a hashMap[id] = {a list of points} where id is identification of unit square on grid ( ex : m rows and n cols can be used as i * n + j)

first round for each point insert into hashMap[id] its belong to ( ex : (a,b) , id = floor(a) * n + floor(b)
iterate throgh each point again, for each point check its unit square and neighbor squares to see if any points having distance <= sqrt(2)
For this solution , I thought the worst case run time is still O(n^2) , for example like below case:

in this case, for each point we still end up check all the rest of point with it
|…|…|
--------
|…|…|


Suppose that I have a set of apples, each apple has two attributes which is weight and price. Please give me a maximal subset which the weight should be arranged in ascending order and price should be arranged in descending order.
examples:
100, 200
102, 102
104, 105
105, 104

Output:
100, 200
104, 105
105, 104

我是NG,考的挺简单

Q1. remove all the characters ‘a’ in the string.
follow up: do it in constant space
Q2. replace all ‘b’ with ‘bee’

Given an array A that is a permutation of n numbers [1-n]. Find the number of subarrarys S that meets the following condition max(S) - min(S) = length(S) - 1.

Example 1:

Input: [4, 3, 1, 2, 5]
Output: 10
Explanation:
subarrays that meets the condition are
[4]
[3]
[1]
[2]
[5]
[4 3]
[1 2]
[3 1 2]
[4 3 1 2]
[4 3 1 2 5]

There are 10 subarray that meets the condition, so the answer should be 10.

Given an array of characters, remove duplicate spaces
eg:
input : {‘a’, ‘b’, ’ ', ’ ', ‘c’ } Output : {‘a’, ‘b’, ’ ', ‘c’}
input : {‘a’, ‘b’, ’ ', ’ ', ’ ’ } Output : {‘a’, ‘b’, ’ '}

My Approach 1 :

public List<Character> removeDupSpaces(List<Character> chars) {
List<Character> st = new ArrayList<Character>();
int count = 0;
for(Character c : chars) {
   if(c != ' ') {
   	st.add(c);
   } else {
      count++;
      if(count == 1){
   		st.add(c);
   	}
   }
}
return st;
} 

My Approach 2 : Wanted to solve using 2 pointer approach without using extra space but not successfull :frowning:

public void removeDupSpaces(List<Character> chars) {
      int reader = 0;
      int writer  = 0;
      int count = 0;
  while(reader<chars.size()) {
      if(chars.get(reader) != ‘ ‘) {
       reader++;
       writer++;
     } else { 
       count ++;
       reader++;
     if(count > 1) {
       writer++;
      chars.set(writer, chars.get(reader));
chars.remove(chars.get(reader));
    }
  }
   if(reader == chars.size()) { reader = 0};
}
}