gistfile1.txt

/**
 * Created by tyson on 14/1/2016.
 *
 * Process:
 *  My initial thought was to use the LinkedList API (java.util.LinkedList)
 *  This was a problem though, as the we need a singly linked list,
 *  java.util.LinkedList has the operations of a doubly linked list.
 *  So I created my own singly LinkedList for this assignment. 
 *  
 *  The method I chose for finding the kth node from the end of the LinkedList 
 *  takes a follow-the-leader approach to find the appropriate node in just one traversal.
 *  I think this approach is the most efficient, as it only requires one traversal of the 
 *  LinkedList.
 *  
 * Tests:
 *  I chose to test some edge cases and out-of-bounds cases in addition to expected input.
 *  Tests are implemented with a mock use case in the main method of this file. 
 *  More testing should be performed on large input sizes using an official unit testing framework like junit.
 *  
 * Other approaches:
 *  I could also have done multiple passes through the list to first determine the size,
 *  then traverse to size - k (input value) to retrieve the appropriate item. 
 *  This approach would still require at least one pass through the list but could require
 *  2 traversals through the list. The approach I chose was more efficient in terms of expected time complexity.
 *
 * Assumptions:
 *  I wasn't sure what data time would be used for the data of each node,
 *  the linkedlist below expects string data but could easily be modified to 
 *  accept any type of data
 *  
 *  I wasn't sure what to return in certain out of bounds cases, 
 *  the linkedlist below will return the head of the list in cases where 
 *  a user tries to pass a value of k which is greater than the length of the list
 *  
 *  Similarly, in cases where a user tries to pass a value of k which is 
 *  negative, the last list item will return.
 */

public class SinglyLinkedList {

    private Node first;

    private static class Node {
        private String data;
        private Node next;

        Node(String data) {
            this.data = data;

        }
    }

    public void add(Node node) {

        if (first == null) {
            first = node;
        } else {
            Node store = first;
            while (store.next != null) {
                store = store.next;
            }
            store.next = node;
        }
    }

    // The follow-the-leader algorithm allows us to find the 'from' item with only one list traversal
    public Node fromLast(int k) {
        Node lead = this.first;
        Node follow = this.first;

        for (int i = 0; i < k; i++) {
            lead = lead.next;
            if (lead == null) {
                // What should I return if the integer is out of bounds?
                return this.first;
                //throw new NullPointerException("Out of bounds");
            }
        }

        // The lead position will continue on the end
        // The follow position will reach the appropriate node, by following the lead.
        while (lead != null) {
            // If the follower runs out of space, it should reserve its position
            // Consider the case where n = 0 or a negative number, we want to return the last node.
            if(follow.next != null) {
                follow = follow.next;
            }
            lead = lead.next;
        }

        return follow;

    }

    public static void main(String[] args) {

        SinglyLinkedList linkedlist = new SinglyLinkedList();

        linkedlist.add(new Node("head"));
        linkedlist.add(new Node("tail1"));
        linkedlist.add(new Node("tail2"));
        linkedlist.add(new Node("tail3"));
        linkedlist.add(new Node("tail4"));

        // Out of bounds assumption
        // Return root if number is out of bounds
        Node outofbounds = linkedlist.fromLast(6);
        System.out.println("Expected Value head, return value is " + outofbounds.data);

        // The second to last output
        Node fromLast= linkedlist.fromLast(2);
        System.out.println("Expected Value tail3, return value is " + fromLast.data);

        // Edge case, what if we want the last node?
        Node last= linkedlist.fromLast(0);
        System.out.println("Expected value tail4, return value is "+ last.data);

        // Assumption: For negative numbers return last node
        Node negative = linkedlist.fromLast(-5);
        System.out.println("Expected value tail4, return value is "+ negative.data);

    }

}