## 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

This is what I told in an interview ..

maintain an array of 256 Nodes.

typedef struct _Node {

bool flag;

int position;

}Node;

while traversing the string,

if flag == false

then make flag=true; and fill the position of that character in the string.

when ever u encounter the repeated character, calculate the length of the unique_character_substring and start traversing string from the previous position of that repeated charater +1 and make visited array[256] flags as false.

maintain a bool visited array of 256 size.

bool visited[256]={0};

remove_duplicates(char* input)

{

int tial=0;

int len=strlen(input);

for(int i=0;i<len;i++)

{

if(visited[input[i]] == 0) {

input[tail++] = input[i];

visited[input[i]-'a'] = 1;

}

}

input[tail]='\0';

}

@ explorer : As per my understanding, u initialise d[][] with some high values.

1 50 1 50

50 1 50 1

50 1 1 50

50 50 50 1

| |

V

1 51 2 51

51 52 101 52

51 52 3 52

51 101 52 52

actual ans is (0,0)->(0,2)->(2,2)->(2,1)->(1,1)->(1,3)->(3,3) = 7.

u'r algo fails when there is need to go back.

Find sum of elements from A[i][j] position to A[i][j+k] as sum[i][j];

sum(0,0) = A[0][0] to A[0][k-1];

sum(i,j) = sum(i,j-1)-A[i][j] + A[i][j+k]; 0>= i > m && 0>= j > n-k-1

Find sum of elements of submatrix of size k.

ksum(i,j) represents sum of submatrix of from A[i][j] to k x k subarray.

ksum(i,j) = ksum(i-1,j) - sum(i,j) + sum(i+k,j);

only corner case I might have missed .like k-1 or k+1 ..

Finds Sliding window maximum ..

void maxSlidingWindow(int A[], int n, int w, int B[]) {

deque<int> Q;

for (int i = 0; i < w; i++) {

while (!Q.empty() && A[i] >= A[Q.back()])

Q.pop_back();

Q.push_back(i);

}

for (int i = w; i < n; i++) {

B[i-w] = A[Q.front()];

while (!Q.empty() && A[i] >= A[Q.back()])

Q.pop_back();

while (!Q.empty() && Q.front() <= i-w)

Q.pop_front();

Q.push_back(i);

}

B[n-w] = A[Q.front()];

}

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

Open Chat in New Window

@ Anonymous: are u considering the first non-repeating character ?

- bharat November 23, 2012U are just saying the first non-repeating character in alphabets. I think, the question is about first non-repeating character in string.

Ex: aacdcb --> ans : 'd' not 'b'.