Permutations of every subset of size K

 Posted on March 27, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N).  Solution Method 1 - Append characters till the length K is reached We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed The for each combination we permute them using another recursive procedure Time : O(N! [Read More]
kodeknight  Permutation  subset 

All possible paths for a robot moving along a NxN grid

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.  Solution We solved the similar question here, where we had to find the count of number of paths. [Read More]
kodeknight  recursion  CrackingTheCodingInterview 

How many lockers are open after 100 passes of toggles

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem: There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open? [Read More]
kodeknight  brainteaser  squares  CrackingTheCodingInterview 

Two egg puzzle

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Problem: There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case. Solution This is similar as binary search. If we have unlimited number of eggs, we only need 7 (log 100 to base 2) to find N i. [Read More]
kodeknight  brainteaser  Dynamic Programming  DP  recursion  CrackingTheCodingInterview 

Interval Search Tree

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

**Problem ** Discuss Interval Search Tree Idea behind Interval Search Tree Lets discuss the 1D Interval search. By 1D I mean in 1 dimension i.e. having interval along 1 axis only. So, suppose along x axis we have collection of intervals - [1,2], [1,3] and so on. Here Interval Tree or Interval Search tree is helpful as it holds set of (overlapping) intervals Insert the interval Search delete Main functionality - Interval intersection query - given the interval (lo, hi) find all intervals in data structure which intersect with given interval. [Read More]
kodeknight  geometric-search  interval  git  github 

Segment trees VS Interval trees VS binary indexed trees VS range trees

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

All these data structures are used for solving different problems: Segment tree stores intervals, and optimized for “which of these intervals contains a given point” queries. Interval tree stores intervals as well, but optimized for “which of these intervals overlap with a given interval” queries. It can also be used for point queries - similar to segment tree. Range tree stores points, and optimized for “which points fall within a given interval” queries. [Read More]
kodeknight  geometric-search  interval 

Merge Overlapping Intervals

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Given a collection of intervals, merge all overlapping intervals. Input - Collection of intervals Output - Collection of mutually exclusive intervals after merging Example Given \[1,3\],\[2,6\],\[8,10\],\[15,18\], return \[1,6\],\[8,10\],\[15,18\]. Solution Method 1 - Brute force A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. [Read More]
kodeknight  merge  sorting  array  interval 

How long does it take to remove c ‘magical’ hats from n people

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., _at least one person has a ha_t). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight. [Read More]
kodeknight  brainteaser  CrackingTheCodingInterview 

Remove duplicates from unsorted array

 Posted on March 25, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

**Problem ** Remove duplicates from unsorted array Example a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] ```so after that operation the array should look like a[1,5,2,6,8,9,10,3,4,11] Solution **Method 1 - Brute Force - Check every element against every other element** The naive solution is to check every element against every other element. This is wasteful and yields an O(n2) solution, even if you only go "forward". **Method 2 - Sort then remove duplicates** A better solution is sort the array and then check each element to the one next to it to find duplicates. [Read More]
kodeknight  duplicate  unsorted-array  remove-duplicates 

Number of unique elements in sorted array with repeated elements

 Posted on March 25, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Find the number of unique elements in sorted array with repeated elements. Follow up - How can you do it without using extra space Example Input = [1,1,1, 2] Output = 2 i.e. 1 and 2. Example for follow up Input = [1,1,2] Output = 2 Solution It’s not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. [Read More]
kodeknight  duplicate  count  sorted-array  java