Algorithm interview questions – page 19

If you click on any orkut member's name you will notice the relationship graph for both of you indicating through whom you are interconnected or in certain cases you won't get this path.

Give an example of an algorithm with time complexity O(1/n)?

Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, cr...

Give an O(n log n)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers((Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a ...

Given 2 numbers in base 10 with digits given in MSB to LSB order in a singly linked list, add the two numbers and return the result as a linked list in MSB to LSB order. Do this in < 4n operations on the given linked lists (including traversals...

Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined ...

For a given file(80 column and 100 lines) find in how many lines a word occur. the answer is like:

You have a fair coin. Make it unfair with win and loose probability p and (1-p) respectively, where p is greater than 0 less than 1 tryv to optimize asmuch as possible write maths behind this clearly

Stock market - There is a company holding shares for over 3000 years and the share value has fluctuated almost every day. Find out the MAX LOSS in it's entire history (MAX LOSS means - on a date x, buy the share for a bigger value...and on the dat...

Write a function that counts the number of words from a given string. Example: "I like this page so much" should give us 6 total.

There is a function which returns 0 or 1. You need to pass each and every element of the array one by one to that function and depending on the return value, you need to store all the numbers in such a way that all the true values should appear fi...

Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

You are given an array of N integers. ur job is to find maximum and second maximum element in N+logN comparisons.

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). Full points are given for the solution bearing efficiency O(log n). Partial po...

Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.

Given an array which has all the elements occuring thrice except one number which occurs only once. Find the number?

Write the code/algorithm to find the k-th Smallest Element in the Union of Two Sorted Arrays.

Implement strstr O(N) solution needed

Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a di...

There are N nuts and N bolts, all unique pairs of Nuts and Bolts. You cant compare Nut with Nut and a Bolt with Bolt. Now ,how would you figure out matching pairs of nut and bolt from the given N Nuts and Bolts.

Given location of huge number of points (you decide the data structure to represent them). Write a function that returns the number of points that are with distance D of a given point P. Write function, complete with what data structures, functi...

You are given a set of boxes b1 to bn. Each box bj has an associated width wj , height hj and depth dj. Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi, the 2D base of bi m...

Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.

A helicopter drops two trains, each on a parachute, onto a straight infinite railway line. There is an undefined distance between the two trains. Each faces the same direction, and upon landing, the parachute attached to each train falls to the gr...

Given an input string S write a function which returns true if it satisfies S = nT. Basically you have to find if a given string can be represented from a substring by iternating it "n" times. n >= 2

Given a series A,B,C ...Z, AA, AB,AC,AD...AZ,BA,BB...BZ,CA...(Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series. & also vice versa if given string prints its co...

Given a string containing multiple words such that spaces between words is missing. Also, you have a dictionary containing valid words.

A game. 7 people in a circle, the third one will be deleted in each round. Use loop or recursive. How many loop and which data structure you will use to store these data?

How will you design an LRU Cache?