DS4Fun

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

A Doubly Linked list looks like a similar to Singly Linked list but there is one extra pointer that holds the previous node information also. It holds the information of the previous as well as the next node. It gives us the flexibility to iterate backward and forward direction. Let moving forward and implement a doubly linked list. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Custom Doubly Linked List Class class Node< T > { T data ; Node< T > next ; Node< T > previous ; public Node() { } public Node( T data) { this . data = data; } public Node( T data, Node< T > next, Node< T > previous) { this . data = data; this . next = next; this . previous = previous; } } The below diagram will really helpful whenever you are going to create a doubly linked list on your own. You can easily guess that t

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.

Given a non negative integer number num . For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array. Input: 2 Output: [0,1,1] Follow up: It is very easy to come up with a solution with run time  O(n*sizeof(integer)) . But can you do it in linear time  O(n)  /possibly in a single pass? Space complexity should be  O(n) . Can you do it like a boss? Do it without using any builtin function like  __builtin_popcount  in c++ or in any other language. Now, It is time to think before we write our code onto a paper. We read about the binary representation in college. A binary number is a special type of representation of a number in a binary format where the bit can be 0 or 1. You had an idea that the computer system also understands the 0's and 1's. 0's mean an inactive  bit and 1's mean an active bit. Let's understand the easiest way to calculate the number using the pictorial dia

As we have already covered the singly linked list in our previous blog . Now, It's the right time to discuss the circular singly linked list which is nothing but our tail node is pointing to the head node. Here we are using a few buzz words like:- Node- It is an actual container that holds data along with the reference of the next node. Head Node- It is the starting node of a linked list, if somehow it's lost then the complete linked list will be lost. Tail Node- It represents the linked list last node. Now, let us understand the implementation of the circular singly linked list with the help of code. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Create a Custom Linked List  class Node< T > { T data ; Node next ; public Node( T data) { this . data = data; } } It's our generic implementation of a class, which can hold any type of da

You are given a string containing characters A and B only. Your task is to change it into a string such that there are no matching adjacent characters. To do this, you are allowed to delete zero or more characters in the string. Your task is to find the minimum number of required deletions. For example, given the string s = AABAAB , remove an A at positions 0 and 3 to make s=ABAB in 2 deletions. Function Description Complete the alternatingCharacters function in the editor below. It must return an integer representing the minimum number of deletions to make the alternating string. alternatingCharacters has the following parameter(s): s: a string Input Format The first line contains an integer  q , the number of queries. The next lines q each contain a string s . Constraints 1 <= q <= 10 1 <= |s| <= 10 5 Each string s will consist only of characters A and B. Output Format For each query, print the minimum number of deletions required on a n

An  image  is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate  (sr, sc)  representing the starting pixel (row and column) of the flood fill, and a pixel value  newColor , "flood fill" the image. To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. At the end, return the modified image. Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color. Note the b