Recent Posts

Announcing AM library 1.0.0

I am happy to announce the launch of a new library called AM or Assert-Mocks for unit-testing Java servlet API code. The library aims to make it a lot easier and faster to test the servlet API code, including and not limited to testing of servlets, servlet filters and tag libraries. It helps remove the need of using Mockito framework for setting up expectations.


Read the full post here.

Releasing jerry-core 3.0.0

I am happy to announce that exactly after an year of the last release, I have a new major release for jerry-core library: version 3.0.0. You may get hold of the library from Maven Central with the following coordinates:

<dependency>
    <groupId>com.sangupta</groupId>
    <artifactId>jerry-core</artifactId>
    <version>3.0.0</version>
</dependency>

Read the full post here.

Fastest way to merge multiple integer sets

Problem

You are given multiple integer sets and you need to merge them into a single set in the fastest possible way.

Solution

The always updated article is always available on Github:sangupta/ps repo

Suppose we have 3 arrays of integer sets and we need to merge them. The fastest solution would be possible in time of O(n1 + n2 + n3) where n1, n2, n3 are the lengths of the three sets respectively. The solution lies in using a bit-vector (also called as bit-set or a bit-array) to represent elements using the index and then iterating over them.

  • Construct a bit-array
  • Iterate over the first array and for each integer set the corresponding bit to true
  • Repeat the above process for remaining arrays
  • Any duplicate element will result in setting true an already set bit
  • The resultant bit-array is the merge of all the arrays

Read the full post here.

Fastest sorting of integers

Problem

We are given a huge array of bounded, non-duplicate, positive integers that need to be sorted. What’s the fastest way to do it.

Solution

The always updated article is always available on Github:sangupta/ps repo

Most of the interview candidates that I have talked to about this problem come up with the quick answer as MergeSort or divide-and-conquer. The cost of sorting being O(N * Log(N)) - which in this case is not the fastest sorting time.

The fastest time to sort an integer array is O(N). Let me explain how.

  • Construct a boolean array of length N
  • For every integer n in array, mark the boolean at index n in array as true
  • Once the array iteration is complete, just iterate over the boolean array again to print all the indices that have the value set as true

Read the full post here.

Finding degrees of separation in a social graph

Problem

Assume two users on a Social network start with zero 0 connections. And add connections at a rate of 100 per minute. Explain how you would design a solution to find out the degrees of separation between two network profiles, given a known function getConnections(profile.id) that returns data from over the network. What differences would you make for realtime less consistent/optimal result vs a slower more accurate result?

Solution

The always updated article is always available on Github:sangupta/ps repo

I can think of many different ways to compute this. I will put them out below.

Approach 2 seems the best considering the storage cost and traversal costs. Approach 3 can be near real-time if we can take care of the storage, and add optimal number of workers for fan-out.


Read the full post here.
The entire blog is available here.