CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Previous large element


Forum Post 4 Answers Previous large element

Hi ,

Given a sequence of n numbers, {a1; a2; · · · ; an}, for each element
ai
, 1 ≤ i ≤ n, nd the index of the rightmost element inside {a1; a2; · · · ; ai1} whose value is
strictly larger than ai
. If no element is larger than ai then output 0. In other words, nd for
each i
pi = max{j|0 ≤ j < i; aj > ai};
in which assume a0 = ∞

algorithm should work in O(n).

How to proceed?

What I thought : it seems to me as a upper triangular matrix and finding max for each column..
Correct me if I am wrong but how to do in O(n)?

Regards

Abhinav

 - abhi1988srivastava September 02, 2013 | Flag |


Comment hidden because of low score. Click to expand.
0
of 0 vote

it seems you copy pasted this from somewhere else. It's not properly formatted and it's not clear what the question is about.
Try to be a bit more clear about the objective and give one or 2 examples of input and output

- Miguel Oliveira September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for the bad formatting,

What I want to do is

Suppose an array given is

79 23 1 11 19 58 2

for each element , I want to find the left most element greater than that element
So,
for 23 it is 79
for 1 it is 23
for 11 it is 23 and so on..

I thought of iterating from the end and finding the element greater(naming it max) than last element and then all the elements between max and last element will have their max element as max. So less number of comparison.

Please correct me if I am wrong ..

Thanks for the help.

- Abhinav September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In your example it seems you're not finding the leftmost element greater than number i, but the number at index j closest to i.

In this case, I know how to do it in O(log n) for each i, giving a total of O(n log n). Are you sure it's possible to do it in O(n)? It seems unlikely to me.

- Miguel Oliveira September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like an algo assignment question. Do it yourself dude!!

- Mike September 05, 2013 | Flag Reply




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More