Fastest Reach in Snakes and Ladders

Introduction For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on. Problem Statement - Fastest Reach in Snakes and Ladders The problem in ha...
Read More

Single Source Shortest Path For Undirected Graph

Introduction Single source shortest path for undirected graph is basically the breadth first traversal of the graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. You can find posts on the same topic for weighted graphs, and that is solved using Dijkstra's or Bellman Ford algorithms. This post is written from the competitive programming perspective. Here I want to focus on the details of simplified implementations. Problem Statement - Shortest Path for Undirected Graph Most of the times, the probl...
Read More

Rotating an Array by a fixed distance

Problem Statement Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array. Here is an example of input and output. The problem seems very easy until s...
Read More

Removing Duplicates from Sorted Linked List

Problem Statement You are given a singly sorted linked list, which has repeated elements. The task at hand is to remove the duplicates from the linked list. Here is a diagram to explain the problem statement Solution for Removing Duplicates from Sorted Linked List As the linked list is sorted, if two nodes contain duplicates, they will always be adjacent to each other. Hence, the trick is to Maintain two pointers (Current_Node_Ptr and Next_Node_Ptr). If the Next_Node_Ptr points to a duplicate node, delete the node and advance the Next_Node_Ptr Make the next of Current_No...
Read More

TechieMe New Android App

Hello there! I have recreated a completely new and better android app for this blog. Have a glimpse of the new UI and features below This app is a companion to the this programming blog  and a possible improved replacement to the older version  This is an ever increasing knowledge repository, with classic and configurable user interface and awesome user experience. The content is cleanly segregated and presented. The app contains posts on topics like: 1) Java/J2EE 2) Algorithms 3) Datastructures The Send a Suggestion feature allows you to request ...
Read More

Find the Point of Rotation in Sorted Array

Problem Statement You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K. Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time. Approach to Find the Point of Rotation Brute Force Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps: Start traversing the array from the beginning There will be a index in the array where the value sto...
Read More

Find the maximum possible profit

Problem Statement Given an array of stock prices per share for a given share over a time period. Calculate the maximum possible profit per share one could have made . Here we do not consider short selling as an option. The trader must have purchased the stocks before selling it. The problem statement is a real world definition of the problem called maximum positive difference. For the above two arrays, here are the maximum profit per share one could have made: A : 18.0 (difference between 21 and 3) B : 13.0 (difference between 19 and 6) What is Maximum Positive Difference? ...
Read More