A recursive solution to sum file sizes in a nested folder tree. Check if each node is a number (file) and add it, otherwise recurse through Object.values on subfolders. Time complexity is O(n) where n is the total number of nodes.
go over interview question for a frontend engineer that is asked in 2024. It's a question, um, to calculate a file size of the folder tree. So we're given this input, a tree that represented as object, so every key is a folder or file, and our nodes can be whether subtree, whether a number of the files. And what we need is we need to sum up all, all of the sizes here and return the result. Okay, so when we, when we see this type of tree It's usually a good idea to use a recursive function. So let's, let's go ahead and use them. So we receive a tree and we want size to collect our size, start it with 0. And so in this case we need to ask if our tree is a number, then we add it to the size. And if it is a subtree, then we need to go over the children and call the recursive function on every child. Okay, so let's, let's do that. So we ask if type of the tree is number, if it is a number, then size— I'm adding, I'm adding the value to the size. Else, so I'm having a tree and yeah, I can I can go for every key in the tree and calculate the child. It will also work. But let's see. So we see this autocompletion, but let's do also something else so that we can, um, go object.values. We can just iterate over values and we don't even need to know the keys. Yes, so here I'm going over values, which means, um, this subtree is a value, this is value, and also file can be a value. So I'll go over every value and I calculate over my children. So, and I'm collecting it. So for this tree, if it is a node, I'm adding it to the size If it is a tree, I'm going over his children, his children, and ask if— and calculate the size. Basically, I'm applying the recursive function, and what is important here is to return the size of this specific tree or subtree. So now we can test it. File size test. Then we're gonna— and I also have, I have two trees to test it, but we also want to print the result. Result console.log for file this and con— and console.log for file size too. So let's run it. And the expected sizes, as you can see here, I I have them written here. So this was a solution, uh, very clean. We receive the tree. If it is a node and it's a number, we add it to the size. If it is a tree, we go, we iterate over the tree children and apply the same recursive function on every child. And this is a solution. The question that can be also asked in this case: what is the time complexity? So we iterate over every child once, so it will be O. When n— we're having a tree, so n is our nodes. What is a node? So root is a node, folder nodes are folder nodes, and the key. So basically all the keys are our nodes, and we're iterating every node, visiting every node once, so it will be O when n are nodes. Also, we can think about stack call complexity because it's a recursive function, so the worst case scenario will be if every child in the tree tree, and if every parent in the— if every node in the tree has one child, so it's basically will be one line folder inside the folder inside the folder, and at the end I have only one file. So the, uh, the call stack will be O number of nodes. And the, the least case scenario is where my tree is all the files are direct children of the tree, so there will be no recursive call and it will be just O of nodes in the tree. So that was this question, very interesting question. I hope you like it and happy coding.
Design System Interview - Design System for a kanban board , Fullstack developer, 2024
