Versioning can be used to support the isolation among transactions via snapshotting (i.e., snapshot isolation level). While one transaction is editing the data, the other transactions should only be able to see the original data before the edit. In order to achieve that, both of the original and new data are kept. That is, we maintain versions of the data.
The unique benefit of snapshot isolation is to allow a great concurrency with the execution of multiple transactions. This is because readers do not block writers and writers do not block readers. The rationale behind that is a well-designed mechanism of versioning, including the version generation, visibility, and reclamation.
A transaction must be always consistent and durable. This is straightforward when everything is normal, whereas maintaining such properties despite of failures becomes nontrivial. Failures like system crashes can leave a system in an inconsistent state. Today we are treating failures as the norm. It’s critical to possess the capability of fault tolerance. One important remedy is to recover transactions after crashes.
While transactions desires isolation, too strong isolation may offset the performance benefit from execution concurrency. In practice, isolation is defined at different levels with trade-offs between consistency and concurrency. The applicability of each isolation level is determined by the specific scenario targeted.
A request to storage systems often involves multiple operations, while the lack of integrity among individual operations complicates the management of a storage system. To address that, transactions are used as a container to encapsulate multiple individual operations and facilitate their management.
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.
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.
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.
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.
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.