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()];
}
@ 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'.