由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 【一个BB公司问的字母排序的问题】
相关主题
请教c++的string vector问题,谢谢!fb 电面
Microsoft interview question再问个简单的C问题
请教一道题目GOOG intern interview 题目
今天才整明白Permutation的最优解!?今天G家电面的一道题
Dream company Onsite被搞了(少量面经)为什么我这段简单的程序segment fault
问一个C++ set和unordered_set iterator的问题再问一个碰到的C++问题
reverse words in a string为啥这个swap不可以?
求问一道G家Onsite题顶风上来问道题:一个很大char[], 如何in-place 删除重复元素
相关话题的讨论汇总
话题: string话题: reference话题: chars话题: char话题: input
进入JobHunting版参与讨论
1 (共1页)
h*****g
发帖数: 944
1
说是有一个string, ABBFKCEDG; 还有一个reference string BAC
说是要把第一个string里的字母按照reference string里字母的顺序进行排序(没有出
现在reference string里的字母按原来的顺序写在后面),有什么比较好的办法?
for example, the first string should output at
BBACFKEDG
j***r
发帖数: 69
2
1. write a comparator function for character comparison according to the
reference string. This comparator will be used in partition function of sort.
2. quicksort
g***s
发帖数: 3811
3
1. put the strings into a linked char list.
2. scan the char list and remove & count the chars which in reference
string. O(n)
3. sort based on the counted result. O(m lgm) m is the length of the
reference string
4. add the reference chars at the beginning of the list based on the
sorted result.
【在 h*****g 的大作中提到】
: 说是有一个string, ABBFKCEDG; 还有一个reference string BAC
: 说是要把第一个string里的字母按照reference string里字母的顺序进行排序(没有出
: 现在reference string里的字母按原来的顺序写在后面),有什么比较好的办法?
: for example, the first string should output at
: BBACFKEDG

g***s
发帖数: 3811
4
quicksort is not a stable sort.

sort.

【在 j***r 的大作中提到】
: 1. write a comparator function for character comparison according to the
: reference string. This comparator will be used in partition function of sort.
: 2. quicksort

r*******y
发帖数: 1081
5
step 2 怎么是 O(n) ? 应该是 O(kn)吧,k是reference string 的size

【在 g***s 的大作中提到】
: 1. put the strings into a linked char list.
: 2. scan the char list and remove & count the chars which in reference
: string. O(n)
: 3. sort based on the counted result. O(m lgm) m is the length of the
: reference string
: 4. add the reference chars at the beginning of the list based on the
: sorted result.
m**q
发帖数: 189
6
A in-place string sorting method inspired by your idea:
1. partition the string - the left part contains chars
which appears in reference string, the right part contains
the rest chars. At the same time, count the chars appeared
in reference string. O(n)
2. overwrite the original string from the beginning, as
we already have the counters calculated in step 1. The
result is the left part is overwritten with chars with
the correct order, and the right part remains unchanged
from step 1. O(k) while k is the length of left part.
The advantage is it doesn't require additional linked list
which occupies O(n) space.

【在 g***s 的大作中提到】
: 1. put the strings into a linked char list.
: 2. scan the char list and remove & count the chars which in reference
: string. O(n)
: 3. sort based on the counted result. O(m lgm) m is the length of the
: reference string
: 4. add the reference chars at the beginning of the list based on the
: sorted result.
m**q
发帖数: 189
7
Create an array for all possible chars, e.g. if don't consider
unicode stuff, there are 256 total chars. Initialize the array,
entries which appear in reference string is set to 1, otherwise 0.
Scan the string and check&count each char by:
if (appear[a[i]]) counter[a[i]]++;

【在 r*******y 的大作中提到】
: step 2 怎么是 O(n) ? 应该是 O(kn)吧,k是reference string 的size
s*****y
发帖数: 897
8
Sounds good. I write the code according to your idea. But still need to defi
ne a 256 byte array to hash the reference string and count the times they ap
pear.
Any better way I could ger rid of the 256 byte array?
#define SWAP(A,B) { \
char tmp; \
tmp = A; \
A = B; \
B = tmp; }
char input[] = "ABBFKCEDGAB";
char pattern[] = "BAC";
void SortString(char input[], char pattern[])
{
char hash[256] = {0};
int i,j;
int count;

i = 0;
while(pattern[i]) {
hash[pattern[i]] = 1;
i++;
}

for (i = -1, j = 0; input[j] ; j++) {
if ((hash[input[j]] & 0x1) == 1) {
//use the higher 7 bits to count the character, 0bit to check if
the character present
hash[input[j]] = (hash[input[j]] & 0x1) | (((hash[input[j]] >> 1
) + 1) << 1);
i++;
SWAP(input[i],input[j]);
}
}
//SORT THE STRING BASE ON COUNT
i = 0;
j = 0;
while(pattern[i]) {
for(count = hash[pattern[i]] >> 1 ; count > 0; count--) {
input[j] = pattern[i];
j++;
}
i++;
}

return;
}
int main()
{
char input[] = "ABBFKCEDGAB";
char pattern[] = "BAC";
SortString(input, pattern);
return 0;
}

【在 m**q 的大作中提到】
: A in-place string sorting method inspired by your idea:
: 1. partition the string - the left part contains chars
: which appears in reference string, the right part contains
: the rest chars. At the same time, count the chars appeared
: in reference string. O(n)
: 2. overwrite the original string from the beginning, as
: we already have the counters calculated in step 1. The
: result is the left part is overwritten with chars with
: the correct order, and the right part remains unchanged
: from step 1. O(k) while k is the length of left part.

g***s
发帖数: 3811
9
It is not correct since it is not stable. - it may changes the order of the
chars that are not in the reference string.

defi
ap

【在 s*****y 的大作中提到】
: Sounds good. I write the code according to your idea. But still need to defi
: ne a 256 byte array to hash the reference string and count the times they ap
: pear.
: Any better way I could ger rid of the 256 byte array?
: #define SWAP(A,B) { \
: char tmp; \
: tmp = A; \
: A = B; \
: B = tmp; }
: char input[] = "ABBFKCEDGAB";

g**e
发帖数: 6127
10
1. use a linked hashmap to add the reference string, char as key, counter as
value, initialized to 0
2. scan target string, update the hashmap counter, put the chars that are
not in ref string to the front of the original string.
3. iterate the linked hashmap, then append the rest in the end.

【在 h*****g 的大作中提到】
: 说是有一个string, ABBFKCEDG; 还有一个reference string BAC
: 说是要把第一个string里的字母按照reference string里字母的顺序进行排序(没有出
: 现在reference string里的字母按原来的顺序写在后面),有什么比较好的办法?
: for example, the first string should output at
: BBACFKEDG

相关主题
问一个C++ set和unordered_set iterator的问题fb 电面
reverse words in a string再问个简单的C问题
求问一道G家Onsite题GOOG intern interview 题目
进入JobHunting版参与讨论
g*********s
发帖数: 1782
11
it is an interesting question. no need to iterate hashmap. just scan the
ref str at the last step.
basically it's a remove_if() + count_sort() combined problem. O(n) T and
O(n) S.
but remember to scan the string from the tail for remove_if().

counter as
are

【在 g**e 的大作中提到】
: 1. use a linked hashmap to add the reference string, char as key, counter as
: value, initialized to 0
: 2. scan target string, update the hashmap counter, put the chars that are
: not in ref string to the front of the original string.
: 3. iterate the linked hashmap, then append the rest in the end.

j***r
发帖数: 69
12
You're right. Use merge sort. Time O(n log n)
An alternative method is counting sort. Time is O(n).

【在 g***s 的大作中提到】
: quicksort is not a stable sort.
:
: sort.

e********s
发帖数: 248
13
1. Recoding the characters:
ABBFKCEDG => A B B FK C EDG
012345678 -2 -3 -3 34 -1 678
'B' => -3
'A' => -2
'C' => -1
2. Then use the regular qsort.
m**q
发帖数: 189
14
Grass is correct, this is not stable thus some chars could
be re-ordered.
A correction is, for step 1, don't partition the string, but
only count each char appeared in the reference string, and
also the total number of chars appeared in the reference string.
Do an in-place deletion from the end. Step 2 is the same.

【在 m**q 的大作中提到】
: A in-place string sorting method inspired by your idea:
: 1. partition the string - the left part contains chars
: which appears in reference string, the right part contains
: the rest chars. At the same time, count the chars appeared
: in reference string. O(n)
: 2. overwrite the original string from the beginning, as
: we already have the counters calculated in step 1. The
: result is the left part is overwritten with chars with
: the correct order, and the right part remains unchanged
: from step 1. O(k) while k is the length of left part.

c*********t
发帖数: 2921
15
按照maxq的想法,我写了下面的程序(in-place)。好像it works.
1 (共1页)
进入JobHunting版参与讨论
相关主题
顶风上来问道题:一个很大char[], 如何in-place 删除重复元素Dream company Onsite被搞了(少量面经)
如何写内存速度最优化的string permutation?有重复字符问一个C++ set和unordered_set iterator的问题
amazon 2nd phone interviewreverse words in a string
a1b2c3d4 变abcd1234求问一道G家Onsite题
请教c++的string vector问题,谢谢!fb 电面
Microsoft interview question再问个简单的C问题
请教一道题目GOOG intern interview 题目
今天才整明白Permutation的最优解!?今天G家电面的一道题
相关话题的讨论汇总
话题: string话题: reference话题: chars话题: char话题: input