For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the Daily Coding Problem (DCP) and decided to give it a shot.
The code is in C#.
How it works?
The folks at DCP send you a problem that was asked at a top company everyday for you to solve. The premium membership also offers the opportunity to verify your solution.
Problem #2
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node: def init(self, val, left=None, right=None): self.val = val self.left = left self.right = right The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right')) assert deserialize(serialize(node)).left.left.val == 'left.left'
My solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Task03
{
public class Program
{
private const string Empty_Marker = "1";
public static void Main(string[] args)
{
var node = new Node("root", new Node("left", new Node("left.left")), new Node("right"));
var serialized = Serialize(node);
Console.WriteLine(serialized);
node = Deserialize(serialized);
Console.WriteLine(node.Left.Left.Value);
}
public static string Serialize(Node node)
{
if (node == null)
{
return Empty_Marker + '-';
}
var builder = new StringBuilder();
builder.Append($"{node.Value}-");
builder.Append(Serialize(node.Left));
builder.Append(Serialize(node.Right));
return builder.ToString();
}
public static Node Deserialize(string serializedNode)
{
var nodes = serializedNode
.Split('-', StringSplitOptions.RemoveEmptyEntries)
.ToArray();
var queue = new Queue<string>(nodes);
var node = DeserializeNode(queue);
return node;
}
private static Node DeserializeNode(Queue<string> nodes)
{
if (nodes.Peek() != null)
{
var nextNode = nodes.Dequeue();
if (nextNode == Empty_Marker)
{
return null;
}
var node = new Node(nextNode);
node.Left = DeserializeNode(nodes);
node.Right = DeserializeNode(nodes);
return node;
}
return null;
}
}
Explanation
For the serialization, we traverse the tree depth first and add the current node's value to the serialized string. When we reach a node which is null (basically it's parent doesn't have a child), we put an Empty_Marker
to signal that there is no node here. This works assuming the symbols for Empty_Marker
and '-' are not going to be used in any node's value.
For the deserialize, we split the given string and put the results in a queue. Then build the tree depth first, getting through the queue's first element and stopping when we reach an Empty_Marker
I will try to do the daily problem everyday, but sometimes life gets in the way :)
Solutions are posted in my github account
.
Feel free to leave a like and let me know in the comments if I should continue to post my solutions.
If you also have any better solution in mind, by all means share it, so we can learn from each other.
Latest comments (10)
I think this is a minimal and fast solution :
Python solution using recursion.
My first time to see someone using Lua, thanks for the code, cool!
In Javascript, JSON serialization/unserialization is already supported, so this felt like cheating:
Exactly man, I looked at it, and thought, what?? They're asking one thing that already exists?
Python solution defining
__repr__
, which is meant for exactly this purpose:Edit: Included test from problem statement in the code, so that it should now be ready for copy and paste into file and
python3 -i <file>
. While we are at it, implemented__eq__
and__hash__
, so that we can assert even stronger tests.Quite impressive, thank you!
Go solution. Its a bit verbose as it does not have optional/default params.
Here's my C# solution
The tricky part is to make it work for arbitrary values, i.e. drop the assumption the symbols for Empty_Marker and '-' are not going to be used in any node's value.
Here's such a solution in Perl, tests included: