-2

A nested dictionary is a dictionary whose keys are strings and whose values are string or other nested dictionaries. Given a string representation , we need to return a String representation where the entries are sorted by key(within each nested dictionary)

Input: { b:{cb:cranberry,bb:blueberry},a:apple,c:cherry}
Output:  { a:apple,b:{bb:blueberry,cb:cranberry},c:cherry}

Here entries in outermost dictionary have been reordered by key (i.e from b,a,c to a,b,c) . Similarly , the entries in innermost dictionary have been reordered by key(i.e from cb,bb to bb,cb)

Also, Note : Output will have same general format as input string. except that within each nested dictionary, keys should be sorted in increasing lexicographic order ( eg. a<b<bb<bbb<bc<c)

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
Deepak Garg
  • 47
  • 1
  • 6
  • Here's how to do it in JavaScript, if that's any help: https://stackoverflow.com/questions/4222690/sorting-a-json-object-in-javascript – ControlAltDel Jun 10 '17 at 22:07

1 Answers1

0

This smells like an interview question. Anyway.

Basic Ideas:

  • You iterate the input char by char.
  • Use a Stack to store each dict depth by depth. The top of the stack will have the deepest sub-dict
  • Every time a sub-dict is scanned, convert the sub-dict to a String value and assign the value belonging to the key from the parent.
  • You can represent each dict / sub-dict with TreeMap in Java.
    Using TreeMap instead of HashMap because TreeMap sort the entries by their keys already.

It's hard to make it "clear" without giving out the complete solution. Hope it helps.

Minjun Yu
  • 3,497
  • 4
  • 24
  • 39