Programming errors cause program crashes in different places every single time

Problem You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? Solution The question largely depends on the type of application being diagnosed. However, we can give some general causes of random crashes. General cases Not initialising a variable but attempting to use its value. Dereferencing...

Read More

Check if array contains duplicates

Problem  Given an array of n elements, check if it has duplicates Solution This problem is similar to following problem : Find the two repeating elements in a given array We can use some of the method used there. Method 1 - Brute force Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements. bool hasDuplicates(int...

Read More

Find duplicates in the ranged array

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 Method 1 and Method 2 of the above link are not applicable as the question says O(n) time complexity and O(1) constant space....

Read More

Find the two repeating elements in ranged array

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. Method 1 - Brute force Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. This method doesn’t use the other useful data...

Read More

Find the two non-repeating elements in a ranged array of repeating elements

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. Time complexity of this method is O(nLogn) Method 2 - Use XOR Let x and y be the non-repeating elements we are looking...

Read More

Find the kth number with prime factors 3, 5 and 7

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. &nbs...

Read More

Find a line which passes the most number of points

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...

Read More

Find a line to cut two squares in half

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. Code in java public class Square { public double left; public double...

Read More

Implement *, -, and / operators using only +

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.  Here is the solution in java: public static int negate(int number) { return ~number + 1; } public static int abs(int number) { return number < 0 ? negate(number)...

Read More

Determine whether two lines would intersect on a Cartesian plane

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. public class Line { static final double epsilon = 0.000001; ...

Read More

One shot or at least two shots in three games?

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.  For game #2, you can either make 2 shots of 3, with probability 3p^2(1-p),...

Read More

Three Gods - God of Truth, Lies and Chaos

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. The gods also speak a language that you...

Read More

Labour and work problem - 20 women replaced by a men and boy alternatively

Problem: 20 women can finish a job in 20 days. After each day, one woman is replaced by a man or a boy alternatively starting with a man. Man is twice efficient and boy is half efficient as a woman. On which day does the job get completed? Solution: Lets treat man as 2 women and boy as half woman. Starting 1st day 1 W is removed and 1M added. So, we have 21W at work. Next day, 1B is added and 1W is removed, so, we have 20.5 W now. Now add...

Read More

3 bags of 2 marbles

Problem: You have three bags, each containing two marbles. Bag A contains two white marbles, Bag B contains two black marbles, and Bag C contains one white marble and one black marble. You pick a random bag and take out one marble. It is a white marble. What is the probability that the remaining marble from the same bag is also white? Solution: Reasoning: A = {W,W} B = {B, B} C = {B, W} We have already selected a bag, which has a white...

Read More

Frog leaping 3m and slipping 2m

Problem: A frog is at the bottom of a 30 meter well. Each day he summons enough energy for one 3 meter leap up the well. Exhausted, he then hangs there for the rest of the day. At night, while he is asleep, he slips 2 meters backwards. How many days does it take him to escape from the well? Solution: Each day he makes it up another meter, and then on the twenty seventh day he can leap three meters and climb out. On the 28th day, he will leap...

Read More

Circus tower sorting problem

Problem A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68,...

Read More

Searching in a sorted array of strings with empty strings

Problem Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""] will return 4 Example: find “ballcar” in ["at", "", "", "", "", "ball", "car", "", "", "dad", "", ""] will return -1 Solution The worst we can do is O(n) where we just do a linear search. I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way,...

Read More

Sorting a 2GB file with one string per line

Problem If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why? Solution When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory. So what do we do? We only bring part of the data into memory.. Method 1 - K way external merge sort Because 2GB size of strings are way too huge to be put into main memory, I came up with two ways: K-way merge sort. Divide the file into K pieces,...

Read More

Sort an array of strings so that anagrams are next to each other

Problem Write a method to sort an array of strings so that all the anagrams are next to each other. Example INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx" Lets see the solutions now. Solution Method 1 - Using bubble sort Check if two pairs of strings are anagrams or not, if yes, swap. Java code private static boolean areAnagrams(String s1, String s2) { if (s1.length() != s2.length() || s1 == null || s2 == null) return false; s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); ...

Read More

Merge two sorted arrays - One having big enough buffer to hold another

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. Do this in linear time and in-place. Example array1 = {1, 3, 6} array2 = {2, 4, 5, _, _, _} sortedArray = {1, 2, 3, 4, 5, 6} Solution Method 1 - Merge sort This is part of the merge-sort. Let...

Read More

Eight Queen Puzzle (likewise N Queen)

Problem Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal. (image courtesy) Solution This is a classic problem to implement using backtracking. It has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 fundamental solutions.Also, when we say N queen...

Read More

Number of ways of representing n cents using quarters, dimes, nickels and pennies

Problem Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents. Solution Method 1 - Recursion This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i.e., sub-problems). Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. What’s the relationship to its sub-problems? We know that makeChange(100): = makeChange(100 using 0 quarters) + makeChange(100...

Read More

Implement the “paint fill” function

Problem Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color. Solution Again, the solution falls in the bucket of recursion, backtracking. Method 1 - Recursion First, let’s visualize how this method works. When we call Paint Fill (eg, “click”...

Read More

Print all combinations of n balanced parentheses

Problem Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses. Example Input     3 (i.e., 3 pairs of parentheses) Output    ()()(), ()(()), (())(), ((())) Solution This is a classic combinatorial problem that manifests itself in many different ways. Such kind of strings are called Dyck strings (see more here), which contain n X's and n Y's such that no initial segment of the string has more Y's than X's. example: XXXYYY     XYXXYY    ...

Read More

LATIN SQUARE” and its implementation

Problem Understand Latin Square and its implementation Understanding the latin square “A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia In this article we will build a square to match the definition. As the definition suggest Latin square is square...

Read More

Permutations of every subset of size K

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!) Space : O(N!) when storing results O(1) if directly output the result Code in c: void swap (char *x, char *y) { ...

Read More

Design an OO parking lot

Problem Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact. Solution Lets start with the design. class ParkingLot 1. ParkingLot keeps array of ParkingSpot 2. Separate array of vacant ParkingSpot 3. Separate array for HandiCappedDrivers, some x% 3. ParkingSpot FindVacantSpaceNearestEntrance() 4....

Read More

Describe the data structures and algorithms that you would use to implement a garbage collector in C++

Problem Describe the data structures and algorithms that you would use to implement a garbage collector in C++. Solution  Have lost touch with cpp, marking this question as incomplete for now. But here 2 good reference References http://tianrunhe.wordpress.com/2012/03/24/data-structure-and-algorithms-for-garbage-collection-in-c/ http://stackoverflow.com/questions/5009869/how-to-implement-garbage-collection-in...

Read More

Design a musical juke box using object oriented principles

Problem Design a musical juke box using object oriented principles. Solution We have already discussed the database design of how we will save information in the DB. Please refer this post for the same. Our OOP design will be incorporating most of the design from there only. Lets start with the design now. class Song 1. has a song name, song artist,year,genre and so on. Song will be part of playlist class Playlist 1. has a track, current...

Read More

Design a database to store music library for your jukebox

Problem Design a database to store music library for your jukebox Solution Basically we have to save everything that has to do anything with organizing digital music Something like this would be good to start with.  It specifies a table for artists, albums (with keys into artists and genres), tracks (keyed into albums), and genres. Also, all these tables will have a surrogate key(basically an auto generated primary key id, which will be...

Read More