logo
Redian新闻
>未名空间
>Money - 海外理财
>
staples buy $300 MC get $20 staples GC via easyrebate
avatar
staples buy $300 MC get $20 staples GC via easyrebate# Money - 海外理财
w*g
1 楼
一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word_list) = ['dat', 'bat']
// similar('bat', word_list) = ['bat', 'batt', 'dat']
// similar('datt', word_list) = ['dat', 'batt']
//
// To execute C++, please define "int main()"
vector similar(string word, vector &word_list, int k);
int editDist(string word1, string word2);
int main() {
string word = "datt";
vector word_list = vector({"dat", "bat", "batt", "beetle"}
);
int k=1;
vector ret = similar(word, word_list, k);
for(int i=0; i< (int) ret.size(); i++)
cout<}
int editDist(string word1, string word2){
int len1=word1.length();
int len2=word2.length();
int m[len1+1][len2+1];
//m[0][0]=0;
//init the matrix
for(int i=0; im[i][0]=i;
}
for(int j=0; jm[0][j]=j;
//then update the matrix
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
m[i][j]=min(m[i-1][j-1]+(int)(word1[i-1]!=word2[j-1]), m[i-1][j]+1);
m[i][j]=min(m[i][j], m[i][j-1]+1);


}

}
return m[len1][len2];


}
vector similar(string word, vector &word_list, int k){
vector ret;
int n= word_list.size();
if(n<1) return ret;
for(int i=0; iif(editDist(word, word_list[i])<=k){
cout<ret.push_back(word_list[i]);
}
}

return ret;
}
avatar
H*V
2 楼
again, next week from sunday 3/20
avatar
v*c
4 楼
爽,谢谢DP,刚撸了400
avatar
j*n
5 楼
顶顶

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
l*l
6 楼
这个MC可以用来充serve吗?
avatar
m*e
7 楼
还是去年的题啊。有谁知道他家的offer给股票在什么水平？根据不同的资历？
avatar
i*i
8 楼
买来的vgc或者master gc咋花的？充？买money order？ 后者有手续费吧？
avatar
w*g
9 楼
哦？是去年的题？板上哪里有讨论么？
avatar
a*a
10 楼
鸟是没戏了，我就留着自用。

【在 i******i 的大作中提到】
: 买来的vgc或者master gc咋花的？充？买money order？ 后者有手续费吧？
avatar
l*6
11 楼
I agree with bfs with target word.
Trie should be solution of preparation of word list. I have a feeling that
when the question is about a set of things and a target, the set should be
prepared for repeated calls.

editing

【在 k*******r 的大作中提到】
: 如果是简单版本，我觉得可以转化为图,用广度优先遍历走k步，就能得到所有editing
: distance之内的词。每个边对应一个add/del/modify操作。trie似乎不适合这道题
: 如果追求更高级的版本，stackflow上有个帖子，http://stackoverflow.com/questions/12886997/how-to-find-all-strings-at-a-given-edit-distance-from-a-given-string, 涉及到一些 NLP词频分析，不过这个面试时肯定写不完代码的
avatar
d*g
12 楼
哪里看到的？我在easy rebate 网上没查到
avatar
w*g
13 楼
用BFS expand这个算法，如果target word的substitution操作字符范围是256个(ASCII
码表)的话，复杂度好像很大哦。谁能贡献一个这个算法的code并分析一下复杂度吗？
avatar
o*g
14 楼
不是下周才开始？

【在 v********c 的大作中提到】
: 爽,谢谢DP,刚撸了400
avatar
G*C
15 楼
onsite 拿到了吗？

ASCII

【在 w******g 的大作中提到】
: 用BFS expand这个算法，如果target word的substitution操作字符范围是256个(ASCII
: 码表)的话，复杂度好像很大哦。谁能贡献一个这个算法的code并分析一下复杂度吗？
avatar
c*g
16 楼
good
avatar
V*i
17 楼
看来是高频题，我也挂在这题上，他让我improve的时候我有想过trie，但觉得不合适
就没说，最后问他答案，他居然说trie，吐血，当时心里就骂了丫的有本事写给我看看
。。。

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
b*c
18 楼
死呆婆的MASTERCARD GC需要用cancel大法才能在WALMART喂鸟。
现在鸟死了，去邮局买MONEY ORDER时也需要用cancel大法么？
USPS允许这样操作么？
谢谢！
avatar
w*r
19 楼
我靠，面试的题目怎么这么难，还让人家怎么找工作
avatar
s*g
20 楼
cancel大法 是啥啊

【在 b***c 的大作中提到】
: 死呆婆的MASTERCARD GC需要用cancel大法才能在WALMART喂鸟。
: 现在鸟死了，去邮局买MONEY ORDER时也需要用cancel大法么？
: USPS允许这样操作么？
: 谢谢！
avatar
c*v
22 楼
US bank MGC 最容易被盗.
[在 HIV (AIDS) 的大作中提到：]
：again, next week from sunday 3/20
：
：...........
avatar
v*y
23 楼
我看到一篇文章，如果用trie的话，可以避免一些重复的计算，例如如果我们已经计算
了target word和mit之间的距离，当我们再计算target word和mits之间的距离时，就
可以省去一些计算，这是使用trie的意义。
avatar
l*l
24 楼
请问这个在riteaid也能冲serve one vip吗? 谢谢.

【在 b***c 的大作中提到】
: 死呆婆的MASTERCARD GC需要用cancel大法才能在WALMART喂鸟。
: 现在鸟死了，去邮局买MONEY ORDER时也需要用cancel大法么？
: USPS允许这样操作么？
: 谢谢！
avatar
c*l
25 楼
问问楼上
“trie”在英文中如何发音？
avatar
b*m
26 楼
can you use staple gc to buy MC?
avatar
v*y
27 楼
"Try"。公开课上说过这个发音...

问问楼上“trie”在英文中如何发音？

【在 c********l 的大作中提到】
: 问问楼上
: “trie”在英文中如何发音？
avatar
f*s
28 楼
这题45分钟弄不出来
import java.util.HashMap;
import java.util.Map;
public class KDistance {
static class Node{
char c;
boolean isLeaf;
Node p;
Map children;
String word;
int no;
int depth;
static int counter = 0;
static Map nodemap = new HashMap();
public Node(Node parent, char c){
children = new HashMap();
p = parent;
if(p == null) depth = 0;
else depth = p.depth+1;
this.c = c;
isLeaf = false;
no = counter++;
nodemap.put(no, this);
}
public void addChild(char c){
assert(children.get(c) == null);
children.put(c, new Node(this, c));
}
public Node getChild(char c){
return children.get(c);
}
public static Node findNode(int num){
assert(num < counter);
return nodemap.get(num);
}
};

public Node constructTire(String[] dict){
Node root = new Node(null, ' ');
for(int i = 0 ; i < dict.length ; i++){
Node ptr = root;
for(int j = 0 ; j < dict[i].length() ; j++){
if(ptr.getChild(dict[i].charAt(j)) == null)
ptr.addChild(dict[i].charAt(j));
ptr = ptr.getChild(dict[i].charAt(j));
}
ptr.isLeaf = true;
ptr.word = dict[i];
}
return root;
}

public void printKDistanceElements(String target, Node ptr, int k){
int m = target.length()+1;
int n = Node.counter;
int[][] matrix = new int[m][n];
int i,j;
for(i = 0 ; i < m ; i++)
matrix[i][0] = i;
for(j = 0 ; j < n ; j++)
matrix[0][j] = Node.findNode(j).depth;

for(j = 1; j < n ;j++){
for(i = 1 ; i < m ; i++){
Node node = Node.findNode(j);
if(target.charAt(i-1) == node.c){
matrix[i][j] = matrix[i-1][node.p.no];
}else{
matrix[i][j] = Math.min(matrix[i-1][j] + 1, matrix[i][
node.p.no]+1);
matrix[i][j] = Math.min(matrix[i][j], matrix[i-1][node.p
.no]+1);
}
if(i == m - 1 && node.isLeaf == true && matrix[i][j] == k){
System.out.println(node.word);
}
}
}
}
public static void main(String[] args) {
KDistance kinst = new KDistance();
String[] input = new String[]{"baa","aaa","zz"};
String target = "a";
Node root = kinst.constructTire(input);
kinst.printKDistanceElements(target, root, 2);
}
}
avatar
a*n
29 楼
用trie怎么解？
比如target字符为[blablabla1]A[blablabla2]
数组有一个字符为[blablabla1]Z[blablabla2]，编辑距离仅为1，但在trie中距离还挺
远的。
avatar
m*g
31 楼
有人能在45分钟内把这个题目做出来吗？好像他们要求能run。
写个bug-free的trie都不容易呀。
avatar
j*t
32 楼
必须写出来一次编译运行通过？
avatar
Q*a
33 楼
实现了4种方法
1: 直接遍历完整计算edit distance. 285 clocks.
2: 直接遍历，计算edit distance到 >k 就返回. 149 clocks.
3: Trie+shortcut edit distance. Build trie: 606 clocks, process: 6 clocks.
http://stevehanov.ca/blog/index.php?id=114
4: Generate delete k transformation. Build dict: 17033 clocks. process: 0
clocks.
但这里不仅需要生成delete k的pattern, 还需要生成所有delete 1..k-1的pattern,
否则不能handle如(chrome brome)的case
http://blog.faroo.com/2012/06/07/improved-edit-distance-based-s
#include "common.h"
class Trie {
public:
class TrieNode {
public:
unordered_map children;
bool isEnd;
TrieNode() {
isEnd = false;
}
void AddChild(const char* s) {
if (*s == 0) {
isEnd = true;
}
else {
auto it = children.find(*s);
TrieNode* child = NULL;
if (it == children.end()) {
child = new TrieNode();
children[*s] = child;
}
else {
child = it->second;
}
child->AddChild(s+1);
}
}
void FindAllEditDistanceUnderThreshold(string path, const string& s,
const vector& curDistance, vector& results, int threshold) {
if (isEnd && curDistance.back() <= threshold) results.push_back(
path);
for (auto kv: children) {
vector newDistance = curDistance;
int topLeft = newDistance[0];
++newDistance[0];
char c = kv.first;
bool underThreshold = newDistance[0] <= threshold;
for (int len = 1; len <= s.size(); ++len) {
int t = newDistance[len];
newDistance[len] = min(topLeft, min(newDistance[len],
newDistance[len-1])) + 1;
if (c == s[len-1]) {
newDistance[len] = min(topLeft, newDistance[len]);
}
if (newDistance[len] <= threshold) {
underThreshold = true;
}
topLeft = t;
}
if (underThreshold) {
string newPath = path;
newPath.append(1, c);
kv.second->FindAllEditDistanceUnderThreshold(newPath, s,
newDistance, results, threshold);
}
}
}
};
void AddString(const char* s) {
root.AddChild(s);
}
vector FindAllEditDistanceUnderThreshold(const string& s, int
threshold) {
string path;
vector results;
vector curDistance(s.size() + 1, 0);
iota(curDistance.begin(), curDistance.end(), 0);
root.FindAllEditDistanceUnderThreshold(path, s, curDistance, results
, threshold);
return results;
}

private:
TrieNode root;
};
int EditDistance(string s1, string s2) {
vector v(s1.size() + 1);
iota(v.begin(), v.end(), 0);
for (int len = 1; len <= s2.size(); ++len) {
int topLeft = v[0];
++v[0];
for (int len1 = 1; len1 <= s1.size(); ++len1) {
int t = v[len1];
v[len1] = min(topLeft, min(v[len1], v[len1-1])) + 1;
if (s1[len1-1] == s2[len-1]) {
v[len1] = min(topLeft, v[len1]);
}
topLeft = t;
}
}
return v.back();
}
int EditDistanceWithThreshold(string s1, string s2, int threshold) {
vector v(s1.size() + 1);
iota(v.begin(), v.end(), 0);
for (int len = 1; len <= s2.size(); ++len) {
int topLeft = v[0];
++v[0];
bool underThreshold = v[0] <= threshold;
for (int len1 = 1; len1 <= s1.size(); ++len1) {
int t = v[len1];
v[len1] = min(topLeft, min(v[len1], v[len1-1])) + 1;
if (s1[len1-1] == s2[len-1]) {
v[len1] = min(topLeft, v[len1]);
}
if (v[len1] <= threshold) {
underThreshold = true;
}
topLeft = t;
}
if (!underThreshold) {
return threshold + 1;
}
}
return v.back();
}
vector correct1(string s, int d, vector& dict) {
vector results;
for (auto word: dict) {
if (EditDistance(s, word) <= d) {
results.push_back(word);
}
}
return results;
}
vector correct2(string s, int d, vector& dict) {
vector results;
for (auto word: dict) {
if (EditDistanceWithThreshold(s, word, d) <= d) {
results.push_back(word);
}
}
return results;
}
void DeleteM(string s, int start, int m, int initM, vector& results)
{
if (m != initM) {
results.push_back(s);
}
if (m == 0) return;
for (int i = start; i < s.size(); ++i) {
string s1 = s;
s1.erase(s1.begin() + i);
DeleteM(s1, i, m-1, initM, results);
}
}
// Need to generate -1 to -m string, not only -m, otherwise
// for m = 2, chrome and brome can't be treated as match
vector DeleteM(string s, int m) {
vector results;
DeleteM(s, 0, m, m, results);
return results;
}
int main() {
int threshold = 2;
const char* dictFile = "british\brit-a-z.txt";
ifstream input(dictFile);
vector wordList;
string source = "chrome";
{
Clock clock("Load word list");
for (string line; getline(input, line);) {
wordList.push_back(line);
}
}
{
Clock clock("iterate without shortcut");
auto results = correct1(source, threshold, wordList);
DumpStringVector(results);
printf("n");
}
{
Clock clock("iterate with shortcut");
auto results = correct2(source, threshold, wordList);
DumpStringVector(results);
printf("n");
}
Trie trie;
{
Clock clock("build trie");
for (string s: wordList) {
trie.AddString(s.c_str());
}
printf("n");
}
{
Clock clock("Trie with shortcut");
auto results = trie.FindAllEditDistanceUnderThreshold(source,
threshold);
DumpStringVector(results);
printf("n");
}
unordered_set origDict;
multimap deleteMDict;
{
Clock clock("Build Delete Deict");
for (auto s: wordList) {
origDict.insert(s);
for (auto del: DeleteM(s, threshold)) {
deleteMDict.insert(make_pair(del, s));
}
}
printf("n");
}
{
Clock clock("Delte dict");
auto deleteSource = DeleteM(source, threshold);
unordered_set results;
if (origDict.find(source) != origDict.end()) {
results.insert(source);
}
{
auto range = deleteMDict.equal_range(source);
auto start = range.first;
auto end = range.second;
while (start != end) {
results.insert(start->second);
++start;
}
}
for (string s: deleteSource) {
if (origDict.find(s) != origDict.end()) {
results.insert(s);
}
auto range = deleteMDict.equal_range(s);
auto start = range.first;
auto end = range.second;
while (start != end) {
if (EditDistanceWithThreshold(source, start->second,
threshold) <= threshold) {
results.insert(start->second);
}
++start;
}
}
DumpStringRange(results.begin(), results.end());
printf("n");
}
return 0;
}

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
w*g
34 楼
一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个word list 和一个target word，要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
======================
#include
#include
#include
#include
using namespace std;
//k=1
// word_list = ['dat', 'bat', 'batt', 'beetle']
// similar(query, word_list)
// similar('cat', word_list) = ['dat', 'bat']
// similar('bat', word_list) = ['bat', 'batt', 'dat']
// similar('datt', word_list) = ['dat', 'batt']
//
// To execute C++, please define "int main()"
vector similar(string word, vector &word_list, int k);
int editDist(string word1, string word2);
int main() {
string word = "datt";
vector word_list = vector({"dat", "bat", "batt", "beetle"}
);
int k=1;
vector ret = similar(word, word_list, k);
for(int i=0; i< (int) ret.size(); i++)
cout<}
int editDist(string word1, string word2){
int len1=word1.length();
int len2=word2.length();
int m[len1+1][len2+1];
//m[0][0]=0;
//init the matrix
for(int i=0; i<=len1; i++){
m[i][0]=i;
}
for(int j=0; j<=len2; j++)
m[0][j]=j;
//then update the matrix
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
m[i][j]=min(m[i-1][j-1]+(int)(word1[i-1]!=word2[j-1]), m[i-1][j]+1);
m[i][j]=min(m[i][j], m[i][j-1]+1);


}

}
return m[len1][len2];


}
vector similar(string word, vector &word_list, int k){
vector ret;
int n= word_list.size();
if(n<1) return ret;
for(int i=0; iif(editDist(word, word_list[i])<=k){
cout<ret.push_back(word_list[i]);
}
}

return ret;
}
avatar
j*n
36 楼
顶顶

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
m*e
37 楼
还是去年的题啊。有谁知道他家的offer给股票在什么水平？根据不同的资历？
avatar
w*g
38 楼
哦？是去年的题？板上哪里有讨论么？
avatar
l*6
39 楼
I agree with bfs with target word.
Trie should be solution of preparation of word list. I have a feeling that
when the question is about a set of things and a target, the set should be
prepared for repeated calls.

editing

【在 k*******r 的大作中提到】
: 如果是简单版本，我觉得可以转化为图,用广度优先遍历走k步，就能得到所有editing
: distance之内的词。每个边对应一个add/del/modify操作。trie似乎不适合这道题
: 如果追求更高级的版本，stackflow上有个帖子，http://stackoverflow.com/questions/12886997/how-to-find-all-strings-at-a-given-edit-distance-from-a-given-string, 涉及到一些 NLP词频分析，不过这个面试时肯定写不完代码的
avatar
w*g
40 楼
用BFS expand这个算法，如果target word的substitution操作字符范围是256个(ASCII
码表)的话，复杂度好像很大哦。谁能贡献一个这个算法的code并分析一下复杂度吗？
avatar
G*C
41 楼
onsite 拿到了吗？

ASCII

【在 w******g 的大作中提到】
: 用BFS expand这个算法，如果target word的substitution操作字符范围是256个(ASCII
: 码表)的话，复杂度好像很大哦。谁能贡献一个这个算法的code并分析一下复杂度吗？
avatar
V*i
42 楼
看来是高频题，我也挂在这题上，他让我improve的时候我有想过trie，但觉得不合适
就没说，最后问他答案，他居然说trie，吐血，当时心里就骂了丫的有本事写给我看看
。。。

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
w*r
43 楼
我靠，面试的题目怎么这么难，还让人家怎么找工作
avatar
v*y
45 楼
我看到一篇文章，如果用trie的话，可以避免一些重复的计算，例如如果我们已经计算
了target word和mit之间的距离，当我们再计算target word和mits之间的距离时，就
可以省去一些计算，这是使用trie的意义。
avatar
c*l
46 楼
问问楼上
“trie”在英文中如何发音？
avatar
v*y
47 楼
"Try"。公开课上说过这个发音...

问问楼上“trie”在英文中如何发音？

【在 c********l 的大作中提到】
: 问问楼上
: “trie”在英文中如何发音？
avatar
f*s
48 楼
这题45分钟弄不出来
import java.util.HashMap;
import java.util.Map;
public class KDistance {
static class Node{
char c;
boolean isLeaf;
Node p;
Map children;
String word;
int no;
int depth;
static int counter = 0;
static Map nodemap = new HashMap();
public Node(Node parent, char c){
children = new HashMap();
p = parent;
if(p == null) depth = 0;
else depth = p.depth+1;
this.c = c;
isLeaf = false;
no = counter++;
nodemap.put(no, this);
}
public void addChild(char c){
assert(children.get(c) == null);
children.put(c, new Node(this, c));
}
public Node getChild(char c){
return children.get(c);
}
public static Node findNode(int num){
assert(num < counter);
return nodemap.get(num);
}
};

public Node constructTire(String[] dict){
Node root = new Node(null, ' ');
for(int i = 0 ; i < dict.length ; i++){
Node ptr = root;
for(int j = 0 ; j < dict[i].length() ; j++){
if(ptr.getChild(dict[i].charAt(j)) == null)
ptr.addChild(dict[i].charAt(j));
ptr = ptr.getChild(dict[i].charAt(j));
}
ptr.isLeaf = true;
ptr.word = dict[i];
}
return root;
}

public void printKDistanceElements(String target, Node ptr, int k){
int m = target.length()+1;
int n = Node.counter;
int[][] matrix = new int[m][n];
int i,j;
for(i = 0 ; i < m ; i++)
matrix[i][0] = i;
for(j = 0 ; j < n ; j++)
matrix[0][j] = Node.findNode(j).depth;

for(j = 1; j < n ;j++){
for(i = 1 ; i < m ; i++){
Node node = Node.findNode(j);
if(target.charAt(i-1) == node.c){
matrix[i][j] = matrix[i-1][node.p.no];
}else{
matrix[i][j] = Math.min(matrix[i-1][j] + 1, matrix[i][
node.p.no]+1);
matrix[i][j] = Math.min(matrix[i][j], matrix[i-1][node.p
.no]+1);
}
if(i == m - 1 && node.isLeaf == true && matrix[i][j] == k){
System.out.println(node.word);
}
}
}
}
public static void main(String[] args) {
KDistance kinst = new KDistance();
String[] input = new String[]{"baa","aaa","zz"};
String target = "a";
Node root = kinst.constructTire(input);
kinst.printKDistanceElements(target, root, 2);
}
}
avatar
a*n
49 楼
用trie怎么解？
比如target字符为[blablabla1]A[blablabla2]
数组有一个字符为[blablabla1]Z[blablabla2]，编辑距离仅为1，但在trie中距离还挺
远的。
avatar
m*g
51 楼
有人能在45分钟内把这个题目做出来吗？好像他们要求能run。
写个bug-free的trie都不容易呀。
avatar
j*t
52 楼
必须写出来一次编译运行通过？
avatar
Q*a
53 楼
实现了4种方法
1: 直接遍历完整计算edit distance. 285 clocks.
2: 直接遍历，计算edit distance到 >k 就返回. 149 clocks.
3: Trie+shortcut edit distance. Build trie: 606 clocks, process: 6 clocks.
http://stevehanov.ca/blog/index.php?id=114
4: Generate delete k transformation. Build dict: 17033 clocks. process: 0
clocks.
但这里不仅需要生成delete k的pattern, 还需要生成所有delete 1..k-1的pattern,
否则不能handle如(chrome brome)的case
http://blog.faroo.com/2012/06/07/improved-edit-distance-based-s
#include "common.h"
class Trie {
public:
class TrieNode {
public:
unordered_map children;
bool isEnd;
TrieNode() {
isEnd = false;
}
void AddChild(const char* s) {
if (*s == 0) {
isEnd = true;
}
else {
auto it = children.find(*s);
TrieNode* child = NULL;
if (it == children.end()) {
child = new TrieNode();
children[*s] = child;
}
else {
child = it->second;
}
child->AddChild(s+1);
}
}
void FindAllEditDistanceUnderThreshold(string path, const string& s,
const vector& curDistance, vector& results, int threshold) {
if (isEnd && curDistance.back() <= threshold) results.push_back(
path);
for (auto kv: children) {
vector newDistance = curDistance;
int topLeft = newDistance[0];
++newDistance[0];
char c = kv.first;
bool underThreshold = newDistance[0] <= threshold;
for (int len = 1; len <= s.size(); ++len) {
int t = newDistance[len];
newDistance[len] = min(topLeft, min(newDistance[len],
newDistance[len-1])) + 1;
if (c == s[len-1]) {
newDistance[len] = min(topLeft, newDistance[len]);
}
if (newDistance[len] <= threshold) {
underThreshold = true;
}
topLeft = t;
}
if (underThreshold) {
string newPath = path;
newPath.append(1, c);
kv.second->FindAllEditDistanceUnderThreshold(newPath, s,
newDistance, results, threshold);
}
}
}
};
void AddString(const char* s) {
root.AddChild(s);
}
vector FindAllEditDistanceUnderThreshold(const string& s, int
threshold) {
string path;
vector results;
vector curDistance(s.size() + 1, 0);
iota(curDistance.begin(), curDistance.end(), 0);
root.FindAllEditDistanceUnderThreshold(path, s, curDistance, results
, threshold);
return results;
}

private:
TrieNode root;
};
int EditDistance(string s1, string s2) {
vector v(s1.size() + 1);
iota(v.begin(), v.end(), 0);
for (int len = 1; len <= s2.size(); ++len) {
int topLeft = v[0];
++v[0];
for (int len1 = 1; len1 <= s1.size(); ++len1) {
int t = v[len1];
v[len1] = min(topLeft, min(v[len1], v[len1-1])) + 1;
if (s1[len1-1] == s2[len-1]) {
v[len1] = min(topLeft, v[len1]);
}
topLeft = t;
}
}
return v.back();
}
int EditDistanceWithThreshold(string s1, string s2, int threshold) {
vector v(s1.size() + 1);
iota(v.begin(), v.end(), 0);
for (int len = 1; len <= s2.size(); ++len) {
int topLeft = v[0];
++v[0];
bool underThreshold = v[0] <= threshold;
for (int len1 = 1; len1 <= s1.size(); ++len1) {
int t = v[len1];
v[len1] = min(topLeft, min(v[len1], v[len1-1])) + 1;
if (s1[len1-1] == s2[len-1]) {
v[len1] = min(topLeft, v[len1]);
}
if (v[len1] <= threshold) {
underThreshold = true;
}
topLeft = t;
}
if (!underThreshold) {
return threshold + 1;
}
}
return v.back();
}
vector correct1(string s, int d, vector& dict) {
vector results;
for (auto word: dict) {
if (EditDistance(s, word) <= d) {
results.push_back(word);
}
}
return results;
}
vector correct2(string s, int d, vector& dict) {
vector results;
for (auto word: dict) {
if (EditDistanceWithThreshold(s, word, d) <= d) {
results.push_back(word);
}
}
return results;
}
void DeleteM(string s, int start, int m, int initM, vector& results)
{
if (m != initM) {
results.push_back(s);
}
if (m == 0) return;
for (int i = start; i < s.size(); ++i) {
string s1 = s;
s1.erase(s1.begin() + i);
DeleteM(s1, i, m-1, initM, results);
}
}
// Need to generate -1 to -m string, not only -m, otherwise
// for m = 2, chrome and brome can't be treated as match
vector DeleteM(string s, int m) {
vector results;
DeleteM(s, 0, m, m, results);
return results;
}
int main() {
int threshold = 2;
const char* dictFile = "british\brit-a-z.txt";
ifstream input(dictFile);
vector wordList;
string source = "chrome";
{
Clock clock("Load word list");
for (string line; getline(input, line);) {
wordList.push_back(line);
}
}
{
Clock clock("iterate without shortcut");
auto results = correct1(source, threshold, wordList);
DumpStringVector(results);
printf("n");
}
{
Clock clock("iterate with shortcut");
auto results = correct2(source, threshold, wordList);
DumpStringVector(results);
printf("n");
}
Trie trie;
{
Clock clock("build trie");
for (string s: wordList) {
trie.AddString(s.c_str());
}
printf("n");
}
{
Clock clock("Trie with shortcut");
auto results = trie.FindAllEditDistanceUnderThreshold(source,
threshold);
DumpStringVector(results);
printf("n");
}
unordered_set origDict;
multimap deleteMDict;
{
Clock clock("Build Delete Deict");
for (auto s: wordList) {
origDict.insert(s);
for (auto del: DeleteM(s, threshold)) {
deleteMDict.insert(make_pair(del, s));
}
}
printf("n");
}
{
Clock clock("Delte dict");
auto deleteSource = DeleteM(source, threshold);
unordered_set results;
if (origDict.find(source) != origDict.end()) {
results.insert(source);
}
{
auto range = deleteMDict.equal_range(source);
auto start = range.first;
auto end = range.second;
while (start != end) {
results.insert(start->second);
++start;
}
}
for (string s: deleteSource) {
if (origDict.find(s) != origDict.end()) {
results.insert(s);
}
auto range = deleteMDict.equal_range(s);
auto start = range.first;
auto end = range.second;
while (start != end) {
if (EditDistanceWithThreshold(source, start->second,
threshold) <= threshold) {
results.insert(start->second);
}
++start;
}
}
DumpStringRange(results.begin(), results.end());
printf("n");
}
return 0;
}

【在 w******g 的大作中提到】
: 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
: 题目是给定一个word list 和一个target word，要求输出在word list 里跟target
: word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
: 法(见下面)，程序是要从头到尾都要写，包括main函数和test数据。写完后他问有没有
: 更好的解法，我说可以用trie，但是我不觉得我能在剩余时间里写得出来基于trie的解
: 法，就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。
: ======================
: #include
: #include
: #include
avatar
j*r
54 楼
qiu refer
avatar
s*3
55 楼
这个不对吧，编辑距离还包括，删除和插入字母的操作。
你的操作只有修改。
avatar
e*6
56 楼

确实是啊，我忘了。那就再多两个loop。一个是del，一个是insert，没有什么大不同。
核心想法就是穷举所有edit distance == 1的情况。我把之前的code删了，免得贻害众
人。。
如下：
// for delete.
for (int i = 0; i < curr.length(); i++)
{
curr.erase(i);
// compare and insert if in dict
}
// for insert
for (int i = 0; i <= curr.length(); i++)
{
for (char c = 'a'; c <= 'z'; c++)
{
curr = curr.substr(0, i) + c + curr.substr(i);
// compare and insert if in dict
}
}

【在 s*********3 的大作中提到】
: 这个不对吧，编辑距离还包括，删除和插入字母的操作。
: 你的操作只有修改。
avatar
n*t
57 楼
如果面试官要的是最优解，那么说明他们就喜欢搞过ACM大牛。。。 没办法，公司太火
，candidate都太强
相关阅读
already have two AMEX Business cards, apply SPG business?同时申请2张不同公司的信用卡，能降低多少分？最近有什么好卡有bonus的吗看起来好像Marriott卡比SPG卡好，为什么用SPG的人多呢？HSBC的check账户以后都要收钱了？UA 65k+50 刀的offer没有了吗？从中国往美国汇钱AMEX blue cash 很好申请啊我这种情况开SPG还能拿30000点吗Money Market 那种high yield的账户可以开么，看到高的有1。3％的利息呢wells fargo 银行的iphone app不能mobile deposit存支票 (转载)双黄包求去年8月Amex Gold Premier申请截图从国内汇2~3w刀那个银行比较省钱？这个蔡伦票 是真是假Walmart在Amex blue cash不算department store问个傻问题求教：Chase CO卡的年费能免吗？包子答谢:怎么关联国内的Visa信用卡到Paypal请教买房和信用记录请教关于激活costco cash card的问题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。