DS4Fun

Given N size node in the Singly Linked list and you have to find the kth node's value from the end.  Suppose, You have been provided the above Singly Linked List and the interviewer asks you to return 2nd last element from the linked list. Your response will be 7 and if the kth element is greater than the size of the Linked list then return -1. -1 will represent that the kth element is not present. This problem is repeatedly asked by many of the product based companies and the interviewer will grill you on it. He will add some constraint on the fly and asks you to solve it optimize way. Suppose, If we are going to solve this problem what would be the solution that comes into our mind. A Singly linked list holds the count of the node in the size variable, We will iterate from the head node to size - kth node and return the kth node's value. Once you give this solution to the interviewer, he/she will directly tell you that there is no size variable available in this custom Singl

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is as follows: After flattening the multilevel linked list it becomes: We have already covered the Doubly Linked List in our previous  blog.  If you look into the above problem then you will realize that the Doubly linked list class contains three references (next, previous, and child). It is clear in the flatten Doubly Linked list whenever a child exists, It first trave

Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: This problem was inspired by  this original tweet  by  Max Howell : Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off. I hope, you understand the above problem where we need to just invert the complete binary tree. While analyzing the problem, I found that we need some kind of storage where we can push elements using FIFO- First In First Out approach. We can say that it can be achieved using the queue data structure. We will push the root in the queue and iterate until the queue becomes empty. We poll/pop the node from the queue and swap it's left and right child and again push the left and right child into the queue itself. This process will happen until the queue is empty. Note: We are not going to push the node which is null.