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.

About these ads

Pages: 1 2

8 Responses to “Three List Exercises”

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

  2. 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
    
  3. javabloggi said

    My java solution here.

  4. eupraxia said
    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)]]
    
  5. Dan said

    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

  6. 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
    
  7. brice said


    #!/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 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

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: