s*****l
发帖数: 45 | 1 实在没想出啥好的解法，来请假大侠们一下。。
Three allowed operations: delete a character, insert a character, replace a
character.
Now given two words - word1 and word2 - find
the minimum number of steps required to convert word1 to word2 |
|
l*****o
发帖数: 214 | 2 一点想法，不知到对不对：
用doubly linked list
step 1. scan text, if in the target word set, add to doubly linked list,
until the doubly linked list has all the target words: you get [word1, word1
, word2, word1, word1, word3]
step 2. from the end of the linked list, go backwards, until find all the
words in target word set, remove the words before, and the result is a
probably shorter list with first element A: you get [word2, word1, word1,
word3], and record the span
step 3. keep scanning the text, push wor... 阅读全帖 |
|
k****r
发帖数: 807 | 3 目测的话，我想用recursive＋backtrack
分情况的, 我简单写了下，请指正
bool matchwords(char* word1, char* word2, int index1, int index2) {
if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
else {
if (word2[index2] == '*') {
if (matchwords(word1, word2, index1+1, index2+1)) return true;
else if (matchwords(word1, word2, index1+1, index2)) return true;
else if (word2[index2] == '?') {
return matchwords(word1, word2, index1+1, index2+1);
else {
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 4 // Find the minimum distance between two words in a list. The words can
repeat.
int EditDistance(string &word1, string &word2) {
if (word1.empty()) {
return word2.size();
} else if (word2.empty()) {
return word1.size();
}
vector vi(word1.size() + 1);
int n(0);
generate(vi.begin(), vi.end(), [&] { return n++; });
for (int i = 0; i < word2.size(); ++i) {
int pre = vi[0];
vi[0] = i + 1;
for (size_t k = 0; k < word1.size(); ++k) {
int temp = vi[k + 1];
... 阅读全帖 |
|
t****a
发帖数: 1212 | 5 楼主说的这题实际上是第127题
刚做了个clojure的解法，比java要短小很多。
可惜不能在leetcode上测试大数据，真心希望leetcode支持C/C++/Java以外的语言。
(defn word-map [dict]
(let [g (group-by first (for [word1 dict
word2 dict
:let [wd (word-dist word1 word2)]
:when (== wd 1)]
[word1 word2]))
ks (keys g)
vs (map (partial mapv second) (vals g))]
(zipmap ks vs)))
(defn word-dist [word1 word2]
(reduce + (map (f... 阅读全帖 |
|
b***p
发帖数: 700 | 6 这个是python solution, worst case 是O(n^2). 比普通的Greedy Solution, 有两个
改进
1. 计算bit map of word, and AND operation to check if there is common char
2. 遍历是从最长的word开始
还有一个可以改进的地方是，利用元音字母，用word_len+vowel 作key，减少不必要
的compare
class DiffWordsMaxLenProduct:
def __init__(self):
# dict: word -> word char bit map
self.dict_word_bit = {}
# dict: word_len -> [word1, word2, word3...]
self.dict_word_len = {}
#
# compute the bit map of word char
#
def bit_word(self... 阅读全帖 |
|
j***u
发帖数: 16 | 7 如果按inverted index方法
DocID_1 = { word1,word2,word3}
DocID_2 = { word2,word3}
DocID_3 = { word1,word3,word4}
那么,Hash链表
H(word1)-->DocID_1-->DocID_3
H(word2)-->DocID_1-->DocID_2
H(word3)-->DocID_1-->DocID_2-->DocID_3
如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1}
就变成求所有查询word的hash链的交集.
如果是这样的话，问题可以先简化找2个链表的重复数据，
然后根据得到的重复数据集合，和下一个链表比较 找交集 |
|
w******g
发帖数: 189 | 8 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个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... 阅读全帖 |
|
w******g
发帖数: 189 | 9 一上来就做题，没有废话。只做一题，但是要求直接编译运行出正确结果。
题目是给定一个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... 阅读全帖 |
|
y**********a
发帖数: 824 | 10 class MinDist{
Map dist;
String separator;
int minDist(String s1, String s2, Map>map) {
dist=new HashMap<>();
Listl1,l2;
if ((l1=map.get(s1))==null||(l2=map.get(s2))==null) return -1;
int rel=Integer.MAX_VALUE;
for(int i1=0,i2=0;i1
int v1=l1.get(i1),v2=l2.get(i2),dif=v1-v2;
rel=Math.min(rel,Math.abs(dif));
if (rel==1) return 0;
el... 阅读全帖 |
|
r*******y
发帖数: 290 | 11 std::ifstream ifs;
ifs.open("file_name");
char line[256];
std::string word1, word2;
while(ifs.getline(line, 256, ',') {
word1 = line;
ifs.getline(line, 256);
word2 = line;
std::cout << "word1 is" << word1 << "\t"
<< "word2 is" << word2 <
} |
|
l*********s
发帖数: 5409 | 12 I am having some very weird bug while trying to write a macro that can
expend the short hand notion like var1--var11 used in SAS.
The "shorthand" macro works fine on its own, but fails to work when called
by the "formula" macro. The error message seems to say that "the set
statement in the data step is not valid or not in proper order", what's
going on?
Many thanks!
////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////... 阅读全帖 |
|
j***u
发帖数: 16 | 13 就是
i.e. m = 3 = word1 + word2 + word3,
1>先求 union(m) = H(word1) + H(word2) + H(word3) 链表里所以doc_id 数目（有重
复)
这个union 包括 同时有3个word的doc_id, 也有只有1个或2个 的doc_id,
2>求交集 intersect(p = m) = H(word1) 交 H(word2) 交 H(word3), 得到的 集合就是
同时含有3个word的doc_id 数目,
3>结果 sum (p < m) = union(m) - 3 * intersect( p = m) (去掉所有 同时含3个
word的doc_id) |
|
T*****u
发帖数: 7103 | 14 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
|
T*****u
发帖数: 7103 | 15 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
|
f**********t
发帖数: 1001 | 16 #include "common.h"
class WordsDistance {
vector _array;
public:
WordsDistance(initializer_list l) : _array(l) {}
int dist(string word1, string word2) {
int res = INT_MAX;
size_t left = 0;
while (left < _array.size() && _array[left] != word1 && _array[left] !=
word2) {
++left;
}
if (left == _array.size()) {
return res;
}
size_t right = left + 1;
while (right < _array.size()) {
if (_array[right] == _array[left]) {
l... 阅读全帖 |
|
l*******b
发帖数: 2586 | 17 C++写了个。。。大伙看吧，这里用的ruby的语法挺好懂呀
#include
#include
#include |
|
r*****n
发帖数: 2 | 18 onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
是fresh master.
两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
解题意。
有一种新型存储设备，特点是：
1. 价格贵，稳定性高
2. 可读写，但写入的内容不能修改
如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
呢。
4轮Onsite 3个印度人一个欧洲人。都是从简单的题开始，不停改改改。都讨论了项目
经验，还问得很细。写完代码都是要照相的，我有个题是开始写得挺干净，后来条件加
加加就改花了，然后interviewer掏出手机拍了一张。。我觉得是不是可以在写完第一
版之后就请他拍一张先。。。
1.一个binary search变体。 写完之后开始抠代码，说如果把终止条件从low<=high 改
成low阅读全帖 |
|
h**o
发帖数: 548 | 19 两题有什么本质区别使得你们会想到一题用DP, 另一题用BFS?
1. Edit Distance：
-----------------
Given two words word1 and word2, find the minimum number of steps required
to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
2. Word Ladder
-----------------
Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, such that:
O... 阅读全帖 |
|
l****1
发帖数: 33 | 20 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
并且满足word1和word2没有common letter. |
|
h****2
发帖数: 46 | 21 昨天电面，两道题 不算难，求好运~~
1. Given a sorted array of floats, find the index of the number closest to x:
Example: {1.2, 2.5, 9.3} x = 5, return 1
2. Of the pairs of words in the dictionary that have no letters in common,
find one that maximizes the product of the words' lengths.
cat
dog
feed
pull
space
pair = word1, word2
length = word1.size() * word2.size() |
|
m*****k
发帖数: 731 | 22 1. compute each word's binary representation in 26 bits and save as an int,
for example, "a" becomes 10000...., which is 1*2^25
"abc" becomes 1110000.... , which is 7 * 2^23
2. construct a Hashmap by
scan the words in the dictionary, if key already exists, update the word if
it is longer.
result=[maximum,"",""];
3. with all the keys in the map,
for (key1 in map.keys):
for (key2 in map.keys):
if (key1 & key2 ==0):
x = word1.length()*words.length()
i... 阅读全帖 |
|
x********v
发帖数: 2535 | 23 http://www.1518.com/s?st=2&word1=%C5%ED&word2=%D3%C0%C4%EA
彭永年姓名测吉凶
彭永年的姓名三才配置为:火金木（凶）
它具有如下数理诱导力，据此会对人生产生一定的影响。
命运被压抑,不易成功,易招失败,易损害呼吸器官而生疾病。
1、总论:不但工作及事业上无法顺利成功,且内外不和,心情苦闷,生活不能安定,易招失
意,失败、家庭失和等情事,应谨慎为人处事,若天运五行属土,一生尚能小成功。
2、性格:虽有坚忍的个性,不怕失败或打击,性急而口齿灵利,容易得罪人而引起反感,应
注意成长时期流于问题少年,卷入朋友是非或法律纠纷,人生的考验较多。
3、意志:意志不够坚定,思想变化万千,但尚能忍受艰苦与突来的打击,痛苦度一生。
4、事业:所谋所做之事表面平稳,其实内面隐藏著随时发生的祸害,应选择人事问题单纯
的小本生意。
5、家庭:家内难和睦,应多忍让免造成婚姻危机,子女亦容易反感,早为独立打算。
6、婚姻:男娶懦弱固执之妻,婚后感情难和睦;女嫁好胜好强之夫,婚后常有争吵。
7、子女:女孩多于男孩,聪明但有反叛性质。
8、社交:个性顽强固执,争勇... 阅读全帖 |
|
b******g
发帖数: 1721 | 24 来自主题: JobHunting版 - 请教一道题 collect letters to set1 from word1
collect letters to set2 from word2
if set1==set2, then anagram ; otherwise not. |
|
z*******y
发帖数: 578 | 25 这个是Dynamic Programming
自己想还是挺难想的
搜一下 Dynamic Programming Edit Distance |
|
d*******8
发帖数: 785 | 26 在Converting的过程中要不要保持这个word还是个词典中的单词？
如果是那样的话，好像只有对相差一个Char的单词网络中做BFS
如果要求Operations最少的话，比如insertion, replacement, deletion都有各自
的Penalty的话，就是sequence alignment，DP就可以了吧。
a |
|
|
g*******y
发帖数: 1930 | 28 这个是算法课动态规划那部分比较简单的作业题吧
replace a |
|
j*****s
发帖数: 189 | 29 用DP好一些
for(int i = 1 ; i< n1 + 1; ++i){
for (int j = 1; j < n2 + 1; ++j){
if (word1[i - 1] == word2[j - 1])
{
dist[i][j] = dist[i - 1][j - 1];
}
else{
dist[i][j] = min(dist[i - 1][j - 1], dist[i - 1][j],
dist[i][j - 1]) + 1;
}
}
} |
|
h********g
发帖数: 496 | 30 面经就发在同一个thread吧
这是个back to back两小时的面试，两轮的流程都是先问了些简历的东西，然后对方介
绍下自己的项目，然后coding。
1. coding题很简单，可能是半research职位，所以coding要求不高？
1) 给一堆document, d1, d2, d3...dn，要求给出 reverse-index: <{word1,
frequence1}, {word2, frequence2} ...>
---document很多，reverse index没法都放在内存里头，所以讨论了下如何partition
---还讨论了下不同document的类型，word之间的delimter可能不同，document预处理等
2) find lowest common parent for two nodes in the tree.
follow question: what's your test cases?
3) print tree nodes in level order
2. machine learning 的题目： 你有很多customer... 阅读全帖 |
|
P****d
发帖数: 137 | 31 这个题是C特有的吗？strlen是求字符串长度吗？如果是java是不是直接遍历所有的元
素用word1.length()*word2.length()看最后哪个乘机大就行了是么？有没有共同元素
对求string长度有什么影响吗？ |
|
J*****n
发帖数: 137 | 32 应该是pull * space吧？
最直观的话应该两层loop，然后问题转换成找 common letter of two words. 记录max
length, word1, word2.
至于找common，应该好多方法，可以new int[] 来记录字符出现次数，或者hashSet 判
断contains char.
复杂度这样看应该是O(n^3).
我这样对不对？有没有好的方法呢？ |
|
h****2
发帖数: 46 | 33 喔喔，哈哈
word1 word2 仅仅是指代两个单词，没有序号的意思哈
表达不清，不好意思 |
|
Z**********4
发帖数: 528 | 34 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
|
c*******r
发帖数: 610 | 35 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MIN;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？ |
|
Z**********4
发帖数: 528 | 36 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。 |
|
m******3
发帖数: 346 | 37 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行 |
|
|
Z**********4
发帖数: 528 | 39 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
|
c*******r
发帖数: 610 | 40 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MAX;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？ |
|
Z**********4
发帖数: 528 | 41 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。 |
|
m******3
发帖数: 346 | 42 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行 |
|
|
s*******m
发帖数: 228 | 44 怎么写这么长
int index1 = -1;
int index2 = -1;
int min_dist = INT_MAX;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
应该很简单的 |
|
|
j**********9
发帖数: 5431 | 46 snowshine classic word 2
word1: you... you whole family...
真爱无敌 |
|
C*****e
发帖数: 367 | 47 【 以下文字转载自 Church 俱乐部 】
发信人: CCBible (神同在圣经), 信区: Church
标 题: 海德堡要理问答主日37
发信站: BBS 未名空间站 (Sun Apr 29 22:25:51 2012, 美东)
海德堡要理问答主日37
来自基督徒百科
目录
1 英文版
2 英文2011版
3 赵中辉版
4 陈达/王志勇版
5 基督教要义圣经课程版
6 链接参考
英文版
37. Lord's Day
Q. 101.
May we then swear religiously by the name of God?
A.
Yes: either when the magistrates demand it of the subjects; or when necessit
y requires us thereby to confirm a fidelity and truth to the glory of God, a
nd the safety of our neighbour: for such an oath is founded on God's w... 阅读全帖 |
|
f*****r
发帖数: 229 | 48 I think about how to use cache line. For example, if the L1 cache line is 4
words (16 bytes), we move word1 to register a, then move word2 to reg b, then
move word3 to reg c, then move word4 to reg d; after those operations, move
rega to dest1, regb to dest2, etc. Is it faster?
Another possible way is using MMX mode. In each operation you can operate 16
bytes (or more). maybe MMX2 can give you better choice. But I guess that this
may be only good for bulk data copy, since mode switch has some ov |
|
r***e
发帖数: 31 | 49 Maybe I did not describe the problem clearly, the attribute A1 is a string,
how can I find all the records that have the value in A1 has the format "word1
word2 word3".
the |
|
n******7
发帖数: 12463 | 50 没用过NoSQL，现在遇到两个问题，都需要储存、查询大量的大数据，考虑是不是可以
用上NoSQL
问题大概是这样的，我有很多docs，每个doc有很多words，很多words出现频率很高，
words在一个doc里面出现顺序不重要。docs本身有一些注释
我希望有个database可以
1. 存储这些docs。我琢磨做成 word1 -> {doc1:count,doc2:count2} 这样的
2. 存储一个新doc时，可以update已有的key-> value 列表。如果遇到新的word，就建
立新的key-> value 关联
3. 比较docs。这个比较麻烦。比如给一个doc，我想很快知道哪些docs跟它有一样的
key。如果有必要，我还想查询substring。比如有个文档有mitbbs这个词，可能我想把
mit和bbs这两个key也包括进来
我本来觉得用SQL应该可以搞定，但是这两个问题里面，可能的词汇表都很大（>10^9）
。 问题1稍好点，文档之间很多高频词是差不多的，问题2词汇表更大，文档之间的关
联更弱。这个用NoSQL有戏吗？看了一下Redis，好像就是个只有... 阅读全帖 |
|
