# "Picking Cards" challenge

I recently tried my hand at CodeSprint2 through Interview Street. Having not coded in quite some time, I wasn't surprised that I had difficulty writing optimized code, but on one problem in particular I can't find where I've gone wrong. I've compared my code to successful algorithms used by other programmers, and I don't see much difference. I tried in both Java and Ruby and hit a wall at the 4th test case with both (I'm just learning Ruby so thought it would be a fun exercise to try it - I tweaked my algorithm a little in the process).

The problem is Picking Cards and the description is here.

Code in Java:

import java.io.*;
import java.util.*;
import java.math.*;

public class Cards3 {

public Cards3()
{
}

public void run()
{
ArrayList<Integer> cards = new ArrayList<Integer>();
try{
/*

StringTokenizer tokenizer = new StringTokenizer(input);
int T = Integer.parseInt(tokenizer.nextToken());
*/

System.out.println("T = " + T);
//read in and test each subsequence
for(int i = 0; i<T; i++)
{
/*
tokenizer = new StringTokenizer(input);
int N = Integer.parseInt(tokenizer.nextToken());

tokenizer = new StringTokenizer(nextLine);
*/

for(int j=0; j<N; j++)
{
}
Collections.sort(cards);
System.out.println(numWays(cards) % 1000000007);
cards = new ArrayList<Integer>();
}

}
catch (IOException e)
{
}
}

//computers the number of ways to pick up cards in currCards given that
//numPicked cards have already been picked up
public long numWays(ArrayList<Integer> cardsLeft)
{
int numPicked = 0;
long numWays = 1;

//calculate until all cards are picked up
while(cardsLeft.size() >= 1)
{
//if we can't pick up the next card, we're at a dead end - no solutions
if(cardsLeft.get(0) > numPicked)
return 0;

int numCanPick = 0;

for(int i: cardsLeft)
{
if(i <= numPicked)
{
numCanPick++;

}
else
{
break;
}
}

cardsLeft.remove(0);
numWays *= numCanPick;
numWays = numWays % 1000000007;
numPicked++;
}

return numWays;
}

public static void main(String args[])
{
Cards3 d = new Cards3();
d.run();
}
}


Code in Ruby

def runProgram
t = STDIN.gets.to_i
t.times{
n = STDIN.gets
numWays = 1
cards = STDIN.gets.split.map(&:to_i)
numPicked = 0
for i in 0...cards.length
numCanPick = cards.count{|a| a<= i}
numWays = numWays * (numCanPick-i)
break if numCanPick==0
numWays = numWays % 1000000007
end
}

end

if __FILE__ == \$0
runProgram
end


The immediate thing that jumps out to me is your use of an ArrayList for this. By continuously removing the first element, you force the array list to shift everything left one space each time (an O(n) operation assuming no underlying optimizations!)

Instead of removing from the array list (incurring an expensive shift), I would recommend that you keep an index.

    while(cardsLeft.size() >= 1)
{
//if we can't pick up the next card, we're at a dead end - no solutions
if(cardsLeft.get(0) > numPicked)
return 0;

// ...
for(int i: cardsLeft)
{
// ...
}

// ...

cardsLeft.remove(0);
// ...
}


becomes

    int cardIndex = 0;
while(cardIndex < cardsLeft.length())
{
//if we can't pick up the next card, we're at a dead end - no solutions
if(cardsLeft.get(cardIndex) > numPicked)
return 0;
// ...
for(int i = cardIndex; i < cardsLeft.length(); ++i)
{
// ...
}
// ...

//cardsLeft.remove(0);
++cardIndex
// ...
}

• I made the change and still hit the time limit after 3 test cases. Commented Jan 31, 2012 at 16:24