Where Binary Heap is Used
A full binary tree (sometimes referred to as a proper binary tree or plane binary tree) is a tree in which every node other than the leaves has two children. In other words, each node has either 0 child or 2 children.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
A perfect binary tree is a binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.
A Binary Heap is a binary tree with following 2 properties:
Simple Database Challenge
Earlier last week, I was asked to implement an in-memory database similar to Redis (name-value pairs). This post is about code style, algorithmic performance, and thought process. For simplicity's sake, my program to the challenge will receive commands via stdin, and should write appropriate responses to stdout.
Java Collection Framework
Java Collection Framework (java.util.* package) is a unified architecture for representing and manipulating collections. This post is a quick note of my knowledge about Java Collection Framework that covers frequently used java data structure to store a group of elements and/or key-value pairs. In the java.util framework, there are two major camps - Collections & Map.
To illustrate, I use solid lines to denote 'extends', and dash lines to denote 'implements'. The way to use my note is to first go to the diagram looking for the specific class or interface, then read the brief blurb that'll remind you what the class or interface is about for the right data structure.
Algorithm - BFS & DFS
Queue and Stack are basic data structure. This post is about implementing Breadth First Search (BFS) & Depth First Search (DFS) using concept of Queue and Stack.
Assuming we have a set of values (see left). If you write these values down on a a piece of paper, from the top element you can branch downward into either left or right element each has its value. You can get a set of values with triangular look as shown.
The question is, going from the value at the top to the bottom by choosing to go down the path of either left or right, what is the maximum sum among all possible paths?
A clear thought process helps coders to get to the solutions. This post simply walks you through my thought process of how to implement some very basic data structure - a stack and a queue.
In this post, I note the approach and my thought process about determining whether a given smaller tree (t2) is a sub-tree of another larger tree (t1).
First, the approach: Since I know t2 is smaller and it is to be matched/found in a larger tree t1, I'll take the approach of scanning through the larger tree t1, and t1's children, by trying to find a match of t2 in t1's left child tree and find a match of t2 in t1's right child tree, recursively.
Data Structure - Mark Entire Row and Column Zero if an Element of an MxN Matrix is Zero
When you're asked to mark an entire row and an entire column with 0's if an element of an MxN matrix is 0, here's my thought process:
When you're asked to delete a node from a given single linked list. Here's my thought process: