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.
Majority Element
A majority element over a collection is the one that occurs more than half of all the elements in the collection.
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.
Sorting (4): Heapsort
Recall that heaps are introduced to help illustrate compact arrays. One useful operation for 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.
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.
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.
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 Primitives
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.
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.