Get 4qt of water using a 5qt jug and a 3qt jug

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

Problem: You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible. Solution: I first thought we can come up with 2qt water by filling up the 5qt jug and pouring 3qt water to the 3qt jug. [Read More]
kodeknight  brainteaser  CrackingTheCodingInterview 

Covering a chess board with dominos

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

Problem: There is an 8×8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible) Solution: No, it’s not possible. Two diagonally opposite squares on a chess board are of the same color. [Read More]
kodeknight  brainteaser  CrackingTheCodingInterview 

Sieve of Atkins

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

Problem Given a number n, print all primes smaller than or equal to n. Example For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″. Algorithm We have discussed sieve of Eratosthenes here, but lets move to the Sieve of Atkins algorithm today which is a modified version of sieve of Eratosthenes. [Read More]
kodeknight  prime 

Algorithm to find out number of factors of a number

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

Problem Given a number find the number of factors of that number Example Factors of 18 are 1, 2, 3, 6, 9, 18. Hence 6 factors. Solution Method 1 - Using divisor function. Let n be the given number. If n = p1^e1 * p2^e2 * ... * pk^ek, where each p is a prime number, then the number of factors of n is (e1 + 1)*(e2 + 1)* . [Read More]
kodeknight  prime  prime-factor  factorization 

Program to print all prime factors of a given number

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

Problem Given a number n, write an efficient function to print all prime factors of n.  Example For example, if the input number is 12, then output should be “2 2 3″. And if the input number is 315, then output should be “3 3 5 7″. Following are the steps to find all prime factors. 1) While n is divisible by 2, print 2 and divide n by 2. [Read More]
factor  kodeknight  prime  prime-factor  factorization 

To find the list of primes till N

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

Problem Given a number n, print all primes smaller than or equal to n. Example For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″. Solution Method 1 - Brute force We just loop till number N, and check if individual iterator is prime or not. Code : [Read More]
kodeknight  prime 

Sieve of Eratosthenes

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

Problem Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. Example For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″. Algorithm The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so (Ref Wiki). [Read More]
kodeknight  prime 

Efficient ways to check if number is prime number

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

Problem How to check if number is prime or not You may remember that a prime number is one whose only factors are itself and 1. Other numbers are called oblong numbers (they can be represented as an oblong of dots) or composite numbers. If you have a number and you want to find out if it’s prime, that is called performing a primality test. The naive approach is to check all numbers m from 2 to sqrt(n) and verify that n % m is not 0. [Read More]
kodeknight  prime 

Given a series (2,3,4,5,6,8,9,10,12,15,...) where the elements are in multiple of 2,3 and 5. Find the nth element of this sequence

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

Problem: Assume given sequence : 2,3,4,5,6,8,9,10,12,15… All these numbers are multiples of either 2 , 3, or 5 (and no other numbers). Find the nth element of this sequence. (This is the interview question in flipkart) Solution: This can be thought in recursive terms. But to begin with, we can clearly see, 2.5=10 is part of series, but 2.7=14 is not part of series. So, while generation of numbers we have to make sure that divisor is not part of numbers like 7,11,13 etc. [Read More]
kodeknight  flipkart 

Check if 2 trees are iso-morphic

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

Problem Given 2 binary trees, check if they are isomorphic. Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic.  In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left. [Read More]
Binary Tree  BT  kodeknight