1

One thousand(1000) elements are entered into an array (no memory constraints). As we know, while entering the elements we can update the max out of entered values by a check whenever we enter a value.

But imagine if the position of max value is somewhere around 900

If I remove 200 elements from positions 800 to 1000, without doing any more comparisons, we should have the next max value. Will that mean while entering the data we should have a plan to organize the data in some way to get the max value out of the remaining data?

Deleting and inserting will keep on happening, but we should have max value updated in less time with less no of steps. (Using stacks might help is the clue that the interviewer gave me). Anyone please help me.

Improve this question
5
  • 1
    Use binary max-heaps! Commented Jun 7, 2015 at 5:29
  • 2
    This is eerily similar to a shrunken version of Finding maximum value. The main difference is that the other question is dealing with 1 crore (10 million) elements and deleting 20 lakh (2 million) of the elements. Commented Jun 7, 2015 at 6:14
  • Can we assume that deletions/additions are only allowed at the end of the array, or could you, for example, remove elements 850 to 950 from the array of 1000? Commented Jun 7, 2015 at 7:05
  • Suppose you have read 1000 elements in sequence (numbers 0..999) and you delete elements 700-899. Are the elements that were read as 900-999 now numbered 700-799? Are new elements still being added given numbers 1000+ or 800+? (That is, do you identify the next 100 elements as 1000..1099 because that was their 'record number' in the source data, or do they become 800..899 because that's where they land in the array?) Commented Jun 7, 2015 at 16:23
  • @JonathanLeffler The elements will be shifted once you delete something in the middle.The elements at index 900-999 will be shifted to 700-799. Commented Jun 13, 2015 at 3:08

3 Answers 3

Reset to default
1

A maximum heap may work in your case. But since 1000 is really small, you may don't need something complicated.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

This 1000 can go to 1 crore.
Could you please explain me how to use maximum heap. I am new to computer science subjects.
I'm curious about how you'd handle the bulk deletion of a range of values from the input sequence.
@RajaSekharReddy Let's make it clear. deletion and insertion only happen at the end of the array?
@XiaotianPei Not only at the end of array, it can happen from any position to any. Total deletion can also happen.
|
0

Create a tree structure upon the array. In each node keep the range and maximum of the subtree. On removing/inserting update the maximum in affected nodes bottom-up.

Improve this answer

Comments

0

You should use max heap data structure. The property of max-heap is that you can get the max value in O(1) time. Whereas each insertion and deletion will take O(log(n)) time. For more info check here

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.