# Leetcode 38: Count and Say

Let’s solve a medium problem together on Leetcode.com: Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

`countAndSay(1) = "1"`

`countAndSay(n)` is the way you would "say" the digit string from `countAndSay(n-1)`, which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. …

# How to flatten a binary tree to a linked list: recursion approach

Data structures such as binary trees, linked lists are frequently asked in a technical interview. Sometimes, interviewees are asked to transform one data structure to another. For example, convert a list to a linked list, or covert an ordered list to a binary tree, etc. Today, I’ll talk about a medium problem in leetcode.com: flatten a binary tree to linked list.

Given the `root` of a binary tree, flatten the tree into a "linked list":

The “linked list” should use the same `TreeNode` class where the `right` child pointer points to the next node in the list and the `left`

# Merge Sort a linked list

Sorting algorithms are frequently asked during a technical interview. Several common sorting algorithms such as quicksort, selection sort, merge sort are usually applied to sorting a list. However, sorting a linked list is not straightforward: it’s not easy to access an element by index in constant running time. Most of the sorting algorithms ask for extra space and the running time is relatively large. Today, I’ll talk about how to apply the merge sort algorithm to a linked list, the running time is O(n*log(n)), and it happens in-place.

Merge sort is a divide and conquer algorithm that sorts the input…

# Implement a doubly linked list with Python

## Introduction

A singly linked list is a set of linked nodes. Different from a singly linked list, each node in a doubly linked list has an extra pointer points to its previous node. Today, I’ll talk about the implementation of a doubly linked list in python.

• Node class

A doubly linked list is composed of a set of nodes. A node has two pointers and a value. One pointer points to its previous node, another pointer points to its next node.

`class Node:    def __init__(self, val):        self.val = val        self.next = None        self.prev = None`

Besides the…

# Max area of the island: dfs and bfs approach

For the given island that’s represented in a matrix of 0's and 1's, we usually use a depth-first search or a breadth-first search algorithm to solve. Today, I’ll introduce how to solve and compare such a problem using both approaches.

Given a non-empty 2D array `grid` of 0's and 1's, an island is a group of `1`'s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example:

`…`

# Solve the sliding window maximum problem

The sliding window algorithm is often used to find the target number in a string/list. Today, I’ll introduce how to solve this leetcode problem using the sliding window algorithm and optimize its running time.

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example 1:

`Input: nums = [1,3,-1,-3,5,3,6,7], k = 3Output: [3,3,5,5,6,7]Explanation: Window…`

# Implement a Trie in Python

We know tree well, a binary search tree performs well in searching. Today, I’ll introduce another tree-like data structure, which is widely used for retrieval of a key in a dataset of strings: trie.

A trie also called prefix-tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are always strings and characters. A trie is structured by trie nodes. …

# Crack the house robber problem

My previous post introduced the Knapsack problem. It states how to solve using the dynamic programming algorithm. Besides Knapsack, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a…

# Intro to dynamic programming knapsack problems

Dynamic programming problems are frequently asked in a tech interview. For me, dynamic programming problems are challenging to understand and to solve. Recently, I see a post demonstrating that dynamic programming problems can be categorized. One of the categories is the Knapsack problem. Today, I'll introduce what’s knapsack problem and its related topics.

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and…

# Deal with subset, permutation, combination problems using backtracking algorithm

It’s often asked during a technical interview: write a function to get the subsets/combinations/permutations for a given set. These problems seem difficult to solve in the first place, but have similarities when applying the backtracking algorithm. In this post, I’ll illustrate how to solve these problems using the backtracking algorithm.

Assume we are given a set A, and it contains several elements. For example, A = [1, 2, 3]. ## Wangyy

on the way to become a programmer