Interesting Properties of Data Structures

1. The stack data structure can come in handy here in representing this recursive structure of the problem. We can't really process this from the inside out because we don't have an idea about the overall structure. But, the stack can help us process this recursively i.e. from outside to inwards.

2. The capability of finding matching prefix is where the data structure called Trie would shine, comparing the hashset data structure. Not only can Trie tell the membership of a word, but also it can instantly find the words that share a given prefix. As it turns out, the choice of data structure (Trie VS. hashset), which could end with a solution that ranks either the top 5\%5% or the bottom 5\%5%.

Below are the Big O performance of common functions of different Java Collections.

List                 | Add  | Remove | Get  | Contains | Next | Data Structure

---------------------|------|--------|------|----------|------|---------------

ArrayList            | O(1) |  O(n)  | O(1) |   O(n)   | O(1) | Array

LinkedList           | O(1) |  O(1)  | O(n) |   O(n)   | O(1) | Linked List

CopyOnWriteArrayList | O(n) |  O(n)  | O(1) |   O(n)   | O(1) | Array

Set                   |    Add   |  Remove  | Contains |   Next   | Size | Data Structure

----------------------|----------|----------|----------|----------|------|-------------------------

HashSet               | O(1)     | O(1)     | O(1)     | O(h/n)   | O(1) | Hash Table

LinkedHashSet         | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Hash Table + Linked List

EnumSet               | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Bit Vector

TreeSet               | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree

CopyOnWriteArraySet   | O(n)     | O(n)     | O(n)     | O(1)     | O(1) | Array

ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1)     | O(n) | Skip List

Queue                   |  Offer   | Peak |   Poll   | Remove | Size | Data Structure

------------------------|----------|------|----------|--------|------|---------------

PriorityQueue           | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap

LinkedList              | O(1)     | O(1) | O(1)     |  O(1)  | O(1) | Array

ArrayDequeue            | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List

ConcurrentLinkedQueue   | O(1)     | O(1) | O(1)     |  O(n)  | O(n) | Linked List

ArrayBlockingQueue      | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Array

PriorirityBlockingQueue | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap

SynchronousQueue        | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | None!

DelayQueue              | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap

LinkedBlockingQueue     | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List

Map                   |   Get    | ContainsKey |   Next   | Data Structure

----------------------|----------|-------------|----------|-------------------------

HashMap               | O(1)     |   O(1)      | O(h / n) | Hash Table

LinkedHashMap         | O(1)     |   O(1)      | O(1)     | Hash Table + Linked List

IdentityHashMap       | O(1)     |   O(1)      | O(h / n) | Array

WeakHashMap           | O(1)     |   O(1)      | O(h / n) | Hash Table

EnumMap               | O(1)     |   O(1)      | O(1)     | Array

TreeMap               | O(log n) |   O(log n)  | O(log n) | Red-black tree

ConcurrentHashMap     | O(1)     |   O(1)      | O(h / n) | Hash Tables

ConcurrentSkipListMap | O(log n) |   O(log n)  | O(1)     | Skip List

Ref : https://gist.github.com/psayre23/c30a821239f4818b0709

Designing Data Intensive Application | Notes 1 | Introduction

Data-intensive applications are pushing the boundaries of what is possible by making use of these technological developments. We call an application data-intensive if data is its primary challenge—the quantity of data, the complexity of data, or the speed at which it is changing—as opposed to compute-intensive, where CPU cycles are the bottleneck

The tools and technologies that help data-intensive applications store and process data have been rapidly adapting to these changes. New types of database systems (“NoSQL”) have been getting lots of attention, but message queues, caches, search indexes, frameworks for batch and stream processing, and related technologies are very important too. Many applications use some combination of these.

Sometimes, when discussing scalable data systems, people make comments along the lines of, “You’re not Google or Amazon. Stop worrying about scale and just use a relational database.” There is truth in that statement: building for scale that you don’t need is wasted effort and may lock you into an inflexible design. In effect, it is a form of premature optimization. However, it’s also important to choose the right tool for the job, and different technologies each have their own strengths and weaknesses. As we shall see, relational databases are important but not the final word on dealing with data.

Ref:https://github.com/ept/ddia-references

This book is arranged into three parts:

In Part I, we discuss the fundamental ideas that underpin the design ofdata-intensive applications. We start in Chapter 1 by discussing what we’re actuallytrying to achieve: reliability, scalability, and maintainability; how we need to think aboutthem; and how we can achieve them. In Chapter 2 we compare several different datamodels and query languages, and see how they are appropriate to different situations. InChapter 3 we talk about storage engines: how databases arrange data on disk so that wecan find it again efficiently. Chapter 4 turns to formats for data encoding (serialization)and evolution of schemas over time.

In Part II, we move from data stored on one machine to data that isdistributed across multiple machines. This is often necessary for scalability, but brings with ita variety of unique challenges. We first discuss replication (Chapter 5),partitioning/sharding (Chapter 6), and transactions (Chapter 7). We thengo into more detail on the problems with distributed systems (Chapter 8) and what itmeans to achieve consistency and consensus in a distributed system (Chapter 9).

In Part III, we discuss systems that derive some datasets from other datasets. Deriveddata often occurs in heterogeneous systems: when there is no one database that can do everythingwell, applications need to integrate several different databases, caches, indexes, and so on. InChapter 10 we start with a batch processing approach to derived data, and we build upon it with stream processing in Chapter 11. Finally, in Chapter 12 we put everythingtogether and discuss approaches for building reliable, scalable, and maintainable applications inthe future.