Array find the second highest value

Question

My array contains 10 integer values. Now I want to know the second highest number. I should not use java API. This question was asked by one interviewer. He wants logic. And his requirement is that I should not go through all the elements. Is there a way we can achieve results without going through? Herbalism means going through all the elements of an array. I've been thinking. Finally I gave up. If anyone can explain, it would be nice. And also I asked about sorting. He does not want to sort the array.

Answer 1

No, this is completely impossible. If you are not looking at all the data, you cannot know the second highest value.

You do not need to sort all the data, of course, which may be your translator, but you need to look at each element at least once. Each element has the ability to change the result, so it must be studied.

Answer 2

You cannot know the answer if you do not look at each element at least once. However, if that is not your problem, you can use a binary search tree:

In computer science, a binary search tree (BST), which can sometimes be called an ordered or sorted binary tree, is a node-based binary tree data structure that has the following properties: [1]

The left subtree of the node contains only nodes with keys smaller than the node key. The right subtree of the node contains only nodes with keys greater than or equal to the node key. Both left and right subtrees should also be binary search trees.
Source: http://en.wikipedia.org/wiki/Binary_search_tree

---

How do you find the 2nd largest item?

Well, from how BST is formed, you know that the largest element is the right-most (starting from the root of the node, take the right child until you have nowhere else to go).

---

Now, how to determine the second largest?
Well, this may not be the most effective approach, but allow it in cases:

• The largest node is the root of the tree and has no children. There is no 2nd largest element in your tree, because there is only node in your tree

• The largest node is the root of the tree (does not have the right child) - the second largest element is the largest element in the left subtree

• The largest element is not the root of the tree, not the leaf (has a left child) - the second largest element is its left child

• The largest element is not the root of the tree, but the leaf (has no children) - the second largest element - its parent

I am sure that now you can define a template and a simple algorithm: D

Answer 3

I know this was answered, but I was thinking about something like that.

double maxVal = array[0]; for (int i=1; i < array.length; i++) { if (array[i] > maxVal) { maxVal = array[i]; } } 

Technically, I am not moving the entire array, but n-1 of the length, because I assign the first value to the maximum value. I am sure there are other ways, but this is similar to what the interviewer might require.

Answer 4

The logic is so simple that I implemented it already in a single cycle.

I give you my program. If you want to use this algorithm, I can also provide you with this.

public static void main (String [] args) {

  int[] arr={0,12,74,56,2,63,45}; int f1=1,f2=0,temp=0; int num=0; for(int i=0;i<arr.length;i++){ num=arr[i]; if(f1<num) { temp=f1; f1=num; num=temp; } if(f2<num) { temp=f2; f2=num; num=temp; } } System.out.println("First Highest "+f1+" Second Highest "+f2+" Third "+num); }