Wednesday, 6 September 2017

Java Find the Next Greatest Element

final class DataSet {

    private final int x;
    private final int nextX;

    public DataSet(int x, int nextX) {
        this.x  = x;
        this.nextX = nextX;
    }

    public int getX() {
        return x;
    }

    public int getNextX() {
        return nextX;
    }

 
    public String toString() {
        return "x: " + x + " nextX: " + nextX;
    }

 
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + nextX;
        result = prime * result + x;
        return result;
    }

 
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        DataSet other = (DataSet) obj;
        if (nextX != other.nextX)
            return false;
        if (x != other.x)
            return false;
        return true;
    }
}

public final class NextGreatestElement {

    private NextGreatestElement() {  
   
   public static List<DataSet> getNextGreatestElement(int[] a) {

        final List<DataSet> dataSetList = new ArrayList<DataSet>();
        final Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < a.length; i++) {

            while (!stack.isEmpty() && stack.peek() < a[i]) {
                dataSetList.add(new DataSet(stack.pop(), a[i]));
            }

            stack.push(a[i]);
        }

        while (!stack.isEmpty()) {
            dataSetList.add(new DataSet(stack.pop(), -1));
        }


        return dataSetList;
    }
}

public class NextGreatestElementTest {

 
    public void test1() {
        int[] a1 = {2, 3, 4, 5};
        List<DataSet> ds1 = new ArrayList<DataSet>();
        ds1.add(new DataSet(2, 3));
        ds1.add(new DataSet(3, 4));
        ds1.add(new DataSet(4, 5));
        ds1.add(new DataSet(5, -1));
        assertEquals(ds1,  NextGreatestElement.getNextGreatestElement(a1));
    }
 public void test2() {
        int[] a2 = {3, 2, 1};
        List<DataSet> ds2 = new ArrayList<DataSet>();
        ds2.add(new DataSet(1, -1));
        ds2.add(new DataSet(2, -1));
        ds2.add(new DataSet(3, -1));
        assertEquals(ds2, NextGreatestElement.getNextGreatestElement(a2));
    }
}

No comments:

Post a Comment

test your brain

https://www.youtube.com/watch?v=bEU9dkOG7co&feature=youtu.be