title: Choosing a data structure to store the words in a sentence and their starting position
body: <p>I'm preparing for an interview and one of the questions that tends to come up is this:</p>
  
  <p>Presented with a sentence (e.g, the song is the best song) broken down into words and the indices of the first letter of the word, i.e. "the" - 0, 12; "song" - 4,21; "is" - 9; "best" - 16; choose a data structure to store this information and, using that data structure, reconstruct the sentence. </p>
  
  <p>My initial attempt involves storing the words in a hashmap where the key is the word and the value is an array of positions. This is totally doable but gets quite complicated with nested for loops and annoying problems at border indices, reading in spaces at appropriate locations etc. </p>
  
  <p>I have the code done for it, so if anyone would like to look I'll post (it's long and makes for a riveting read!!)</p>
  
  <p>Anyway, to my question: can anyone suggest a more efficient way of representing and reconstructing the data? I'd love to try another way but this is all I've come up with so far</p>