# Vivek bhargav A seasoned Software Engineer with a demonstrated history of working in the computer software industry. Skilled in Backend, Mobile Applications, Web development, Game Engine, Image Processing and Machine learning. Strong information technology professional with a Bachelor's degree focused in Computer Science and Engineering from Indian Institute of Technology, Guwahati. LinkedIn Profile: [link](https://www.linkedin.com/in/gomchikbhoka) # Seven Databases In Seven Weeks Data is getting bigger and more complex by the day, and so are your choices in handling it. From traditional RDBMS to newer NoSQL approaches, *Seven Databases in Seven Weeks* takes you on a tour of some of the hottest open source databases today. In the tradition of Bruce A. Tate’s [*Seven Languages in Seven Weeks*](http://pragprog.com/book/btlang/seven-languages-in-seven-weeks) this book goes beyond your basic tutorial to explore the essential concepts at the core of each technology. **This is a summary for the original book.** You can get original complete copy [here](https://pragprog.com/book/rwdata/seven-databases-in-seven-weeks) # Factors to consider * What data types does it support and what are your own requirements for data types ? * Do you need flexible schema or rigid schema ? * Is query flexibility important to you ? * Do you want to store large amounts of data across several machines * How much important is sata safety (via ACID compliance or something else) * Do you need Triggers * Do you need Transactions (for atomicity) * Do you need Stored Procedures * How much important is having ability to create **Views** for you ? * Can you live without **Joins** ? * Do you need **Partitioning** ? * Do you need to store only large blobs of data ? * Do you have enough information about the database requirements (like schema, probable tables, data types etc) # Genres of databases > **Don’t ask:** Can I use this database to store this data ? > > **Ask:** Should I use this database to store this data? It’s important to remember that most of the data problems you’ll face could be solved by most or all of the databases in this book, not to mention other databases. The question is less about whether a given database style could be shoehorned to model your data and more about whether it’s the best fit for your problem space, your usage patterns, and your available resources. You’ll learn the art of divining whether a database is intrinsically useful to you. * **Relational Databases** * Relational database management systems are set-theory-based systems implemented as two-dimensional tables with rows and columns * Data values are typed and may be numeric, strings, dates, uninterpreted blobs, or other types * Tables can join and morph into new, more complex tables because of their mathematical basis in relational (set) theory * examples: MySQL, H2, HSQLDB, SQLite, **PostgreSQL** * **Key-Value** * A KV store pairs keys to values in much the same way that a map (or hashtable) would in any popular programming language. * Because the KV moniker demands so little, databases of this type can be **incredibly performant** in a number of scenarios but generally **won’t be helpful when you have complex query and aggregation needs** * examples: memcached, memcachedb, membase, Voldemort, **Redis**, **Riak** * **Columnar** * data from a given column is stored together. * adding columns is quite cheap and is done on a row-by-row basis. * Each row can have a different set of columns, or none at all, allowing tables to remain sparse without incurring a storage cost for null values. * With respect to structure, columnar is about midway between rela- tional and key-value. * examples: HBase, Cassandra, Hypertable. * **Document** * Different document databases take different approaches with respect to **indexing, ad hoc querying, replication, consistency, and other design decisions**. Choosing wisely between them requires understanding these differences and how they impact your particular use cases. * examples: MongoDB, CouchDB * **Graph** * graph databases excel at dealing with highly interconnected data. * A graph database consists of nodes and relationships between nodes. * Both nodes and relationships can have properties (as key-value pairs) that store data. * The real strength of graph databases is traversing through the nodes by following relationships. * **Polyglot** * In real world, databases of one type are often used alongside databases of other types. * It’s still common to find a lone relational database, but over time it is becoming popular to use several databases together, leveraging their strengths to create an ecosystem that is more powerful, capable, and robust than the sum of its parts. This practice is known as polyglot persistence. # Important questions ## What type of datastore is this ? * relational * key-value * columnar * document-oriented * graph ## What was the driving force ? * RDBMS databases arose in a world where **query flexibility** was more important than **flexible schemas** * Column-oriented datastores were built to be well suited for **storing large amounts of data across several machines**, while **data relationships** took a backseat ## How do you talk to it ? * command line interface * script * graphical interface ## What makes it unique ? * querying on arbitrary fields * **indexing** for rapid lookup * some support **ad hoc queries**; For others, **queries must be planned** * Is schema a **rigid framework** enforced by the database or **merely a set of guidelines** to be renegotiated at will ## How does it perform ? * Does it support **sharding** * What about **replication**? * Does it distribute data **evenly using consistent hashing**, or does it **keep like data together** ? * Is this database tuned for reading, writing, or some other operation ? * How much control do you have over its tuning ## How does it scale ? * Talking about scalability without the context of what you want to scale to is generally fruitless * Whether each datastore is geared more for * **horizontal scaling** (MongoDB, HBase, Riak), * **vertical scaling** (Postgres, Neo4J, Redis), * **something in between** # PostGreSQL PostgreSQL is a relational database management system, which means it’s a set-theory-based system, implemented as two-dimensional tables with data rows and strictly enforced column types. Despite the growing interest in newer database trends, the relational style remains the most popular and probably will for quite some time. * The prevalence of relational databases comes from their vast toolkits * triggers * stored procedures * advanced indexes * their data safety (via ACID compliance), * or their mind share (many programmers speak and think rela- tionally) * query flexibility ``` Unlike some other type of datastores, you needn’t know how you plan to use the data ``` * PostgreSQL is by far the oldest and most battle-tested database in this book. It has * plugins for natural-language parsing * multi-dimensional indexing * geographic queries * custom datatypes * sophisticated transaction handling * built-in stored procedures for a dozen languages * and runs on a variety of platforms * built-in Unicode support, * sequences * table inheritance * subselects * and it is one of the most ANSI SQL–compliant relational databases on the market ``` PostgreSQL, being of the relational style, is a design-first datastore. First you design the schema, and then you enter data that conforms to the definition of that schema. ``` #### Why are relational databases called relational ? Relational databases are relational based on mathematics. They aren’t relational because tables “relate” to each other via foreign keys. Well [this link](http://www.vertabelo.com/blog/notes-from-the-lab/why-are-relational-databases-relational) explains it very well #### What's unique in relational databases ? All of the other databases we’ll read about in this book perform CRUD opera- tions as well. What sets relational databases like PostgreSQL apart is **their ability to join tables together** when reading them. Joining, in essence, is an operation taking two separate tables and combining them in some way to return a single table. ### Transactions PostgreSQL transactions follow ACID compliance, which stands for * Atomic (all ops succeed or none do) * Consistent (the data will always be in a good state—no inconsistent states) * Isolated (transactions don’t interfere) * Durable (a committed transaction is safe, even after a server crash) > We should note that consistency in ACID is different from consistency in CAP theorem ### Stored Procedures Every command we’ve seen until now has been declarative, but sometimes we need to run some code. At this point, you must make a decision: * execute code on the client side **or** * execute code on the database side. Stored procedures can offer huge performance advantages for huge architectural costs. You may avoid streaming thousands of rows to a client application, **but you have also bound your application code to this database. It will cause problems when you will wish to migrate to some other database** . The decision to use stored procedures should not be arrived at lightly. ### Triggers Triggers automatically fire stored procedures when some event happens, like an insert or update. They allow the database to enforce some required behavior in response to changing data. For example running a function that logs whenever a row is updated ## Views Using **views**, we can use the results of a complex query just like any other table. Unlike stored procedures, these aren’t functions being executed but rather **aliased queries**. Creating a view is as simple as writing a query and prefixing it with **CREATE VIEW view\_name AS**. For example: ``` CREATE VIEW holidays AS SELECT event_id AS holiday_id, title AS name, starts AS date FROM events WHERE title LIKE '%Day%' AND venue_id IS NULL; ``` and now you can use this "holidays" view just like a table ``` SELECT name, to_char(date, 'Month DD, YYYY') AS date FROM holidays WHERE date <= '2012-04-01'; ``` ## PostgreSQL’s Strengths * flexible query ability * very consistent and durable data * Most programming languages have battle-tested driver support for Postgres * flexibility of the join * You needn’t know how you plan to actually query your model, since you can always perform some joins, filters, views, and indexes—odds are good you will always have the ability to extract the data you want ![](https://780527828-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LvkgWUAGrfIe4fJMSob%2F-LvkgXS4vS6r54FBnn-c%2F-Lvkgi1Gfrq-U3S2BXDN%2Fno-sql-meme.png?generation=1575996286272594\&alt=media) PostgreSQL goes beyond the normal open source RDBMS offerings, such as powerful schema constraint mechanisms. You can write your own * language extensions, * customize indexes, * create custom datatypes, * and even overwrite the parsing of incoming queries ## PostgreSQL’s Weaknesses * Partitioning is not one of the strong suits of relational databases like Post- greSQL. If you need to scale out rather than up (multiple parallel datastores rather than a single beefy machine or cluster), you may be better served looking elsewhere. * If your data requirements are too flexible to easily fit into the rigid schema requirements of a relational database * or you don’t need the overhead of a full database, * or require very high-volume reads and writes as key values, * or need to store only large blobs of data, then one of the other data-stores might be a better fit ## Parting Thoughts A relational database is an excellent choice for query flexibility. While Post- greSQL requires you to design your data up front, it makes no assumptions on how you use that data. As long as your schema is designed in a fairly normalized way, without duplication or storage of computable values, you should generally be all set for any queries you might need to create. And if you include the correct modules, tune your engine, and index well, it will perform amazingly well for multiple terabytes of data with very small resource consumption. Finally, to those for whom data safety is paramount, Post- greSQL’s ACID-compliant transactions ensure your commits are completely atomic, consistent, isolated, and durable. # C++ I maintain collection of common templates used in my c++ code here * [Vector](/tech/c++/vector-1) * [Set](/tech/c++/set) * [Unordered Set](/tech/c++/unordered_set) * [Map](/tech/c++/map) * [Unordered Map](/tech/c++/unordered_map) * [Queue](/tech/c++/queue) * [Priority Queue](/tech/c++/priority_queue) * [Union find](/tech/c++/union_find) * [Utils](broken://pages/6FnGFxNdOMtDr27UWCP6) * [Algorithms](/tech/c++/algorithms) * [Matrix to Graph](/tech/c++/matrix_to_graph) * [Trie](/tech/c++/trie) * [Dijkstra](/tech/c++/dijkstra) # Utils
string to int ``` // no special include statement required int num = stoi("23"); // num is 23 now ```
int to string ``` // no special include statement required string s = to_string(12345); // s is "12345" now ```
int to char ``` // no special include statement required char itoc(int number) { return char('0' + number); } char c = itoc(5); // c is '5' now ```
char to int ``` // no special include statement required int ctoi(char c){ return c - '0'; } int i = ctoi('6'); // i is 6 now ```
is small case char (a-z) ? ``` bool isSmallCaseChar(char c){ return islower(c); } isSmallCaseChar('a') // true isSmallCaseChar('z') // true isSmallCaseChar('G') // false isSmallCaseChar('0') // false isSmallCaseChar('9') // false isSmallCaseChar('%') // false isSmallCaseChar('?') // false ```
is upper case char (A-Z) ? ``` bool isUpperCaseChar(char c){ return isupper(c); } isUpperCaseChar('a') // false isUpperCaseChar('z') // false isUpperCaseChar('A') // true isUpperCaseChar('G') // true isUpperCaseChar('0') // false isUpperCaseChar('9') // false isUpperCaseChar('%') // false isUpperCaseChar('?') // false ```
is digit ? ``` #include bool result = isdigit('6'); // result is true bool result = isdigit('g'); // result is false ```
is alphaNumeric ? ``` isalnum('a') // true isalnum('z') // true isalnum('G') // true isalnum('0') // true isalnum('9') // true isalnum('%') // false isalnum('?') // false ```
get ascii value of character ``` // no special include statement required int getAsciiValue(char c){ return int(c); } getAsciiValue('a') // 97 getAsciiValue('D') // 68 getAsciiValue('5') // 53 getAsciiValue('\n') // 10 ```
gcd ``` // GCD aka HCF int gcd(int a, int b){ if(a < b) return gcd(b,a); if(b == 0) return a; return gcd(b, a%b); } ```
NCR (i.e. N-choose-R) ``` // N-choose-R int NCR(int N, int R){ double ans = 1; R = min(R, N-R); for (int numer=N-R+1, denom = 1; denom <= R; numer++,denom++){ ans = (ans * numer) / denom; } return (int)ans; } ```
# Math ```cpp #include // Include cmath (std namespace) pow(x, y); // x to the power y sqrt(x); // square root of x ceil(x); // round up to int floor(x); // round down to int fabs(x); // absolute value fmod(x, y); // x mod y exp(x); log(x); log10(x); // e to the x, log base e, log base 10 sin(x); cos(x); tan(x); // Trig functions, x (double) is in radians asin(x); acos(x); atan(x); // Inverses atan2(y, x); // atan(y/x) sinh(x); cosh(x); tanh(x); // Hyperbolic sin, cos, tan functions ``` # String ``` #include // Include string (std namespace) string s; // Create strings s = "hello"; // assign s.size(); // number of characters in string s[0]; // 'h' s.substr(m, n); // Substring of size n starting at s[m] s = to_string(12.05); // Converts number to string reverse(s.begin(), s.end()); // reverse a string ``` # Vector ```cpp #include // include vector in code vector arr; // create an empty vector vector arr(10); // create a vector of size 10 vector arr{1,2,3}; // create vector with values 1,2,3 vector arr(10, 5); // create an arr of size 10, all elements initialised to 5 int n = arr.size(); // get number of elements in arr arr.resize(20, 0); // resize the vector to new final size = 20, each new item set as 0 // here existing values stay intact as new_size > old_size // check if vector is empty if (arr.empty()){ cout << "arr is empty"; } arr.push_back(3); // add element at end of vector arr.insert(arr.begin(), 7); // add an element at beginning of vector arr.insert(arr.end(), brr.begin(), brr.end()); // add another vector at end of a vector reverse(arr.begin(), arr.end()); // reverse vector arr.clear(); // clear all enteries sort(arr.begin(), arr.end()); // sort vector elements // sort vector elements in descending order using a comparator function sort(arr.begin(), arr.end(), [](int lhs, int rhs){ return (lhs > rhs); // read it like: lhs should come before rhs if (lhs > rhs) // or read it like: // In the final sorted array, relation between lhs and rhs is lhs > rhs }); ``` # Set ```cpp #include set s; // create a set of integers set s({4, 3, 9, 2, 0, 6}); // create a set with few initial elements cout << s.size() << endl; // number of elements in set s.insert(123); // add element to set s.erase(444); // erase an element from the set s.clear(); // remove all the elements from the set // search for an element if (s.find(444) != s.end()) { // It means 444 exists in the set } // iterate over all elements for(set::iterator it = s.begin(); it != s.end(); it++) { cout << *it << endl; } ``` # Unordered Set ```cpp #include unordered_set s; // create an unordered_set of integers unordered_set s({4, 3, 9, 2, 0, 6}); // create an unordered_set with few initial elements cout << s.size() << endl; // number of elements in unordered_set s.insert(123); // add element to unordered_set s.erase(444); // erase an element from the unordered_set s.clear(); // remove all the elements from the unordered_set // search for an element if (s.find(444) != s.end()) { // It means 444 exists in the set } // iterate over all elements for(unordered_set::iterator it = s.begin(); it != s.end(); it++) { cout << *it << endl; } ``` # Map ``` // case: keys in map is of type int struct KeyComparator { bool operator()(int lhsKey, int rhsKey) const { return lhsKey > rhsKey; } }; // case: keys in map is of type string struct KeyComparator { bool operator()(string lhsKey, string rhsKey) const { return lhsKey > rhsKey; } }; ``` ```cpp #include map mapp; // create a map of string: {integer} map mapp; // create a map of string: {integer} // create a map with few initial elements map mapp = { {"batman", 100}, {"superman", 500}, {"shaktiman", 250} }; cout << mapp.size() << endl; // number of enteries in myMap mapp["spiderman"] = 150; // add entry to the map int bmMarks = mapp.at("batman"); // get a value in map corresponding to a key int smMarks = mapp["superman"]; mapp.erase("superman"); // erase an entry from the map mapp.clear(); // remove all the enteries from the map // check whether map is empty if(mapp.empty()){ ... } // search for an element if (mapp.find("shaktiman") != mapp.end()) { // It means key: "shaktiman" exists in the map } // iterate over all elements for(map::iterator it = mapp.begin(); it != mapp.end(); it++) { cout << *it << endl; cout << it->first << endl; cout << it->second << endl; } ``` # Unordered Map ```cpp #include unordered_map umap; // create a map of string: {integer} // create a map with few initial elements unordered_map umap = { {"batman", 100}, {"superman", 500}, {"shaktiman", 200} }; cout << umap.size() << endl; // number of enteries in myMap umap["spiderman"] = 150; // add entry to the map int bmMarks = umap.at("batman"); // get a value in map corresponding to a key int smMarks = umap["superman"]; umap.erase("superman"); // erase an entry from the map umap.clear(); // remove all the enteries from the map // check whether map is empty if(umap.empty()){ ... } // search for an element if (umap.find("shaktiman") != umap.end()) { // It means key: "shaktiman" exists in the map } // iterate over all elements for(unordered_map::iterator it = umap.begin(); it != umap.end(); it++) { cout << *it << endl; cout << it->first << endl; cout << it->second << endl; } ``` # Queue ```cpp #include // include vector in code queue q; // create an empty queue q.push(10); // Insert element in queue int head = q.front(); // head int tail = q.back(); // tail int size = q.size(); // size of queue q.pop(); // Remove if(q.empty()){ // checks if queue is empty } ``` # Priority Queue ```cpp #include priority_queue pq; // create priority queue for ints pq.push(10); // push integer in priority queue pq.top(); // get the top element from pq without popping it pq.pop(); // pop the top element from pq. It returns void while(!pq.empty()){ // pq.empty returns whether pq is empty or not } ``` Note: If we update the value of a node inside our priority\_queue, that node will not be auto-heapified and hence will not be placed at correct position. Our priority queue will become inconsistent. So whenever you have to update a node inside priority queue * update the node's value * create a new node\* pointing to that node and push that in priority queue * our new node\* will be placed at correct position. Since we are updating the value in the node and the priority queue contains only node pointers, the old node pointer and fresh node pointer, both will point to same node which always contain the updated value. So when we will process this priority queue, it doesn't matter which pointer is popped out first since both are pointing to node with updated value. Now, to prevent multiple processing of node, keep a "isProcessed" field inside every node, initially set to false. whenever you process that node for the first time (can be via old pointer or via fresh pointer, doesn't matter), set that isProcessed field to true. Check this field whenever you are processing a node after popping it out, ignore that node if it is already processed ```cpp // priority queue with custom object class Student { private: string name; int marks; public: Student(string name, int marks){ this->name = name; this->marks = marks; } string getName(){ return name; } int getMarks() { return marks; } }; class StudentComparator { public: bool operator() (Student& lowerPriorityStudent, Student& higherPriorityStudent) { return higherPriorityStudent.getMarks() > lowerPriorityStudent.getMarks(); } }; int main() { priority_queue, StudentComparator> pq; pq.push(Student("A1", 90)); pq.push(Student("A2", 12)); pq.push(Student("A3", 45)); pq.push(Student("A4", 30)); pq.push(Student("A5", 50)); while(!pq.empty()){ Student top = pq.top(); cout << top.getName() << ", " << top.getMarks() << endl; pq.pop(); } return 0; } Result: A1, 90 A5, 50 A3, 45 A4, 30 A2, 12 ``` ```cpp // priority queue when keys inside the nodes of priority queue are updated during prrocessing (e.g. in dijkstra) #include #include using namespace std; class Node { public: int key; // priority queue will do sorting based on key string label; // label is general metadaata stored in the node. bool processed; // whenever we update key in a node, we insert a new node pointer in the pq // To prevent multiple processing of same node, we use this flag to keep track // if some node is already processed Node(int key, string label, bool processed): key(key), label(label), processed(processed){ } }; class NodeComparator{ public: bool operator()(Node* &lowerPriorityNode, Node* &higherPriorityNode){ return higherPriorityNode->key <= lowerPriorityNode->key; } }; int main(int argc, char const *argv[]) { // Always use Node* instead of Node. If there is some update in node key which decreases node's priority // (by increasing its key value here in this example), then stale node will be popped earlier than the updated node // which is wrong. If we use pointer, then stale node pointer and fresh node pointer, both will point to same node // which contains the updated value of key. // https://stackoverflow.com/a/27305600 priority_queue, NodeComparator> pq; Node* n3 = new Node(50, "N3", false); pq.push(new Node(10, "N1", false)); pq.push(new Node(3, "N2", false)); pq.push(n3); pq.push(new Node(150, "N4", false)); pq.push(new Node(1, "N5", false)); pq.push(new Node(100, "N6", false)); pq.push(new Node(15, "N7", false)); cout << "Priority Queue Initialised\n\n" << endl; n3->key = 5; pq.push(n3); cout << "n3 key updated\n" << endl; cout << "\n\nstarting processing of nodes in priority queue \n" << endl; while(!pq.empty()){ Node* top = pq.top(); pq.pop(); if(!top->processed){ // process node cout << "top node = " << top->label << " : " << top->key << endl; top->processed = true; } } return 0; } ``` # Union find ```cpp class UnionFindManager { public: // every connected component has a single root node identified using: i == parent[i] // parent[i] is the parent of ith node vector parent; // size[i] is meaningful only if i is a root node, // size[i] = number of nodes in its connected component vector size; /** * inputs :: * N : total number of nodes count */ UnionFindManager(int N) { size.resize(N, 1); // every node is in different set (each of size 1) initially parent.resize(N, -1); // set each node as its own parent initially for(int i=0 ; i= size[rootj]) ? rooti : rootj ; parent[smallRoot] = bigRoot; size[bigRoot] += size[smallRoot]; } bool isRoot(int i){ return (i == parent[i]); } }; int main(){ UnionFindManager ufm(10); ufm.unionNodes(0,2); // 2 gets merged in 0, rootNnode = 0 ufm.unionNodes(1,7); // 7 gets merged in 1, rootNnode = 1 ufm.unionNodes(7,8); ufm.unionNodes(8,9); ufm.unionNodes(4,5); cout << ufm.findRoot(8) << endl; // ans = 1 int totalDisjointSets = 0; for(int i = 0; i search index of item exactly equal to given number (if repeated, then first occurrence) ``` // **************** Own Implementation **************** int binarySearch(vector& arr, int low, int high, int target) { if (low == high) { if(arr[low] == target){ return low; } else { return -1; } } int mid = (low + high) / 2; if (arr[mid] < target) { return binarySearch(arr, mid + 1, high, target); } else { return binarySearch(arr, low, mid, target); } } int binarySearch(vector& arr, int target) { if (arr.empty()) { return -1; } return binarySearch(arr, 0, arr.size() - 1, target); } // ******************** Using STL ********************** #include int binarySearch(vector& arr, int target) { auto it = lower_bound(arr.begin(), arr.end(), target); if (it != arr.end() && *it == target) { return it - arr.begin(); } return -1; } ```
search index of item exactly equal to given number (if repeated, then last occurrence) ``` // **************** Own Implementation **************** int binarySearch(vector& arr, int low, int high, int target) { if (low == high) { if(arr[low] == target){ return low; } else { return -1; } } int mid = (low + high + 1) / 2; if (target < arr[mid]) { return binarySearch(arr, low, mid-1, target); } else { return binarySearch(arr, mid, high, target); } } int binarySearch(vector& arr, int target) { if (arr.empty()) { return -1; } return binarySearch(arr, 0, arr.size() - 1, target); } // ******************** Using STL ********************** #include int binarySearch(vector& arr, int target) { // upper_bound returns an iterator to the first element // that is strictly greater than 'target' auto it = upper_bound(arr.begin(), arr.end(), target); if(it == arr.begin()){ // the first element is strictly greater than 'target' return -1; } // Go one step back it--; if (*it == target) { return it - arr.begin(); } else { return -1; } } ```
search index of item exactly equal to given number (if repeated, then any occurrence) 
// **************** Own Implementation ****************


int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid - 1, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        return it - arr.begin();
    }
    return -1;
}
search index of first item just greater_than_or_equal to given number ``` // **************** Own Implementation **************** int binarySearchGte(vector& arr, int low, int high, int target) { if (low == high) { return low; } int mid = low + (high - low) / 2; if (target <= arr[mid]) { return binarySearchGte(arr, low, mid, target); } else { return binarySearchGte(arr, mid + 1, high, target); } } int binarySearchGte(vector& arr, int target) { // assuming arr[N] contains infinity, answer is going be one of [0,N] return binarySearchGte(arr, 0, arr.size(), target); } // ******************** Using STL ********************** #include int binarySearchGte(vector& arr, int target) { auto it = lower_bound(arr.begin(), arr.end(), target); if (it == arr.end()) { // return arr.size() if no such element is found // or -1 if you prefer to indicate 'not found'. return arr.size(); } return it - arr.begin(); } ```
search index of first item strictly_greater_than given number ``` // **************** Own Implementation **************** int binarySearchGreater(vector& arr, int low, int high, int target) { if (low == high) { return low; } int mid = low + (high - low) / 2; if (target < arr[mid]) { return binarySearchGreater(arr, low, mid, target); } else { return binarySearchGreater(arr, mid + 1, high, target); } } int binarySearchGreater(vector& arr, int target) { // assuming arr[N] contains infinity, answer is going be one of [0,N] return binarySearchGreater(arr, 0, arr.size(), target); } // ******************** Using STL ********************** #include int binarySearchGreater(vector& arr, int target) { auto it = upper_bound(arr.begin(), arr.end(), target); return it - arr.begin(); } ```
search index of last item which is less_than_or_equal to given number ``` // **************** Own Implementation **************** int binarySearchLte(vector& arr, int low, int high, int target) { if (low == high) { return low; } int mid = (low + high + 1) / 2; if (arr[mid] <= target) { return binarySearchLte(arr, mid, high, target); } else { return binarySearchLte(arr, low, mid-1, target); } } int binarySearchLte(vector& arr, int target) { // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1] return binarySearchLte(arr, -1, arr.size()-1, target); } // ******************** Using STL ********************** #include int binarySearchLte(vector& arr, int target) { // Find the first element strictly greater than 'target'. auto it = upper_bound(arr.begin(), arr.end(), target); // If 'it' is at the beginning, it means all elements in the vector // are strictly greater than 'target' if (it == arr.begin()) { return -1; // No element <= target found. } // If 'it' is not at the beginning, then the element immediately before it // is the last element less than or equal to 'target'. it--; return it - arr.begin(); } ```
search index of last item which is strictly_lesser_than given number ``` // **************** Own Implementation **************** int binarySearchLesser(vector& arr, int low, int high, int target) { if (low == high) { return low; } int mid = (low + high + 1) / 2; if (arr[mid] < target) { return binarySearchLesser(arr, mid, high, target); } else { return binarySearchLesser(arr, low, mid-1, target); } } int binarySearchLesser(vector& arr, int target) { // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1] return binarySearchLesser(arr, -1, arr.size()-1, target); } // ******************** Using STL ********************** #include int binarySearchLesser(vector& arr, int target) { // lower_bound finds the first element >= target. auto it = lower_bound(arr.begin(), arr.end(), target); // If 'it' is the beginning of the array, it means all elements are >= target, // or the array is empty if (it == arr.begin()) { return -1; // No element is strictly less than the target } // Decrement the iterator to point to the element immediately before // the first element greater than or equal to 'target'. This will be the // last element strictly less than 'target'. it--; return it - arr.begin(); } ```
# Graph Algorithms #### Graph Terms An undirected graph G is said to be **connected** if every pair of vertices in G is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called **disconnected**. G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. A graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected. A directed graph is called * **Weakly connected:** if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. * **Unilaterally connected:** if it contains a directed path from u to v OR a directed path from v to u for every pair of vertices u, v. * **Strongly connected:** if it contains a directed path from u to v AND a directed path from v to u for every pair of vertices u, v. * **Disconnected:** if replacing all of its directed edges with undirected edges produces a disconnected (undirected) graph. #### Important Graph Algorithms * BFS on a Tree * DFS on a Tree * BFS on a Graph * DFS on a Graph * Disconnected Graph * Connected Graph * Weakly connected * Unilaterally connected * Strongly connected * DFS on a Graph to detect cycle Shortest path algorithms * (Single pair of nodes) or (Single source node to all nodes) * Dijkstra => weighted graph (only positive weights) * E + Vlog(V) * Bellman Ford => weighted graph (can contain negative weights, can't contain negative cycle) * All pair of nodes (both directions) * Floyd warshall => weighted graph (can contain negative weights, can't contain negative cycle) * Topological Sort * Minimum Spanning Tree * Kruskel * Prim #### Trees * Binary Trees * BST (Binary Search Trees) * Balanced Trees * Min Heap, Max Heap * Segment Trees * Prefix Tree * Trie * Suffix Tree * Binary Indexed Tree * Dynamic Programming Problems * [Link](https://people.computing.clemson.edu/~bcdean/dp_practice) * Binary Search Problems * String Algorithms Problems * Union Find Problems * Sliding Window # Matrix to Graph ```cpp #include #include #include #include #include using namespace std; class Cell{ public: int i; int j; char val; Cell(){} Cell(int i, int j, char val): i(i), j(j), val(val){} string getKey(){ return getKey(i, j); } static string getKey(int i, int j){ return to_string(i) + "_" + to_string(j); } }; class Graph{ private: int M; int N; unordered_map nodes; unordered_map > outwardEdges; void addEdge(Cell* src, Cell* dst){ outwardEdges[src->getKey()].push_back(dst->getKey()); } Cell* getCell(int i, int j){ string cellKey = Cell::getKey(i, j); if(nodes.find(cellKey) == nodes.end()){ return NULL; } return nodes[cellKey]; } vector getAllCells(){ vector cells; for(auto kv : nodes) { cells.push_back(kv.second); } return cells; } void connectAdjacentCells(Cell* cell){ Cell* upCell = getCell(cell->i - 1, cell->j); Cell* downCell = getCell(cell->i + 1, cell->j); Cell* rightCell = getCell(cell->i, cell->j + 1); Cell* leftCell = getCell(cell->i, cell->j - 1); if(rightCell){ addEdge(cell, rightCell); } if(downCell){ addEdge(cell, downCell); } if(leftCell){ addEdge(cell, leftCell); } if(upCell){ addEdge(cell, upCell); } } void buildGraph(vector >& board){ M = board.size(); N = board[0].size(); for(int i=0; igetKey()] = cell; // initialise vector to store adjacent cells of a cell outwardEdges[cell->getKey()] = vector(); } } vector cells = getAllCells(); for(auto cell : cells){ connectAdjacentCells(cell); } } public: Graph(vector >& board){ buildGraph(board); } bool existInSet(unordered_set& set, string key){ return set.find(key) != set.end(); } bool searchUsingDfs(Cell* root, char c, unordered_set& visited){ cout << "visiting " << root->val << " (" << root->getKey() << ") " << endl; if(root->val == c){ return true; } visited.insert(root->getKey()); vector adjacentCellsKeys = outwardEdges[root->getKey()]; for(auto cellKey: adjacentCellsKeys){ if(!existInSet(visited, cellKey)){ bool exist = searchUsingDfs(nodes[cellKey], c, visited); if (exist) { return true; } } } return false; } bool search(char c){ Cell* root = getCell(0, 0); unordered_set visited; return searchUsingDfs(root, c, visited); } }; int main(){ vector > board = vector >{ vector{'a', 'q', 'c'}, vector{'d', 'n', 'f'}, vector{'k', 't', 'p'}, }; Graph g(board); bool result = g.search('k'); cout << "exist = " << result << endl; } ``` # Trie ```cpp #include #include #include using namespace std; const int ALPHABET_SIZE = 26; // trie node class TrieNode { public: vector children; bool isEndOfWord; // true means that the node represents end of a word TrieNode(){ children.resize(ALPHABET_SIZE); } }; // Returns new trie node (with all children initialized to NULLs) TrieNode* createNewNode() { TrieNode *node = new TrieNode(); node->isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++){ node->children[i] = NULL; } return node; } // If not present, inserts key into trie // If the key is prefix of trie node, just // marks leaf node void insert(TrieNode* root, string key) { TrieNode *itr = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!itr->children[index]){ TrieNode* newNode = createNewNode(); itr->children[index] = newNode; } itr = itr->children[index]; } // mark last node as leaf itr->isEndOfWord = true; } bool search(TrieNode* root, string key) { TrieNode* itr = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!itr->children[index]){ return false; } itr = itr->children[index]; } return (itr->isEndOfWord); } // Driver int main() { // Input keys (use only 'a' through 'z' and lower case) vector keys = {"the", "a", "there", "answer", "any", "by", "bye", "their" }; int n = keys.size(); TrieNode *root = createNewNode(); // Construct trie for (int i = 0; i < n; i++){ insert(root, keys[i]); } // Search for different keys cout << "the :: " << search(root, "the") << endl; cout << "these :: " << search(root, "these") << endl; cout << "their :: " << search(root, "their") << endl; cout << "thaw :: " << search(root, "thaw") << endl; return 0; } ``` # Dijkstra ```cpp /** * Dijkstra's algorithm. * In essence, Dijkstra's algorithm maintains two sets: one set of nodes whose * distance from source is NOT finalized, one set of nodes whose distance * from source IS finalized. * In implementation, we keep track of the two sets explicitly or implicitly. * * https://leetcode.com/problems/path-with-maximum-probability/solutions/732293/dijkstras-algorithm-implementation-c/ * */ #include #include #include #include using namespace std; // Helper functions vector>> buildGraph(int n, vector>& edges, vector& weights) { vector>> graph(n); for (int i = 0; i < edges.size(); i++) { vector edge = edges[i]; graph[edge[0]].push_back({edge[1], weights[i]}); graph[edge[1]].push_back({edge[0], weights[i]}); } return graph; } void printSolution(vector& dist) { printf("Vertex \tDistance from Source\n"); for (int i = 0; i < dist.size(); i++) printf(" %d \t\t\t %d\n", i, dist[i]); cout << "\n\n" << endl; } class Solution { public: vector getShortestPathsUsingDijkstraUsingPrioirityQueue(vector>>& graph, int src) { int n = graph.size(); vector dist(n, INT_MAX); auto comp = [](const pair& p1, const pair& p2) { // pair => this pair is different from pair in the graph. // This pair is an entry in the priority_queue return p1.first > p2.first; }; priority_queue, vector>, decltype(comp)> unfinalized(comp); dist[src] = 0; unfinalized.push({0, src}); while (!unfinalized.empty()) { int u = unfinalized.top().second; unfinalized.pop(); for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].first, weight = graph[u][i].second; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; unfinalized.push({dist[v], v}); } } } return dist; } }; int main() { Solution sol; int n = 9; vector> edges({{0, 1}, {0, 7}, {1, 2}, {1, 7}, {2, 3}, {2, 8}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {5, 6}, {6, 7}, {6, 8}, {7, 8}}); vector weights({4, 8, 8, 11, 7, 2, 4, 9, 14, 10, 2, 1, 6, 7}); vector>> graph = buildGraph(n, edges, weights); // adjacency list, with C++ priority_queue vector dist = sol.getShortestPathsUsingDijkstraUsingPrioirityQueue(graph, 0); printSolution(dist); } ``` # Database Transactions Often, a collection of several operations on the database appears to be a single unit from the point of view of the database user. For example, a transfer of funds from a checking account to a savings account is a single operation from the customer’s standpoint; within the database system, however, it consists of several operations. Clearly, it is essential that all these operations occur, or that, in case of a failure, none occur. It would be unacceptable if the checking account were debited but the savings account not credited. ## Transaction: ``` Collection of operations that form a single logical unit of work is called transaction. ``` A database system must ensure proper execution of transactions despite failures—either the entire transaction executes, or none of it does. Fur- thermore, it must manage concurrent execution of transactions in a way that avoids the introduction of inconsistency. In our funds-transfer example, a transaction computing the customer’s total balance might see the checking-account (account from which we are debiting) balance before it is debited by the funds-transfer transaction, but see the savings balance after it is credited. As a result, it would obtain an incorrect result. * **Atomicity:** It is important that either all actions of a transaction be executed completely, or, in case of some failure, partial effects of each incomplete transaction be un- done. This property is called atomicity. * **Durability:** Once a transaction is successfully executed, its effects must persist in the database system. A failure should not result in the database forgetting about a transaction that successfully completed. This property is called durability. Basically we have to transfer complete effect of transaction from computer memory to disk. * **Isolation:** In a database system where multiple transactions are executing concurrently, if updates to shared data are not controlled there is potential for transactions to see inconsistent intermediate states created by updates of other transactions. Such a situation can result in erroneous updates to data stored in the database. Thus, database systems must provide mechanisms to isolate transactions from the effects of other concurrently executing transactions. This property is called isolation. Formally speaking, the system guarantees that, for every pair of transactions **Ti** and **Tj** , it appears to **Ti** that either **Tj** finished execution before **Ti** started or **Tj** started execution after **Ti** finished.Thus,each transaction is unaware of other transactions executing concurrently in the system. * **Consistency:** The consistency property ensures that any transaction will bring the database from one valid state to another. Any data written to the database must be valid according to all defined rules, including constraints, cascades, triggers, and any combination thereof. This does not guarantee correctness of the transaction in all ways the application programmer might have wanted (that is the responsibility of application-level code), but merely that any programming errors cannot result in the violation of any defined rules. # A Simple Transaction Analysis **read(X):** which transfers the data item X from the database to a variable, also called X, in a buffer in main memory belonging to the transaction that executed the read operation. **write(X):** which transfers the value in the variable X in the main-memory buffer of the transaction that executed the write to the data item X in the database. > for now, we will assume that the write operation updates the database immediately. Real life case is not like this \ Let Ti be a transaction that transfers $50 from account A to B. This transaction can be defined as: **Ti =** ``` read(A); A := A − 50; write(A); read(B); B := B + 50; write(B); ``` ## Lets analyze ACID properties of this transaction: * **Consistency**: The consistency requirement here is that the sum of A and B be unchanged by the execution of the transaction. Without the consistency requirement, money could be created or destroyed by the transaction! It can be verified easily that, if the database is consistent before an execution of the transaction, the database remains consistent after the execution of the transaction. Ensuring consistency for an individual transaction is the responsibility of the application programmer who codes the transaction. This task may be facilitated by automatic testing of integrity constraints * **Atomicity**: We can easily see that if system(computer which is executing transaction) crashes just after write(A);, the database will end up in inconsistent state. Now there has to be a mechanism by database itself so that it brings back the database in consistent state. * The basic idea behind ensuring atomicity is this: The database system keeps track (on disk) of the old values of any data on which a transaction performs a write. This information is written to a file called the log. If the transaction does not complete its execution, the database system restores the old values from the log to make it appear as though the transaction never executed. We discuss these ideas further in Section 14.4. Ensuring atomicity is the responsibility of the database system; specifically, it is handled by a component of the database called the recovery system * **Durability**: We assume for now that a failure of the computer system may result in loss of data in main memory, but data written to disk are never lost. We can guarantee durability by ensuring that either: * The updates carried out by the transaction have been written to disk before the transaction is marked as complete. Information about the updates carried out by the transaction and written to disk is sufficient to enable the database to reconstruct the updates when the database system is restarted after the failure. The recovery system of the database is responsible for ensuring durability, in addition to ensuring atomicity. * **Isolation**: If several transactions, Ti, are executed concurrently, their operations may interleave in some undesirable way, resulting in an inconsistent state. e.g. account A has Rs. 100 initially. T1 transfers Rs. 20 from account B to A. At the same time, T2 transfers Rs. 50 from account C to A. Ideally final output should be Rs. 170 in account A. But consider this sequence:   T1 reads from account A in variable X.\   X = X + 20\   T2 reads from account A in variable Y.\   Y = Y + 50\   T1 writes from X to account A\   T2 writes from Y to account A
* The final output in this sequence will be Rs. 150. The total money drawn from the system (from account B and C) is Rs. 170. The total money added back to system after T1 and T2 are complete is Rs. 150. Hence inconsistent * Ensuring the isolation property is the responsibility of a component of the database system called the concurrency-control system. # Implementation of Isolation Levels ### Using different concurrency policies #### Policy 1: Locking Database * A transaction acquires a lock on the entire database before it starts and releases the lock after it has committed. * A concurrency-control policy such as this one leads to poor performance #### Policy 2: Locking accessed data items only * Instead of locking the entire database, a transaction could, instead, lock only those data items that it accesses. Under such a policy, the transaction must hold locks long enough to ensure serializability, but for a period short enough not to harm performance excessively. We can implement this using these techniques: * **Two Phase Locking with Two modes of locks** * Two Phase Locking: *First phase* where it acquires locks but does not release any, and a *Second phase* where the transaction releases locks but does not acquire any. * Two modes of locks: *Shared locks* are used when transactions are reading same data and *exclusive locks* are used when transactions are writing on same data. * **Using Timestamps** * assign each transaction a timestamp, typically when it begins * For each data item, the system keeps two timestamps: * the timestamp of the transaction which read it latest * the timestamp of the transaction which wrote over it latest * Timestamps are used to ensure that transactions access each data item in order of the transactions’ timestamps if their accesses conflict. When this is not possible, offending transactions are aborted and restarted with a new timestamp. * **Multiple Versions and Snapshot Isolation** * By maintaining more than one version of a data item, it is possible to allow a transaction to read an old version of a data item rather than a newer version written by an uncommitted transaction or by a transaction that should come later in the serialization order. There are a variety of multiversion concurrency- control techniques. One in particular, called snapshot isolation, is widely used in practice. * In snapshot isolation, we can imagine that each transaction is given its own version, or snapshot, of the database when it begins.4 It reads data from this private version and is thus isolated from the updates made by other transactions. Of course, in reality, the entire database is not copied. Multiple versions are kept only of those data items that are changed. If the transaction updates the database, that update appears only in its own version, not in the actual database itself. Information about these updates is saved so that, after making some checks, the updates can be applied to the “real” database when the transaction commits. # Isolation Levels There are various **concurrency-control policies** that we can use to ensure that, even when multiple transactions are executed concurrently, only acceptable schedules are generated, regardless of how the operating system time-shares resources (such as CPU time) among the transactions. The protocols required to ensure serializability may allow too little concurrency for certain applications. In these cases, weaker levels of consistency are used. The use of weaker levels of consistency places additional burdens on programmers for ensuring database correctness. So strictness of concurrency control policy reduces the extent of concurrency. So, according to our usecase, we can use less strict policies to get more concurrency. ## The isolation levels specified by the SQL standard are as follows: * **Serializable:** usually ensures serializable execution. This uses restrictions like we discussed in previous page. * **Repeatable read:** allows only committed data to be read and further requires that, between two reads of a data item by a transaction, no other transaction is allowed to update it. However, the transaction may not be serializable with respect to other transactions. For instance, when it is searching for data satisfying some conditions, a transaction may find some of the data inserted by a committed transaction, but may not find other data inserted by the same transaction. * **Read committed:** allows only committed data to be read, but does not require repeatable reads. For instance, between two reads of a data item by the transaction, another transaction may have updated the data item and committed. * **Read uncommitted:** allows uncommitted data to be read. It is the lowest isolation level allowed by SQL. All the isolation levels above additionally disallow **dirty writes**, that is, they disallow writes to a data item that has already been written by another transaction that has not yet committed or aborted. # Isolation ## Why do we need concurrent execution? * **Improved throughput and resource utilization:** A transaction consists of many steps. Some involve I/O activity; others involve CPU activity. The CPU and the disks in a computer system can operate in parallel. Therefore, I/O activity can be done in parallel with processing at the CPU. The parallelism of the CPU and the I/O system can therefore be exploited to run multiple transactions in parallel. While a read or write on behalf of one transaction is in progress on one disk, another transaction can be running in the CPU, while another disk may be executing a read or write on behalf of a third transaction. All of this increases the **throughput** of the system—that is, the number of transactions executed in a given amount of time. Correspondingly, the **processor and disk utilization** also increase; in other words, the processor and disk spend less time idle, or not performing any useful work. * **Reduced waiting time:** There may be a mix of transactions running on a system, some short and some long. If transactions run serially, a short transaction may have to wait for a preceding long transaction to complete, which can lead to unpredictable delays in running a transaction. If the transactions are operating on different parts of the database, it is better to let them run concurrently, sharing the CPU cycles and disk accesses among them. Concurrent execution reduces the unpredictable delays in running transactions. Moreover, it also reduces the **average response time**: the average time for a transaction to be completed after it has been submitted. > Concurrency: CPU is switching between transactions while executing them.\ > Higher degree of concurrency =>
> > * Pros: more processor and disk utilization, more throughput, less average response time > * Cons: can lead database to inconsistent state if concurrency control policies are not used ## Concurrency Control If every transaction has the property that it maintains database consistency if executed alone, then serializability ensures that concurrent executions maintain consistency. The concurrency-control component of the database system ensure that any schedule that is executed will leave the database in a consistent state. * A transaction is composed of sequence of instructions. * If two transactions run concurrently (i.e. CPU is switching between transactions while executing them), their instructions will get interleaved. * The sequence of instructions written in chronological order in which they are executed in the system is called **schedule**. * A schedule will be called a **serial schedule** if it consists of a sequence of instructions from various transactions, where the instructions belonging to one single transaction appear together in that schedule. * If a schedule S, in some sense, is equivalent to some **serial schedule** Y, than we say that schedule S is a serializable schedule. ## How to determine if a schedule is serializable Equivalence can have multiple meanings. Here we will focus on conflict equivalence. Consider two instructions I (from transaction T1) and J (from transaction T2) * If I and J are operating on different data, their order of execution does not matter. * If I and J are both operating on same data but both are read instruction, their order of execution doesn't matter. * If I and J are both operating on same data and at least one of them is a 'write' instruction, then their order does matter. We say that I and J **conflict** if they are ``` i) operations by different transactions ii) on the same data item, iii) and at least one of these instructions is a write operation ``` otherwise they are nonconflicting instructions (both read instruction or both operating on different data) If a schedule S can be transformed into a schedule S′ by a series of swaps of nonconflicting instructions, we say that S and S′ are **conflict equivalent** A schedule S is **conflict serializable** if it is conflict equivalent to a serial schedule. \
We now present a simple and efficient method for determining conflict serializability of a schedule. Consider a schedule S. We construct a directed graph G, called a **precedence graph**, using S. The set of vertices (N1, N2, etc) represents all the transactions (T1, T2, etc) participating in the schedule. The set of edges consists of all edges Ni → Nj for which one of three conditions holds: * Some instruction in Ti executes write(Q) before Some instruction in Tj executes read(Q). * Some instruction in Ti executes read(Q) before Some instruction in Tj executes write(Q). * Some instruction in Ti executes write(Q) before Some instruction in Tj executes write(Q). > Note: It is not *"just" before*. If an edge Ni → Nj exists in the precedence graph, then, in any serial schedule S′ equivalent to S, Ti must appear before Tj. If the precedence graph for S has a cycle, then schedule S is not conflict serializable. If the graph contains no cycles, then the schedule S is conflict serializable. A **serializability order** of the transactions can be obtained using topologically sorting of precedence graph. ## Recoverable Schedules Consider the partial schedule 9, in which T7 is a transaction that performs only one instruction: read(A). We call this a **partial schedule** because we have not included a commit or abort operation for T6. Notice that T7 commits immediately after executing the read(A) instruction. Thus, T7 commits while T6 is still in the active state. Now suppose that T6 fails before it commits. T7 has read the value of data item A written by T6. Therefore, we say that T7 is **dependent** on T6. Because of this, we must abort T7 to ensure atomicity. However, T7 has already committed and cannot be aborted. Thus, we have a situation where it is impossible to recover correctly from the failure of T6. Schedule 9 is an example of a *nonrecoverable schedule*. A **recoverable schedule** is one where, for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti , the commit operation of Ti appears before the commit operation of Tj . For the example of schedule 9 to be recoverable, T7 would have to delay committing until after T6 commits. ## Cascadeless Schedules Even if a schedule is recoverable, to recover correctly from the failure of a transaction Ti , we may have to roll back several transactions. Such situations occur if transactions have read data written by Ti . As an illustration, consider the partial schedule 10. Transaction T8 writes a value of A that is read by transaction T9. Transaction T9 writes a value of A that is read by transaction T10. Suppose that, at this point, T8 fails. T8 must be rolled back. Since T9 is dependent on T8, T9 must be rolled back. Since T10 is dependent on T9, T10 must be rolled back. This phenomenon, in which a single transaction failure leads to a series of transaction rollbacks, is called **cascading rollback**. Cascading rollback is undesirable, since it leads to the undoing of a significant amount of work. It is desirable to restrict the schedules to those where cascading rollbacks cannot occur. Such schedules are called **cascadeless schedules**. Formally, a cascadeless schedule is one where, for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti , the commit operation of Ti appears before the read operation of Tj . It is easy to verify that every cascadeless schedule is also recoverable. # Storage Types * **Volatile storage:** Information residing in volatile storage does not usually survive system crashes. Examples of such storage are main memory and cache memory. Access to volatile storage is extremely fast, both because of the speed of the memory access itself, and because it is possible to access any data item in volatile storage directly. * **Nonvolatile storage:** Information residing in nonvolatile storage survives system crashes. Examples of nonvolatile storage include secondary storage devices such as magnetic disk and flash storage, used for online storage, and tertiary storage devices such as optical media, and magnetic tapes, used for archival storage. At the current state of technology, nonvolatile storage is slower than volatile storage, particularly for random access. Both secondary and tertiary storage devices, however, are susceptible to failure which may result in loss of information. * **Stable storage:** Information residing in stable storage is never lost (never should be taken with a grain of salt, since theoretically never cannot be guaranteed—for example, it is possible, although extremely unlikely, that a black hole may envelop the earth and permanently destroy all data!). Al- though stable storage is theoretically impossible to obtain, it can be closely approximated by techniques that make data loss extremely unlikely. To implement stable storage, we replicate the information in several nonvolatile storage media (usually disk) with independent failure modes. Updates must be done with care to ensure that a failure during an update to stable storage does not cause a loss of information. # Transaction Atomicity and Durability A transaction may not always complete its execution successfully. Such a transaction is termed **aborted**. If we are to ensure the atomicity property, an aborted transaction must have no effect on the state of the database. Thus, any changes that the aborted transaction made to the database must be undone. Once the changes caused by an aborted transaction have been undone, we say that the transaction has been **rolled back** It is part of the responsibility of the recovery scheme to manage transaction aborts. This is done typically by maintaining a log. Each database modification made by a transaction is first recorded in the log. We record the identifier of the transaction performing the modification, the identifier of the data item being modified, and both the old value (prior to modification) and the new value (after modification) of the data item. Only then is the database itself modified. Maintaining a log provides the possibility of redo- ing a modification to ensure atomicity and durability as well as the possibility of undoing a modification to ensure atomicity in case of a failure during transaction execution. A transaction that completes its execution successfully is said to be committed. A committed transaction that has performed updates transforms the database into a new consistent state, which must persist even if there is a system failure. Once a transaction has committed, we cannot undo its effects by aborting it. The only way to undo the effects of a committed transaction is to execute a **compensating transaction**. ## A transaction must be in one of the following states: * **Active**: the initial state; the transaction stays in this state while it is executing. * **Partially committed**: after the final statement has been executed. * **Failed**: after the discovery that normal execution can no longer proceed. * **Aborted**: after the transaction has been rolled back and the database has been restored to its state prior to the start of the transaction. * **Committed**: after successful completion. we say that a transaction has aborted only if it has entered the aborted state. A transaction is said to have **terminated** if it has either committed or aborted. A transaction starts in the active state. When it finishes its final statement, it enters the partially committed state. At this point, the transaction has completed its execution, but it is still possible that it may have to be aborted, since the actual output may still be temporarily residing in main memory, and thus a hardware failure may preclude its successful completion. The database system then writes out enough information to disk that, even in the event of a failure, the updates performed by the transaction can be re-created when the system restarts after the failure. When the last of this information is written out, the transaction enters the committed state. # Java #### What is Java? Java is a popular programming language, created in 1995. It is owned by Oracle, and more than 3 billion devices run Java. #### It is used for: * Mobile applications (specially Android apps) * Desktop applications * Web applications * Web servers and application servers * Games * Database connection * And much, much more! # Important Questions ### What is bytecode ? Every Java program is first compiled into an intermediate language called Java bytecode. Java applications must be capable of executing on a variety of hardware architectures and operating systems. To accommodate this, the Java Compiler (javac) generates bytecodes-- *an architecture neutral intermediate format designed to transport code efficiently to multiple hardware and software platforms*. ### What is difference between Assembly Code and ByteCode ? Assembly code means the human readable form of a machine code. Byte code on the other hand is normaly a language that can be interpreted by a byte code interpreter -- so it is not the processors native language. ### What is JVM and do we have different JVM for different environment ? A Java virtual machine (JVM) is an **abstract** computing machine that enables a computer to run a Java program. There are three notions of the JVM: specification, implementation, and instance. * The specification is a document that formally describes what is required of a JVM implementation. Having a single specification ensures all implementations are interoperable. * A JVM implementation is a computer program that meets the requirements of the JVM specification. * An instance of a JVM is an implementation running in a process that executes a computer program compiled into Java bytecode. JVM is not platform independent, thats why you have different JVM for different operating systems. The JVM is used primarily for 2 things: * Translate the bytecode into the machine language for a particular computer * Actually execute the corresponding machine-language instructions as well. The JVM and bytecode combined give Java its status as a "portable" language – this is because Java bytecode can be transferred from one machine to another. # Spring MVC #### What is a bean ? Spring IoC container uses a **configuration metadata** (which is provided in the form of an xml file or using annotations) to instantiate **objects**, which are used by our java application. These objects are called bean. **configuration metadata** contains following properties and their value: * class : which java class to use to instantiate object * name: unique id/name that will be used to request this bean * scope, constructor-arg, properties, autowiring mode, lazy-initialization mode, initialization method, destruction method etc. # Program execution ## General concepts * Code * Translation * Compiler * Optimizing compiler * Intermediate representation (IR) * Execution * Runtime system * Executable * Interpreter * Virtual machine ## Types of code * Source code * Object code * Bytecode * Machine code * Microcode ## Compilation strategies * Just-in-time (JIT) * Tracing just-in-time * Ahead-of-time (AOT) * Transcompilation * Recompilation ## Notable [runtimes](https://github.com/gomchikbhoka/blogs/tree/c21b011e5bbbf41649b1466e37a9e9d2a22defab/Program%20execution/runtimes.html) * Android Runtime (ART) * Common Language Runtime (CLR) * crt0 * Java virtual machine (JVM) * [Node.js](https://github.com/gomchikbhoka/blogs/tree/c21b011e5bbbf41649b1466e37a9e9d2a22defab/Program%20execution/nodejs.html) * Zend Engine ## Notable compilers & toolchains * GNU Compiler Collection (GCC) * LLVM # Node.js ## {% center %} Node.js {% endcenter %} ## What is Node.js? It is a C++ program which takes in input a javascript code and executes it with a speciality that it doesn't block on I/O requests. It is called javaScript [runtime system](https://github.com/gomchikbhoka/blogs/tree/c21b011e5bbbf41649b1466e37a9e9d2a22defab/Program%20execution/runtimes.html) because it is a program that performs core or essential function for running javascript programs on system. Node.js combined * V8 JavaScript engine code (which was already written in c++) * libuv, a *multi-platform support library* with a focus on evented I/O. It is a C library that implements the Node.js event loop and all of the asynchronous behaviors of the platform You can develop any type of application on Node. e.g. * a program which prints fibonacci series * a chat application * a compiler * etc. etc. A subset of those will be server applications (like FTP server, video streaming server etc.), and then a subset of that will be web server applications. The most commonly used web server on Node is **Express**. ### I/O examples: * database I/O * console I/O * socket I/O, like waiting for an http request on some port, sending reponse to an http request, making network request to some other server etc. ### Chrome V8 engine The Chrome V8 engine is responsible for executing JavaScript code. It can actually be embedded into a C++ application which is what Node.js is at its core. The V8 engine takes in JavaScript as a string and executes it. When Node.js c++ code starts executing, * it initializes the event loop, * then processes the provided input script (using v8 engine code) which may make async API calls, schedule timers, or call process.nextTick() and * then begins processing the event loop. Important Resources: * **(Must read)** [How node.js event loop works](https://nodejs.org/en/docs/guides/event-loop-timers-and-nexttick/) * [Understanding the node.js event loop ](http://blog.mixu.net/2011/02/01/understanding-the-node-js-event-loop/) * [Presentation on node.js](https://www.youtube.com/watch?v=M-sc73Y-zQA) by Ryan Dahl, creator of nodejs ### Apache vs Nginx/Node.js Apache is multithreaded: it spawns a thread per request (or process, it depends on the conf). The overhead for each thread/process eats up memory as the number of concurrent connections increases and more threads are needed to serve multiple simulataneous clients. Nginx and Node.js are not multithreaded, because threads and processes carry a heavy memory cost. They are single-threaded, but event-based. This eliminates the overhead created by thousands of threads/processes by handling many connections in a single thread. **How is node.js inherently memory efficient and faster when it still relies on threads internally ?** * **memory efficient:** the actual threads are all contained at a fairly low level, and thus remain constrained in size and number. The catch is that Asynchronous I/O, when properly implemented at kernel level, does not use threads while performing async I/O operations. Instead the calling thread is released as soon as an I/O operation is started and a callback is executed when the I/O operation is finished and a thread is available for it. So node.js can run 50 concurrent requests with 50 I/O operations in (almost) parallel using just one thread if the async support for the I/O operations is properly implemented * **faster:** OS-level "switching" via select() is faster than thread context swaps. * [Stackoverflow discussion](https://stackoverflow.com/questions/3629784/how-is-node-js-inherently-faster-when-it-still-relies-on-threads-internally) ### Is it apt to compare Tomcat and Node.js ? No, we should compare * JVM vs. V8+Node * Java vs. Javascript * and Tomcat vs. Express ### Key points * Node.js increased CPU utilization by using asynchronous I/O. CPU is able to do other work while I/O is happening. * Node.js does not blow up memory like apache when there are huge number of connections concurrently because it is not creating a thread per connection. * Node.js is fast as OS-level "switching" via select() is faster than thread context swaps. * Node.js is not good for CPU intensive tasks. Better use something like apache for such tasks as they would take advantage of multiple cores/processors. # Runtimes * **What is a Runtime ?** It's a generally used term for **runtime system**. runtime (= runtime system) is different from "Run time". * **What is a Run time ?** Run time is a phase of a computer program in which the program is run or executed on a computer system. Run time is part of the program life cycle, and it describes the time between when the program begins running within the memory until it is terminated or closed by the user or the operating system. Run time is also known as execution time. * **What is a Runtime System ?** A runtime system is an **engine** that *generally* performs these functions for other programs * Garbage collection * Stream input/output * Structured input/output * Process suspension * Operating System Calls * Handling interrupts and asynchronous events * Handling arithmetic exceptions * Assembly language implementation of language primitives * Foreign language procedure calls * Execution profiling * Debugging For nice detailed perspective, you should read [this paper](https://firebasestorage.googleapis.com/v0/b/project-8410974076296794045.appspot.com/o/A-Runtime-System.pdf?alt=media\&token=e265eb05-4a42-4961-9332-4115a6dcf870) by Andrew D Appel: * **What is an engine ?** In computer programming, an engine is a program that performs a core or essential function for other programs. Engines are used in operating systems, subsystems or application programs to coordinate the overall operation of other programs. The engine must be running in the computer in order for those other programs to use its functions. * **What is a Runtime Library:** The runtime library is primarily the software/programming component of a runtime system. Typically, it consists of many different programs or functions that are commonly used in various programs. These include I/O routines, graphical functions, mathematical functions and more. The runtime library is invoked in all programs. At program runtime, the respective runtime library or function is loaded in the memory until the primary program has finished execution or no longer requires that function. * **What is a Runtime Environment:** Runtime environment is a state of the target machine, which may include the environment variables, CPU registers, memory resources, operating system, **runtime systems** and system software required by a particular category of applications. Distinguish this from Development Environments and Build Environments: * **Run time environment**: Everything you need to execute a program, but no tools to change it. * **Build environment:** Given some code written by someone, everything you need to compile it or otherwise prepare an executable that you put into a Run time environment. Build environments are pretty useless unless you can see tests what you have built, so they often include Run too. In Build you can't actually modify the code. * **Development environment:** Everything you need to write code, build it and test it. Code Editors and other such tools. Typically also includes Build and Run. # System Design A sound understanding of storage scalability is really important if you intend to interview for a senior backend engineer or a senior infrastructure engineer role. We try to walk you through some of these problems here to set a tone around how to approach these problems. Do note that no design is correct or wrong. There are just good designs and bad designs which heavily depend on the use case. Hence, it is extremely important to clarify the requirements for the problem asked. # Basic Terminologies ## We try to explain some of the terminologies in simple words. * **Replication:** Replication refers to frequently copying the data across multiple machines. Post replication, multiple copies of the data exists across machines. This might help in case one or more of the machines die due to some failure. * **Consistency:** Assuming you have a storage system which has more than one machine, consistency implies that the data is same across the cluster, so you can read or write to/from any node and get the same data. * **Eventual consistency :** Exactly what the name suggests. In a cluster, if multiple machines store the same data, an eventual consistent model implies that all machines will have the same data eventually. Its possible that at a given instance, those machines have different versions of the same data ( temporarily inconsistent ) but they will eventually reach a state where they have the same data. Availability: In the context of a database cluster, Availability refers to the ability to always respond to queries ( read or write ) irrespective of nodes going down. * **Partition Tolerance:** In the context of a database cluster, cluster continues to function even if there is a “partition” (communications break) between two nodes (both nodes are up, but can’t communicate). * **Vertical scaling and Horizontal scaling:** In simple terms, to scale horizontally is adding more servers. To scale vertically is to increase the resources of the server ( RAM, CPU, storage, etc. ). Example: Lets say you own a restaurant which is now exceeding its seating capacity. One way of accomodating more people ( scaling ) would be to add more and more chairs (scaling vertically). However since the space is limited, you won’t be able to add more chairs once the space is full. Another way of scaling would be to open new branches of the restaurant ( horizontal scaling ). Source : * **Sharding:** With most huge systems, data does not fit on a single machine. In such cases, sharding refers to splitting the very large database into smaller, faster and more manageable parts called data shards. # CAP Theorem CAP Theorem states that in a distributed system, it is impossible to simultaneously guarantee all of the following: * Consistency * Availability * Partition Tolerance does an awesome job of explaining it in simple english. # Normalization of Database Normalization is a systematic approach of decomposing tables to * minimize data redundancy and * minimize undesirable characteristics like Insertion, Update and Deletion Anomalies ## Lets start with an example: Here we can see that Student Info (his rollno and name) and Branch Info (branch-name, hod, office-tel) are unnecessarily put in same table. Wherever in a row we mention branch CSE, we have to put hod to Mr. X and office-tel to 53337 as well. Here we can see that two independent table are unnecessarily mingled into one causing data redundancy. ## Now lets understand the anomalies part. * **Insertion Anomaly:** whenever we enter a new student entry (rollno and name), we have two options: * We put NULL for (branch-name, hod and office-tel) whenever we do not have student branch's info while we are writing to table. This is not an appropriate information about the student's branch. * We make it compulsory that we have student branch's info whenever we write to this table. Having such compulsion is not good. * **Update Anomaly:** Suppose we have to update the Hod for CSE branch (Mr.X -> Mr.Y). We have to update all the rows where student belongs to CSE branch. You can see the problem there. * **Deletion Anomaly:** Suppose there is an entry of a student who belongs to ECE branch. There's only one such entry (No other student with ECE branch). Now if we remove that student from list, we also lose information about ECE branch in the process. SO bad :( ## Normalization rules are divided into following normal form: * First Normal Form * Second Normal Form * Third Normal Form * BCNF **First Normal Form** * each column must contain atomic values (i.e no multiple things in one cell). * a column should contain values of same type * each column's name should be unique * order in which data is saved doesn't matter **Second Normal Form** * table must satisfy first-normal-form rules * there must **not be any partial dependency** of any column on primary key. * It means that for a table that has concatenated primary key, each column in the table that is not part of the primary key must depend upon the entire concatenated key for its existence. If any column depends only on one part of the concatenated key, then the table fails Second normal form. * it helps in reducing Update Anomalies > Note: primary key can be a group of columns. **Third Normal Form** * table must satisfy second-normal-form rules * it requires that every non-prime attribute of table must be dependent on primary key, or we can say that, there should not be the case that a non-prime attribute is determined by another non-prime attribute. So this transitive functional dependency should be removed from the table. * For example, consider a table with following fields. In this table Student\_id is Primary key, but street, city and state depends upon Zip. The dependency between zip and other fields is called transitive dependency. Hence to apply 3NF, we need to move the street, city and state to new table, with Zip as primary key. **The advantage of removing transitive dependency is:** * Amount of data duplication is reduced. * Data integrity achieved. **BCNF** # Useful Reads * **System Design Introduction By Tushar Roy** * * **Master Slave:** * * **Real life example of scaling using MySQL:** * * **Paxos** * # Asset Classes * An asset class is a grouping of investments that exhibit similar characteristics and are subject to the same laws and regulations. * Equities (e.g., stocks), fixed income (e.g., bonds), cash and cash equivalents, real estate, commodities, and currencies are common examples of asset classes. * There is usually very little correlation and in some cases a negative correlation, between different asset classes. * Financial advisors focus on asset class as a way to help investors diversify their portfolios. # Equity instruments ### Equity asset class The equity asset class in India refers to investments in stocks, or shares, of companies listed on Indian stock exchanges, such as the Bombay Stock Exchange (BSE) and the National Stock Exchange of India (NSE). Investing in the equity asset class involves buying shares in a company with the expectation that the company will perform well and the value of the shares will increase over time. This can be a more risky investment than the debt asset class, as the value of equities can fluctuate significantly due to changes in the company's performance, market conditions, and other factors. However, investing in equities can also offer the potential for higher returns over the long term. Many investors in India, including individuals, mutual funds, and pension funds, choose to include some level of equity exposure in their portfolios to help diversify their risk and potentially achieve higher returns. # Debt instruments ### Fixed income asset class The fixed-income asset class refers to investments in fixed-income securities such as FD, bonds, treasury bills etc. These investments are issued by the Banks, Indian government, Corporates, Financial institutions etc. The Reserve Bank of India (RBI) is the central bank of India and plays a key role in regulating the country's debt markets. It sets monetary policy, including the benchmark interest rate, and issues government securities, including treasury bills and bonds. Corporations and financial institutions in India also issue debt securities to raise capital. These may include commercial paper, certificates of deposit, and corporate bonds. Investors in the debt asset class in India may include banks, insurance companies, pension funds, and individual investors. They may be attracted to the stability and income potential of these investments, as well as the relative safety of investing in high-quality issuers with strong credit ratings. However, as with any investment, there are risks to consider. * Treasury bills (T-bills) are short-term fixed-income securities that mature within one year that do not pay coupon returns. Investors buy the bill at a price less than its face value and investors earn that difference at maturity. * Treasury notes (T-notes) come in maturities between two and 10 years, pay a fixed interest rate, and are sold in multiples of $100. At the end of maturity, investors are repaid the principal but earn semiannual interest payments until maturity. * Treasury bonds (T-bonds) are similar to the T-note except that it matures in 20 or 30 years. Treasury bonds can be purchased in multiples of $100. * Treasury Inflation-Protected Securities (TIPS) protect investors from inflation. The principal amount of a TIPS bond adjusts with inflation and deflation. * A municipal bond is similar to a Treasury since it is government-issued, except it is issued and backed by a state, municipality, or county, instead of the federal government, and is used to raise capital to finance local expenditures. Muni bonds can have tax-free benefits to investors as well. * Corporate bonds come in various types, and the price and interest rate offered largely depend on the company’s financial stability and its creditworthiness. Bonds with higher credit ratings typically pay lower coupon rates. * Junk bonds—also called high-yield bonds—are corporate issues that pay a greater coupon due to the higher risk of default. Default is when a company fails to pay back the principal and interest on a bond or debt security. * A certificate of deposit (CD) is a fixed income vehicle offered by financial institutions with maturities of less than five years. The rate is higher than a typical saving account, and CDs carry FDIC or National Credit Union Administration (NCUA) protection There are several types of risk that investors in the debt asset class should be aware of: * **Credit risk:** This is the risk that the borrower (of money) will default on their debt payments. It is higher for bonds issued by lower credit-rated borrowers and lower for bonds issued by higher credit-rated borrowers. * **Interest rate risk:** This is the risk that increase in interest rates \[\[ which the borrower (e.g. bank as borrower) offers to the depositor/lender (e.g a person who is depositing money in the bank) OR which the lender (e.g. bank as a lender) charges to the borrower (e.g a person who is taking loan from bank) ]] will affect the value of a bond. When interest rates rise, people (with money) will be attracted more towards other investment options as those options are now offering better interest rates as compared to their earlier self and at the same time they have same liquidity and risk as their earlier self. So the value of bonds (which you hold) falls. Fewer people will prefer to buy these bonds from you at discounted rate if you wish to sell it now. * **Inflation risk:** This is the risk that inflation will erode the purchasing power of the bond's future cash flows. Inflation-protected bonds, such as Treasury Inflation-Protected Securities (TIPS), can help mitigate this risk. * **Liquidity risk:** This is the risk that the bond will be difficult to sell at a reasonable price in the secondary market, especially during times of market stress. * **Reinvestment risk:** Reinvestment risk is the risk that an investor will not be able to reinvest the bond's future cash flows at the same interest rate, leading to a lower overall return. For example, suppose an investor buys a bond with a 5% coupon rate. The investor receives interest payments of 5% of the bond's principal every year. If the investor reinvests these payments at a rate of 5%, they will earn the same return on their investment each year. However, if interest rates fall and the investor is only able to reinvest the payments at a rate of 3%, the investor will earn a lower return on their investment. Reinvestment risk is particularly relevant for investors in long-term bonds, as they will have more cash flows to reinvest over a longer period of time. It can also be an issue for investors in bond funds, as the fund may need to continuously reinvest the proceeds from maturing bonds into new ones with lower interest rates. * **Event risk:** This is the risk that a specific event, such as a natural disaster or a change in government policy, will negatively impact the bond-issuer's ability to make debt payments.