i******s
发帖数: 301 | 1 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
了，求祝福～
题：
1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
划分这个字符串，使得每个字符串都在dictionary中。 | f***g
发帖数: 214 | 2 1. 有Binary Search可以找到元素第一次出现的位置。
以当前位置为始，再做找元素出现最后一次的位置的Binary Search
如果这个数量不多，就Linear。
只是有一点不明白，为什么要double，这是要考什么呢？
不能直接==？ | i******s
发帖数: 301 | 3 可能是想考察比较double时不能直接用==吧，要用一个误差e来比较两个数，比如(a-b)
< e之类的。还有用binary search一次不能保证找到的一定是第一次出现的位置吧，
还是得要找多次，求分析
【在 f***g 的大作中提到】
: 1. 有Binary Search可以找到元素第一次出现的位置。
: 以当前位置为始，再做找元素出现最后一次的位置的Binary Search
: 如果这个数量不多，就Linear。
: 只是有一点不明白，为什么要double，这是要考什么呢？
: 不能直接==？
| P********l
发帖数: 452 | 4 bless!
1. binary search for a range.
Remember to use the previous result.
2. I think it is correct to use DP. But your method will count result
multiple times.
example:
dictionary : aaa, bb, cc, aaabb, bbcc.
word: aaa, bb, cc. | V*****i
发帖数: 92 | 5 For the first one, do three binary searches. My code as follows. It is easy
to combine three binary searches into one routines through a flag, I wrote
this way for clearance.
int binary_search(int* num, int left, int right, int K) {
// find any pos such that num[pos] == K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid]) return mid;
if (K < num[mid]) return binary_search(num, left, mid-1, K);
else return binary_search(num, mid+1, right, K);
}
int binary_search_l(int* num, int left, int right, int K) {
// find pos such that num[pos] < K && num[pos+1] == K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid+1] && K > num[mid]) return mid;
if (K == num[mid]) return binary_search_l(num, left, mid-1, K);
else return binary_search_l(num, mid+1, right, K);
}
int binary_search_r(int* num, int left, int right, int K) {
// find pos such that num[pos] == K && num[pos+1] > K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid-1] && K < num[mid]) return mid;
if (K == num[mid]) return binary_search_r(num, mid+1, right, K);
else return binary_search_r(num, left, mid-1, K);
}
int find_K(int* num, int N, int K) {
int pos = binary_search(num, 0, N-1, K);
int left_bound, right_bound;
if (pos == 0) left_bound = 0;
else left_bound = binary_search_l(num, 0, pos-1, K);
if (pos == N-1) right_bound = N-1;
else right_bound = binary_search_r(num, pos+1, N-1, K);
return right_bound-1-(left_bound+1)+1;
}
binary
worse
【在 i******s 的大作中提到】
: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。
| j****a
发帖数: 55 | 6 第二题看不懂...能讲讲啥意思马？
楼上为啥3次binary search阿？？ Don't get what's going on... | f***g
发帖数: 214 | | V*****i
发帖数: 92 | 8 For the second problem, it is correct to use DP.
But I think the correct formula should be T(n) = \sum_{i=1}^(n-1)(T(i)*H(i+1
, n)), here T(n) the number of partitions for string (1,n), H(i+1, n) if 1
of string (i+1, n) is in dict and 0 if string (i+1, n) is not.
binary
worse
【在 i******s 的大作中提到】
: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。
|
| i******s
发帖数: 301 | 9 你的解法应该是对的，基于这个写了如下C++代码
/*
* Author: Shengzhe Yao
* Date: 08 Nov 2010
*/
#include
#include
#include
#include
using namespace std;
// T(n) = \sum_{i=1}^{n-1} (T(i) * H(i+1))
int findAllStr(const set &dict, char *str,
int end, int *lookup_table) {
if (lookup_table[end] > 0)
return lookup_table[end];
int total = 0;
for (int i=1; i < end; ++i) {
char *substr = (str+i+1);
if (dict.find(substr) != dict.end()) {
char tmp = str[i+1];
str[i+1] = '\0'; // To use default set comparator
if (dict.find(str) != dict.end()) {
// calculate all split ways between position 0 to i
total= findAllStr(dict, str, i, lookup_table);
}
str[i+1] = tmp;
}
}
if ((dict.find(str) != dict.end())) {
++total;
}
lookup_table[end] = total;
return total;
}
int main(int argc, char *argv[]) {
set dict;
dict.insert("a");
dict.insert("aa");
dict.insert("aaa");
dict.insert("aaaa");
char str[] = "aaaa";
int lookup_table[100];
for (int i=0; i < 100; ++i)
lookup_table[i] = -1;
printf("Total combination is: %d\n",
findAllStr(dict, str, strlen(str), lookup_table));
for (int i=0; i < 10; ++i)
printf("%d, ", lookup_table[i]);
printf("\n");
return 0;
} | s*****n
发帖数: 5488 | 10 can you write a bp program? really hard to me.
looks to me just a bfs or DFS searching with dictionary graph is enough. use
a static/global counter to count when you reach the end of the target
string.
foreach string S in D
{
if S prefix match T && T-S > null
recursively call on T - S, D
if T-s is null,
count++;
}
of caz, a trie or prefix tree can speed up the searching.
+1
【在 V*****i 的大作中提到】
: For the second problem, it is correct to use DP.
: But I think the correct formula should be T(n) = \sum_{i=1}^(n-1)(T(i)*H(i+1
: , n)), here T(n) the number of partitions for string (1,n), H(i+1, n) if 1
: of string (i+1, n) is in dict and 0 if string (i+1, n) is not.
:
: binary
: worse
| | | j****a
发帖数: 55 | 11 能解释一下第二题是什么意思吗？看不懂？
binary
worse
【在 i******s 的大作中提到】
: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。
| i******s
发帖数: 301 | 12 Thanks for pointing out the mistake !
【在 P********l 的大作中提到】
: bless!
: 1. binary search for a range.
: Remember to use the previous result.
: 2. I think it is correct to use DP. But your method will count result
: multiple times.
: example:
: dictionary : aaa, bb, cc, aaabb, bbcc.
: word: aaa, bb, cc.
| i******s
发帖数: 301 | 13 就是有一个字典dict，里面有若干字符串。现在输入一个字符串str, 将str分成若干个
子串，要求每个子串都在dict中，问这样的切分方法有几种？
【在 j****a 的大作中提到】
: 能解释一下第二题是什么意思吗？看不懂？
:
: binary
: worse
| j*****u
发帖数: 1133 | 14 1. two binary search
2. 可否用prefix tree？
for (int i = 0; i < str.lengh, ++i)
{
match str[i..k1], [k1+1..k2]...in prefix-tree until str.length-1,
continue if any match fails;
++count;
}
binary
worse
【在 i******s 的大作中提到】
: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。
| r**u
发帖数: 1567 | 15 第二题，你的递归公式，把str分成A，B俩部分后，A继续会被划分，所以有重复。
end是str结尾的position，
F(i)是从i到end的划分个数，那么
F(i) = sum_{k = 1 to end-i} | F(i+k), if str[i, i+k-1] is a valid word.
| 0. Otherwise
对每个A，which is a valid word，划分B，然后加一起.
binary
worse
【在 i******s 的大作中提到】
: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。
| V*****i
发帖数: 92 | 16 There is no need to pass Dictionary and lookup table, use global variable or
use class. My solution as follows:
#include
#include
#include
#include
using namespace std;
// T(n) = \sum_{i=1}^{n-1} (T(i) * H(i+1))
const int MAXSIZE = 100;
class find_str {
private:
set dict;
int lookup_table[MAXSIZE];
public:
find_str(set &d) {
dict = d;
for (int i=0; i
}
int findAllStr(const string &str, int pos) {
if (lookup_table[pos] != -1)
return lookup_table[pos];
int total = 0;
for (size_t i=1; i <= pos; ++i) {
string substr = str.substr(i, pos-i+1);
if (dict.find(substr) != dict.end())
total += findAllStr(str, i-1);
}
if (dict.find(str.substr(0, pos+1)) != dict.end()) ++total;
lookup_table[pos] = total;
return total;
}
};
int main(int argc, char *argv[]) {
set dict;
dict.insert("aaa");
dict.insert("bb");
dict.insert("cc");
dict.insert("aaabb");
dict.insert("bbcc");
find_str f(dict);
string str = "aaabbcc";
printf("Total combination is: %d\n", f.findAllStr(str, str.length()-
1));
return 0;
}
【
在 ipodfans (jojo) 的大作中提到: 】 | b****n
发帖数: 84 | 17 第一题可以参考std::equal_range()的实现
就是套用std::lower_bound()和std::upper_bound() | A*H
发帖数: 127 | 18 #q2
#include
#include | h**6
发帖数: 4160 | 19 map 这种结构不如直接改为 set
否则在程序运行结束后，所有 n(n-1)/2 个子字符串全部加入到map里去了。 |
|
