Generate an integer which is not in a file with 4 billion integers, limited memory
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 8 minutes
| Kinshuk Chandra
Problem
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory.
FOLLOW UP
What if you have only 10 MB of memory?
Solution
Case 1 - If very large integers are allowed then one can generate a number that is statistically likely to be unique in O(1) time. For example, a psuedo random 128 bit integer like a GUID will only collide with one of the existing four billion integers in the set in less than one out of every 64 billion billion billion cases.
[Read More]Sorting 10 GB file of integer with limited ram.
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
I have only x GB RAM in computer. I have a text file of 10 GB data.This file contains numbers. x is less than 10. How will I sort them?
Solution
Generic algorithm
Here is the generic algorithm:
split the file into parts (buffers) that you can sort in-memory then when all buffers are sorted take 2 (or more) at the time and merge them (like merge sort) until there’s only 1 buffer remaining which will be the sorted file Example x = 4
[Read More]How to test an ATM in a distributed banking system
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
How would you test an ATM in a distributed banking system?
Solution
The first thing to do on this question is to clarify assumptions Ask the following questions:
Who is going to use the ATM? Answers might be “anyone”, or it might be “blind people” – or any number of other answers What are they going to use it for? Answers might be “withdrawing money”, “transferring money”, “checking their balance”, or many other answers What tools do we have to test?
[Read More]How to test a pen
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
How would you test a pen?
Solution
This problem is largely about understand the constraints: what exactly is the pen?
You should ask a lot of questions to understand what exactly you are trying to test To illustrate the technique in this problem, let us guide you through a mock-conversation.
Interviewer: How would you test a pen?
Candidate : What kind of pen is it? Is it a ball pen, pilot pen, roller pen, sketch pen?
[Read More]Load test a webpage without using any test tools
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
How would you load test a webpage without using any test tools?
Solution
Load testing helps to identify a web application’s maximum operating capacity, as well as any bottlenecks that may interfere with its performance. Similarly, it can check how an application responds to variations in load.
To perform load testing, we must first identify the performance-critical scenarios and the
metrics which fulfill our performance objectives. Typical criteria include:
[Read More]How to test a canMoveTo(int x, int y) method in a chess game
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position. Explain how you would test this method.
Solution
There are two primary types of testing we should do:
Validation of input/output:
We should validate both the input and output to make sure that each are valid.
[Read More]Find the mistake(s) in the code
Posted on April 1, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Find the mistake(s) in the following code:
unsigned int i; for ( i = 100; i <= 0; --i) printf("%d\\n", i); Solution
Because i is an unsigned integer, i cannot be negative. Hence the for loop should be:
for ( i = 100; i >= 0; --i) As i is unsigned integer, when i == 0 and one does –i, i will be FFFF FFFF in hex. Then when you do printf with “%d”, i will be interpret as an signed integer.
[Read More]Programming errors cause program crashes in different places every single time
Posted on March 31, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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.
[Read More]Check if array contains duplicates
Posted on March 31, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
**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.
[Read More]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]