A palindrome is a word, phrase, or other sequence that reads the same backward as forward. One interesting example is “A man, a plan, a canal, Panama!”. Such property of palindromes leads to interesting problems and solutions.
Algorithm Cheat Sheet: Majority Element
A majority element over a collection is the one that occurs more than half of all the elements in the collection. When there exists a majority, a sorted array has that majority element placed in the middle position. For an unsorted array, a majority element can be identified by the times of its appearance (a hash table can be used to track the appearance of each unique element). Both sorting and hash tables involve certain overhead of time and space. Here we are studying Boyer–Moore majority vote algorithm which identifies the majority element in linear time with constant space.
Algorithm Cheat Sheet: Combination and Permutation
Combinations and permutations are two common operations applied to a collection of elements. There are also formulas to calculate the number of possible combinations or permutations, which sometimes can be leveraged to directly get answers which otherwise may require going through every possible case.
Algorithm Cheat Sheet: Heapsort
Recall that heaps are introduced to help illustrate arrays. One important operation on arrays is sorting and heaps can also be leveraged for that purpose. We know that a heap provides us the element with the maximum (or minimum) value on the top. Repeating the heapify operation for the rest of elements would continue telling us the second largest value and so on. This is the basic idea of heapsort.
Data Structure Checklist: Heap
Heaps are a useful data structure where the element on the top possesses the maximum (for max heap) or minimum (for min heap) value. A heap is essentially a specialized tree with two properties.
Data Structure Checklist: Binary Tree
One interesting aspect about binary trees is the way to store and represent them. Linked lists provide an intuitive illustration of binary trees, while extra spaces are required for pointers. Arrays seem to enable the most compact representation for binary trees, but the advantage only applies to some cases like complete binary trees.
Synchronization: Reader-writer Problem
The reader-writer problem is another synchronization problem of accessing a shared resource between two different roles. The only constraint is that when someone is writing, no others are allowed to either read or write. This indicates that at a time there can be only one active writer or multiple active readers.
Synchronization: Producer-Consumer Problem
The producer-consumer problem is also known as the bounded-buffer problem. It’s about the synchronization between a producer and a consumer who share a bounded buffer. The producer generates and puts items into the buffer, one at a time, and pauses when the buffer is full. The consumer consumes and removes items from the buffer, one at a time, and pauses when the buffer is empty. We can generalize the producer-consumer problem to have multiple producers or consumers.
Synchronization: Implementation Basics
Processors are often utilized effectively by running multiple tasks simultaneously. To guarantee the correct results of concurrent tasks, synchronization is desired across processes that execute those tasks. The fundamental of synchronization relies on the support of hardware, upon which a wide variety of high-level synchronization operations are built on software.
System Design: Social Network Feeds
Social networks play an important role in our daily life. Without physical connections, we are aware of the status of our friends. We are even able to connect with famous persons and learn their life, which was unimaginable before. One key way of connections in social networks is via feeds, where people publish status or information and others who subscribe or follow it would see. With more and more people are connecting virtually, there is a massive growth of feeds and their flow between people. A system to support such function in the global scale is the foundation of modern social networks.