Grader incorrectly returns "Time Limit Exceeded" for a faster implementation
first implementation (Accepted without an issue)
class PreOrder {
static serialize(root) {
const arr = [];
function serializeNode(node) {
if (node === null) {
arr.push('');
return;
}
arr.push(node?.val.toString());
serializeNode(node?.left);
serializeNode(node?.right);
}
serializeNode(root);
return arr.join();
}
static deserialize(data) {
const nodes = data.split(',').map(value => {
if (value === '')
return null;
return +value;
});
let index = 0;
function deserializeNode() {
const value = nodes[index];
if (value === null || value === undefined) {
return null;
}
const node = new TreeNode(value);
index++;
node.left = deserializeNode();
index++;
node.right = deserializeNode();
return node;
}
return deserializeNode();
}
}Second implementation (Time Limit Exceed)
class HeapStruct {
static serialize(root) {
const arr = [];
function serializeNode(node, index = 0) {
if (node === null) {
return;
}
arr[index] = node.val;
serializeNode(node?.left, 2 * index + 1);
serializeNode(node?.right, 2 * index + 2);
}
serializeNode(root);
return arr.join();
}
static deserialize(data) {
const nodes = data.split(',');
function deserializeNode(index = 0) {
const nodeVal = nodes[index];
if (nodeVal === '' || nodeVal === undefined) {
return null;
}
return new TreeNode(
parseInt(nodeVal, 10),
deserializeNode(2 * index + 1),
deserializeNode(2 * index + 2),
);
}
return deserializeNode(0);
}
}implementation #2 is around 4-5 times faster on my device, and uses half as much memory as implementation #1
##methodology
first I created 500 trees with 10000 nodes of random numbers with 30% chance of a node being null using this code
function createRandomTree(): string {
return Array.from({ length: 10_000 }, (_val, index) => {
if (index !== 0 && Math.random() < 0.3) {
return null;
}
return Math.floor(Math.random() * 20_000) - 10_000;
}).join();
}
const dataSets = Array.from({ length: 500 }, createRandomTree);I ran both implementations with the built-in chrome profiler making sure to run garbage collection in before each run
as you can see it takes around 68 MB and 396 ms for the second implementation (HeapStruct), and 114 MB and 2018 ms for the first implementation (PreOrder)
Comments (1)