Algorithm Simple random sample Problem Choose a simple random sample, without replacement, of k items from a population of size n. Fisher-Yates shuffling for known n The basic idea is to shuffle the original array of n

Algorithm Quick note on Count-Min Sketch Problem Count the number of times elements appear in a stream of data. This can be solved easily by using a HashMap. However, data streaming is unbounded so we may end up out

Algorithm On All nearest smaller values problem 1. Background 1.1 All nearest smaller values problem Given an array A[0..n-1], for each element in A, search among the previous positions for the nearest position that contains a smaller

Algorithm On a side-effect of Merge Sort The problem Given an array A, we call (i, j) an important reverse pair if i < j and A[i] > 2*A[j]. Count the number of important reverse pairs. For

Algorithm A note on Stream Sync - The protocol behind Dropbox's sync performance Introduction File hosting services like Dropbox/ Google Drive require ability to sync files fast between clients. One of the simple techniques is to break the file into multiple fixed-size blocks so - we

CS Rate limiter algorithms's consideration High level design of Rate LimiterRequirement Limit the number of requests a user can send to an API within a time window: n requests/minute. Window size = 1 minute. The APIs are accessible

Algorithm A note on Detecting cycle - Floyd algorithm Problem Detect the cycle in a Linked list, return the starting Node of the cycle if any, otherwise return NULL. E.g: return Node 2 in following linked list: Algorithm Let fast and

Algorithm Graph Algorithms for Coding Interview Apart from the well-known BFS and DFS algorithms, I find the following algorithms useful for Coding Interview.Topology sort & circle check Given directed graph, sort the nodes in graph so that, if

Algorithm A note on an interesting technique: Range addition Assume you have an array of length n initialized with all 0's and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of

Algorithm A note on a technique of Two Pointers algorithm The pattern of question can be solved by Two Pointers algorithms is Return the length of the longest contiguous subarray [u,v] of array A that [u,v] meets the requirement X. With