s*******y
发帖数: 44 | 1 要求用c。第二题我说用hash对第一个string建立一个array，index是字符，value区别
出现还是不出现，然后扫描第二个string，改动这个array对应字符的值，区分出现在
第一个string和第二个string的值，然后扫描这个array就可以得出结果。时间复杂度
是O(m+n)。面试的小印说不让用hash，然后我就没想出来更好的办法。结果他提示说排
序+二分查找，没觉得这个更快啊，不知道他到底要考什么。
1. Write a function to print all possible permutation of a string. Assume
there is no duplication of characters in the string.
void print_permutation(char *s1);
2. Write a function to get the set difference between two sets, A and B
which are null-terminated strings. The set difference
of two sets A and B is the set C = (A union B) - (A intersect B). Function
should return pointer to a new null-terminated string
with memory allocation. Optimize for speed/memory.
char *set_difference(char *A, char *B); |
l*******b
发帖数: 2586 | 2 不准counting? counting 排序最快了，哈哈，准counting还查找什么呀 |
c********t
发帖数: 5706 | 3 第二题A有没有重复字符？B有没有？如果都说是set,应该没有重复。你的解正确，而且
比面试官的好。
但既然他不允许（估计他不会），只好排序，用二分查找。
还有一种，就是两个都排序以后，两个指针一起扫A,B,每次输出比较小的值，并改变那
个指针，如果等值则不输出，两个指针一起增加。也是nlgn的复杂度。
总结, 你的面试官是个面瓜。
【在 s*******y 的大作中提到】
: 要求用c。第二题我说用hash对第一个string建立一个array，index是字符，value区别
: 出现还是不出现，然后扫描第二个string，改动这个array对应字符的值，区分出现在
: 第一个string和第二个string的值，然后扫描这个array就可以得出结果。时间复杂度
: 是O(m+n)。面试的小印说不让用hash，然后我就没想出来更好的办法。结果他提示说排
: 序+二分查找，没觉得这个更快啊，不知道他到底要考什么。
: 1. Write a function to print all possible permutation of a string. Assume
: there is no duplication of characters in the string.
:
: void print_permutation(char *s1);
: 2. Write a function to get the set difference between two sets, A and B
|
s*******y
发帖数: 44 | 4 题目中说是set，我不放心问了是否允许重复，说允许。hash的办法可以处理这个重复
的情况。否则的话可以排序后用线性时间先去重，不影响最后的时间复杂度。
他面试还有个特点，在你写code的时候，不停地发问你这里好像不对吧，是不是应该这
样那样，思路很容易被打乱。也许边写边解释是一个应付面试官的办法，或者先写注释
伪码？这个实际中该怎么对付比较好？
【在 c********t 的大作中提到】
: 第二题A有没有重复字符？B有没有？如果都说是set,应该没有重复。你的解正确，而且
: 比面试官的好。
: 但既然他不允许（估计他不会），只好排序，用二分查找。
: 还有一种，就是两个都排序以后，两个指针一起扫A,B,每次输出比较小的值，并改变那
: 个指针，如果等值则不输出，两个指针一起增加。也是nlgn的复杂度。
: 总结, 你的面试官是个面瓜。
|
f*******t
发帖数: 7549 | 5 做题要灵活，别只会一种解法，即使那是最优的，遇到某些脑子一根筋，只想得到自己
脑中某种解法的面试官就会悲剧。 |
c****p
发帖数: 6474 | 6 第二题说要优化内存了，估计是不让用hash的原因。而且你想过用C写hash表的代码复
杂度么（hash算法还好，还得有防碰撞的机制，说白了就是实现链表）。。。。
我个人觉得这版上动不动就想到用hash不是一个太好的趋势（虽然C++和Java都提供了
很方便的解决方案），不知道是因为我是用C出来的，老顽固了，还是大家太贪懒。 |
s*******y
发帖数: 44 | 7 其实我也是c用得比较多，就这题而言，所谓的hash其实不过是一个数组，以字符的
ascii码为index，和用table解决查找问题一样，以空间换时间。
【在 c****p 的大作中提到】
: 第二题说要优化内存了，估计是不让用hash的原因。而且你想过用C写hash表的代码复
: 杂度么（hash算法还好，还得有防碰撞的机制，说白了就是实现链表）。。。。
: 我个人觉得这版上动不动就想到用hash不是一个太好的趋势（虽然C++和Java都提供了
: 很方便的解决方案），不知道是因为我是用C出来的，老顽固了，还是大家太贪懒。
|
c****p
发帖数: 6474 | 8 string的hash值是会有碰撞的啊（无碰撞的hash就有个空间和动态数组的问题，还是逃
不掉链表吧），怎么解决碰撞问题呢？
【在 s*******y 的大作中提到】
: 其实我也是c用得比较多，就这题而言，所谓的hash其实不过是一个数组，以字符的
: ascii码为index，和用table解决查找问题一样，以空间换时间。
|
l*****a
发帖数: 559 | 9 怕写代码时被打断的话，就先讲思路，得到他认可以后再码代码。
【在 s*******y 的大作中提到】
: 题目中说是set，我不放心问了是否允许重复，说允许。hash的办法可以处理这个重复
: 的情况。否则的话可以排序后用线性时间先去重，不影响最后的时间复杂度。
: 他面试还有个特点，在你写code的时候，不停地发问你这里好像不对吧，是不是应该这
: 样那样，思路很容易被打乱。也许边写边解释是一个应付面试官的办法，或者先写注释
: 伪码？这个实际中该怎么对付比较好？
|
c*****a
发帖数: 808 | |
s*******y
发帖数: 44 | 11 就这道题而言，不需要解决碰撞问题。更像是个反向表，就像那个如何最快算出一个
byte中有多少位1的算法，用一个array[256]记录即可，用空间换时间。
【在 c****p 的大作中提到】
: string的hash值是会有碰撞的啊（无碰撞的hash就有个空间和动态数组的问题，还是逃
: 不掉链表吧），怎么解决碰撞问题呢？
|
