Posts

Showing posts from 2010

Find 10 maximum integer out of 1 million integers.

You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..

Constraints- U can't Store Whole File in memory at one time.

finding the guilty managers

The FBI has surrounded the headquarters of the Norne corporation. There are n people in the building. Each person is either an engineer or a manager. All computer files have been deleted, and all documents have been shredded by the managers. The problem confronting the FBI interrogation team is to separate the people into these two classes, so that all the managers can be locked up and all the engineers can be freed. Each of the n people knows the status of all the others. The interrogation consists entirely of asking person i if person j is an engineer or a manager. The engineers always tell the truth. What makes it hard is that the managers may not tell the truth. In fact, the managers are evil geniuses who are conspiring to confuse the interrogators.

Under the assumption that more than half of the people are engineers, can you find a strategy for the FBI to find one engineer with at most n-1 questions?
Is this possible in any number of questions if half the people are managers?
Onc…

divide the array

How will you divide an array of approx 100 elements(integer) into two sub sets
of 50 each such that the difference between both the subsets is the
minimum possible .

What is the output?

What could be the output for following code segment and why:

int *ptr;

ptr = malloc(100);

ptr++;

free(ptr);

Last Ball

A bag has 20 blue and 14 red balls.Each time you randomly take two balls out of the bag.(Assume each ball has equal probability of being taken).You do not put the two balls back.Instead,if both balls are of same color,you add a blue ball to the bag;if they have different color,red ball is put in the bag.Assume that you have infinite supply of red and blue balls,if you keep on repeating this process ,what will be color of last ball left in the bag.Will the case remains same if we have 13 red balls????

finding odd one out of 12 balls in 3 weighings

The problem is you have 12 identical balls (of any kind), one ball either
lighter or heavier than the other 11. A scale is provided to you but only
three weighs are allowed. How can you possibly figure out which is the odd ball?

Overlapping intervals

Once again this is an interview question that was asked to me at Adobe.

You have N pairs of intervals, say integers. You're required to identify all intervals that overlap with each other in O(N logN) time. For example, if you have

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.

Finding a Circle From 3 Points

Given 3 points which are not colinear (all on the same line) those three points uniquely define a circle. But, how do you find the center and radius of that circle?
Propose a simple algorithm for this.

point of intersection

One of the most common tasks you will find in geometry problems is line intersection. Say we are given two different points, (x1, y1) and (x2, y2) for both the lines.How will you find the point of intersection of two lines.

Casino game

A casino offers a card game using a normal deck of 52 cards.The rule is that you turn over two cards at a time.If both of them are red,they go to your pile ;if both are black they go to dealer's pile;and if one black and one red they are simply discarded.The process is repeated until you go through all the 52 cards.If you have more cards in your pile you will get $100,otherwise(including ties)you will get nothing.The casino allows you to negotiate price you want to pay for the game.How much you would be willing to pay for the game.

sorting result array

We have an integer array that is sorted in ascending order. We also have 3 ints A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example:

Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1

Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

Time complexity :o(n)
no extra space

in-place merge sort

Given two arrays, larger one has enough space in the end to hold
the smaller array. Both the arrays are sorted. Merge the smaller one into larger
one so that ending array is sorted.

eg:
1, 3,55,66,77,_,_,_
5,9,20

output:
1,3,5,9, 20,55 66 ,77

The Fox and The Duck

A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?

Burning ropes

You have two ropes,each of them takes 1 hour to burn.But either rope has varying density so there is no consistency in time that it takes to burn for different section.How do you use these two ropes to calculate 45 minutes.

A Needle in the Haystack

The program has to detect all occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below.

Input

The input consists of a number of test cases. Each test case is composed of three lines, containing:

the length of the needle,
the needle itself,
the haystack.

Output

For each test case your program should output all positions of the needle's occurences within the haystack.

eg:
Input :
2
na
banananobano

output:
2
4

rank of node

Propose a tree based data structure to identify a node with nth rank with maximum efficiency .

[MS][Adobe]Divisible by 3 or not

Given an infinite stream of bits with the bits being appended at the highest significant position. give an algorithm to to say whether the number formed by using the sequence of bits that had been processed till then, is divisible by 3 or not?

find the unique element

You have an array consisting of 2n+1 elements, n elements in it are
paired, i.e they occur twice in the array, however there is one
element which only appears once in the array. You need to find that
number in a single pass using constant memory,assuming that all are
positive numbers.

probability of occurrence

This question was asked in the adobe interview:
void foo1()
{
  if(A < B)
    Then { }
  else
   if(C < D)
     then foo2()

} How many time foo2 () would get called given
A < B 25% of the times and C < D 75% of the times and foo1 () is called
5000 times 

Door to offer

You are facing two doors.one door leads to job offer and second to rejection.In front of either door is a guard.one tells lie and other truth.you can ask only one (yes/no)question to only one guard.Assuming that you want to get the job what question you will ask the guard.

polite numbers

In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers.

The first few polite numbers are
3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17,...

for instance, 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8. The number of ways that a number can be written as the sum of two or more consecutive numbers is its politeness. Any number that is a power of 2 cannot be written as the sum of two or more consecutive numbers; such a number has a politeness of 0, and is thus impolite.

write a program that calculates all the ways that a number can be written as the sum of two or more consecutive numbers and generate those sets.

comma operator

Again one of the confusing topic in c,comma operator.

intmain()