Image for post
Image for post
Courtesy: shutterstock.com

Introduction

We use real time location search services all the time in our real life — whether it’s a food ordering app or on-demand cab booking service, it’s everywhere nowadays. The intention of this article is to look into how to design the back end infrastructure for a Geo-spatial index in real life.

We will explore how several companies in relevant space have solved the problem, what are the pros & cons of different approaches & how you can approach the problem. Also we will see how to approach the problem in a System & Architecture Design Technical Interview perspective.

Some Real Life Use Cases

  1. Real time cab booking service like Uber, Lyft, Bolt. …

Consider the following scenario.

You have to design a generic vending machine which can provide you different variants of Coffee, Hot Water, Hot Milk, Coke, Lemonade & what not. How will you design that vending machine software?

This post is not about designing the complete vending machine, rather it discusses only one portion of the machine — how to support different variants of beverages, customers will browse all product & choose any one as per their choice. Remember, going forward you may be asked to add support for say fruit juice, tea or some variety of milk shake, chocolate shake etc. …


Image for post
Image for post

In the first part of this series, we have seen networking & TCP basics which are necessary to understand the advanced stuffs discussed in this article. We saw what a TCP segment is, how it gets transferred through different network layers & how devices communicate with each other to transfer network data. We will now discuss what happens on the way when a segment is getting transferred, what kind of challenges are there, what kind of optimizations TCP apply for fast transmission & error control, what kind of optimization we developers can apply while developing applications.

Data Transmission Challenge: Network Congestion

Not all nodes connected to the internet have same link bandwidth. Hence the rate at which server sends data through the network may quickly overflow the buffer of intermediate nodes causing delay in round trip time of a segment & segment drop / unreliability in the network. Hosts may send the same packet several times to the receiver eventually some copy of each packets arrives at the destination. This is called Congestion collapse. …


Image for post
Image for post

When we hear of networking & related topics like connection, protocols, data transfer, the dreaded university lectures & boring slides come to our mind (probably to most of us). As software engineers, we can’t be fearful of technical details of networking, all of us may not be network engineers, still we need to know enough details so that we can make proper decision with minimum & appropriate trade-offs while designing a system architecture.

Most of the networking books or slides are fat, very serious, covers many topics in minute details. This post is designed exactly opposite to that, it explains few networking concepts & TCP in a top-down fashion from a software engineer’s perspective in simple English accompanied by enough technical details so that once you go through it, you get a clear picture of how, what & why of different aspects of TCP. …


Image for post
Image for post

In 2010, Jeff Dean from Google gave a wonderful talk in Standford & he discussed few numbers of computing systems, he got really famous for that. Peter Norvig published those numbers for the first time in the internet. Time passes away, so the numbers also change. I found a very good interactive web UI of those numbers which roughly tell how much those numbers have changed over the years as a function of time.

This article is a compilation of not only Jeff Dean’s estimated data, rather of all such numbers from different sources which may help you as a system designer & architect. …


Image for post
Image for post

There are lot of articles online describing database scalability patterns, but they are mostly scattered articles —just techniques are defined haphazardly without much context, they are not defined in a step by step manner i.e; when to choose which scaling option, which scaling options are feasible in practise & why. Moreover I am planing to discuss some of the techniques in details in future articles, so I feel it’s better if I discuss step by step techniques with some context in my own way. This article is high level article — I will not discuss scaling techniques in details here.

Assume you have built a startup which offers ride sharing at cheap cost. Initially when you start, you target a city & hardly you have tens of customers after initial advertisement. You save all customer, trip, locations, bookings data, customer trip history in the same database or most likely in a single physical machine, there is no fancy caching or big data pipeline to solve problems since your app is very new. …


Image for post
Image for post
Courtesy: Unsplash

Factory design pattern is probably one of the most used design patterns. If you have ever cared about doing low level object model properly for your service or if you have ever studied design patterns, it’s highly probable that you have incurred some scenario where you can use Factory pattern. But this post is not just about basic knowledge of Factory pattern, rather it discusses about how you can choose objects dynamically at the run time with different approaches & their pros and cons.

What is Factory Pattern & When to use it?

Factory is a creational design pattern which is used to create different implementation objects of the same type. …


Variant:

Given coins of different denominations in a haphazard manner, find out the sum that you can’t make using those denominations.

Image for post
Image for post
Courtesy: Unsplash

Clarification of the Problem Statement:

Let’s clarify some of the facts from the problem statement:

  • The array contains positive numbers.
  • The array is unsorted.
  • The array can be of any length within our memory limit.
  • We need to find the minimum number that we can not find as sum of any subset of the array.
  • If the question is asked in a problem solving interview, you can ask about the expected time & space complexity. A clever interviewer might refuse to tell the time & space complexity upfront, rather s/he would look for all possible & increasingly more efficient solution from you. …

Image for post
Image for post
Photo by Markus Spiske on Unsplash

Performance is extremely important in many consumer products like e-commerce, payment systems, gaming, transportation apps, etc. Although databases are internally optimised through multiple mechanisms to meet their performance requirements in the modern world, a lot depends on the application developer as well — after all, only a developer knows what queries the application has to perform.

Developers who deal with relational databases have used or at least heard about indexing, and it’s a very common concept in the database world. However, the most important part is to understand what to index & how the indexing is going to boost the query response time. For doing that you need to understand how you are going to query your database tables. …


Image for post
Image for post

Problem Statement:

You are getting a stream of numbers (say long type numbers), compute the parity of the numbers. Hypothetically you have to serve a huge scale like 1 million numbers per minute. Design an algorithm considering such scale. Parity of a number is 1 if the total number of set bits in the binary representation of the number is odd else parity is 0.

Solution:

Approach 1 - Brute Force:

The problem statement clearly states what parity is. We can calculate the total number of set bits in the binary representation of the given number. If the total number of set bits is odd, parity is 1 else 0. …

About

Kousik Nath

Deep discussions on problem solving, distributed systems, computing concepts, real life systems designing. Developer @PayPal. https://in.linkedin.com/in/kousikn

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store