pgbovine/OnlinePythonTutor — Issue #2: Optimize Find Duplicates: Asks for ListType, but tests for Python set
Author: GitSullied
Created: 2012-02-19 22:30:04+00:00
State: open

# Mismatch in Requested and Tested Object Type #

The issue is that the posed question asks for a specific type of return object (a list-type object), but will not pass solutions that correctly return the dictated object type. The solution verification code only seems to accept results submitted as a set object.

- - -

_**Steps to reproduce**_

Open the task Optimize: Find Duplicates

Provide a solution that:

Returns its results as a list object (You can cut/paste code samples from the write-up below if needed)

Meets the criteria set forth in the task/challenge

Follow the button navigation through to "Submit this Solution"

- - -

_**Notice**_

The expected results specified and the provided results, in the case of a valid solution, are different objects that contain members of identical values

Return a set-object instead of a list-object, without changing anything else, and the same validation tests succeeded instead of failing.

The task/challenge description indicates that a list object should be returned.

- - -

# Further Details

If further details are needed see the discussion below, but it is optional. The concise description above should be sufficient when combined with a little hands-on.
- - -

## The Defined Task ##

The task/challenge presented as [Optimize: Find Duplicates](http://people.csail.mit.edu/pgbovine/python/question.html?optimize-find-dups#mode=edit "Optimize: Find Duplicates") states:

> The given function returns a list of duplicate elements [...]. Optimize this function [...]

and presents the code to be optimized as:

def findDups(lst):
dups = set()
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] == lst[j]:
dups.add(lst[i])
return dups

### Visual Inspection ###

It can be seen that the returned variable object is instantiated as a set object in the first line of the function and is never rendered into a list-type before returning from the function.

### Programmatic Inspection ###
Extending the original two lines of test code will also illustrate the situation.

# Test Code
input = ['a', 'b', 'c', 'a', 'd', 'c', 'e', 'f', 'g', 'f']
result = findDups(input)
print type(result)

## A Valid Solution ##
The following solution to the optimization task returns the expected results as a list-type, but fails all of the solution validation tests.

def findDups(lst):
memory = dict()
for i in lst:
if memory.has_key(i):
memory[i] += 1
else:
memory[i] = 1
dups = [i for i,c in memory.items() if c > 1]
return dups

### Result Matrix Returned by Server ###

Input
Result
Status

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"c"	"a"	"d"	"c"	"e"	"f"	"g"	"f"

result:

list:

0	1	2
"a"	"c"	"f"

Debug me

Expected:

set:

"a"	"c"	"f"

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"xxx"	"c"	"d"	"e"	"f"	"g"	"h"	"xxx"

result:

list:

0
"xxx"

Debug me

Expected:

set:

"xxx"

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"c"	"d"	"e"	"f"	"g"	"h"	"i"	"j"

result:

empty list

Debug me

Expected:

empty set

## Provide a Set Object Instead Passes Verification Tests ##

def findDups(lst):
memory = dict()
for i in lst:
if memory.has_key(i):
memory[i] += 1
else:
memory[i] = 1
dups = [i for i,c in memory.items() if c > 1]
return set(dups)

### Result Matrix Returned by Server ###

Input
Result
Status

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"c"	"a"	"d"	"c"	"e"	"f"	"g"	"f"

result:

set:

"a"	"c"	"f"

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"xxx"	"c"	"d"	"e"	"f"	"g"	"h"	"xxx"

result:

set:

"xxx"

input:

list:

0	1	2	3	4	5	6	7	8	9
"a"	"b"	"c"	"d"	"e"	"f"	"g"	"h"	"i"	"j"

result:

empty set

## WTF ##

That's a lot of write up for a simple bug... yeah, I know. Actually, I'm experimenting with github and the Markdown syntax. I just needed a task to make it realistic as I familiarize myself with the tools and services provided here. I'm looking forward to the code-review feature that I've read about.

I hope you don't mind my rambling and scribbles, @pgbovine. I am not picking on you; on the contrary, I quite enjoyed your little demo and will continue to play with it a bit more if you don't mind.