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 

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