## Compute Random Permutation

Compute Random Permutation Problem Statement  Design an Algorithm that creates a uniform permutation from (0 – n-1).  Given a random number generator that return a number (0 – n-1 ) with equal probability. Use as few call to it as possible.  Problem Solving Immediately I thought about the shuffle algorithm. However here we are provided […]

## Sudoku Checker

Sudoku Checker Problem Statement Given  a vector<vector<int>> of size 9*9. Check whether it is a valid Sudoku or not.   Problem Solving  I thought of starting with Iterators, writing Iterators for row iterator a column iterator and square iterator.  This got me involved in a lot of Object Oriented Problem and how to implement == nicely.  […]

## Online Sampling

Online Sampling Problem Statement Write a program that takes a stream and reads value from it to maintain a random subset of k elements.  Problem Solving  Instantly I think about a function that takes in a stream First fetches k values to fill a vector of size k.  On further input decides whether to take […]

## Offline Sampling

Offline sampling  Problem Statement  Write a program that taken a vector on n integers and return a random sample of size k. All sample must be equally likely.  Problem Solving At first, I had trouble understanding what exactly is a sample,how do measure a probability of such a permutation.  After a while I thought that […]

## Next Permutation

Next Permutation Problem Statement Given a permutation M, return the next permutation. Problem Solving   In this problem, the first thing that clicks is to observe examples.  And after multiple attempts, I started seeing a pattern.  First of all we need to see if there is a next permutation. If the sequence is already in the […]

## Apply Permutation

Apply Permutation Problem Statement Write a program that takes a permutation array and a input array and reorder the input array as per the given permutation. Problem Solving  I can see that this seems to be a linear time problem.  We need to apply permutation inc cycle. Start at 0 replace current position at 0 […]

## Enumerate All Primes to N

Enumerate All Primes to N Problem Statement Write a program that takes an integer argument and returns all primes between 1 and that integer.  Problem Solving There is not much of any solving here as I already know an ancient and well known algorithm for this. It’s called the Sieve of Eratosthenes.  The idea is […]

## Buy and Sell stock twice

Buy and Sell stock twice  Problem Statement  Given an array of stock prices on each day. Write a program that gives the maximum profit one can achieve by buying and selling a stock at most twice.  Problem Solving Immediately I started to think like I solved the previous one stock problem and thought of instead […]

## Delete Duplicates From Sorted Array

Delete Duplicates From Sorted Array  Problem Statement Write a program that takes input as a sorted array and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the empty indices. Problem Solving We need to update the array in place. Something gives me intuition about […]

Catch Me On Social !!