# DS & Algo Problems — Tries and Radix Trees

In this post we are going to solve problems related to one of my favourite data structures-Tries. This is probably going to be the longest post in this series as the variety of problems that can be solved using Tries are quite a lot. Apart from standard Trie implementation I will demonstrate Radix Tree, which is a compressed Trie (memory optimized Trie).

I will not get into explaining what a Trie data structure is, as that can be found on several websites. This post will mainly deal with some variety of problems that can be solved using Tries.

Problem 1:

Pattern Matching — Design a data structure that supports adding new words and finding if a pattern matches any previously added string. …

# Problems With Advanced DS — Sorted Sets

In this post we are going to look at data structures for storing stream of numbers in a way such that the following operations can be efficiently performed (although the data structures we are going to visit here can do a lot more):

1. Current minimum and maximum numbers.
2. Median of all numbers seen so far.
3. Smallest (Largest) number greater (smaller) than a given number.
4. Count of all smaller (or larger) numbers given a number.
5. Binary search on numbers seen so far.

For 1 and 2, we can use a Min-Heap and a Max-Heap. 3 and 4 are special cases of Binary Search (5). But all of the above use cases can be solved efficiently if the numbers are sorted. …

# DS & Algo Problems — Binary Search and the Russian Doll

In the last post on binary search optimization, we found out that we can solve optimization problems using binary search under certain conditions. In this post we are going to look at another class of optimization problems that can again be solved using binary search technique. This class of problem is called the Longest Increasing Subsequence. I fondly call it the Russian Doll problem.

In its most simplest form, we are given an array A of size N. Each element of the array A is a real number. …

# DS & Algo Problems — Binary Search Optimization

Binary Search is probably one of the most ‘interesting’ algorithm from our high school and sophomore college computer science course. But most of us have encountered binary search either in the context of searching in a sorted array or some tweaked versions of similar problem:

1. Find an element in a rotated sorted array (with and without duplicates allowed).
2. Find an element in the 2D sorted array, only rows sorted, only columns sorted and both row and column sorted versions.

While these problems are interesting enough to puzzle even the most well prepared interview candidates. But in this post I will go into a different direction with binary search. …

# DS & Algo Problems — Bridges and Articulation Points

In this post we are going to look at a problem that is very relevant from a network analysis point of view. In a circuit network of wires, we would like to identify vulnerable connections that could be a single point of failure. Single point of failures like these are known as Articulation Points.

In a social network we would like to identify people who sits at the vulnerable points and hold together multiple sub-networks. Targeting these people for marketing offers and promotions and preventing them from churning will ensure that the network is still connected. …

# DS & Algo Problems — Bitmasking and DP

In this post we are going to look at one of the ‘simplest’ Dynamic Programming variation — Bitmasking. When I say ‘simplest’ I mean that ‘Bitmasking + DP’ problems are easy to identify and also most bit-masking problems have a more or less similar approach.

Some of the common traits of Bitmasking problems are:

1. Path finding problems — Enumerate all possible paths or paths based on certain conditions.
2. For a given input array A, depending in which order we go through the elements of the array A our objective function will change.
3. They require exponential runtime.
4. For folks into competitive programming will understand that problems with constraint on N (≤ 20) (i.e. size of array) hints towards bitmasking + DP. …

# Coding Problems and Solutions-15

[1] Number of Ways to Wear Different Hats to Each Other — There are `n` people and 40 types of hats labeled from 1 to 40.

Given a list of list of integers `hats`, where `hats[i]` is a list of all hats preferred by the `i-th` person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo `10^9 + 7`.

Example:

`Input: hats = [[3,5,1],[3,5]]Output: 4Explanation: There are 4 ways to choose hats(3,5), (5,3), (1,3) and (1,5)`

Approach — Use Bitmasking + Dynamic Programming. …

# Coding Problems and Solutions-9

[1] Flatten a Multilevel Doubly Linked List — 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.

Example:

`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]…`

# Coding Problems and Solutions — 14

[1] Find Longest Awesome Substring — Given a string `s`. An awesome substring is a non-empty substring of `s` such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of `s`.

Example:

`Input: s = "3242415"Output: 5Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.`

Approach — A substring is palindrome if all the numbers occurs even number of times or only one number occurs odd number of times.

Let ‘n’ represent the integer corresponding to the bit vector whether count of the digit k is even or odd. …

# Coding Problems and Solutions-8

[1] Remove Nth Node From End of List — Given a linked list, remove the n-th node from the end of list and return its head.

Example:

`Given linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.`

Approach — Use 2 pointer approach. One pointer is n+1 nodes ahead of the other. When the forward pointer reaches the end, the backward pointer’s next node is to be removed.

[2] Reverse Nodes in k-Group — Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. …