title: Interview: Renaming all files in a directory using a data structure
body: <p>This is a problem I have encountered in a tech interview. You have 500,000 files in a directory, which is configured so that they are always in alphabetical order. They have names as such:</p>
  
  <ul>
  <li>Afile</li>
  <li>Bfile</li>
  <li>File00000001</li>
  <li>File00000002</li>
  </ul>
  
  <p>...</p>
  
  <p>You want to rename all the files <strong>while preserving their order</strong> as such:</p>
  
  <ul>
  <li>File00000001</li>
  <li>File00000002</li>
  <li>File00000003</li>
  </ul>
  
  <p>...</p>
  
  <p>You can probably see the obvious issue here. If you rename Afile into File00000001, it will collide with the existing file with the same name and also the order will be altered, which is not what we want.</p>
  
  <p>The question here is, how can you devise an algorithm with the most optimal run-time to do the renaming task efficiently?</p>