Categories
System

System Design (Draft Post)

Classical Design Patterns Consistency Basics of Distributed Systems How databases work Message queueing Performance Applicability Scalability Reliability How do you design a messaging service? How do you design a database system? How do you design a scalable hashtagging system? Spend 30-40 minutes on each problem. Spend a certain time on each aspect for example to […]

Categories
Essays

Entrepreneurship = Selling Vision ?

What does it take for the creative leaders and entrepreneurs to manage money, people, investment, resources, and manage so many aspects to make big dreams come to reality. Why do people trust their vision? Why do people sign up thinking the cause is worth their effort?

Categories
Algorithms OMSCS

Artificial Neural Network: Perceptron Training

There could be two types of training algorithms for the weights for a neuron. First is to minimize the error between predicted y_hat and y. Here y_hat = boolean(activation >= threshold). This type of perceptron-based learning works best for linearly separable data and guarantees finite iterations. Second type is Gradient Descent algorithm which minimizes the […]

Categories
Algorithms

Properties of Tree

Quoting from Dasgupta, Papadimitrou, and Vazirani textbook: “Trees A tree is an undirected graph that is connected and acyclic.” p.135 Trees have these properties, quoting from DPV again: A tree on n nodes has n − 1 edges Any connected, undirected graph G = (V, E) with |E| = |V| − 1 is a tree. […]

Categories
Algorithms

Detect Cycle in a Directed Graph

A directed graph without any cycle is a Directed Acyclic Graph (DAG). If there is a cycle, then there will be a back edge, which goes backwards. For such edge(u,v), postorder number for u will be smaller than that of v, i.e. post(u) < post(v). So after DFS, if any edge satisfies post(u) < post(v) […]

Categories
Algorithms

Connected Components in Graphs

There can be three types of graphs here. 1. Undirected Graph For undirected graphs, we can use Depth First Search (DFS) to find the connected component number for each vertex. The runtime is O(|V|+|E|). 2. Directed Graph Directed graphs can be of two types. Directed Acyclic Graphs (DAG) and General Directed Graphs. DAGs’s do not […]

Categories
Algorithms

Topologically Sorting a DAG

In Directed Acyclic Graphs (DAG), there are no cycles. So it is simple to find the connected components just by sorting the vertices by post-order visit number in decreasing order after one run of DFS. The run time for DFS is again O(|V|+|E|)

Categories
Essays

The Idea to Discover a Business Idea

To find a viable business idea, one needs to delve into one domain of life. Over time, deficiencies in the current status quo becomes visible and opportunities to offer a drastically better solution presents itself. If it does not happen, one needs to seek into a different domain. There is a great essay by YCombinator […]

Categories
Algorithms

Finding x in an Infinite Array

This is a programming problem where the given array A is of infinite length and we have to find the position of a value x in it. The first n values are sorted and after n-th number, all remaining values in the array are None. For example: A= [1, 3, 5, 100, 102, 1050, 1061, […]

Categories
Uncategorized

Quotes

“The more you sweat in peace, the less you bleed in war” “Too bad! Same old story! Once you’ve finished building your house you notice you’ve accidentally learned something that you really should have known—before you started.”– Friedrich Nietzsche, Beyond Good and Evil “if you don’t know where you are going you’ll end up someplace else”