我正在准备面试,其中一个问题往往是这样的:
提供句子(例如,歌曲是最好的歌曲),该句子被分解成单词和单词的第一个字母的索引,即," the“- 0,12;" song”- 4,21;" is“- 9;" best”- 16;选择数据结构来存储该信息,并使用该数据结构重构该句子。
我最初的尝试是将单词存储在hashmap中,其中键是单词,值是位置数组。这是完全可行的,但是嵌套的for循环和在边界索引、在适当位置读取空格等恼人的问题会变得相当复杂。
我已经为它做了代码,所以如果有人想看,我会发布(它很长,是一本引人入胜的读物!!)
无论如何,对于我的问题:有没有人能提出一种更有效的方式来表示和重建数据?我很想尝试另一种方法,但到目前为止我只能想到这一点。
发布于 2012-04-10 09:15:33
作为一个面试不同技能水平的候选人的人,我希望受访者在决定最终数据结构之前问更多的问题。
一种选择是为包含单词、其位置和对下一个单词的引用的每个单词创建一个WordPosition对象。这些将形成一个链表,使得重构句子成为一种简单的顺序遍历。将它们存储在映射中,将单词作为关键字,并为每个单词提供一个WordPosition列表。
发布于 2012-04-10 09:10:05
让键作为位置怎么样?然后你不需要使用arrays.and,你可以使用树映射,然后集成器将按顺序返回令牌。
发布于 2012-04-10 09:25:17
我在这里避免使用地图,因为这看起来太简单了。
class Sentence {
String[] words;//Every word in the sentence
int[][] word_positions;//{index into the word array,start position of that word in the sentence}
String getSentence(){
//Find the last position of the last character of the last word
int length = word_positions[word_positions.length][1]
+ word[word_positions[word_positions.length][0]].length();
//Allocate an appropriate sized array
char[] sentence = new char[length];
//Iterate through every word in the sentence, putting it into the correct place.
for (int w=0; w<word_positions.length; w++){
//figure out where in the array this word will start
int start = word_positions[w][1];
//get the word
char[] word = words[wordpositions[w][0].toCharArray();
//copy it into the master array at the correct position
for (int letter=0; letter<word.length; letter++ ) {
sentence[start+letter] = word[letter];
}
}
return sentence.toString();
}
}如果这没有涵盖问题的一部分,请发表评论。我不确定我是否理解了所问问题的全部范围。
https://stackoverflow.com/questions/10081800
复制相似问题