System Design Problems

| Comments

Unique User ID

Design a system to generate unique id for 1 billion user in distributed system

Mean and Median

You are given say 20 nodes in a distributed system and each node have 1 billion numbers. Find mean and median. You can have some other nodes for co-ordination.

Mean = (sum of all the numbers) / total numbers
Median = Mid element in sorted sequence

For example
Input = [2, 3, 4, 1]

Mean = (2+3+4+1) / 4 =2.5
For median sorted sequence is [1, 2, 3, 4]. Median is 2 or 3.

Naming in Distributed Systems

| Comments


The scope of this post is limited to the study of naming systems for following system
• Directory Service for Wide Area
• File system or Content manage system for collaborative work

Naming can be categorized into four kinds
1. Host based naming
2. Global naming
3. User/Objet centered naming
4. Attribute based naming

Scale in Distributed Systems

| Comments


This blog is summary of the research paper Scale in Distributed Systems.

A system is Scalable if it can handle addition of users and resources without suffering a noticeable loss of performance or increase in administrative complexity.

Systems designed to Scale

Some historic systems desgined to scale

D3.js and Octopress

| Comments

This article is about how to use versatile D3.js with Octopress.

Recently I was looking for flow chart diagram or tree structure diagram, but I did not want to produce static image diagrams using Microsoft Vizio or similar softwares.

My requirement was to come up with tree structure data representation, which I could change in future unlike static pictures and can not be changed in future.

I found D3.js to be perfect for this scenario. Here, I store data in JSON file and I use D3.js to display that data according to my needs.

Array and Strings

| Comments

Array Problems

Sum of 2 numbers

We are given a sorted array A of length n and a value k. We want to find out if there are indices i, j such that A[i] + A[j] == k.

Give a Θ(n) way of solving this problem. Prove its running time and correctness.
Your algorithm should also output one pair of indices i, j such that A[i] + A[j] == k (if at least one pair exists; if multiple exist, you only need to output one of them).

Other variant of the same problem
When array is not sorted
We need to find pair of numbers in an array whose sum is equal to a given value.
Input [6,4,5,7,9,1,2]
Sum = 10
Then the pairs are [6,4] , [9,1]

Scalability in Distributed Systems

| Comments

This article is about Scalability in Distributed Systems and various engineering organizations approaching the problem of Scalability..


In electronics (including hardware, communication and software), scalability is the ability of a system, network, or process to handle a growing amount of work in a capable manner or its ability to be enlarged to accommodate that growth. For example, it can refer to the capability of a system to increase total throughput under an increased load when resources (typically hardware) are added. An analogous meaning is implied when the word is used in an economic context, where scalability of a company implies that the underlying business model offers the potential for economic growth within the company.

Read more