Three List Exercises

May 7, 2013

Today’s exercise provides three little exercises on linked lists, designed to help beginning programmers learn more about how lists work; there is also a special invitation for more experienced programmers.

1. Write a function that takes an input list and an interval n and returns a new list with all the elements of the original list, in order, except that every nth item has been removed. For instance, given the input list (1 2 3 4 5 6 7 8 9 10) and n = 4, the function should return the list (1 2 3 5 6 7 9 10).

2. Write a function that takes an input list and returns a new list with all the elements of the original list, in order, except that in the case of duplicate elements all of the duplicates except the first has been removed. For instance, all of the following lists should be transformed into the list (1 2 3 4 5): (1 2 3 4 5), (1 1 2 3 4 5), (1 2 1 3 1 4 1 5 1), and (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5).

3. Write a function that takes an input list and splits the list in half; for instance, given the input list (1 2 3 4 5) the two outputs are the lists (1 2) and (3 4 5). If the list has odd length the middle element can be placed in either half, at your option, so the lists (1 2 3) and (4 5) are an alternate acceptable solution for the example problem.

Your task is to write the three indicated functions. If you find that to be too simple, write one or more exercises for your student friends. 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

Posted by programmingpraxis
Filed in Exercises
8 Comments »

8 Responses to “Three List Exercises”

  1. Programming Praxis – Three List Exercises | Bonsai Code said
    May 7, 2013 at 11:43 AM

    […] today’s Programming Praxis exercise, we need to implement three functions that work on linked lists. […]

  2. Remco Niemeijer said
    May 7, 2013 at 11:43 AM

    My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/07/programming-praxis-three-list-exercises/ for a version with comments):

    deleteNth :: Int -> [a] -> [a]
deleteNth _ [] = []
deleteNth n xs = take (n - 1) xs ++ deleteNth n (drop n xs)

nub :: Eq a => [a] -> [a]
nub = foldl (\a x -> if elem x a then a else a ++ [x]) []

half :: [a] -> ([a], [a])
half xs = splitAt (div (length xs) 2) xs
  4. javabloggi said
    May 8, 2013 at 9:57 AM

    My java solution here.

  5. eupraxia said
    May 8, 2013 at 2:02 PM 
    skip_every_nth = lambda lst, n: [x for i, x in enumerate(lst, 1) if i%n!=0]
#
ordered_set = lambda lst: [lst[lst.index(x)] for x in set(lst)]
#
halfish_split = lambda lst: [(lst[:n], lst[n:]) for n in [int(len(lst)/2)]]
  6. Dan said
    May 9, 2013 at 12:56 AM

    def remove_nth_from_list(input, nth)
    new_list = []
    input.each { |i| new_list.push(i) unless i % nth == 0 }
    new_list
    end

    def deduplicate(input)
    new_list = input.uniq
    end

    def split_list(input)
    both_lists = [[],[]]
    half_point = input.size/2
    input.each_with_index { |i, index| index < half_point ? both_lists[0].push(i) : both_lists[1].push(i) }
    both_lists
    end

  7. trojanfromnormandy said
    May 17, 2013 at 1:02 AM 
    def delete_nth(list, n)
  list.each_index.select{|i| (i+1) % n != 0}.map{|i| list[i]}
end

def drop_dups(list)
  list.each_index.select{|i| i == list.index(list[i])}.map{|i| list[i]}
end

def halve(list)
  Array[list[0...(list.count / 2)], list[(list.count / 2)..-1]]
end
  8. brice said
    May 26, 2013 at 8:19 PM


    #!/usr/bin/env python

    def remove_ns(ls, n):
    return (v for i, v in enumerate(ls, 1) if i % n != 0)

    print("".join(remove_ns("abdefgh", 2)))

    def remove_dups(ls):
    seen = set()
    for i in ls:
    if not i in seen:
    seen.add(i)
    yield i

    print("".join(remove_dups("abbdssfgsha")))

    def split(ls):
    return ls[:int(len(ls)/2)], ls[int(len(ls)/2):]

    print(split([1,2,3,4,5]))

Leave a comment