Some notes from: http://inder-gnu.blogspot.com/
Many problems are very good.
####### Design Questions #######
# how do you design an elevator algorithm
Elevator:
Responsibilities -- no. of passengers aboard, destination floors, state & direction, current floor
Methods: load /unload passengers, current floor/passeengers/directions/ state
Attributes: passengers, floor, dir, state, elevator_id
Passenger:
Res -- keep track of the desitnation fllor
Mds -- current destination
Att - desintation fllor
Observer:
Res -- keeps track of the passengers entering & leaving the elevator
Mda -- total entry /exit passengers, passenger enter /exit
Att - total -entry/ exit passengers.
# How would you design a server that has to process a fair number of good number of requests a second. What if you didn't know how many requests you'd be getting? What if requests had different priorities? (I always think of the Apache design for this question)
# Design malloc and free. (give up? see how G++ malloc works or this page for more examples)
# Design an elevator control system. Don't forget buttons on every floor and supporting multiple elevators. (What objects/methods/properties/how components communicate)
# Design a chess game (what objects? what methods? which data where? how will it work?)
# Design a deck of cards class (object/methods/data)
# How would you design the infrastructure front half of a very large web ecommerce site? what if it was very personalized? (how sessions are handled? where and what you can cache? how to load-balance?)
# Composition is a OOP concept:
It works similar functionality to inheritance but creates a different relationship. Compostion a "has-a" relationship - versus the inheritance of "is-a" relationship
Composition - the way you model objects that contain other objects. In OOP- you use instance variables of one object to hold references to other objects.
Car Object must have an Engine. So Car is composed of Engine. That is a composition.
# Design a deck of cards.(http://www.careercup.com/question?id=173901)
Write code for Shuffle() method.
enum Suit { spades, clubs, hearts, diamonds,};
enum Face {ACE, TWO, THREE, FOUR, FINE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, };
class card{
public:
Card(Suit suit, Face face): suit(suit), face(face) {}
Card(const Card& orig): suit(orig.suit), face(orig.face) {}
Suit getSuit() const {return suit;}
Face getFace() const {return Face;}
private:
Card() {}
Suit suit;
Face face;
friend class Deck;
};
class Deck{
public:
Deck()
{
int index = 0;
for (int = 0; i < SUITS_PER_DECK; ++I){
for( int j = 0; j < CARDS_PER_SUIT; ++j){
index = i * CARDS_PER_SUIT +J;
CARDS[index].suit = (Suit) i;
CARDS[index].face = (face) j;
}
}
}
Deck(const Deck& orig)
{
for (int i = 0; i < SUITS_PER_DECK * CARDS_PER_SUIT; ++ i){cards[i] = orig.cards[i];}
}
void Shuffle()
{
int bagSize = SUITS_PER_deck * CARDS_pER_SUIT;
in t index = 0;
srand(time(NULL));
while(bagSize){
index = rand() & bagSize;
swap(cards[--bagSize], cards[idex]);
}
}
static const int SUITS_PER_DECK = 4;
static const int CARDS_PER_SUIT = 13;
private:
Card cards[SUITES_PER_DECK * CARDS_PER_SUIT];
friend ostream & operator<< (ostream&, cont Deck&);
};
# Minimum number of scales required A company produces play ball of weights 0-25kg, 25-50kg, 50-75kg, 75-100kg. You need to put the balls in four different buckets daily depending on the number of ball company produces.BucketA (0-25kg), BucketB (25-50kg), BucketC (50-75kg) and BucketD(75-100kg).
A scale is provided on which you can weigh only 1 ball at a time which has a bulb. If the weight of the ball matches the scale category, the bulb will light up otherwise it will be OFF. e.g. If scale is marked to measure 10-25 kg, then any ball between 10 to 25kg (inclusive 10 and 25) will switch on the bulb and say if you weigh 26 it wont switch on the bulb. The cost of scale is 1 million dollar.
Question: You need to find the minimum number you will use to do the job.Also what is weight category you will choose for the scales to do the job.
==> 2 scales can do the job .... 0-50 and 25-75 ....
# Multiple lines, which the cost for connecting them is their sum of the length, how to connect n ropes with least cost
ANS: x, y, z wherein x < y < z
if you tie y+z first
then you tie x+ y +z which is essentially x + 2* (y+z)
so all ropes which have been tied before actually keep adding to the cost again and again. Hence the best strategy would be to include smaller ropes initially so that they contribute lower cumulative cost in future
keeping it in min heap..
# Find maximum interval across two arrays
We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0...
we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal...
i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
ANS==>
# Find consecutive numbers from n sorted arrays
Suppose there are n arrays storing integers in a sorted manner. You need to find all those sequences of numbers one frm each array so that the numbers are consecutive...
For example: let us consider 2 arrays
array 1 has 2 4 7 9 11 14 16 19
array 2 has 3 8 15 20
the answer must be (2,3),(7,8),(14,15),(19,20)
==> this could borrow some idea from the list merging, where we may add some condision, when judging, such as whether their differences is within (-1 or 1)
# Longest increasing subsequence in chain of numbers
Find out the the longest increasing subsequence in a sequence of 'n' numbers.
eg: 1, 5, 3, 2, 100
==> we can borrow the idea from bubble sort,where the comparision of each pari is conducted, increase the count, whenever there is a swap
Or try the recursive structure:
Here x is first element and y is successive of x. Call this method as lcs(1,2,1); x,y are first,second element of array. len is initial length which is 1.
void lcs(int x, int y, int len) {
if( y <= array.length-1){
if( array[x] <= array[y]){
if( largest < len +1){
largest = len+1;
}
lcs(y,y+1,len+1);
}
else{
else{
lcs(x-1,y,len -1);
lcs(x,y+1,len);
}
}
}
It was said that the "patience sorting" can solve this problem in O(n log n) :
# Partition array in k ranges to minimize the maximum sum over all ranges
A given arrangement S of non-negative numbers and an integer k.
Output: Partition S into k ranges, so as to minimize the maximum sum over all the ranges. This so-called linear partition problem arises often in parallel processing, since we seek to balance the work done across processors so as to minimize the total elapsed run time. Indeed, the war story of Section revolves around a botched solution to this problem.
Application - Suppose that three workers are given the task of scanning through a shelf of books in search of a given piece of information. To get the job done fairly and efficiently, the books are to be partitioned among the three workers. To avoid the need to rearrange the books or separate them into piles, it would be simplest to divide the shelf into three regions and assign each region to one worker.
But what is the fairest way to divide the shelf up? If each book is the same length, say 100 pages, the job is pretty easy. Just partition the books into equal-sized regions,
so that everyone has 300 pages to deal with.
But what if the books are not the same length?
==> First find the sum of all the numbers in S, divide it by k and store it in b.
Our aim now to divide S, so that sum should be as close to b as possible, for that purpose purpose we'd define a range b - k/2 and b + k/2. Now start scanning the array from start and keep adding to sum, if the sum falls in range previously mentioned, try to get closer to b by removing last array element or by adding the next one, whichever is closer should be end of first partition. On the similar lines partition rest of array.
Though this does not guarantee the fair partitions but I think if difference between array elements is not much, it would lead to near fair distribution.
I hope it made sense.
# Arrange numbers in decreasing order of their frequency
Input : {5, 13, 6, 5, 13, 7, 8, 6, 5}
Output : {5, 5, 5, 13, 13, 6, 6, 7, 8}
The question is to arrange the numbers in the array in decreasing order of their frequency, preserving the order of their occurrence.
If there is a tie, like in this example between 13 and 6, then the number occurring first in the input array would come first in the output array.
==> -1- traverse the arraay, use the map to recored their frequency
-2- sort the frequency, acending order
-3- start from the smallest frequency, and also start from the end of the array, multiplication of the element to re-stored it into the array ( actaully we can do thing by using the deceding frequecy, and start from the front of the array)
# Design an algorithm for an automated parking lot
You have a set of parking slots along with the distance from entrance, you need to devise an algorithm to support the following operations
1. Figure out a nearest free parking slot in the quickest way
2. Figure out where the car is parked for a valet to take it out in the quickest way.
==>
1. use a min heap for storing Parking Lot objects which are ordered by minDistance from entrance.
2. Find and provide a free lot is O(logn), take the top from the heap and put it in the hash table and rearrange the heap
3. Have a hash table with key--> car number and value as NODE
4. find where the car is parked for valet --> given a care number sesarch in hashtable, free from hash table and ass it to the heap of free nodes in log(n)
# Design an algorithm for optical character reading
Assuming you have been given some very old papers which are scanned as JPG images.
You have been asked to write a program which can read those images and identify lines in the same.
Trick lies in the fact that the lines could have negative/positive slopes as they are old documents.
Source - Algorithm design manual by Stevens
1. create a graph which each and every pixel of the image
2. if the area from left to right is grey/empty give a weight of edge 0 else 1
3. now the problem is to find a path in the graph from left to right as straigt as possible so that the path remains positive.
# find row with minumum 0's
You have a matrix with 0 & 1 with rows being in sorted order. Find the row with minimum number of 1's
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 0 1 1 1
==> Solution 1
1. Start from row1 till you keep getting a 0, as soon as you encounter a 1 go south and use the following table
1 -> 1 similar row
1 -> 0 better row make this is as candidate for answer
1. let's run through the algorithm from row1, col4 go south as row1, col4 is 1
2. transition is 1->1 so ignore second row and go south
3. 1 -> 1 similar row ignore row3 also
4. on same logic ignore row4 also so answer is row1
Let's take another matrix and run the same algo again
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
1. first transtion on row1, col3 is 1->0 so row is better
2. now run right on row2 till you get a 1 which is row3,col4 and now go south for which the transition is 1->0 making it a better row and since this is the last row hence the final answer
Time complexity analysis
1. best case-> 0(number of rows) it's a straight down south
2. worst case -> 2 (number of rows) wherein it's a zig zag motion
==> Solution2:
We first traverse 1st row and count number of 0's in it.
Now we start checking for second row and moment we find more number of 0's in it we skip the row.
if it has less number of 0's then keep this as reference for other rows..keep doing the same.
# Map rectangles to plane
In my graphics work I need to solve the following problem. Given an arbitrary set of rectangles in the plane, how can I distribute them into a minimum number of buckets such that the subset of rectangles in the same bucket do not intersect each other? In other words, there should not be any overlapping area between any two rectangles in the same bucket.'
==>Use graph coloring, you need to create a graph so that adjacent nodes should be colored in different colors
#Find k-th largest in two sorted arrays
Find kth largest element in two sorted arrays.
Can there be a solution better that O(k)
Solution 1:
Suppose input array's are in the following fashion
A[] = {2, 3, 7, 12, 27, 81, 91}
b[] = {1, 25, 32, 74, 89}
1. Take two pointers ptr1 and ptr2 at start in A[] and B[]
2. if(A[i] > B[j])
j++;
else
i++;
3. if ( (i +j ) == k)
compare A[i] and B[j] and return the larger of them
else
repeat step2.
Time Complexity = O(k)
Solution2:
Idea = We have to find the median of first k elements of A and B and k = 5
1. The kth largest among the union of A[] and B[] would be in the first k elements of of A[] and b[]
2. Consider k elements from A[] and B[] which results in the following array
a[] = {2. 3, 7, 12, 27}
b[] = {1, 25, 32, 74, 89}
3. Compare (A[mid], B[mid])
if (A[mid] is GT)
{
For ArrayA = We can skip a[mid]..a[k] elements since a[mid] is greater and all elements from a[0]..a[mid] are valid candidates for being the median; since A[mid] is the greater element no point considering bigger elements than that for the median
For Array B = We can skip b[0]...b[mid] elements since b[mid] is less; so all elements less than are not valid candidates for being median.
}
4. Repeat Step3 till you are left with either 2 or 3 elements then you do a comparision and find kth largest.
Time Complexity = O(log k)
Example showing Solution 2
A[] = { 2, 3, 7, 12, 27}
B[] = {1, 25, 32, 75, 89}
After step2 i.e. k elements from both arrays
A[mid] = 7 and B[mid] = 32
B[mid] is Greater.
Now array becomes after step3
a[] = {7, 12, 27}
b[] = { 1, 25, 32}
a[mid] = 12 and b[mid] = 25
After step3 the arrays become
a[] = { 12, 27} -- skpping the left portion of smaller element array
b[] = { 1, 25} -- skipping the right portion of larger element array
Now a[mid] = 12 and b[mid] = 1
after step3 the array becomes
a[] = {12}
b[] = {1,25}
Find the median of 12, 1, 25 in O(1) which is 12 which is the 5th largest
#Find the nth number with m binary 1s
There is a series of numbers in ascending order. All these numbers have the same number of binary 1s in them. Given the number of 1 bits set in the numbers, write an algorithm/C program to find the nth number in
the series.
Example: Given a number m find the next higher number r, that has same number of 1-bits
Ex. 3(0000011) ==> 5 (0000101)
6(0000110) => 9 ( 0001001)
11(0000110) ==> 13 ( 0001101)
What we can do here is that (http://www.slideshare.net/gkumar007/bits-next-higher-presentation.):
+ The left hand side is:
- A 0 followed by
- One or more 1's (say x) followed by
- Zero or more 0's (say y)
+ is changed to
- A 1 followed by
- (y+1) zeros followed by
- (x-1) 1's
An example: 001 ==> 101 ..... 011000 => 100001
Now let's frame the algorithm
- Given a bit-pattern, start from right, find successive zeros (xxxx011110000)
- Followed by zeros find successive 1's (xxxx011110000)
- Stop on hitting a zero (xxxx01111000)
- Interchage that zero with a 1 from successive 1's (xxxx101110000)
- Now move the remaining 1's to extrem right, filling the gap with zeros (xxxx100000111)
---- Doing it progammatically in C -----
unsigned snoob( unsigned x)
{
unsigned smallest, ripple, ones;
// x = xxx011110000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x^ripple; // 0001 1111 0000
ones = (ones >> 2)/smallest; // 0000 0000 0111
return ripple | ones; // xxx1 0000 01111
}
# Find path in two nodes of Trees
Suppose you have a tree. A binary tree (for something like simplicity :p). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you "cant" change:
struct node{Data data; node *right,*left;};
what will you strategy be to tackle this problem.
To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).
Solution::
In this case say i was give 3 and 9 then
Two cases:: First case tree is BST
1. Find and store the path from root till 3 and 4 in 2(LOG(n)) time
now path is 5,4,3 and 5,8,9
2. Now since both the sublists are sorted using two pointers in one pass find the common node in the two lists from the last.
Say in the above example the common node is 5 so 4,3,5,8,9 is the path between 3 and 9.
Say in the above example the common node is 5 so 4,3,5,8,9 is the path between 3 and 9.
Step requires O(n) time complextiy.
So overall complexity is O(n)
