请假大家一道BB的题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请假大家一道BB的题

请假大家一道BB的题# JobHunting - 待字闺中

h*02013-01-29 08:01

1 楼

Find out the first non duplicate character in a string.
eg: "nasa" output: 'n'
只允许扫一遍字符串，如果只是用hash，需要扫2遍。我的想法是用double linked
list和hash。第一次读到char，就放到linkedlist结尾，并插入（char，对应node
pointer）到hash中。如果第二次读到这个char，把这个node删除，将hash[char]
的value变成NULL。如果删除的node为cur，那么删除cur，并让cur指向下一个。最
后返回cur的data。
这个方法可以吗？

l*b2013-01-29 08:01

2 楼

看起来很好吧

c*u2013-01-29 08:01

3 楼

hashset 一遍可以么

node

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

: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串，如果只是用hash，需要扫2遍。我的想法是用double linked
: list和hash。第一次读到char，就放到linkedlist结尾，并插入（char，对应node
: pointer）到hash中。如果第二次读到这个char，把这个node删除，将hash[char]
: 的value变成NULL。如果删除的node为cur，那么删除cur，并让cur指向下一个。最
: 后返回cur的data。
: 这个方法可以吗？

c*a2013-01-29 08:01

4 楼

linkedlist删除worst case是n吗?

p*p2013-01-29 08:01

5 楼

有个问题，"abba"，你的描述好像会返回最后的a
我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
char findFirstNonDuplicate(string str) {
int n = str.size();
if (!n) return '\0';
// assume string contains only ascii chars
int map[256] = {0};
list index_list;
for (int i = 0; i < n; ++i) {
if (!map[str[i]]) {
index_list.push_back(i);
}
++map[str[i]];
}
while (!index_list.empty()) {
if (map[str[index_list.front()]] > 1) index_list.pop_front();
else break;
}
if (!index_list.empty())
return str[index_list.front()];
else
return '\0';
}

node

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

s*n2013-01-29 08:01

6 楼

256 char数组或者32个long搞定。
loop数组或者>>找 1.

node

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

s*n2013-01-29 08:01

7 楼

bool findFirstNonDuplicate(string str, out firtchar) {
int n = str.size();
if (!n) return false;
// assume string contains only ascii chars
int map[256] = {0};
for(int i = 0 ; i < str.Length; i++)
map[str[i])++;
for (int j = 0; j < 256; j++)
if (map[j] == 1)
{
firstchar = map[j];
return true;
}
return false;

}

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

: 有个问题，"abba"，你的描述好像会返回最后的a
: 我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
: 检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
: char findFirstNonDuplicate(string str) {
: int n = str.size();
: if (!n) return '\0';
: // assume string contains only ascii chars
: int map[256] = {0};
: list index_list;
: for (int i = 0; i < n; ++i) {

B*t2013-01-29 08:01

8 楼

难道不是xor?

h*02013-01-29 08:01

9 楼

hash里面存的是linkedlist的点，所以你需要查找这个node，遇到了直接删除就行

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

: linkedlist删除worst case是n吗?

h*02013-01-29 08:01

10 楼

那面试官说只允许扫一遍，我也不知道为啥要这么要求。。其实你的方法已经可以了
。。

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

: bool findFirstNonDuplicate(string str, out firtchar) {
: int n = str.size();
: if (!n) return false;
: // assume string contains only ascii chars
: int map[256] = {0};
: for(int i = 0 ; i < str.Length; i++)
: map[str[i])++;
: for (int j = 0; j < 256; j++)
: if (map[j] == 1)
: {

h*02013-01-29 08:01

11 楼

可以设linkedlist pointer指向null， loop结束后检查pointer是否指向了null。如
果指向null了，返回\0。不过我觉得面试官考的有点无厘头。。。

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

c*u2013-01-29 08:01

12 楼

这样可以么
String str = "lacyrkaplcknb";
char[] cr = str.toCharArray();
LinkedHashSet set = new LinkedHashSet();
for (char val : cr) {
if (set.contains( val ))
set.remove( val );
else
set.add( val );
}
System.out.println( set.iterator().next() );

node

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

y*n2013-01-29 08:01

13 楼

面试中，如果遇到字符，一定要问一句字符的范围。
如果你默认是[0-255]，甚至[32-127]。
万一你兴冲冲地写完算法后，对方告诉你，你的算法对中日韩文字出错，岂不晚矣了？

c*52013-01-29 08:01

14 楼

这样写应该有问题吧。。
输出肯定是一个字典顺序的非duplicate的结果
比如输入是ba 那输出就是a而不是b吧

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

r*g2013-01-29 08:01

15 楼

基于你的算法，我稍作改变：
建立一个hashset 和一个linkedlist， linkedlist 不需要double single即可有
header和tail两个指针
对于string，在遍历时，先检验是存在于hashset之中如果存在检验下一个char
如果不存在，放到linkedlist的tail后面 tail指向这个node 同时放到hashset中
这样遍历string一边后，
从linkedlist的header 开始查找如果存在于hashset中 header指向下一个，如果不
存在于hashset
return header的value 如果header指向null return 不dupliate的char 不存在。

h*02013-01-29 08:01

16 楼

虽然俺不太懂java，但是我觉得好像有点问题。这样的序列可以通过吗？ “bbba”

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

: 这样可以么
: String str = "lacyrkaplcknb";
: char[] cr = str.toCharArray();
: LinkedHashSet set = new LinkedHashSet();
: for (char val : cr) {
: if (set.contains( val ))
: set.remove( val );
: else
: set.add( val );
: }

f*c2013-01-29 08:01

17 楼

他那个答案只是返回字母顺序第一个不是原来string 第一个，认同这句话

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

: 这样写应该有问题吧。。
: 输出肯定是一个字典顺序的非duplicate的结果
: 比如输入是ba 那输出就是a而不是b吧

h*02013-01-29 08:01

18 楼

要遍历linkedlist是吗？其实我觉得BB家的人题都是乱出的。。

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

: 基于你的算法，我稍作改变：
: 建立一个hashset 和一个linkedlist， linkedlist 不需要double single即可有
: header和tail两个指针
: 对于string，在遍历时，先检验是存在于hashset之中如果存在检验下一个char
: 如果不存在，放到linkedlist的tail后面 tail指向这个node 同时放到hashset中
: 这样遍历string一边后，
: 从linkedlist的header 开始查找如果存在于hashset中 header指向下一个，如果不
: 存在于hashset
: return header的value 如果header指向null return 不dupliate的char 不存在。

r*g2013-01-29 08:01

19 楼

string 遍历一遍即可
伪码：
for each char in string str
if char in hashtable
change the value of key char in hashtable( key char value 2)
next char
else
linkedlist.tail->next.value= char
tail = tail->next;
add char to hashtable( key char value 1)
end of loop for string // just one time
//now let us deal with the linkedlist
while( header != null){
if header value in hashtable is 2 ( hashtable.get(header)==2) // header is
duplicate
header = header->next;
else return header->value // first non-duplicate char
}
return "all char in string is duplicate"
// go through the linkedlist, can not find non-duplicate char , all char
could be found in hashtable with value 2

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

: 要遍历linkedlist是吗？其实我觉得BB家的人题都是乱出的。。

c*u2013-01-29 08:01

20 楼

一、用 HashSet 和 LinkedHashSet
String str = "cbacbbbfa";
HashSet set = new HashSet();
LinkedHashSet linkSet = new LinkedHashSet();
int len = str.length();
for (int i=0;ichar ch = str.charAt( i );
if (set.contains( ch ))
linkSet.remove( ch );
else{
set.add( ch );
linkSet.add( ch );
}
}
System.out.println( linkSet.iterator().next() );

二、用 HashSet 和 LinkedList
String str = "cbacbbbfa";
HashSet set = new HashSet();
List list = new LinkedList();
for (int i=0;ichar ch = str.charAt( i );
if (set.contains( ch )){
if(list.contains( ch ))
list.remove( (Object)ch );
}
else{
set.add( ch );
list.add( ch );
}
}
System.out.println( list.get(0) );

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

: 虽然俺不太懂java，但是我觉得好像有点问题。这样的序列可以通过吗？ “bbba”

p*p2013-01-29 08:01

21 楼

对于二：list contain方法应该是遍历的吧，这样变成O(n^2)了？

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

: 一、用 HashSet 和 LinkedHashSet
: String str = "cbacbbbfa";
: HashSet set = new HashSet();
: LinkedHashSet linkSet = new LinkedHashSet();
: int len = str.length();
: for (int i=0;i: char ch = str.charAt( i );
: if (set.contains( ch ))
: linkSet.remove( ch );
: else{

p*e2013-01-29 08:01

22 楼

试了一下，合格不
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
char getnonduplicate(string s)
{
int size = s.size();
if(size == 0) return '\0';
vector cc;
int lastnonduplicate = 0;
for(int i = 0; i < size; i++)
{
bool duplicate = false;
for(int j=0; j < cc.size(); j++)
{
if(cc[j] == s[i])
{
duplicate = true;
if(j < lastnonduplicate)
{
cc.erase(cc.begin() + j);
cc.push_back(s[i]);
lastnonduplicate--;
}
break;
}
}
if(! duplicate)
{
cc.insert(cc.begin() + lastnonduplicate, s[i]);
lastnonduplicate++;
}
}
if(lastnonduplicate != 0)
return cc[0];
else
return '\0';
}
int main() {
// Start typing your code here...
string s("nasasnmkkpppmegiil");
cout<
return 0;
}

c*t2013-01-29 08:01

23 楼

大家为啥都用linkedlist呢？
linkedlist search and remove 都是O(n)啊，最终得到一个O（n^2)算法，还不如扫两
遍。

node

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

c*u2013-01-29 08:01

24 楼

直接调 remove也行
if (set.contains( ch ))
linkSet.remove( ch );

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

: 对于二：list contain方法应该是遍历的吧，这样变成O(n^2)了？

c*u2013-01-29 08:01

25 楼

linkedlist remove 是 O(1) 吧

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

: 大家为啥都用linkedlist呢？
: linkedlist search and remove 都是O(n)啊，最终得到一个O（n^2)算法，还不如扫两
: 遍。
:
: node

w*a2013-01-29 08:01

26 楼

可以获得string的大小么？可以的话从后往前扫，用hash辅助。