是否可以拿着485receipt去更新驾照 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

是否可以拿着485receipt去更新驾照

是否可以拿着485receipt去更新驾照# EB23 - 劳工卡

m*62019-01-02 08:01

1 楼

LZ在GOOGLE面试过两次，第一次是大学毕业。为了追CHICAGO的一个女孩子，申请了
GOOGLE CHICAGO的位子。第一轮CAMPUS面试通过，第二轮NEW YORK后，收到CHICAGO
的EMAIL问我availability说要为我订机票第三轮面试，三天后却收到NEW YORK的电话
说我申请的位子取消了，我没被录用。后来我在NEW YORK找了一份IT的工作。三年后
，我决定跳槽其他的IT工作， GOOGLE刚巧邀请我去面试，所以我第二次去GOOGLE面
试。这次拿到了offer，但是也拿到了更好的HFT的offer。虽然没去GOOGLE工作，但
是我很喜欢GOOGLE的面试，觉得每次都有收获。在此分享一下我被问过的问题。我也
很希望看到其他朋友们的面试问题，我会当兴趣爱好来试解答。
Behavior Questions:
1. In java, a method declared as private restrict access to within the class
. For example, a private void doHeartbeat() method within Heartbeat class
can only be called within the Heartbeat class. However, it doesn't prevent
the Heartbeat class to access the method of a different Heartbeat object.
For example, a private void forceHeartbeat(Heartbeat other) method is
allowed to call other.doHeartbeat(). Java doesn't provide a way to limit
access to a per object level. Why not?
2. Given set amount of memory and ram, how do you implement a process that
takes the longest amount of time to finish? The process has to finish, it
can not be an infinite loop. (Of all of the questions I got asked from
Google, I'm not sure I know the right answer to this one to this day)
Coding Questions:
1. Bar chart island. Given a two dimensional island that looks like a bar
chart represented by an int array. Calculate the amount of water it can
collect when it rains on the island. For example, [1,2,3] collects no water,
[2,1,3] collects 1 unit of water, [3,2,1,4] collects 3 units of water, [3,2
,4,1,5] collects 4 units of water.
2. Ancestor. You are ancestry.com, you have a graph of related ancestors.
One ancestor node contains the following fields: Node mother, Node father,
Node[] children. Write a method that checks if two Nodes are blood related.
For example, you and your half brother is blood related, your father and
your mother are (hopefully but not guaranteed to be ) not blood related.
Please note that information might be incomplete meaning mother, father or
children can all be null.
3. Eviction Hash Map. Write a hash map that can store at most N key value
pairs. If more than N key value pairs are associated, the least recently
accessed key value pair is removed from the map. For example, for a map of
capacity 3. put(1,1), put(2,2), put(3,3), put(4,4) will cause key 1 to be
removed. However, put(1,1), put(2,2), put(3,3), get(1), put(4,4) will cause
key 2 to be removed, put(5,5) will cause key 3 to be removed.
4. Meeting place. You have a city with streets running parallel both
horizonally and vetically creating a giant grid. The dimension of each grid
is 1 X 1. All street corners in the city can be represented by a coordinate
(int x, int y). Given an array of people represented by their closest street
corner, calculate a street corner to meet where their combined traveling
distance is the shortest. Assume everyone can only travel on road. For
example, the traveling distance from [1,1] to [2,2] is 2.
5. Nth largest from tree. Given a binary search tree where the left node is
smaller and the right node is larger. Calculate the Nth largest number in
the tree throwing exception when there is less than N elements in the tree.
6. Anagram solver. An anagram is two words that contains the same letters
the same amount of times. For example, angle and angel are anagrams. Given a
dictionary, perform some preprocessing for a anagram solver. The anagram
solver takes a string as input and prints out a list of all anagrams
contained in the dictionary.
7. Next tree sibling. Given a tree where each node has left and right
pointers
, implement a function that sets the next pointer. Next pointer will point
to a node in the same level immediately to the right. For example, if a node
has both left and right children, next pointer of the left child will point
to the right child. The next pointer of the right child will point to
parent's sibling's left child. The fact that left child and right child can
both be null make things complicated.

h*12019-01-02 08:01

2 楼

是否可以拿着485的receipt去更新驾照？这样做有什么风险吗？我去bmv问了，说是可
以更新驾照，但不知道这样做是否会带来问题，刚提交485，准备去打指纹，用
485receipt更新驾照会不会给background check带来麻烦？谢谢

j*82019-01-02 08:01

3 楼

Behavior的第一题没看懂。。哪位讲讲？

n*d2019-01-02 08:01

4 楼

y*n2019-01-02 08:01

5 楼

谢谢分享，5和7你为什么要说map，这不就是Tree吗？

r*a2019-01-02 08:01

6 楼

办驾照怎么还要485的收据？护照就行了吧？

y*n2019-01-02 08:01

7 楼

是不是问为什么Private Method 可以在Class 内部被调用。

【在 j*****8 的大作中提到】

: Behavior的第一题没看懂。。哪位讲讲？

w*e2019-01-02 08:01

8 楼

第二题我记得我看面经也看过，一直也查不到，没想到刚刚中文google了下，发现有这
个答案
假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定
性终止（非死循环），问如何求得这台计算机上程序运行的最长时间，可以做出任何
大胆的假设。
分析：任何时候内存状态都不能相同，否则进入死循环：假设某2个时刻t1,t2满足t1小
于t2，内存的状态完全相同，那么到达t2时刻又想当于回到了t1的执行位置。1k的内存
共有状态 2^(1024*8)个（相当大）每秒cpu为1m，一秒钟改变1m次，所以两者相除即可
得CPU的最长运行时

j*82019-01-02 08:01

9 楼

我的理解好像不是，不是调用this.privateMethod()，是调用另外一个instance的
private method

【在 y***n 的大作中提到】

: 是不是问为什么Private Method 可以在Class 内部被调用。

m*62019-01-02 08:01

10 楼

Thank you. Brain freeze. I typed too much.

【在 y***n 的大作中提到】

: 谢谢分享，5和7你为什么要说map，这不就是Tree吗？

m*62019-01-02 08:01

11 楼

public class Heartbeat
{
private void doHeart() {}

private void forceHeart(Heartbeat other) {other.doHeart();}

public static void main(String[] args)
{
Heartbeat a = new Heartbeat();
Heartbeat b = new Heartbeat();
b.forceHeart(a);
}
}
The above program is legal in Java. Object b in this case is able to access
the private method of object a. Java does not provide a way to restrict
access on a per object level, why not?

【在 j*****8 的大作中提到】

: 我的理解好像不是，不是调用this.privateMethod()，是调用另外一个instance的
: private method

m*62019-01-02 08:01

12 楼

Thank you. The answer I gave during the interview is to clear all memory and
treat it like a big number. I increment by 1 per cpu cycle. I was never
able to provide a good enough argument for why this is the slowest possible
program. I like your explanation. It is impossible to prevent an infinite
loop if memory got into the same state without terminating.

【在 w******e 的大作中提到】

: 第二题我记得我看面经也看过，一直也查不到，没想到刚刚中文google了下，发现有这
: 个答案
: 假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定
: 性终止（非死循环），问如何求得这台计算机上程序运行的最长时间，可以做出任何
: 大胆的假设。
: 分析：任何时候内存状态都不能相同，否则进入死循环：假设某2个时刻t1,t2满足t1小
: 于t2，内存的状态完全相同，那么到达t2时刻又想当于回到了t1的执行位置。1k的内存
: 共有状态 2^(1024*8)个（相当大）每秒cpu为1m，一秒钟改变1m次，所以两者相除即可
: 得CPU的最长运行时

j*82019-01-02 08:01

13 楼

答不出来，请指点。。

【在 m********6 的大作中提到】

: public class Heartbeat
: {
: private void doHeart() {}
:
: private void forceHeart(Heartbeat other) {other.doHeart();}
:
: public static void main(String[] args)
: {
: Heartbeat a = new Heartbeat();
: Heartbeat b = new Heartbeat();

y*n2019-01-02 08:01

14 楼

同求，这个有什么高深的东西吗？

【在 j*****8 的大作中提到】

: 答不出来，请指点。。

m*62019-01-02 08:01

15 楼

It's not too difficult.
In java, access restriction is enforced during compilation time. If a class
try to access the private method of a different class, it wouldn't compile.
On the other hand, objects are created during runtime. In order to properly
perform object level access restriction, java will have to check access
restrictions during runtime on everything method call. This is too costly.

【在 y***n 的大作中提到】

: 同求，这个有什么高深的东西吗？

y*n2019-01-02 08:01

16 楼

谢谢分享。。

【在 m********6 的大作中提到】

: Thank you. The answer I gave during the interview is to clear all memory and
: treat it like a big number. I increment by 1 per cpu cycle. I was never
: able to provide a good enough argument for why this is the slowest possible
: program. I like your explanation. It is impossible to prevent an infinite
: loop if memory got into the same state without terminating.

m*v2019-01-02 08:01

17 楼

谢谢分享

CHICAGO
class

【在 m********6 的大作中提到】

: LZ在GOOGLE面试过两次，第一次是大学毕业。为了追CHICAGO的一个女孩子，申请了
: GOOGLE CHICAGO的位子。第一轮CAMPUS面试通过，第二轮NEW YORK后，收到CHICAGO
: 的EMAIL问我availability说要为我订机票第三轮面试，三天后却收到NEW YORK的电话
: 说我申请的位子取消了，我没被录用。后来我在NEW YORK找了一份IT的工作。三年后
: ，我决定跳槽其他的IT工作， GOOGLE刚巧邀请我去面试，所以我第二次去GOOGLE面
: 试。这次拿到了offer，但是也拿到了更好的HFT的offer。虽然没去GOOGLE工作，但
: 是我很喜欢GOOGLE的面试，觉得每次都有收获。在此分享一下我被问过的问题。我也
: 很希望看到其他朋友们的面试问题，我会当兴趣爱好来试解答。
: Behavior Questions:
: 1. In java, a method declared as private restrict access to within the class

j*82019-01-02 08:01

18 楼

茅塞顿开。多谢！

class
.
properly

【在 m********6 的大作中提到】

: It's not too difficult.
: In java, access restriction is enforced during compilation time. If a class
: try to access the private method of a different class, it wouldn't compile.
: On the other hand, objects are created during runtime. In order to properly
: perform object level access restriction, java will have to check access
: restrictions during runtime on everything method call. This is too costly.

g*s2019-01-02 08:01

19 楼

你这个了两个完全状态就进入循环，是需要最少假设了所有函数都跟时间无关(随机数
也要和时间无关）。
例如这个
while(true){
getCurrentTime() >　2015年1月1日
}

【在 w******e 的大作中提到】

m*62019-01-02 08:01

20 楼

You are making the assumption that there is a timer which is not a given. If
there is a timer, you can use some memory to keep a unix timestamp value.
Fire when the timestamp value is the same (every time unix time rolls over),
increment the remaining memory each time until the remaining memory rolls
over.

你这个了两个完全状态就进入循环，是需要最少假设了所有函数都跟时间无关(随机数
也要和时间无关）。例如这个while(true){ getCurrentTime()

【在 g***s 的大作中提到】

: 你这个了两个完全状态就进入循环，是需要最少假设了所有函数都跟时间无关(随机数
: 也要和时间无关）。
: 例如这个
: while(true){
: getCurrentTime() >　2015年1月1日
: }

g*s2019-01-02 08:01

21 楼

我是举个反例说明woodgate给的解释不对。他要用这个方法判断是否有死循环是不行的
。因为没有假设有timer，但也没有假设没有。

If
),

【在 m********6 的大作中提到】

: You are making the assumption that there is a timer which is not a given. If
: there is a timer, you can use some memory to keep a unix timestamp value.
: Fire when the timestamp value is the same (every time unix time rolls over),
: increment the remaining memory each time until the remaining memory rolls
: over.
:
: 你这个了两个完全状态就进入循环，是需要最少假设了所有函数都跟时间无关(随机数
: 也要和时间无关）。例如这个while(true){ getCurrentTime()

m*k2019-01-02 08:01

22 楼

7. Next tree sibling. Given a tree where each node has left and right
pointers
, implement a function that sets the next pointer. Next pointer will point
to a node in the same level immediately to the right. For example, if a node
has both left and right children, next pointer of the left child will point
to the right child. The next pointer of the right child will point to
parent's sibling's left child. The fact that left child and right child can
both be null make things complicated.
BFS using queue 小小变一下？

CHICAGO
class

【在 m********6 的大作中提到】

m*62019-01-02 08:01

23 楼

You bring up a good point.

我是举个反例说明woodgate给的解释不对。他要用这个方法判断是否有死循环是不行的
。因为没有假设有timer，但也没有假设没有。

【在 g***s 的大作中提到】

: 我是举个反例说明woodgate给的解释不对。他要用这个方法判断是否有死循环是不行的
: 。因为没有假设有timer，但也没有假设没有。
:
: If
: ),

m*62019-01-02 08:01

24 楼

If you go from root and set next pointer level by level. You can use
previous level's next pointers to help you traverse. It's just messy to
implement with all of the edge cases. This question is so much easier on a
balanced tree, which if I remembered correctly was the initial question
during the interview session.

7. Next tree sibling. Given a tree where each node has left and
rightpointers, implement........

【在 m*****k 的大作中提到】

: 7. Next tree sibling. Given a tree where each node has left and right
: pointers
: , implement a function that sets the next pointer. Next pointer will point
: to a node in the same level immediately to the right. For example, if a node
: has both left and right children, next pointer of the left child will point
: to the right child. The next pointer of the right child will point to
: parent's sibling's left child. The fact that left child and right child can
: both be null make things complicated.
: BFS using queue 小小变一下？
:

x*a2019-01-02 08:01

25 楼

除了BFS的方法外，还有其他什么方法？

【在 m********6 的大作中提到】

: If you go from root and set next pointer level by level. You can use
: previous level's next pointers to help you traverse. It's just messy to
: implement with all of the edge cases. This question is so much easier on a
: balanced tree, which if I remembered correctly was the initial question
: during the interview session.
:
: 7. Next tree sibling. Given a tree where each node has left and
: rightpointers, implement........

d*i2019-01-02 08:01

26 楼

For the first question.
Another way to think the first question maybe that there could be a class or
instance method that accepts a object of itself as argument. In that case,
by definition of private accessor is that an instance can access its private
method, However, at compile time, it cannot be determined if this arg is
the instance of itself or not. So java has to allow that situation to happen
.
Well, not sure whether this is a good way to answer this question.

c*z2019-01-02 08:01

27 楼

请问2和4怎么做？

CHICAGO
class

【在 m********6 的大作中提到】

m*62019-01-02 08:01

28 楼

2. The key is to understand what it means to be blood related. It means that
if you trace the lineages of both nodes upwards starting from self, to
parents, to parent's parent, etc the two nodes hit a common ancestor node.
For example, you are your cousin are blood related because you share the
same grand parents. After understanding that, you can elaborate on
implementation. BST probably works the best.
4. Again, the key is to understanding how to minimize the combined distance
travelled. First of all, since you have to travel on the grid, x and y axis
are completely independent. On a given axis, the medium meeting place will
yield the shortest combined distance because if you go either direction by 1
from the medium, half of the people will travel 1 less block, and half plus
one people will travel 1 more block (For even number of people, any point
between the two middle will yield optimal result). In terms of
implementation, I'm not aware of a way to calculate the medium that's better
than O(N logN) which you can get by sorting (this is your opportunity to
shire with your sorting knowledge).

【在 c**z 的大作中提到】

: 请问2和4怎么做？
:
: CHICAGO
: class

g*s2019-01-02 08:01

29 楼

as i remember, nth_element in stl is O(n), which can be used to calculate
the median (i think you meant median instead of medium).

that
distance
axis
1

【在 m********6 的大作中提到】

: 2. The key is to understand what it means to be blood related. It means that
: if you trace the lineages of both nodes upwards starting from self, to
: parents, to parent's parent, etc the two nodes hit a common ancestor node.
: For example, you are your cousin are blood related because you share the
: same grand parents. After understanding that, you can elaborate on
: implementation. BST probably works the best.
: 4. Again, the key is to understanding how to minimize the combined distance
: travelled. First of all, since you have to travel on the grid, x and y axis
: are completely independent. On a given axis, the medium meeting place will
: yield the shortest combined distance because if you go either direction by 1

y*e2019-01-02 08:01

30 楼

Use a stack to track the level of tree nodes
Input:
Node root
----------
provide a wrapper class for Node which contains level
NodeWrapper{
Node node
int level
}
Stack stack;
List list;
int i = 1;
stack.push (root, i)
while (stack not empty){
NodeWrapper current = stack.pop();
list.append(current);
if (current->right != null){
stack.push(right, i + 1);
}
if (current->left != null){
stack.push(left, i + 1);
}
}
The list contains in order traversal of all the tree nodes, so traverse the
list once, and link all nodes of the same level.
Each node is pushed and popped once to the stack, so the run time complexity
is 2n or 3n depending on how you count. This might not be the most
efficient solution, but it is good for an interview because it's clean.

【在 x*********a 的大作中提到】

: 除了BFS的方法外，还有其他什么方法？

m*62019-01-02 08:01

31 楼

I like this a lot. It's so neat. Not a lot edge cases.

【在 y*e 的大作中提到】

: Use a stack to track the level of tree nodes
: Input:
: Node root
: ----------
: provide a wrapper class for Node which contains level
: NodeWrapper{
: Node node
: int level
: }
: Stack stack;