perlscar
BAN USER- 0of 0 votes
AnswersAssume there's a website with 8 pages. We are interested in calculating the most frequently visited page sequences of size 3( e.g 1->5->2 ).We are given a log file that has several rows for a particular time period. Each row has following info : time, UserID, page visited
- perlscar in India
Suggest an optimal algorithm to find the most frequest visited page sequence of size 3.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersGiven an initial word and a final word(both same length) suggest an algorithm to find if there were some intermediate steps to convert the initial word to the final word.
- perlscar in United States
The word at every step should be just one character different from the previous word and should be a valid dictionary word.( E.g TAP -> TOP is allowed, since the only difference from previous word is 2nd character and TOP is a valid dictionary word , but TAP -> TOO isn't allowed since 2 characters are different).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
@kkr.ashish : Just give me an example of a tree which has common path for all array elements and array size > 2.
PS : I think with your assumption of path, there can't be common paths for all array elements. That's because, for the 3rd element to have same path we will need its immediate parent to be parents of 3 nodes, which is not possible in "Binary" search tree
@kkr.ashish : Well, with your assumption you will never have same path for any array of size greater than 2. So, by same path I assume, that path from root to lowest node in the path such that no group element is present in the path.
For instance,
Group array : { G1, G2 , G3, G4 .... }
path to some element GN : A->B->C->D->G3->F->G1->GN
then I assume path is : A->B->C->D
If you think my assumption is wrong, Please give an example where the array size is more than 2 and all elements have common path.
Time Complexity : O( M * N )
Step 1 ) Store sum of each row and each column.
Mark all row/columns with sum 0 or 1 as ZERO or ONE.
If sum is 1, store what index had element 1.
Step 2 ) Iterate through all rows marked ZERO/ONE.
a) If a row is ZERO and a column marked ZERO/ONE exists, Bingo! we have our pair.
b ) If a row is ONE then check if the column corresponding to stored index is marked ZERO/ONE. If yes, we have our pair
keep repeating this process upto last row. if no success, no such row/column exists.
level 1: A
level 2: B x
level 3: x C x x
level 4: x x 3 5 x x x x
the array: [3,5]
In this case you algorithm would have both flags set for "C". Hence would result in wrong answer.
Here path for 3 : A->B->C
Path for 5 : A->B->C
So both have same path, answer should be yes.
@Erasmus and - @mingjun : Can you please answer what happens with the tree - mingjun has given. Does it have common ancestors or not ? If you feel the answer is NO, please give an example of some BST with the same group 'g' for which you would answer YES.
As far as I am concerned, my answer would be YES for this case, and my suggested algorithm would result with the same answer.
Can you explain what is exactly meant by same path here ?
I have presumed that we are comparing the path from root to the point below which some group element is present along the path.
So essentially the path must not have any group element in it.
For instance :
level 1: A
level 2: B x
level 3: x G1 x x
level 4: x x G2 G3 x x x x
In this tree I would say that the group elements have a common path ( A->B ).
This problem may be solved without sorting.
Let's call the size of group 'g' G(n) and size of BST as N.
Step 1) Time : O( G(n) )
Find the max and minimum element in the group 'g'.
Step 2) Time : O( log(N) )
Search for min and max elements of group g (Previously calculated) in the BST. Verify if these have the same path, if they do, all the intermediate elements will also have the same path.
Here's my solution using basic DP :
I would add the following to give complete solution :
int& getMaxCount(int* a, int N, int M){
int max = 0;
for(int i = M-2 ; i >= 0 ; i--)
for(int j = N-2 ; j >= 0 ; j--){
if( a[i][j] == 1 ){
a[i][j] += a[i+1][j]>a[i][j+1]?a[i+1][j]:a[i][j+1];
}
if( a[i][j] > max )
max = a[i][j];
}
return max;
}
This is a dynamic programming problem.
My solution : I create another array of same size, initialize the last row with the same values. Now we traverse rows bottom up, for each row updating the values depending upon the values in the next row. Finally the maximum value in the top row is our answer. Here's my code for it :
int findMaxSum(int* a, const int& N){
int b[N][N];
//initialise the last row with values from original array
for(int i = 0 ; i < N ; i++){
b[N-1][i] = a[N-1][i];
}
//keep updating the values depending upon the values in
//the next row
for(int i = N-2 ; i >= 0 ; i-- )
for(int j = 0 ; i < N ; j++ ){
b[i][j] = max ( a[i+1][j-1] , a[i+1][j] , a[i+1][j+1] );
}
int max = b[0][0];
for( int i = 0 ; i < N ; i++){
if(max < b[0][i] )
max = b[0][i];
}
return max;
}
We can calculate the length of the circular list in O(n) time. Then do a O(n^2) comparision to check for duplicates. Here's my code for it :
bool hasDuplicates(node* slist){
node* start = slist;
node* n = slist;
node* m;
int len = 0;
//Calculate the length
if(n != NULL)
count++;
//Calculate the length
while(n->next != start){
count++;
n = n->next;
}
n = slist;
m = slist;
// check if some dupliacte is present
for( int i = 0 ; i < count ; i++){
m = n;
for( int j = i + 1; j < count ; j++){
m = m->next;
if( m->val == n->val)
return true;
}
n = n->next;
}
//Duplicate not found
return false;
}
Start a BFS from the given node as source node. The first leaf node we encounter will be the nearest leaf.
- perlscar September 12, 2013