interview

Find Path through grid – constrained motion

Introduction This is another addition to the backtracking series of problems. The problem is asked in many interviews in many different forms. Here are few of them: Given a grid where few of the cells are blocked. You have a robot placed at the top left corner of the grid. Find path through grid such that the robot starts from the top left corner and moves to the bottom right corner. Another form just asks for all possible paths from one cell to another into a grid. Of course there are constraints on the movement of the robot, else you would end up going in circles and the paths wo...
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