Epic_coder
BAN USER- 0of 2 votes
AnswersGiven an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.
- Epic_coder in United StatesFor example: if input = {4,5,6,8,3,1,4,5,6,3,1} Result: {4,5,6}
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Sorry, I meant for each element that is 1. And yes, If we are scanning from left to right, we just need to check the right and bottom neighbor.
- Epic_coder October 17, 2012Idea:
iterate over each element in the matrix and
Do for each element that is 1
if all of its neighbors are 0, count=count+1,
otherwise, overwrite the value in current index by 0 and move to next index in the matrix.
count is the desired result.
Should work in O(n*m) time.
2
- Epic_coder October 17, 2012Scan from left to right and find the starting index of lexicographically largest string at each index. Interesting thing is that you could tell the lexicographically largest string at index i, based on the lexicographically greatest string at index i-1 with constant number of comparisons.
If A[i] is the current character and maxlex is the starting index of lexicographically largest string till A[i-1]. It gets a bit trickier when A[i]=A[maxlen].
Could be done in O(n) time and constant space.
What if there are multiple vertices with (v[j]+r)%k==0
- Epic_coder October 15, 2012Find the LCA of x and z(takes O(n)+O(n) time). There are 2 possibilites:
1. LCA is either x or z, in the case traverse the nodes from LCA to non-LCA node and if y occurs in the path return TRUE.(O(n) time)
2. LCA is neither x nor z. In this case, traverse the nodes between LCA and x and LCA and y, if you found y in any of them, return TRUE. (O(n)+O(n)) time
Overall time complexity=O(n)
Space complexity=O(1)
Works in O(nlogn)
- Epic_coder September 29, 2012Apply Djikshtra's algorithm and keep track of number of times you update the destination node.
- Epic_coder September 29, 2012Calculate the time at which maximum buses are at the platform(O(nlogn) by sorting). The number of buses present at this time is the number of platforms needed.
- Epic_coder September 29, 2012Apply the Floyd Warshall to find all pair shortest path and use optimal matrix for path reconstruction. Since this is a tree so there is just one and only path between 2 nodes. Print path for all the nodes that are at a distance K apart.
- Epic_coder September 29, 2012
RepI am a good learner
Repannavhedge4, AT&T Customer service email at ABC TECH SUPPORT
Hi everyone, I am from Worcester,USA. I currently work in the Argus Tapes & Records as Scientific illustrator . I love ...
You are right vincent, here is the modified approach:
- Epic_coder October 17, 2012iterate over each element in the matrix and
Do for each element that is 1
if none of the neighbors is 2, count=count+1 and overwrite the value in current index by 2
if at least one of the neighbors is 2 , overwrite the value in current index by 2 and move to next index
If we are scanning from left to right we just need to check right and bottom neighbor.
count is the desired result.
Should work in O(n*m) time.