Tennis match problem

[diminishin]

Hi this should be a simple one.

Let's say we have a tennis match between two players. The game is set as first to N wins. Write a function to return the winner.

Input:
String array (Players who won that round), random size of up to 10000 - [A,A,B,A,B,...]

N - Integer

Expected: A or B

Please put spoilers in your submission

 

[davidktw]

A naive one from me first.
Solution

• O(M), M is number of games played
• input from arguments,
• don't care how many different players are there too.
• no answer if it is impossible to reach N

UPDATE: STRICTLY A WRONG SOLUTION THAT WASTED COMPUTING RESOURCES. DO NOT FOLLOW THE CODE BELOW.

Spoiler

use strict;
use warnings;

# assuming number of games won by any players <= N
my($games, $N) = @ARGV;

my %winner = ();
foreach my $c (split //, $games) {
  if (++$winner{$c} == $N) {
    print $c, "\n";
    last;
  }
}

This is not a recommended solution, but will be the most hardcore I can come up with using perl. Just for fun though.
It's not meant to be nice, it is meant to just work. (^.^)

eval{$ARGV[0]=~/(?:(.)(?{++$w{$1}==$ARGV[1]&&die("$1\n")}))+/};$@&&print"$@"

Output:

$ ./tennismatch.pl ABBA 0
$ ./tennismatch.pl ABBA 1
A
$ ./tennismatch.pl ABBA 2
B
$ ./tennismatch.pl ABBA 3
$

 

[diminishin]

A naive one from me first.
Solution

• O(M), M is number of games played
• input from arguments,
• don't care how many different players are there too.
• no answer if it is impossible to reach N

Spoiler

use strict;
use warnings;

# assuming number of games won by any players <= N
my($games, $N) = @ARGV;

my %winner = ();
foreach my $c (split //, $games) {
  if (++$winner{$c} == $N) {
    print $c, "\n";
    last;
  }
}

This is not a recommended solution, but will be the most hardcore I can come up with using perl. Just for fun though.
It's not meant to be nice, it is meant to just work. (^.^)

eval{$ARGV[0]=~/(?:(.)(?{++$w{$1}==$ARGV[1]&&die("$1\n")}))+/};$@&&print"$@"

Output:

$ ./tennismatch.pl ABBA 0
$ ./tennismatch.pl ABBA 1
A
$ ./tennismatch.pl ABBA 2
B
$ ./tennismatch.pl ABBA 3
$

Nice, but can u make it even faster?

 

[davidktw]

Nice, but can u make it even faster?

What complexity should we be looking at?

 

[diminishin]

What complexity should we be looking at?

I feel like this will be a major hint already, but can u think of a o(1) solution?

 

[davidktw]

I feel like this will be a major hint already, but can u think of a o(1) solution?

Sounds like a question that I didn't read properly

Spoiler

// assuming `games` is the input array of characters
games[games.length - 1] // minus the caveat of no games

 

[diminishin]

Sounds like a question that I didn't read properly

Spoiler

// assuming `games` is the input array of characters
games[games.length - 1] // minus the caveat of no games

U got it. I wanna make this an interview qn to test candidates critical thinking, what do u think?

 

[davidktw]

U got it. I wanna make this an interview qn to test candidates critical thinking, what do u think?

Sure why not. I did fail it, didn't I ?

 

[davidktw]

Sure why not. I did fail it, didn't I ?

@diminishin
However I must indicate. It would seems the inclusion of Nis extremely misleading. Because your Nis constrained by your games array input.

Simply for a game array input of ABBAA, you can't have any values other than N=3. Games inputs like ABBA is invalid too.

Hence on 2nd thought, I probably don't think this is a good question.

 

[diminishin]

@diminishin
However I must indicate. It would seems the inclusion of Nis extremely misleading. Because your Nis constrained by your games array input.

Simply for a game array input of ABBAA, you can't have any values other than N=3. Games inputs like ABBA is invalid too.

Hence on 2nd thought, I probably don't think this is a good question.

Yes this is done on purpose, N serves no purpose at all. Hmm, maybe I should find a better way to phase this qn?