Next To Last Item In A List

July 28, 2015

Today’s exercise is a reminder about the importance of writing good test code. We have two tasks. The first is to extract the next-to-last item from a linked list; for instance, given the list (1 2 3 4 5) the next-to-last item is 4. The second task is to extract the nth-from-last item from a linked last; for instance, given the same list, the second-from-last item is 4. In addition to writing the two functions, you should write test code that exercises the functions thoroughly.

Your task is to write the two functions and test code. 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.

Pages: 1 2

6 Responses to “Next To Last Item In A List”

  1. Paul said

    In Python. I assumed that n cannot exceed the length of the list. I did use a list for the linked list, but did not use len and slicing.
    For testing I use the hopthesis library.

    from hypothesis import given, Settings, Verbosity
    import hypothesis.strategies as st
    from itertools import tee, islice
    
    def slidingwindow(iterable, n=2):
        """example: [1,2,3,4,5],3) -> (1,2,3), (2,3,4), (3,4,5)"""
        its = tee(iter(iterable), n)
        for i, it in enumerate(its):
            next(islice(it, i, i), None)
        return zip(*its)
    
    def bf(seq, n):
        """for testing
           assumption is that n cannot exceed the length of the sequence
        """
        if len(seq) < n:
            return None
        return seq[-n]
    
    # use list as linked list - you cannot use seq[-2] and len
    def next_to_last_n(seq, n):
        a = None
        # slidingwindow(s,2) returns (s1,s2), (s2,s3), ....., (s_n-1, s_n)
        for a, *b in slidingwindow(seq, n): 
            pass
        return a
        
    def next_to_last(seq):
        return next_to_last_n(seq, 2)
        
    # generate random lists of integers with random lengths, and generate a random n
    @given(st.lists(st.integers(), average_size=20), st.integers(min_value=1, max_value=20),
           settings=Settings(verbosity=Verbosity.normal))
    def test_next_to_last_n(seq, n):
        exp = bf(seq, n)
        act = next_to_last_n(seq, n)
        assert act == exp, "{} {} {}".format(act, exp, seq[-4:])
    
    @given(st.lists(st.integers()))
    def test_next_to_last(seq):
        exp = bf(seq, 2)
        act = next_to_last(seq)
        assert act == exp, "{} {} {}".format(act, exp, seq[-4:])
    
    if __name__ == "__main__":
        test_next_to_last()
        test_next_to_last_n()
        print("OK")
    
  2. Paul said

    In Python. A simpler version.

    from collections import deque    
    def next_to_last_n(seq, n):
        d = deque(seq, n) # d contains the last n values of seq
        return d[0] if len(d) == n else None
    
  3. Jussi Piitulainen said

    With Lisp-style lists in Python, and a verbose option in the test function for checking that no news is any news at all.
    Backwards indexing has always been tricky for me, including this time. Oh, and I let Python raise an exception when the list is too short, and then I test for that.

    from functools import reduce
    
    def nest(flat):
        return reduce((lambda rest, elt: (elt, rest)), reversed(flat), ())
    
    def tail(nested, n = 1):
        '''Tail starting at index n.'''
        for k in range(n):
            _, nested = nested
        return nested
    
    def nthtolast(nested, n = 0):
        '''Head of the tail of length n + 2.'''
        slow, fast = nested, tail(nested, n + 2)
        while fast:
            _, slow = slow
            _, fast = fast
        elt, _ = slow
        return elt
    
    def test(n, verbose = False):
        for data in ('abcdef'[:e] for e in range(7)):
            if n + 1 < len(data):
                x = nthtolast(nest(data), n)
                assert x == data[-2-n]
                ( verbose and
                  print('nthtolast(({}), n = {}) => {}'
                        .format(' '.join(data), n, x)) )
            else:
                try:
                    nthtolast(nest(data), n)
                    assert False
                except ValueError:
    		( verbose and
                      print('nthtolast(({}), n = {}) => ValueError'
                            .format(' '.join(data), n)) )
    
    test(0)
    test(1)
    test(2)
    
  4. r. clayton said

    A solution in (Racket) Scheme.

  5. matthew said

    nfl0 is the inefficient but clear functional specification, nfl is the implementation (using the double pointer approach). Both assume n is non-negative.
    Test just compares the two functions over a suitable set of inputs.

    nfl0 n s
         | n >= length s = Nothing
         | otherwise = Just (s !! (length s - n - 1))
    
    f 0 s t = g s t
    f n s (_:t) = f (n-1) s t
    f _ _ _ = Nothing
    g (a:_) [] = Just a
    g (_:s) (_:t) = g s t
    nfl n s = f (n+1) s s
    
    test0 m n =
          nfl n [1..m] == nfl0 n [1..m]
    test1 m = all (test0 m) [0..m+1]
    test = all test1 [0..5]
    
    main = print test
    
  6. mcmillhj said
    fun next_to_last_item [] = ~1 (* return -1 on error *)
      | next_to_last_item (x::y::nil) = x
      | next_to_last_item (x::xs) = next_to_last_item xs
                                                      
    val test_valid_list = (next_to_last_item [1, 2, 3, 4, 5]) = 4
    val test_empty_list = (next_to_last_item []) = ~1
    val test_single_elem_list = (next_to_last_item [1]) = ~1
    
    fun nth_from_last_item n [] = ~1
      | nth_from_last_item n lst = let
          val len = List.length lst
          fun loop counter [] = ~1 (* counter goes past end of list *)
            | loop counter (x::xs) = if len - counter = n then x
                                     else loop (counter + 1) xs
      in
    
          loop 0 lst
      end
    
    val test_1st_from_last = (nth_from_last_item 1 [1, 2, 3, 4, 5]) = 5
    val test_2nd_from_last = (nth_from_last_item 2 [1, 2, 3, 4, 5]) = 4
    
    (* rewriting next_to_last_item using nth_from_last_item *)
    fun next_to_last_item2 xs = nth_from_last_item 2 xs;
    val test_valid_list2 = (next_to_last_item2 [1, 2, 3, 4, 5]) = 4
    val test_empty_list2 = (next_to_last_item2 []) = ~1
    val test_single_elem_list2 = (next_to_last_item2 [1]) = ~1
    
    val all_test_pass =
        List.all (fn x => x) [test_valid_list, test_empty_list, test_single_elem_list, test_1st_from_last, test_2nd_from_last, test_valid_list2, test_empty_list2, test_single_elem_list2];
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: