dev
BAN USER- -1of 1 vote
AnswersGiven a doubly linked list with a data item, a previous and a next ptr along with another pointer "child" that may point to the head of another doubly linked list of same type(it will lead to a general tree type of structure) or it may be null. Flatten the tree into a linked list... minimum space and time complexity(order n). The doubly linked lists's head and tail are given.
- dev in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space
- dev in India
I cud think of this algo..Do two inorder traversals, one in the usual (descend to the left
before descendung to the right) direction and the other in the
reversed(descend to the right before descending to the left)
direction.and compare the sum with x..
But i am unable to code it properly..(in C)
Need help| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersu have to perform following tasks in O(1) time
- dev in India
1.)insertion
2.)deletion
3.)searching
no range of input numbers is given
wat data structure will you use?
if u use hashing wat will be the key and value pairs??| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersSuppose here are n processes in the system and each one needs k instances of a resources to complete. What would be the minimum number of resources that you should keep in the system to ensure no deadlock in the system.]
- dev
a.n*k
b.n*k-n+1
c.n*k+1
d.n*k*k
e.None of the above| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Operating System - 0of 0 votes
AnswersFind longest interval:-
- dev
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]| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 0of 0 votes
AnswersLets assume we have a rat maze as represented by the following NxM matrix
- dev
where S is the start location and F is the end location.
S 0 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 1 1 1 F
The idea (as with any rat maze) is to traverse from S to F. The matrix can
have only 0 and 1 as values. 1 represents a path that can be taken and 0
represents a blocked path.
We can make the following assumption:
S will always be (0,0) and F will always be (N,M).
As seen from above, there can be many paths from S to F.
How do we find the shortest (or longest) path from S to F without actually
traversing all the possible paths.
Please post (with proof/explantion) your algorithms. Also can you then think
of ways to optimize the algo?| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 0of 0 votes
AnswersWrite a "C" function,
- dev
int AddOvf(int* result, int a, int b)
If there is no overflow, the function places the reusltant
sum a+b in "result" and returns 0. Otherwise it returns -1.
The solution of casting to long and adding to find detecting the
overflow is not allowed :-)| Report Duplicate | Flag | PURGE
Adobe Developer Program Engineer Coding
Was this for hyderabad centre or blore?
- dev February 28, 2012