## bharat

BAN USER- 0of 4 votes

AnswersGiven a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1.

- bharat in United States

Ex :

3 5 7 3

4 5 8 1

6 4 5 2

here sequence is

3

4 5

4 5| Report Duplicate | Flag | PURGE

Amazon SDE1 - 12of 12 votes

AnswersGiven 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree.

- bharat in India

Ex:

2 3 1

2 1 3

will construct the same tree

A1[]={2,1,3}

2

1 3

A2[]={2,3,1}

2

1 3| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer - 3of 3 votes

AnswersThere are N floors and N persons each one is tagged with some random unique number between 1 to N(represents floor number).

- bharat in India

We have a lift which can accommodate one person at a time. Every person is in some random floor.

Initially lift is at floor 1 and all floors have single person. Problem here is.. we have to move the persons to their corresponding floor with minimum travelled distance of lift.

Restriction : Lift can have at most one person at a time.

One more thing we have to think of is .. At a time, we can keep more than one person in a floor.. means, we don't necessarily need to take the person out from the floor if we keep another person on the same floor.| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersAn array of building coordinates (x-axis point from origin,height,width) in units were given as an input. Buildings can overlap. We have to give the side view as an answer. Input will be given in sorted order based on x-axis point.

- bharat in United States

Ex : Draw rectangles based on the given co-ordinates to understand the problem better.

i/p : (5,10,25),(10,20,15),(15,5,5)

o/p : 5R 10U 5R 10U 15R 10D 5R 10D

means draw line 5units Right 10units Up 5 units Right ...

here

R-right, U-up , D- Down

the o/p should be in such a way if we follow that, we should be able to draw side view of those buildings.

Expected better than O(n^2) solution.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

AnswersMatrix of size MxN filled with characters is given. Assume that we have a dictionary of words and searching whether a word present can be done efficiently. Find all dictionary words. A word can traverse in any direction, but the position should not be repeated for a particular word.

- bharat in India

Ex: A word can occupy (1,1),(2,1),(2,2) positions in matrix.

Words can overlap(Ex1: understand--> under, stand , Ex2: mismatch,mistake,match,take)| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm

The question is to find the maximum steps we can go.

If there exists an integer solution to quadratic equation(as you mentioned), then we can skip the first step to escape on landing kth step.

Then the solution would be something like follows.

1+2+...x = k --> solve this, if there exists integer solution, answer would be n(n+1)/2 -1 else, n(n+1)/2

Say n is the number of highly rated books we are looking for and V is the number of vertices, E is the number of edges in the graph.

While running BSF, we should maintain minHeap(at max size of n). When ever we encounter a book with rating more than the min of heap tree, replace it with top.

Complexity: O((E+V)logn)

@CollinSchupman : read the answer correctly... "keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element" --> while inserting '6' , you pop till stack top is 10, and last poped element is 5, make '6' as right child of '5' and push '6'.

- bharat December 15, 2013quick sort works .. but there is a catch ..

For the first time, we take first element as pivot from both arrays and divided the arrays..

For the 2nd iteration onwards, we have to take the same element as pivot in both arrays .. this needs O(n) time or we have to do some kind of pre-processing ...

Second approach is not accepted as it was stated in the question itself that we should give answer without constructing BSTs.

@Gabriel: your idea is good .. but there is a catch..

In the above example, it worked because , all the persons are needed to move in continuous floors. What if they are not continuous ?

Ex: F[1]=P[2],F[2]=P[6],F[6]=P[1] etc....

here the above one is a connected component .. as per u'r algo .. 3 lift movements are sufficient.. but actually ..1+4+5=10 lift movements(Initially lift position is at Floor 1).

small modification is needed ..

if we can't able to find a word at some point of time, we have to discard the latest word which we committed ....and go with other alternatives ... recursion is the best way to do this...

And for searching whether the word is present with some letter or not, trie is the best suitable data structure(searching can be done in amortizedO(1))....

If someone gives best psuedo code .. that will be appreciated :)

@EJ : condition mid==0 is needed ..

take this case .. low=0,high=1 ==> mid=0 and a[mid]==1 then this condition is needed.

@srikath.mujjiga : This works with one element also.. when there is single element .. a[]={0} or a[]={1}..

low=0,high=0, mid=0.

In first case,

binSearch(a, mid + 1, high); will be executed and return -1.

In second case,

if (a[mid] == 1 && (mid == 0 || a[mid - 1] == 0)) will be true and return index 0.

@Nbob : ideally we should not maintain m_level in class...

we can print level by level without maintaining this also ..

push a dummy node each time u push all the friends of a member node.... while pop() ing, when ever we come across dummy node .. means we have covered a level ...

yes, its just intersection which takes O(n) where n is the number of friends each one has.

All nodes are white colour.

Mark each friend of A as black and while visiting the friends of B, if any one the friends is black, then he/she is a mutual friend of both. ---> O(n) where n is avg. number of friends one has.

This is just sorting algo (descending order ).. the only modification we need to do is .. while comparing 2 integers , we have concat one with other and compare ....

ex: {9,10} --> then while comparing 9 and 10 .. we have concat these two...910 > 109 ... so 9 comes before 10

Ex: {9,900}--> 9900>9009 --> 9 comes before 900..

Ex {10,107} --> 10710 > 10107 --> 107 comes before 10....

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Treat the given matrix as graph where a point will have a connection to its neighbours iff the adjacent point is 1. Using BSF/DSF we can find the path from given point to other point.

- bharat September 22, 2015