【EB3 2018年2月第8绿】费城面试PD14.9 RD17.6 ID18.2 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

【EB3 2018年2月第8绿】费城面试PD14.9 RD17.6 ID18.2

【EB3 2018年2月第8绿】费城面试PD14.9 RD17.6 ID18.2# EB23 - 劳工卡

S*82018-02-02 08:02

1 楼

发个面筋攒点rp
店面：
1.实现 readline，假设提供read4k可以读取4k个字符
2.convert binary tree to double linked list
Onsite:
1.string serialize & deserialize
serialize: 输入两个string，返回serialized string
deserialize：输入serialized string，返回原来两个string
2.integer divide without using /
3.会议室安排问题
4.给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
5.regex mathing, 比leetcode上还方便一些，只要实现＋
6.colour sorting

e*y2018-02-02 08:02

2 楼

要往国内汇款2万刀左右怎么最方便，还有手续费是多少？

w*h2018-02-02 08:02

3 楼

公司以前帮申请的EB2，最后pd时间是9月11号，2014。去年年中果断降级。2017年6月
交掉485。今天上午去费城移民局Office面签。我，老婆和女儿一起浩浩荡荡去面试。
律师帮整理了差不多5斤的资料。结果3个人面试全加起来才40分钟。就问了姓名，出生
年月，还有那一堆要回答no的问题，别的啥都没问。然后就告诉我绿卡批准了。回到家
一查状态，已经变成了”卡正在生成中”。最后的处理速度真的出乎意料的快！

l*i2018-02-02 08:02

4 楼

电面第一题能解释一下么？
onsite第4题，要考虑pattern的顺序？

s*m2018-02-02 08:02

5 楼

银行电汇方便
美国这边收40左右，中间行10几

k*o2018-02-02 08:02

6 楼

恭喜这么神速！来沾沾喜气。我们下周二面试。

j*32018-02-02 08:02

7 楼

mark

x*62018-02-02 08:02

8 楼

出门右转去二手。

l*u2018-02-02 08:02

9 楼

请问哪个office？谢啦

i*u2018-02-02 08:02

10 楼

thank you so much for the sharing, big bless
could you also elaborate on the string seialization question pls?

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

: 发个面筋攒点rp
: 店面：
: 1.实现 readline，假设提供read4k可以读取4k个字符
: 2.convert binary tree to double linked list
: Onsite:
: 1.string serialize & deserialize
: serialize: 输入两个string，返回serialized string
: deserialize：输入serialized string，返回原来两个string
: 2.integer divide without using /
: 3.会议室安排问题

n*d2018-02-02 08:02

11 楼

进入二手看看

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

: 出门右转去二手。

j*92018-02-02 08:02

12 楼

恭喜恭喜。我明天面，沾沾喜气！！！

j*32018-02-02 08:02

13 楼

mark

s*72018-02-02 08:02

14 楼

看来current的同学，面试可以在local直接绿。恭喜恭喜。吧标题改统一了吧。方便统
计。

f*r2018-02-02 08:02

15 楼

Bless!

l*i2018-02-02 08:02

16 楼

哪位大牛出来讲解一下，第4题怎么做？

S*82018-02-02 08:02

17 楼

第一题，我把我当时面试的代码贴上来，可能还有问题，但面试官说可以了
class File {
static String buffer = "";
String readLine() {
if(!buffer.equals("")) { // we have characters left last time
StringBuilder sb = new StringBuilder();
int i = 0;
while(buffer.charAt(i) != '\n' && i < buffer.length()) { //
read one line
sb.append(buffer.charAt(i));
i++;
}
buffer = buffer.substring(i + 1);
if(i == buffer.length()) { // we have some caharcters in next
4k
return sb.toString() + readLine(); // }
else {
return sb.toString(); // return current line
}
}
else { // buffer is empty, we need call read4k
buffer = read4k();
if(!buffer.equals())
return readLine();
else
return "";
}
}

String read4k() {

}
}

S*82018-02-02 08:02

18 楼

Onsite第四题，不考虑顺序，我给的例子的答案应该是BA(貌似就跟leetcode的Minimum
Window Substring一样)，但是考虑顺序的话(A要在B前面)，答案就是AUB

S*82018-02-02 08:02

19 楼

seialization question，其实这个很简单，我当时的解法就是两个String合并一下，
然后在开头添加一个[num],num是第一个String的长度，然后deserialize的时候只要判
断'[]'，在把里面的数字读出来，判断一下是不是有效的就可以了

l*82018-02-02 08:02

20 楼

seialization result的前四个字节是一个int数字？

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

: seialization question，其实这个很简单，我当时的解法就是两个String合并一下，
: 然后在开头添加一个[num],num是第一个String的长度，然后deserialize的时候只要判
: 断'[]'，在把里面的数字读出来，判断一下是不是有效的就可以了

s*f2018-02-02 08:02

21 楼

那假设原string允许[num]这样的pattern呢？
有没有更generic的解法？

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

S*82018-02-02 08:02

22 楼

没有问题吧，我只要判断第一个阿，或者你可以规定开头的多少位是表示长度

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

: 那假设原string允许[num]这样的pattern呢？
: 有没有更generic的解法？

l*82018-02-02 08:02

23 楼

I see. It works. Thanks.

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

: 没有问题吧，我只要判断第一个阿，或者你可以规定开头的多少位是表示长度

d*s2018-02-02 08:02

24 楼

我觉得序列化是用来传输所以用json或xml就好了不过这个应该也可以

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

: 没有问题吧，我只要判断第一个阿，或者你可以规定开头的多少位是表示长度

f*n2018-02-02 08:02

25 楼

mark

b*g2018-02-02 08:02

26 楼

没有design的题吗？

S*12018-02-02 08:02

27 楼

Minimum
写一个考虑顺序的inverted indexing做法
//7:10
//给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
int findMinWindow(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return -1;
if (p.isEmpty())
return 0;

Map> indexMap = new HashMapInteger>>();
for (int i = 0; i < s.length(); i++) {
if (!indexMap.containsKey(s.charAt(i)))
indexMap.put(s.charAt(i), new ArrayList());

indexMap.get(s.charAt(i)).add(i);
}

List indexLists = new ArrayList[p.length];
for (int i = 0; i < p.length; i++) {
if (!indexMap.containsKey(p.charAt(i)))
return -1;

indexLists[i] = indexMap.get(p.charAt(i));
}

int minWindow = -1;
List lstBeg = indexLists[0];
for (int it : lstBeg) {
int lookForBigger = it;
for (int i = 1; i < indexLists.length; i++) {
int res = binSearchFirstBigger(indexLists[i], lookForBigger);
if (res < 0)
break;

lookForBigger = res;
}

int curWindow = (lookForBigger - it + 1);
minWindow = minWindow < 0 ? curWindow : Math.min(minWindow,
curWindow);
}

return minWindow;
}
int binSearchFirstBigger(List lst, int val) {
int beg = 0;
int end = lst.size()-1;

while (beg <= end) {
int mid = (beg + end)/2;
if (lst.get(mid > val && (mid == beg || lst.get(mid-1) <= val)))
return mid;

if (lst.get(mid) > val)
end = mid-1;
else
beg = mid + 1;
}

return mid;
}

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

: Onsite第四题，不考虑顺序，我给的例子的答案应该是BA(貌似就跟leetcode的Minimum
: Window Substring一样)，但是考虑顺序的话(A要在B前面)，答案就是AUB

S*82018-02-02 08:02

28 楼

我是new grad，所以没有design题

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

: 没有design的题吗？

m*v2018-02-02 08:02

29 楼

what is 会议室安排问题? thanks!

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

S*82018-02-02 08:02

30 楼

给很多的schedules,(start time, end time),然后计算最少用几个rooms可以安排所有
这些schedules

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

: what is 会议室安排问题? thanks!

t*72018-02-02 08:02

31 楼

bless and mark.

z*i2018-02-02 08:02

32 楼

序列化这个问题比较有意思，我的想法
1）计算长度可能不够好，字符串可能很长，溢出可能。
2）增加offset格式位，增加存储负担。
3）可能最简单就是每行写一个字符串，最多多出"rn"2个char，且容易读取。
4）最优肯定是编码映射或者压缩方案，但要求两个字符串有特定性质。在无限制字符
串环境下，不是很合适。

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

d*g2018-02-02 08:02

33 楼

这题没思路啊。。求指点

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

: 给很多的schedules,(start time, end time),然后计算最少用几个rooms可以安排所有
: 这些schedules

m*k2018-02-02 08:02

34 楼

private static String buffer="";
private static int start = 0;
private static String readLine(){

if (buffer == null){
return null;
}

int n = buffer.indexOf("n", start);
while(n<0){

String new4k = read4k();
if(new4k==null || new4k.length()==0){
String firstLine = buffer ;
buffer = null;
return firstLine;

}
start = buffer.length();
buffer+=new4k;
n = buffer.indexOf("n", start);
}

String firstLine = buffer.substring(0, n ) ;
buffer = buffer.substring(n + 1 );
return firstLine;
}

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

: 第一题，我把我当时面试的代码贴上来，可能还有问题，但面试官说可以了
: class File {
: static String buffer = "";
: String readLine() {
: if(!buffer.equals("")) { // we have characters left last time
: StringBuilder sb = new StringBuilder();
: int i = 0;
: while(buffer.charAt(i) != '\n' && i < buffer.length()) { //
: read one line
: sb.append(buffer.charAt(i));

m*k2018-02-02 08:02

35 楼

seems bug here, i compare with changed buffer length?
buffer = buffer.substring(i + 1);
if(i == buffer.length()) { // we have some caharcters in next
4k

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

m*k2018-02-02 08:02

36 楼

http://www.careercup.com/question?id=5142448749674496
sort all si and ei gloablly,
set needed = 0,
scan all sorted si and ei , see si, ++needed, see ei, --needed
take the max number you get for needed during the scanning.

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

:
: 这题没思路啊。。求指点