# Doppleganger challenge

• (4 Pages)
• 1
• 2
• 3
• Last »

## 55 Replies - 20280 Views - Last Post: 03 September 2012 - 02:25 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=241261&amp;s=28366d1fabed9e7deef970bf52f10eb3&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

# Doppleganger challenge

Posted 27 July 2011 - 12:15 PM

POPULAR

Here's a challenge that's short and sweet.

Write a function that takes two lists of ints as input and outputs a single list that contains only the values that appear in both lists. Shoot for efficiency!
Is This A Good Question/Topic? 7

## Replies To: Doppleganger challenge

• Changed Man With Different Priorities

Reputation: 963
• Posts: 2,382
• Joined: 15-February 11

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:19 PM

Does it have to be in Python?

### #3 Brewer

• Awesome

Reputation: 182
• Posts: 1,044
• Joined: 14-June 10

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:19 PM

```def doppleganger(listone, listtwo):
return set(listone).intersection(set(listtwo))
```

### #4 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:26 PM

Haha don't be lame brewer! Create an actual algorithm for solving the problem

Quote

Does it have to be in Python?

Any high level language will do fine... but no functional languages :)

Put it in any language you damn well please.

This post has been edited by atraub: 28 July 2011 - 09:42 PM
Reason for edit:: Clarification

### #5 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,840
• Joined: 16-October 07

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:29 PM

Spoiler

Edit: Hmmm, got it backwards. brb.

This post has been edited by baavgai: 27 July 2011 - 12:31 PM

### #6 Brewer

• Awesome

Reputation: 182
• Posts: 1,044
• Joined: 14-June 10

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:31 PM

This sounds like fun, I'll give it a shot when I get off work.

### #7 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,840
• Joined: 16-October 07

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:33 PM

Spoiler

Actually an easier question.

### #8 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:36 PM

haha these are some creative answers for sure. Not exactly what I was hoping for though

### #9 Motoma

Reputation: 452
• Posts: 798
• Joined: 08-June 10

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:46 PM

How should it behave when there are multiples of an integer in a list? What's the output for: ([1,2,3,3,3,4,4], [3,1,1,6])?

Here's a less-traditional way of doing this; not sure if dict's hashing of the key will give a performance gain or loss:
Spoiler

### #10 gregwhitworth

• Tired.

Reputation: 221
• Posts: 1,613
• Joined: 20-January 09

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:47 PM

PHP

```function dg(\$listone, \$listtwo)
{
return array_merge(\$listone, \$listtwo);
}

```

### #11 Raynes

• D.I.C Lover

Reputation: 614
• Posts: 2,815
• Joined: 05-January 09

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:51 PM

atraub, on 27 July 2011 - 08:26 PM, said:

Haha don't be lame brewer! Create an actual algorithm for solving the problem

Quote

Does it have to be in Python?

Any high level language will do fine... but no functional languages

Why no functional languages? If you don't use core functions, you still have to write an algorithm for this. It isn't cheating by any means.

### #12 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,840
• Joined: 16-October 07

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:53 PM

Hmm... what if the lists look like [ 2, 5, 5, 5, 8, 3, 3, 12 ], [ 12, 5, 5, 1, 3, 3, 3, 4 ].

The answer I'd want ( order doesn't matter): [3, 3, 12, 5, 5]

That's far more fun:
Spoiler

I'm sure someone can do better than that.

### #13 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:58 PM

Fine, functional languages too

### #14 Nallo

• D.I.C Regular

Reputation: 165
• Posts: 258
• Joined: 19-July 09

## Re: Doppleganger challenge

Posted 27 July 2011 - 12:59 PM

Another O(len(seq1) + len(seq2)) solution:
Spoiler

Without using a hash table, i.e. a dictionary or set, it would be troublesome.

### #15 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Doppleganger challenge

Posted 27 July 2011 - 01:06 PM

am I the only one who did not use a set or a dictionary?