CareerCup

This can, as always, be solved in multiple ways.

Solution 1: Simply sort the n elements array and pick the (n-1)th element. O(sorting algo = nlogn)

Solution 2: This is a job interview question - in other words from a practical point of view the solution you come up with should be easily extended to finding any k-th largest element (instead of just 2nd)
So here is my solution for that:

I) Do basic sanity checks and check for array.size >= k. If <k then notify that there is no answer.
II) Take first k elements and then create a min-heap. From k+1 th element onwards, check with top value in heap, if it is smaller than top min-heap value, there is no way it can be in the set of k largest values in array - so discard it.
If it is greater than min-heap top value, then we got new set of k largest elements (from the elements traversed so far). So remove the min element in heap and add the new element (and heapify). Keep doing this until end of array. The min element of the heap is the answer.
Advantages: Everytime we check for min value and discard, we are avoiding checking with all other (k-1) values. Even in worst case we ended up having a value bigger than min every time (if input array is in ascending order), our insertion is now reduced to log k. So complexity = O(n log k)

Standard question. Solved in chapter 11 CLR.
Best case complexity is still O(n), but you can optimize using two variables.

public static int GetSecondLargest(List<int> lst)
        {
            int first = int.MinValue;
            int second = int.MinValue;

            foreach (int i in lst)
            {
                if (i > first)
                {
                    second = first;
                    first = i;
                }
            }

            return second;
        }

Using Tournament tree would be O(n) time complexity but the number of comparisons would be minimum..

public static int GetSecondLargest(List<int> lst)
{
	if (lst.length <2)
	{
		throw new Exception("List too small to find second largest");
	}
	int largest = 0; secondLargest = 0;
	if (lst[0] > lst[1])
	{
		largest = lst[0];
		secondLargest=lst[1];
	}
	for (int i=2; i <list.length; i++
	{
		if (lst[i] > largest)
		{
			secondLargest = largest;
			largest = lst[i];
		}
	}
	return secondLargest;
}

Sorting is not an option here.
1. One option is to look for min element, and then again look for min which doesn't equal to found one. Complexity – exactly 2*N comparisions
2. Keep two variables, and compare each element to each of them - still 2*N comparisons
3. Keep two variables as min1 and min2, and then proceed through array as follows – pick 2 elements from array, compare them (1 comparison), and then compare the smallest of those with min1 and min2 (another 2 comparisons) . In this case we will have N/2 * 3 = 1.5*N comparisons. Still O(N), but I guess this is what expected from this problem.

/*
	Question ID: 18078662
	
	Write a code to print the second largest element in a list
	Shortest possible complexity.
	
	Time Complexity: Linear -> O(n)
*/

public class sol18078662{

	static int length;
	static int[] a;
	static int first;
	static int second;

	public static void main(String[] args){
		length = args.length;
		a = new int[length];
		for(int i = 0; i < length; i ++){
			a[i] = Integer.parseInt(args[i]);
		}
		first = a[0];
		second = a[1];
		for(int i = 2; i < length; i ++){
			if(a[i] < second)
				continue;
			if(a[i] > first){
				second = first;
				first = a[i];
				}
			else
				second = a[i];
		}
		System.out.println(second);
	}
}

def get_second_number(arr):
	if (len(arr) > 2):
		a, b = max(arr[0], arr[1]), min(arr[0], arr[1])
		for x in arr:
			if x > a:
				b, a = a, x
		return b
	else:
		return min(arr)

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <list>
 
int second_largest(std::list<int> list){
    int largest = 0, second_largest = 0;
    for(auto it = list.begin(); it != list.end(); it++)
        if (second_largest < *it){
            if (largest <= *it){
                second_largest = largest;
                largest = *it;
            }
            else{
                second_largest = *it;
            }
        }
    return second_largest;
}

int main(){
    srand(time(NULL));

    std::list<int> my_list;
    for (int i = 0; i < 10; i++){
        my_list.push_back(rand() % 10);
        std::cout << my_list.back() << " ";
    }

    std::cout << "\n" << second_largest(my_list) << "\n";
    return 0;
}

It can be done in n+log n-2 comparisons. This question is also in CLRS.

Think of elements as competitors, and a tournament is going to rank them.

First, compare the elements, as in the tree

|
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.

The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

from stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

package sy;

public class Solution {
public static void main(String[] args) {
int a[]={3,2,6,4,49,7,43,68,7,3};
find_2th_largest(a);
}
public static void find_2th_largest(int input[])
{
int max=Integer.MIN_VALUE;
int second_max=Integer.MIN_VALUE;
for (int i = 0; i < input.length; i++) {
if(input[i]>=max)
{
second_max=max;
max=input[i];
}
}
System.out.println(max);
System.out.println(second_max);
}
}

package sy;

public class Solution {
public static void main(String[] args) {
int a[]={3,2,6,4,49,7,43,68,7,3};
find_2th_largest(a);
}
public static void find_2th_largest(int input[])
{
int max=Integer.MIN_VALUE;
int second_max=Integer.MIN_VALUE;
for (int i = 0; i < input.length; i++) {
if(input[i]>=max)
{
second_max=max;
max=input[i];
}
}
System.out.println(max);
System.out.println(second_max);
}
}

import java.util.TreeSet;

public class Tree {
	public static int getKthLargest(int k){
		TreeSet<Integer> tSet = new TreeSet<Integer>();
		for(int i=0;i<20;i++){
			int number = new Double(Math.random()*100).intValue(); 
			tSet.add(number);			
		}
		System.out.println(tSet);
		for(int i=0;i<k-1;i++)
		tSet.pollLast();
		return tSet.pollLast();
	}
	public static void main(String[] args) {
		System.out.println(Tree.getKthLargest(2));
	}

}

Two answer suggestions.
answer1. Sort the array asc order, get the n-2th element.
Answer2. Two variables: largest and secondlargest. Assign them with 1st element and 2nd element of the array respectively if 1st element is greater than 2nd else vice versa.
Now loop from 3rd element onwards till end of the array.
For each element, Case 1:If current element is greater than largest, then replace secondlargest element with largest and replace largest by current element.
Case2: If current element is greater than secondlargest but less than largest, then replace secondlargest with current element.
O(n) complexity.

It can be done in O(n) time complexity and O(1) space complexity.


public int findSecondMax(int[] nums){
if(nums.length<=1){
System.out.println("invalid input");
}

int lower =nums[0];
int higher =nums[1];
for(int j=2;j<nums.length;j++){
if(nums[j]>lower && nums[j]<higher){
lower=nums[j];
}else if(nums[j]>higher){
higher=nums[j];
}
if(lower<=higher){
System.out.println("2nd lowest"+lower);
}else{
System.out.println("2nd lowest"+lower);
}
}


}

public class SecondLargest {
	public static void main(String[] args){
		int[] array = {1,5,8,9,3,4,10,34, 33, 44};
		int f1 = array[0];
		int f2 = array[1];
		if ( f2 > f1){
			int tmp = f2;
			f2 = f1;
			f1 = tmp;
		}
		for ( int i = 2; i < array.length; i++){
			if ( array[i] > f1){
				int tmp = f1;
				f1 = array[i];
				f2 = tmp;
			}else if ( array[i] > f2){
				f2 = array[i];
			}
		}
		System.out.print("Second Largest : "+ f2);
	}

}}

use quicksort partition pass

Why can't we use MaxHeap, where the second largest element will be one of the roots' immediate child.