saturday night (almost) live - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PhotoGear - 摄影器材

saturday night (almost) live

saturday night (almost) live# PhotoGear - 摄影器材

w*x2010-04-10 07:04

1 楼

//Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 && nIndex2 >= nIndex1)
{
for (int i = nIndex1; i <= nIndex2; i++)
cout<}
else cout<}
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2)
{
if (nBeg < 0 || nEnd < nBeg || nPos < 0)
{
index1 = index2 = -1;
return;
}
//left boundary
int s = nBeg;
int e = nEnd;
index1 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nBeg ||
strs[nMid][nPos] != strs[nMid-1][nPos]))
{
index1 = nMid;
break;
}
else if (strs[nMid][nPos] > chr || strs[nMid][nPos] == chr)
e = nMid - 1;
else s = nMid + 1;
}
//right boundary
s = nBeg;
e = nEnd;
index2 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nEnd ||
strs[nMid][nPos] != strs[nMid+1][nPos]))
{
index2 = nMid;
break;
}
else if (strs[nMid][nPos] < chr || strs[nMid][nPos] == chr)
s = nMid + 1;
else e = nMid - 1;
}
}

S*l2010-04-10 07:04

2 楼

估计transfer下来还要1个月。原来的2014年过期，能用来带款么？
多谢指教

r*r2010-04-10 07:04

3 楼

晚饭后晃出去摁了几张.

z*h2010-04-10 07:04

4 楼

private void printstringwithprefix(String[] ss, String prefix) {
if(ss == null) return;
if(prefix == null || prefix.isEmpty()) return;
int low = 0;
int high = ss.length -1;
for(int i = 0; i< prefix.length() && low <= high; i++)
{
int mid = (low+high)/2;

if(i >= ss[mid].length())
{
return;
}

if(ss[mid].charAt(i) < prefix.charAt(i))
low = mid + 1;
else if(ss[mid].charAt(i) > prefix.charAt(i))
high = mid -1;
else // ==
{
low = mid;
high = mid;
while(low> 0 && ss[low - 1].charAt(i) == prefix.charAt(i))
--low;
while(high < ss.length -1 && ss[high + 1].charAt(i) ==
prefix.charAt(i))
++high;
}
}
if(low > high)
return;
for(int i = low; i <= high; i++)
Helper.println(ss[i]);
}

k*o2010-04-10 07:04

5 楼

如果还有6month, 应该没问题.如果<6month,看具体situation.

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

: 估计transfer下来还要1个月。原来的2014年过期，能用来带款么？
: 多谢指教

T*t2010-04-10 07:04

6 楼

sf?

【在 r*********r 的大作中提到】

: 晚饭后晃出去摁了几张.

p*22010-04-10 07:04

7 楼

这题有什么tricky得地方吗？

S*l2010-04-10 07:04

8 楼

2014年过期，你是指这个么？现在的那个797和工作单位不一样，还是前一个工作单位
的。

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

: 如果还有6month, 应该没问题.如果<6month,看具体situation.

t*a2010-04-10 07:04

9 楼

NYC?

p*22010-04-10 07:04

10 楼

这是zhangchi面经里的题吧？应该就是binary search吧。

p*y2010-04-10 07:04

11 楼

已经换公司了吧？如果pay stub上已经不是原来H1B上的那家，就最好是等新的H1B拿到
之后再做了。

v*a2010-04-10 07:04

12 楼

你捏的呢

【在 T*******t 的大作中提到】

: sf?

w*x2010-04-10 07:04

13 楼

没啥trick, 就是binary search.
现在的题都没啥太难得, 就是考binary search的变种和编程的细节.
不过这题白板写说实话真心不容易

【在 p*****2 的大作中提到】

: 这是zhangchi面经里的题吧？应该就是binary search吧。

b*d2010-04-10 07:04

14 楼

会有问题，银行会问为什么sponsor和现在的工作单位不一样。

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

: 2014年过期，你是指这个么？现在的那个797和工作单位不一样，还是前一个工作单位
: 的。

c*y2010-04-10 07:04

15 楼

肯定还没洗出来吧。

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

: 你捏的呢

p*22010-04-10 07:04

16 楼

找两边的boundary能不能合并一下？做个sub function?

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

:
: 没啥trick, 就是binary search.
: 现在的题都没啥太难得, 就是考binary search的变种和编程的细节.
: 不过这题白板写说实话真心不容易

T*t2010-04-10 07:04

17 楼

我后来给娃买消防车去了....没捏

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

: 你捏的呢

l*a2010-04-10 07:04

18 楼

把题说清楚点吧
是数组所有string的common prefix?

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

: //Print strings with certain prefix in a sorted string array
: void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
: OUT int& index1, int& index2);
: void PrintComPrefix(const char* strs[], int n, const char* szPre)
: {
: assert(strs && szPre && n > 0);
: const char* p = szPre;
: int nIndex1 = 0;
: int nIndex2 = n-1;
: while (*p != 0 && nIndex1 >= 0)

r*r2010-04-10 07:04

19 楼

这是新泽西居民的视角...
再往布鲁克林看一点

w*x2010-04-10 07:04

20 楼

其实还真能合, 写这个程序的时候这里就很别扭, 不过算了, 麻烦死了

【在 p*****2 的大作中提到】

:
: 找两边的boundary能不能合并一下？做个sub function?

T*t2010-04-10 07:04

21 楼

ah...中间隔的什么岛？

【在 r*********r 的大作中提到】

: 这是新泽西居民的视角...
: 再往布鲁克林看一点

p*22010-04-10 07:04

22 楼

呵呵。F家BS是必考的。这道题也差不多算很难的了。我有时间也得练练。这两天太累
，没心情做题。看你做的很开心呀。

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

:
: 其实还真能合, 写这个程序的时候这里就很别扭, 不过算了, 麻烦死了

T*t2010-04-10 07:04

23 楼

你这是住在liberty park附近的吧

【在 r*********r 的大作中提到】

: 这是新泽西居民的视角...
: 再往布鲁克林看一点

w*x2010-04-10 07:04

24 楼

感情受挫折了, 心烦做题玩, 每天都不知道该干啥, 难受死了.
一天也就两道题, 算起来一共就不到一小时, 短的半小时.

【在 p*****2 的大作中提到】

:
: 呵呵。F家BS是必考的。这道题也差不多算很难的了。我有时间也得练练。这两天太累
: ，没心情做题。看你做的很开心呀。

r*r2010-04-10 07:04

25 楼

中间是 ellis 岛, 早年纽约的移民监狱.
不是三番的那个岛 :)

【在 T*******t 的大作中提到】

: ah...中间隔的什么岛？

y*u2010-04-10 07:04

26 楼

比我强
我发现我不光水平差，而且对cs完全没兴趣，书一看5页就想上youtube

太累

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

:
: 感情受挫折了, 心烦做题玩, 每天都不知道该干啥, 难受死了.
: 一天也就两道题, 算起来一共就不到一小时, 短的半小时.

T*t2010-04-10 07:04

27 楼

那你很靠南了...

【在 r*********r 的大作中提到】

: 中间是 ellis 岛, 早年纽约的移民监狱.
: 不是三番的那个岛 :)

p*22010-04-10 07:04

28 楼

这么强？5页？我一般就看半页。

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

: 比我强
: 我发现我不光水平差，而且对cs完全没兴趣，书一看5页就想上youtube
:
: 太累

v*a2010-04-10 07:04

29 楼

教主在家就能看到

【在 T*******t 的大作中提到】

: 那你很靠南了...

p*22010-04-10 07:04

30 楼

写了一个练练手。
// assume prefix exists
int Find(String[] words, String prefix, boolean left)
{
int l = 0;
int r = words.length - 1;
while (l < r)
{
int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
String s = words[m];
if (s.length() > prefix.length())
s = s.substring(0, prefix.length());
if (s.compareTo(prefix) < 0)
{
l = m + 1;
}
else if (s.compareTo(prefix) > 0)
{
r = m - 1;
}
else
{
if (left)
{
r = m;
}
else
{
l = m;
}
}
}
return l;
}

T*t2010-04-10 07:04

31 楼

这个是在家打的

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

: 教主在家就能看到

w*x2010-04-10 07:04

32 楼

bug, while里是<=

【在 p*****2 的大作中提到】

: 写了一个练练手。
: // assume prefix exists
: int Find(String[] words, String prefix, boolean left)
: {
: int l = 0;
: int r = words.length - 1;
: while (l < r)
: {
: int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
: String s = words[m];

r*r2010-04-10 07:04

33 楼

这个要九月份才能打到...

【在 T*******t 的大作中提到】

: 这个是在家打的

p*22010-04-10 07:04

34 楼

我怎么觉得＝＝的时候就可以退出了？我是assume prefix是存在的。

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

:
: bug, while里是<=

T*t2010-04-10 07:04

35 楼

过期胶片打的
翻拍的正片...

【在 r*********r 的大作中提到】

: 这个要九月份才能打到...

w*x2010-04-10 07:04

36 楼

要是数组只有一个, 而且这个满足条件, 你的程序直接跳出来找不到了

【在 p*****2 的大作中提到】

:
: 我怎么觉得＝＝的时候就可以退出了？我是assume prefix是存在的。

r*r2010-04-10 07:04

37 楼

看来帮主是在 exchange place 了.

p*22010-04-10 07:04

38 楼

String[] ss = new String[]
{ "aaa", "abc", "abcd", "abcde", "bbb" };
out.println(Find(ss, "abcde", true));
out.println(Find(ss, "abcde", false));
o我的程序返回3

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

:
: 要是数组只有一个, 而且这个满足条件, 你的程序直接跳出来找不到了

c*y2010-04-10 07:04

39 楼

哈哈，今天晚上教主棒打帮主，
然后自己就升为帮主了。。。

【在 r*********r 的大作中提到】

: 看来帮主是在 exchange place 了.

z*h2010-04-10 07:04

40 楼

为啥一定要找分两次找ｌｅｆｔ／ｒｉｇｈｔ？
遇到ｍ＝＝ｐｒｅｆｉｘ的时候，两边扩展一下找到边界不好吗？

r*r2010-04-10 07:04

41 楼

原来是教主啊. 什么教的? 我以为就是丐帮帮主了.

p*22010-04-10 07:04

42 楼

那就是O(n)e了。

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

: 为啥一定要找分两次找ｌｅｆｔ／ｒｉｇｈｔ？
: 遇到ｍ＝＝ｐｒｅｆｉｘ的时候，两边扩展一下找到边界不好吗？

v*a2010-04-10 07:04

43 楼

接着MARK
鸡冻人心的一夜啊

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

: 哈哈，今天晚上教主棒打帮主，
: 然后自己就升为帮主了。。。

w*x2010-04-10 07:04

44 楼

没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成

【在 p*****2 的大作中提到】

:
: 那就是O(n)e了。

p*22010-04-10 07:04

45 楼

恩。返回的0.

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

:
: 没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成

t*e2010-04-10 07:04

46 楼

没错，我总是搞不清最后几数。差不多4个case:
1. search for a number.
2. search for insert index.
3. search for lower bound of a range.
4. search for upper bound of range.

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

:
: 没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成

z*h2010-04-10 07:04

47 楼

不是从头找。是二分找到一个相等值后，再左右两边扩展找左右边界。ｏ（ｌｇｎ　+k
) k　＝有相同ｐｒｅｆｉｘ的ｓｔｒｉｎｇ的个数。

【在 p*****2 的大作中提到】

:
: 恩。返回的0.

z*h2010-04-10 07:04

48 楼

int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
是为啥？

【在 p*****2 的大作中提到】

p*22010-04-10 07:04

49 楼

+k
k跟n没什么区别。时间复杂度一样。

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

: 不是从头找。是二分找到一个相等值后，再左右两边扩展找左右边界。ｏ（ｌｇｎ　+k
: ) k　＝有相同ｐｒｅｆｉｘ的ｓｔｒｉｎｇ的个数。