Nth From The End

September 11, 2018

Counting from the end of the list, the third-last item in the list (1 2 3 4 5 6 7 8 9) is 7.

Your task is to write a program to find the nth-last item in a list; you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

3 Responses to “Nth From The End”

  1. Globules said

    A Haskell version. “Fundamentally different” is in the eye of the beholder…

    import Data.Maybe (listToMaybe)
    import           Data.Vector ((!?))
    import qualified Data.Vector as V
    import Text.Printf (printf)
    
    -- Reverse the list, returning the leading element (if any) after having dropped
    -- the first n-1 elements.
    nthFromEnd1 :: Int -> [a] -> Maybe a
    nthFromEnd1 n xs | n > 0     = listToMaybe . drop (n - 1) . reverse $ xs
                     | otherwise = Nothing
    
    -- Form a list of key/value pairs, returning the element (if any) whose
    -- zero-based key is equal to the length of the list minus n.
    nthFromEnd2 :: Int -> [a] -> Maybe a
    nthFromEnd2 n xs = let len = length xs
                       in lookup (len - n) $ zip [0..] xs
    
    -- Store the list in a vector, returning the element (if any) whose zero-based
    -- position is the length of the vector minus n.
    nthFromEnd3 :: Int -> [a] -> Maybe a
    nthFromEnd3 n xs = let (ys, len) = (V.fromList xs, V.length ys)
                       in ys !? (len - n)
    
    test :: Show a => String -> (Int -> [a] -> Maybe a) -> Int -> [a] -> IO ()
    test desc f n xs = let x = f n xs
                       in printf "%s %2d %s -> %s\n" desc n (show xs) (show x)
    
    main :: IO ()
    main = do
      let xs = [1..9] :: [Int]
    
      test "nthFromEnd1" nthFromEnd1  0 xs
      test "nthFromEnd2" nthFromEnd2  0 xs
      test "nthFromEnd3" nthFromEnd3  0 xs
    
      test "nthFromEnd1" nthFromEnd1  3 xs
      test "nthFromEnd2" nthFromEnd2  3 xs
      test "nthFromEnd3" nthFromEnd3  3 xs
    
      test "nthFromEnd1" nthFromEnd1 13 xs
      test "nthFromEnd2" nthFromEnd2 13 xs
      test "nthFromEnd3" nthFromEnd3 13 xs
    
    $ ./nthfromend
    nthFromEnd1  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd2  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd3  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd1  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd2  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd3  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd1 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd2 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd3 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    
  2. Daniel said

    Here’s a solution in C. n is zero-indexed. It doesn’t handle invalid inputs (e.g., setting n=5 for a list with three elements).

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int value;
        struct node* next;
    } node_t;
    
    void print_list(node_t* list) {
        printf("{");
        node_t* node = list;
        while (node != NULL) {
            if (node != list) printf("->");
            printf("%d", node->value);
            node = node->next;
        }
        printf("}");
    }
    
    int length(node_t* list) {
        node_t* node = list;
        int len = 0;
        while (node != NULL) {
            ++len;
            node = node->next;
        }
        return len;
    }
    
    void reverse(node_t** list) {
        node_t* prev = NULL;
        node_t* node = NULL;
        node_t* next = *list;
        while (next != NULL) {
            prev = node;
            node = next;
            next = next->next;
            node->next = prev;
        }
        *list = node;
    }
    
    // Get length of list. Then walk the list to the
    // nth element from the end and return.
    int from_end1(node_t* list, int n) {
        int len = length(list);
        node_t* node = list;
        for (int i = 1; i < len - n; ++i) {
            node = node->next;
        }
        return node->value;;
    }
    
    // Reverse the list. Then get the nth element.
    // Reverse the list back to its original ordering
    // and return.
    int from_end2(node_t** list, int n) {
        reverse(list);
        node_t* node = *list;
        for (int i = 0; i < n; ++i) {
            node = node->next;
        }
        reverse(list);
        return node->value;
    }
    
    // Walk n elements into the list. Then walk from there
    // and from the beginning of the list until the first
    // pointer reaches the end.
    int from_end3(node_t* list, int n) {
        node_t* n1 = list;
        node_t* n2 = list;
        for (int i = 0; i < n; ++i) {
            n1 = n1->next;
        }
        while (n1 != NULL && n1->next != NULL) {
            n1 = n1->next;
            n2 = n2->next;
        }
        return n2->value;
    }
    
    int main(int argc, char* argv[]) {
        if (argc < 2) {
            fprintf(stderr, "Usage: %s N [X1 [X2 [X3 ...]]]\n", argv[0]);
            return EXIT_FAILURE;
        }
        int n = atoi(argv[1]);
        node_t* list = NULL;
        for (int i = argc - 1; i >= 2; --i) {
            node_t* node = (node_t*)malloc(sizeof(node_t));
            node->value = atoi(argv[i]);
            node->next = list;
            list = node;
        }
        printf("list:\n  ");
        print_list(list);
        printf("\n");
        int e1 = from_end1(list, n);
        printf("from_end1(list, %d):\n  %d\n", n, e1);
        int e2 = from_end2(&list, n);
        printf("from_end2(list, %d):\n  %d\n", n, e2);
        int e3 = from_end3(list, n);
        printf("from_end3(list, %d):\n  %d\n", n, e3);
        node_t* node = list;
        while (node != NULL) {
            node_t* next = node->next;
            free(node);
            node = next;
        }
        return EXIT_SUCCESS;
    }
    

    Example output:

    $ ./a.out 0 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 0):
      9
    from_end2(list, 0):
      9
    from_end3(list, 0):
      9
    
    $ ./a.out 3 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 3):
      6
    from_end2(list, 3):
      6
    from_end3(list, 3):
      6
    
    $ ./a.out 8 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 8):
      1
    from_end2(list, 8):
      1
    from_end3(list, 8):
      1
    
  3. sri vignesh said

    I know only one.
    b= [10,9,8,7,6,5,4,3,2,1,0]
    index = 7
    print b[len(b) – (index+1)]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: