Problem: JSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day, suddenly, all of the JSON parser libraries went missing. You have been called upon to save us all from impending doom.
Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order. Please note that to simplify the things key is a string and value is either a string or a json object. No other data type is allowed.
You need to write following methods:
- Constructor: Make an object of the class.
- Serialize: Returns the json string.
- Deserialize: Save the json string in a data structure.
Example:
Input: ["JsonParser", "Deserialize("{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}")", Serialize()] Output: [None, None, "{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}"]
Approach: This can be done using many DS like trees, dictionary/map but I am using Linked List here with child pointer. As for me it looks like a list, where if value is another list of key value pair then we can say it is child otherwise it's simple data stored in the node.
Each comma ',' says this is next node. With this thought just look at the implementation to understand the solution in more details.
Please note that I haven't tested it throroughly so there might be some corner cases where the below program will fail but the approach will remain same.
Implementation in C#:
public class ListNode
{
public string Key {get; set;}
public string Value { get; set; }
public ListNode Next {get; set;}
public ListNode Child {get; set;}
public ListNode(string key)
{
this.Key = key;
}
}
public class JsonParser
{
public JsonParser()
{
this.head = null;
}
public void Deserialize(string str)
{
this.Clear();
int currIndex = 1;
this.head = this.DeserializeToList(str, ref currIndex);
}
private ListNode DeserializeToList(string str, ref int currIndex)
{
// Nothing to consume
if (currIndex >= str.Length)
{
return null;
}
int keyIndex = str.IndexOf(":", currIndex);
// No key exist means wrong input
if (keyIndex == -1)
{
return null;
}
// Get key
string key = str.Substring(currIndex, keyIndex - currIndex);
// Create the node
ListNode node = new ListNode(key);
// First case when value is string
if (str[keyIndex + 1] != '{')
{
int bracketIndex = str.IndexOf("}", keyIndex + 1);
int commaIndex = str.IndexOf(",", keyIndex + 1);
int valIndex = Math.Min(bracketIndex, commaIndex);
if (valIndex == -1)
{
valIndex = bracketIndex;
}
string val = str.Substring(keyIndex + 1, valIndex - (keyIndex + 1));
node.Value = val;
currIndex = valIndex + 1;
}
// Second case when value is JsonObject, Need to initialize child
else
{
currIndex = keyIndex + 2;
node.Child = this.DeserializeToList(str, ref currIndex);
}
// In case of closing bracket there is no next node.
if (str[currIndex - 1] == '}')
{
node.Next = null;
++currIndex;
}
// In case of comma there is a next node.
else
{
node.Next = this.DeserializeToList(str, ref currIndex);
}
// Current node is properly initialized now
return node;
}
public string Serialize()
{
return this.SerializeToStr(this.head);
}
private string SerializeToStr(ListNode node, bool isNext = false)
{
if (node == null)
{
return "";
}
// In case of next we don't need to wrap around brackets
string str = isNext ? "" : "{";
str += node.Key + ":";
// If value is null means child is there so serialize it first before moving
// to next
if (node.Value == null)
{
str += this.SerializeToStr(node.Child);
}
else
{
str += node.Value;
}
// Go to next node
if (node.Next != null)
{
str += ("," + this.SerializeToStr(node.Next, true));
}
str += isNext ? "" : "}";
return str;
}
public void Clear()
{
this.head = null;
}
private ListNode head;
}
Complexity: O(n) for both serialize and deserialize
No comments:
Post a Comment