1

我正在准备面试，往往会出现的问题之一是：

呈现一个句子（例如，这首歌是最好的歌曲）分解成单词和单词第一个字母的索引，即“the” - 0、12；“歌曲” - 4,21；“是” - 9; “最佳” - 16；选择一个数据结构来存储这些信息，并使用该数据结构重构句子。

我最初的尝试涉及将单词存储在哈希图中，其中键是单词，值是位置数组。这是完全可行的，但是对于嵌套的 for 循环和边界索引处的烦人问题、在适当位置的空间中读取等会变得相当复杂。

我已经为它完成了代码，所以如果有人想看，我会发布（它很长，读起来很吸引人！！）

无论如何，对于我的问题：任何人都可以提出一种更有效的方式来表示和重建数据吗？我很想尝试另一种方式，但这就是我迄今为止想出的全部

4

3 回答 3

1

作为一个面试不同技能水平的候选人的人，我希望被面试者在决定最终的数据结构之前问更多的问题。

  • 数据会专门用于重建句子吗？如果是这样，最好有一个清单。
  • 您需要能够查找单词位置吗？如果是这样，你的结构很好。
  • 对于使用这些数据的句子，您还可能会问什么其他问题？

一种选择是为每个单独的单词创建一个WordPosition对象，该对象包含该单词、它的位置以及对下一个单词的引用。这些将形成一个链表，使重构句子成为简单的按顺序遍历。将这些存储在地图中，其中单词作为键，WordPosition每个单词都有一个 s 列表。

于 2012-04-10T01:15:32.600 回答
0

让键成为位置怎么样？那么你不需要使用数组。你可以使用树形图，然后积分器将按顺序返回令牌。

于 2012-04-10T01:10:04.673 回答
0

我在这里避免使用地图，因为这似乎太简单了。

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();
  }
}

如果这不涵盖问题的一部分，请发表评论。我不确定我是否了解所问内容的全部范围。

于 2012-04-10T01:25:16.953 回答