Find duplicates in the ranged array
Posted on March 31, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.
Follow UP - Find these repeating numbers in O(n) and using only constant memory space.
Example
Input : array = {1, 2, 3, 1, 3, 6, 6}, n = 7
Output = 1,3,6
Solution
This problem is an extended version of following problem.
Find the two repeating elements in a given array
[Read More]Find the two repeating elements in ranged array
Posted on March 31, 2014
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
Problem
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
Example
Input : array = {4, 2, 4, 5, 2, 3, 1} and n = 5, array.length = n+2 = 7
Output : 4,2
Solution
This can be achieved by various methods.
[Read More]Find the two non-repeating elements in a ranged array of repeating elements
Posted on March 31, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Example
Input : {2,4,7,9,2,4}
Output : 7,9
Solution
Method 1 - Use Sorting
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements.
[Read More]Find the kth number with prime factors 3, 5 and 7
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
Solution
We have already solved the similar problem for ugly numbers, where the factor was 2,3 5 here.
Find a line which passes the most number of points
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a two dimensional graph with points on it, find a line which passes the most number of points.
Solution
Method 1 - Naive solution
This is the brute force solution. We take point 1, and then point 2 and make a line. Now in the third nested loop, check if point 3 is existing on the same line or not.
Pseudocode
Line findLineWithMaxPoint(Set points){ foreach Point p1 in points foreach Point p2 in (points - {p1}){ Line l = makeLine(p1,p2); int count = 2 //line contains p1 and p2 foreach(Point p3 in (points-{p1,p2})){ if(l.
[Read More]Find a line to cut two squares in half
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Given two squares on a two dimensional plane, find a line that would cut these two squares in half.
Solution: Any Line passing the centers of the two squares will cut them in halves. So, we have to connect the lines between the center of the 2 squares. The straight line that connects the two centers of the two squares will cut both of them into half.
[Read More]Implement *, -, and / operators using only +
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write a method to implement *, – , / operations You should use only the + operator.
Solution
IF we have 2 numbers a, b
a * b can be implemented as adding a for b times.Take care of overflow as a*b may result in overflow. a – b can be implemented as addition of a and -b. a / b can be implemented as finding how many times you need to add b, until getting a.
[Read More]Determine whether two lines would intersect on a Cartesian plane
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given two lines on a Cartesian plane, determine whether the two lines would intersect.
Solution
On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect.
[Read More]One shot or at least two shots in three games?
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: You have a basketball hoop and someone says that you can play 1 of 2 games.
Game #1: You get one shot to make the hoop.
Game #2: You get three shots and you have to make 2 of 3 shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
Solution: For game #1, you have probability p of winning.
[Read More]Three Gods - God of Truth, Lies and Chaos
Posted on March 30, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem: You are stranded on an Island and on that island are 3 all knowing all powerful gods. One god is the god of truth, who always tells the truth and can never lie. The second god is the god of lies, he always lies and never tells the truth. The 3rd god is the god of chaos, he tells both lies and truths, however, completely randomly. The gods appear as identical twins, they all look the same.
[Read More]