- Here's a problem that occurs in automatic program analysis. For a set of variables x1; ...... ; xn, you are given some equality constraints, of the form "xi = xj" and some dis equality constraints, of the form "xi != xj" Is it possible to satisfy all of them? Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.
- What are the running times of each of these algorithms, and which would you choose?
- Algorithm A solves problems by dividing them into 5 subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
- Algorithm B solves problems of size n by recursively solving two subproblems of size n-1 and then combining the solutions in constant time.
- Algorithm C solves problems of size n by dividing them into nine subproblems of size n=3, recursively solving each subproblem, and then combining the solutions in O(n2) time.

- You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists.
- An array A[1....n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element.

The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?".

However you can answer questions of the form: "is A[i] = A[j]?" in constant time.

Technical & HR Interview Questions of Google,Microsoft,Yahoo and many more Companies.

### Some Interesting Algorithm Questions

Subscribe to:
Post Comments (Atom)

Ans 1 - I can think of a O(n^2) Soln. Construct an adjacency matrix and use Warshall's algo(not floyd Warshall) to convert it into path matrix - and if there occurs a situation, where you have to exchange a positive variable(+1 is =) with a -ve one(-1 mean !=), or vice versa, then it is not possible.

ReplyDeleteOther method could be by maintaining sets and combining them in equal to condition and after all equals verify the not equal tos, but i think that'll take more time.

Hi,

ReplyDeleteCould you give me the solution for problem number 1? I've been trying for the last few days and I don't seem to get forward.

Answers Please???????

ReplyDeletei have worked on these algorithms where can i

ReplyDeletecheck my answer ???

please

ReplyDeletethe solution

thanks a lot

for problem 1

ReplyDeletetwo adjacent elements in the array are same

1,2,2,3,3,4,5,6,7,8,9,10

=>1=2;2=3; and so on

now create a new array :

1,1,1,1,5,5,7,7,9,9; (union/find algo)

then say other array is

1,3,5,6

=>1!=3 AND 5!=6

just check for the indexes in the previous array, if they are same=> not possible.

Really interesting algorithm. i like it. Thank you.

ReplyDeleteUpcoming Bank Exams

1) A chess board is represented with the help of 2D Array (such as [0][0]......[63][63]). The game is going on and one opponent is left with only and only KING (it is not CHECKMATE yet). Write a program which takes current position of KING from the user and tells the all possible moves of the KING according to the position given by the user.

ReplyDeleteCan anyone answer this algorithm...please help me with this question...Monica..:)

Great and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai