Hello everyone!

It’s Day 6 of #100DaysOfCode.

Today I completed the CSS video I was watching before. It was kind of knowing many properties about grid and flexbox. Grid is like a fixed space which we define before but flex-box is which we change according to the content, it is flexible that way :P. Although I completed the challenges along with the video, I think I will be learning a lot more when I am writing my own code for the application. But overall I can say I know the basics of CSS.

Next, I solved 2 leetcode design questions. These design questions take you a long time to understand and get the requirements right. I think it comes with more practice. The 1st one is Design Underground System. We have to design a system that checks in and checks out user with unique id’s at stations given and also given 2 stations it should return average time taken to travel between them by all users till then. It can be solved by using 2 hashmaps. One stores the key as id with tuple of (station, time) as value when the user checks in. When he checks out, we take his starting (station, time) to calculate the time taken and update this in the new dictionary with (start, destination) tuple as key and (distance, number of users) tuple as value. This is because when we want to know the average between 2 stations we can lookup in the dictionary and return total/users instead of calculating sum if we had to store individual entries. After we do this, we can delete the check-in entry in the first table to save memory since we don’t need the value again. To get the average, we call the (start, destination) and return average as mentioned above. Here the time complexity is O(1) cause inserting, deleting and finding a key in dictionary are all O(1) average time operations. The space complexity would be O(P+S^2) where P is the number of passengers and S is the number of stations which gives us S^2 pairs of stations in the second hash table.

The next one is the Design Browser History. Here we need to perform visit, forward and backward operations as specified. Have a look at the question for better understanding. It has 2 approaches to solve it. The first one being two stacks approach which I am not quite comfortable with. The next one is list approach which I will discuss. Initially we will create as list with the current url. We also initialize 2 pointers cur and end. In the visit command we increment the cur pointer and check if we are at the end of the list or in the middle of the traversal. If in the middle, we rewrite the value to given url otherwise append it at the end. Next, for the forward we move by given steps or till end of the list whichever is shorter and return the url. For the backward we go until given steps or begin of the list whichever is higher and return that url. So that’s the approach. The time complexity is  O(n) for forward or backward and insertion. Space is also O(n) for the list.

Later I also solved the DFS graph I was talking in the yesterday’s post. The question is we have n numbers 1 to n but are scattered in order. We are given pairs of adjacent values and we have to return the list as modified. First we will make a dictionary by traversing the given pairs. Each of the 2 pair values become key and value for each other. The catch here is we need to find the starting or ending point of that list to start our dfs. How we can find that is, the end values has only one adjacent value which means in the dictionary it is the one with has value with only one entry. So that’s either our start or end point. The question specified either list or reversed list is fine for the output. So, we traverse from that node till the end and return the list. The time complexity will be O(n^2). n in the worst case to find the end point and then dfs for that. The space would be O(n) for the dictionary and visited set that we take while in dfs.

That’s it for today, catch you guys tomorrow. Bye!!