Facebook Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

Simple recursion should work, however I am not sure if a more optimized solution is expected.
The only thing to be careful here is that you should not make a recursive call when both teams score 0 as it will call forever. Here is a C# code.

public static int solve(int s1, int s2, int[] A, int c)
        {
            if (s1 == 0 && s2 == 0) return c;
            else if (s1 < 0 || s2 < 0) return -1;

            int max = -1;
            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < A.Length; j++)
                {
                    int sc1 = A[i];
                    int sc2 = A[j];

                    if (sc1 == 0 && sc2 == 0) continue;
                    bool change = (s1 > s2 && s1 - sc1 < s2 - sc2 ||
                           (s1 < s2 && s1 - sc1 > s2 - sc2 ));
                    int x = solve(s1-sc1, s2-sc2, A, c + (change ? 1 : 0));
                    if (x > max) max = x;
                }
            }

            return max;
        }

Returns 5 with 10, 6, and {0,2,3} (0:0 0:2 3:2 3:4 5:4 5:6 8:6 10:6)

- Anon August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is right. Return 'c' from the deepest recursion is a little wired. But better than below:
if(s1<0||s2<0)return INT_MIN;
...
return max(max, solve(s1-sc1, s2-sc2, A)+(change?1:0))

- chenkainp August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Here is my Dynamic Programming solution.
It comes up with 6 since it counts the first point score as a lead change (no one is in the lead to someone being in the lead).

static void Main(string[] args)
        {
            int S1 = 10;
            int S2 = 6;

            int[] a = { 2, 3 };
            int[,] max = new int[S1+1,S2+1];


            for (int i = 0; i <= S1; i++)
                for (int j = 0; j <= S2; j++)
                    max[i,j] = -1;
            max[0,0] = 0;

            // Loop through each array element
            for (int j = 0; j <= S2; j++)
            {
                for (int i = 0; i <= S1; i++)
                {

                    // Loop through each possible scoring increment at each array element
                    for (int x = 0; x < a.Length; x++)
                    {
                        int t1 = i - a[x];
                        int t2 = j - a[x];

                        // Case where team 1 scores these points
                        if (t1 >= 0)
                        {
                            // The max number of lead changes from before these points happened
                            int lastMax = max[t1, j];

                            // The max changes at this score should be at least the max from before this score happened
                            if (lastMax != -1 && 
                                lastMax > max[i,j])
                                max[i, j] = lastMax; ;
                            
                            // If a lead change happened and that gets a new max number of changes, store that number
                            if( t1 <= j && 
                                i > j  &&
                                lastMax >= max[i,j])
                                    max[i,j] = lastMax + 1;
                        }

                        // Case where team 2 scores these points
                        if (t2 >= 0)
                        {
                            int lastMax = max[i, t2];
                            if (lastMax != -1 &&
                                lastMax > max[i, j])
                                    max[i, j] = lastMax;
                            
                            if( t2 <= i &&
                                j > i &&
                                lastMax >= max[i,j])
                                    max[i, j] = lastMax + 1;
                        }
                    }
                }
            }

            for (int i = 0; i <= S1; i++)
            {
                for (int j = 0; j <= S2; j++)
                {
                    Console.Write(max[i, j].ToString() + " ");
                }
                Console.WriteLine("\n");
            }

- ChristmasDonkey August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, ChristmasDonkey,
I agree with you that it's a definitely dynamic programming question. And the dp function should be:
dp[i][j] = Math.max(dp[p][q]), if (i - j) * (p - q) > 0, here no lead change
Math.max(dp[p][q]) + 1, if(i - j) * (p - q) < 0, here lead changes

where p < i and p < j;

- ravio September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Couple of points
#1 : for (int i = 0; i <= S1; i++)
for (int j = 0; j <= S2; j++)
max[i,j] = -1;
max[0,0] = 0;
Now of Rows : S1

// Loop through each array element
for (int j = 0; j <= S2; j++)
{
Number of Rows : S2 .
These two are inconsistent .


#2 : In loops if (t1 >= 0)
{} and
if (t2 >= 0)
{}

You are considering maximum number of ways to get the score , Not maximum number of ways with lead change to get the score.

- Mohit Nagpal October 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok. Got it . Ignore #2 comment .

- Mohit Nagpal October 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why would you need to check for lastMax >= max[i,j] when you update?

- Anonymous October 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 votes

why do u start writing code like an idiot. Just tell your algo, and we will find out if its correct or not. I'm not going to read through your crap code and try to understand.

- whatever October 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't it be 7 for (10, 6)? if scores {0,2,3} are given,
0,0 -> 0,2 -> 2,2 -> 4,2 -> 4,4 -> 4,6 -> 6,6 -> 8,6 -> 10,6

- anonymous November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1:0, 1:2, 3:2, 3:4, 5:4, 5:6, 10:6. At least the lead could change 6 times, not 4. This is a math question, not a programming question, though.

- paul4156 August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is asking for finding the maximum number of changes. 4 is just an example.

- maomaofixer August 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree, this is a maths question, not programming question, every change lead to 1 minus among a,b

given 10, 6, it will be 6
given 5, 6, it will be 5, always the smaller number

- coast October 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the scores you could get could only be 2 or 3. You CANNOT get 1 point.

- Anonymous October 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

shouldn't it be just min[S, S']. The losing team at most can lead maximum of the team score times. So does the wining team,

- Anonymous August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for the pointer! after going through other possible examples, it makes sense.

if S!=S' :
min(S,S') is the max opportunities for losing team
return min(S,S')
else if S==S':
both teams have equal chance of winning
return S or S'

- Anonymous August 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works only if a single point can be scored; does not work if the minimum number of points that can be scores id 2 or greater

- Ore Asonibare August 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution definitely works, but as @Asonibare pointed out, it works for scores that increment by 1.
Again, the question is not clear if scores can increment in a range, that is if score increase can vary between certain values.
But if you think scores can increase by 2 or greater, then the maximum number of leads would be

min(S,S')/score increment value

Here is my algorithm to check if the scores can increment variably within a given range.

1. consider the least possible value in given range
2. min(S,S')/least possible value in given range

This will give me the maximum number of lead changes possible

- chaitutvk25 November 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is a tie considered a lead change? I.e. 2:0, and then 2.3 - lead change, then 3:3. Is it a lead change? I would think so since there was a leader and now there is no leader.

- Anonymous August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Indeed one only need to recurse on the last step, ie, A[-1]
if finalA > finalB, then the last scoring should go to finalA to increase the chance of maximal exchanges of leads, if finalA - A[-1] < finalB, then the exchanges should be 1 + numberOfChanges(A[:-1], finalA-A[-1], finalB), otherwise it is numberOfChanges(A[:-1], finalA-A[-1], finalB).

Similarly, we can conclude for the case finalA < finalB. It needs discussion that if there is a tie, whether the original leader still considered to be leading or not.

- Biteorange August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Every time the losing team scores 2, there can be two lead changes: (s-1,s)->(s+1,s)->(s+1, s+2). So the answer is essentially the score of the losing team. min(s, s').

- sabz August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My first thought of a solution was to use a graph of all the possible solutions and then simply to do BFS distance on the final score node. I think this is the best solution from a optimal perspective as it can achieve linear time. However, it does take quite a bit of code.

You can always do a recursive solution but this isn't efficient, heres my go. Note: I count a tie breaker as a leader change.

public static int getMax(int s1, int s2, int[] plays, int c) {
        if (s1 == 0 && s2 == 0) return c;

        int max = -1;
        for (int i=0; i<plays.length; i++) {
            for (int j=0; j<plays.length; j++) {
                int s1_play = s1 - plays[i];
                int s2_play = s2 - plays[j];

                if ((s1_play < 0 || s2_play < 0) || (plays[i] == 0 && plays[j] == 0)) continue;
                if ((s1 > s2) && (s2_play >= s1_play)) {
                    c++;
                    System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+"  "+c);
                } else if ((s2 > s1) && (s1_play >= s2_play)) {
                    c++;
                    System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+"  "+c);
                }
                int x = getMax(s1_play, s2_play, plays, c);
                if (x > max) {
                    max = x;
                }
            }
        }
        return max;
    }

- infinitone August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh yeah and for maximum changes on the example 10, 6 is 9 times for me.

- infinitone August 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in ruby. I assume that it is always possible for a team to not score (ie, get 0). If that assumption is correct we start with the winning team (if the end is a tie it doesn't matter which team) and figure out the minimum amount they can score to get ahead of the losing team or get to the their final score. Then we switch teams and do it again.

scores = [ 0, 1, 2, 3 ]
final = [6, 10]


# find the minimum amount the team can score to
# trigger a score change or get to the final score
def find_min_score(team, actual, final, scores)
  minscore = (actual[0] - actual[1]).abs
  score = scores.select { |i| i > minscore }.first
  if score and (actual[team] + score <= final[team])
      score
  else
    minscore = final[team] - actual[team]
    score = scores.select { |i| i >= minscore }.first
    if score and (actual[team] + score <= final[team])
      score
    else
      raise "error"
    end
  end
end

def team_play(team, actual, final, scores, inlead)
  score = find_min_score(team, actual, final, scores)
  actual[team] += score
  puts "score is: #{actual[0]} : #{actual[1]}"

  if (actual[0] != actual[1])
    tmp = (actual.max == actual[team]) ? team : ((team == 0) ? 1 : 0)
    if (tmp != inlead)
      puts "change! team #{team} in lead"
      true
    else
      false
    end
  else
    false
  end
end

scores.sort!
changes = 0
inlead = -1
inplay = (final[0] > final[1]) ? 0 : 1
actual = [0, 0]
puts "score is: #{actual[0]} : #{actual[1]}"
while actual[0] < final[0] or actual[1] < final[1]
  if team_play(inplay, actual, final, scores, inlead)
    changes += 1
    inlead = inplay
  end
  inplay = (inplay + 1) % 2
end

puts "total changes: #{changes}"

- ruby September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is java code
key is you have to minus from final score ,
minus options are 0,2,3
e.g: 10-3 vs 6-0 --> 7-2 vs 6-0 (lead change)

public static void main(String[] args){

		int _s1=10;
		int _s2=6;
		int[] _A={0,2,3};
		int _c=0;
		
		int max=solve(_s1,_s2,_A,_c);
		
		System.out.println(max);
		
		
		
	}	
	
	public static int solve(int s1, int s2, int[] A, int c)
    {
        if (s1 == 0 && s2 == 0) return c;
        else if (s1 < 0 || s2 < 0) return -1;

        int max = -1;
        for (int i = 0; i < A.length; i++)
        {
            for (int j = 0; j < A.length; j++)
            {
                int sc1 = A[i];
                int sc2 = A[j];

                if (sc1 == 0 && sc2 == 0) continue;
                boolean change = (s1 > s2 && s1 - sc1 < s2 - sc2 ||
                       (s1 < s2 && s1 - sc1 > s2 - sc2 ));
                int x = solve(s1-sc1, s2-sc2, A, c + (change ? 1 : 0));
                if (x > max) max = x;
            }
        }

        return max;
    }

- Youngsam September 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

4 times correct

public static void main(String[] args){

		int _s1=10;
		int _s2=6;
		int[] _A={0,2,3};
		int _c=0;
		
		int max=solve(_s1,_s2,_A,_c);
		
		System.out.println(max);
		
		
		
	}	
	
	public static int solve(int s1, int s2, int[] A, int c)
    {
		if(s1==0 && s2==0) return c;
		else if (s1<0 || s2<0 ) return -1;
		
        int max=-1;
        for(int i=0;i<A.length;i++){        	
        	for(int j=0;j<A.length;j++){
        		int sc1=A[i];
        		int sc2=A[j];
        		
        		if(sc1==0 && sc2==0) continue;
        		boolean change=false;
        		if(
        			(s1>s2 &&  (s1-sc1 <s2-sc2) &&s1-sc1>0 &&  s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1) )
        			||
        		    (s1<s2 && (s1-sc1 >s2-sc2) &&s1-sc1>0 &&  s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1)) 		
        		 ){
        			change=true;
        			System.out.println("(+"+sc1 +")---->  " +s1 +" : " +s2 + "<---(+" + sc2 +")");
        		}
        		
        		int x=solve(s1-sc1,s2-sc2,A,c+(change==true?1:0));
        		if(x>max) max=x;
        	}
        }
        
        return max;
    }

(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+3)----> 8 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 7 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 7 : 6<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
4

- Youngsam September 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A team is said to lead if in an individual game, it scores higher than the other team and a change in the lead happens if it overtakes the score of the other team. If the score is calculated as positive integer(as mentioned in the question), the minimum number required to overtake the other teams score is by adding 1 over the other team.
A B
0 0 --> initial values.
1 0 --> teamA lead by 1. (A = B + 1)
1 2 --> teamA's score is same, teamB lead by 1. (B = A + 1)
3 2 --> ..... (A = B + 1)
3 4 --> ... (B = A + 1)
5 4 --> ... (A = B + 1)
5 6 -->... (B = A + 1)
7 6 --> (A = B + 1); We should stop our algorithm here.
8 6 -->No change in the lead. Highest(TeamA) = 10, Highest(TeamB) = 6.
9 6 --> No change
10 6 --> No change

We can solve this by going from initial scores (0, 0) to (10, 6) or we can trace back (10, 6) --> (0, 0) and I chose to trace back the scores. Also, we don't care about any scores where the lead does not change.

/**
 *
 Given an array of positive integers that represents possible points a team could score in an individual play.
 Now there are two teams play against each other. Their final scores are S and S'.
 How would you compute the maximum number of times the team that leads could have changed?
 */
public class MaxLeadChangeCalculator {

    public static void main(String[] args) {
        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(0, 0));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(10, 6));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(6, 10));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(1, 2));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(2, 1));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(5, 6));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(5, 5));

        System.out.println("----------------------");
    }

    public int calculate(int firstTeamScore, int secondTeamScore) {

        // If it's a tie we need to decrease change count by 1 as the algorithm below considers that there was initially a change.
        boolean decreaseLeadChangeByOne = firstTeamScore == secondTeamScore && firstTeamScore != 0;
        System.out.println("Final scores are : firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);

        int leadChangeCount = 0;
        while(true) {
            if(firstTeamScore == 0 && secondTeamScore == 0) {
                // As we're tracing back, if both scores reached initial values, we break.
                break;
            }

            if((firstTeamScore > secondTeamScore) || (firstTeamScore == secondTeamScore && firstTeamScore != 0)) {
                // Handles the iteration where teamA's score is higher also
                // Handles equal final scores situation.
                firstTeamScore = (secondTeamScore - 1) < 0 ? 0 : (secondTeamScore - 1);
                printLeadChange(firstTeamScore, secondTeamScore);
                leadChangeCount++;

            } else if(firstTeamScore < secondTeamScore) {
                // Handles iteration where teamB's score is higher.
                secondTeamScore = (firstTeamScore - 1) < 0 ? 0 : (firstTeamScore - 1);
                printLeadChange(firstTeamScore, secondTeamScore);
                leadChangeCount++;
            }

        }

        return decreaseLeadChangeByOne ? leadChangeCount - 1 : leadChangeCount;
    }

    private void printLeadChange(int firstTeamScore, int secondTeamScore) {
        System.out.println("Lead changed decreasing order: firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);
    }

}

- leogps September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I misunderstood the question above. Right solution is as follows:

/**
 *
 Given an array of positive integers that represents possible points a team could score in an individual play.
 Now there are two teams play against each other. Their final scores are S and S'.
 How would you compute the maximum number of times the team that leads could have changed?
 */
public class MaxLeadChangeCalculator {

    public static void main(String[] args) {

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(10, 6, new int[]{1, 2, 4, 6, 7, 9, 10}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(6, 10, new int[]{1, 2, 4, 6, 7, 9, 10}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(1, 2, new int[] {1, 2}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1,2,3,4,5}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1, 5}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1, 5, 10}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(2, 1, new int[]{1, 2}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(9, 1, new int[]{1, 2, 6, 7, 8, 9}));

        System.out.println("----------------------");


        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(120, 200, new int[]{1, 2, 6, 7, 8, 9, 10, 20, 30, 40, 45, 60, 76, 80, 90, 100, 120, 160, 180, 190, 200}));

        System.out.println("----------------------");


        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(120, 120, new int[]{1, 2, 6, 7, 8, 9, 10, 20, 30, 40, 45, 60, 76, 80, 90, 100, 120, 160, 180, 190, 200}));

        System.out.println("----------------------");

        System.out.println("Max Lead change: "
                + new MaxLeadChangeCalculator().calculate(3, 10, new int[]{10, 10, 10, 2, 3, 1, 1})); // Duplicate scores added.

        System.out.println("----------------------");
    }

    public int calculate(final int firstTeamFinalScore, final int secondTeamFinalScore, int[] possibleScores) {

        int firstTeamScore = 0, secondTeamScore = 0;
        int possibleScoreIndex = -1;

        possibleScores = removeDuplicatesAndSort(possibleScores);

        int leadChangeCount = 0;

        while(true) {

            if(possibleScoreIndex + 1 > possibleScores.length
                    || (firstTeamScore == firstTeamFinalScore && secondTeamScore == secondTeamFinalScore)
                    ||(firstTeamScore == firstTeamFinalScore && secondTeamScore > firstTeamScore)
                    || (secondTeamScore == secondTeamFinalScore && firstTeamScore > secondTeamScore)) {
                break;
            }

            if(firstTeamScore == secondTeamScore) {
                if(possibleScores[possibleScoreIndex + 1] <= firstTeamFinalScore) {
                    firstTeamScore = possibleScores[possibleScoreIndex + 1];
                    possibleScoreIndex++;
                    leadChangeCount++;
                    printLeadChange(firstTeamScore, secondTeamScore);
                } else if(possibleScores[possibleScoreIndex + 1] <= secondTeamFinalScore) {
                    secondTeamScore = possibleScores[possibleScoreIndex + 1];
                    possibleScoreIndex++;
                    leadChangeCount++;
                    printLeadChange(firstTeamScore, secondTeamScore);
                }
            } else if(firstTeamScore > secondTeamScore) {
                if(possibleScores[possibleScoreIndex] == secondTeamFinalScore) { // Equating values.
                    secondTeamScore = possibleScores[possibleScoreIndex];
                    continue;
                } else if(possibleScores[possibleScoreIndex + 1] <= secondTeamFinalScore) {
                    secondTeamScore = possibleScores[possibleScoreIndex + 1];
                    possibleScoreIndex++;
                    leadChangeCount++;
                    printLeadChange(firstTeamScore, secondTeamScore);
                }
            } else if(firstTeamScore < secondTeamScore) {
                if(possibleScores[possibleScoreIndex] == firstTeamFinalScore) { // Equating values.
                    firstTeamScore = possibleScores[possibleScoreIndex];
                    continue;
                }
                if(possibleScores[possibleScoreIndex + 1] <= firstTeamFinalScore) {
                    firstTeamScore = possibleScores[possibleScoreIndex + 1];
                    possibleScoreIndex++;
                    leadChangeCount++;
                    printLeadChange(firstTeamScore, secondTeamScore);
                }
            }

        }

        return leadChangeCount;

    }

    private int[] removeDuplicatesAndSort(int[] possibleScores) {

        Set<Integer> sortedSet = new TreeSet<Integer>();
        for(int i : possibleScores) {
            sortedSet.add(i);
        }

        int[] retArr = new int[sortedSet.size()];
        int index = 0;
        for(int i : sortedSet) {
            retArr[index] = i;
            index++;
        }

        return retArr;
    }

    private void printLeadChange(int firstTeamScore, int secondTeamScore) {
        System.out.println("Lead changed increasing order: firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);
    }

}

- leogps September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why is everyone's code so over complicated? I feel like I'm misunderstanding the question. From my interpretation the array of scores are given. No need to find all of the scenarios.

so something like:

public Integer calculateLeads(scores)
{
	scores.sort();
	int count = 0;

	while(!scores.isEmpty()){
		Integer curr = scores.get(0);
		scores.remove(0);

		for(int i = 0; i < scores.size(); i++){
			if(scores.get(i)> curr)
			{
				scores.remove(i);
				count = count + 1;
				break;
			}
		}
}

- Kate September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take the min of S' and S if they are not equal. Then add 1 to the min and then divide that min by the min of the array holding the possible points that can be scored on any given play that is not 0.

Pseudocode :
For example if S'=10 and S=6:
possible_points_per_play = [0,1,2,3]
min(10, 6) = 6
6 + 1 = 7
min(possible_points_per_play) = 1 //min thats not 0
then divide 7 by the min and you'll get the maximum lead changes.

I know this is not perfect but it seems the a step in the right direction.

- ak October 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

class CUtil
{
public:
	int GetMaxTransitions(vector<int>& pts, int SWin, int SLose)
	{
		//prepare the pairs
		vector<PTPAIR> ptpairs;
		for (int i = 0; i < pts.size()-1; i++)
		{
			for (int j = i + 1; j < pts.size(); j++)
			{
				PTPAIR pt1, pt2;

				pt1.first = pts[i];
				pt1.second = pts[j];

				pt2.first = pts[j];
				pt2.second = pts[i];

				ptpairs.push_back(pt1);
				ptpairs.push_back(pt2);
			}
		}

		//pass the pairs and sum goals to recursive procedure
		int max_trans;
		if (GetMaxTransitions_Pvt(ptpairs, SWin, SLose, max_trans))
		{
			return max_trans;
		}

		return -1;
	}

private:

	typedef pair<int, int> PTPAIR;

	typedef pair<int, int> CACHEKEY;
	typedef pair<int, bool> CACHEVALUE;

	map<CACHEKEY, CACHEVALUE> m_cache;

	struct GOALPAIR
	{
		int goal1;
		int goal2;
		int max_trans;
		bool fValid;
	};

	bool GetMaxTransitions_Pvt(vector<PTPAIR>& ptpairs, int Goal1, int Goal2, int& max_transition)
	{
		CACHEKEY key;
		key.first = Goal1;
		key.second = Goal2;

		if (m_cache.count(key) > 0)
		{
			CACHEVALUE cval = m_cache[key];
			max_transition = cval.first;
			return cval.second;
		}

		vector<GOALPAIR> goalpairs;
		goalpairs.resize(ptpairs.size());

		for (int i = 0; i < ptpairs.size(); i++)
		{
			//compute the goal1 and goal2
			int gnew1 = Goal1 - ptpairs[i].first;
			int gnew2 = Goal2 - ptpairs[i].second;

			GOALPAIR& gp = goalpairs[i];
			gp.fValid = false;
			gp.goal1 = gnew1;
			gp.goal2 = gnew2;
			gp.max_trans = 0;

			if (gnew1 == 0 && gnew2 == 0)
			{
				gp.fValid = true;
			}
			else if (gnew1 < 0 || gnew2 < 0)
			{
				continue;
			}
			else
			{
				gp.fValid = GetMaxTransitions_Pvt(ptpairs, gnew1, gnew2, gp.max_trans);
			}
		}

		//now decide the max_transition from each pair

		max_transition = 0;
		bool fValid = false;

		for (int i = 0; i < goalpairs.size(); i++)
		{
			GOALPAIR& gp = goalpairs[i];

			if (!gp.fValid)
			{
				continue;
			}

			fValid = true;

			RESDIRECTIONS prevDir = GetDirection(gp.goal1, gp.goal2);
			RESDIRECTIONS newDir = GetDirection(gp.goal1 + ptpairs[i].first, gp.goal2 + ptpairs[i].second);

			int local_max_trans = gp.max_trans;
			if (prevDir != newDir && !(gp.goal1 == 0 &&  gp.goal2 == 0))
			{
				local_max_trans++;
			}

			if (max_transition < local_max_trans)
			{
				max_transition = local_max_trans;
			}
		}

		CACHEVALUE cval;
		cval.first = max_transition;
		cval.second = fValid;

		return fValid;
	}

	enum RESDIRECTIONS
	{
		FIRST, SECOND,
	};

	RESDIRECTIONS GetDirection(int SFirst, int SSecond)
	{
		if (SFirst < SSecond)
		{
			return SECOND;
		}

		return FIRST;
	}
};

#define ARRAYSIZE(a) (sizeof(a)/sizeof(a[0]))

int main()
{
	int a[] = { 0, 10};
	vector<int> nums(a, a + ARRAYSIZE(a));

	CUtil utl;
	cout << utl.GetMaxTransitions(nums, 100, 60) << endl;
}

- Anonymous January 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;

public class MaxFluctuationsInTournament {

	int[] a;
	int s1,s2;
	int[][] b;
	
	public MaxFluctuationsInTournament(int[] a, int s1, int s2) {
		this.a = a;
		this.s1 = s1;
		this.s2 = s2;
	}

	/**
	 * assume scores non negative, assume only one team scores in a game
	 * assume a sorted 
	 */
	public int getMaxFlips(){
		if(s1<0 || s2 < 0 || (s1==0 && s2==0) || a==null || a.length == 0){
			return 0;
		}
		
		int k = a.length;
		int m = Math.max(a[k-1], s1)+1;
		int n = Math.max(a[k-1], s2)+1;
		
		b = new int[m][n];
		
		// base cases
		for(int i = 0; i < k; i++){
			b[0][a[i]] = 1;
			b[a[i]][0] = 1;
		}
		
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				int max = b[i][j];
				for(int l = 0; l < k; l++){
					int c = 0;
					if(a[l] > 0 && a[l] <= i){
						c = b[i-a[l]][j];
						boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
						if(winnerFlipped){
							c = c+1;
						}
					}
					if(c > max){
						max = c;
					}
					if(a[l] > 0 && a[l] <= j){
						c = b[i][j-a[l]];
						boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
						if(winnerFlipped){
							c = c+1;
						}
					}
					if(c > max){
						max = c;
					}	
				}
				b[i][j] = max;
			}
		}
		
		// find maximizer
		System.out.println("DEBUG max(#flips)=" + (b[s1][s2]-1));
		
		return b[s1][s2]-1;
	}
	
	public List<List<Integer>> getMaximizer(){
		int k = a.length;
		return findMaximizer(a,k,s1,s2,b);
	}
	
	List<List<Integer>> findMaximizer(int[] a, int k, int i, int j, int[][] b){
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		
		if(b[i][j] > 0){
			List<Integer> prevState = new LinkedList<Integer>();
			for(int l = 0; l < k; l++){
				int c = 0;
				if(a[l] > 0 && a[l] <= i){
					c = b[i-a[l]][j];
					boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
					if(winnerFlipped){
						c = c+1;
					}
				}
				if(c == b[i][j]){
					// found maximizer
					prevState.add(i-a[l]);
					prevState.add(j);
					break;
				}
				if(a[l] > 0 && a[l] <= j){
					c = b[i][j-a[l]];
					boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
					if(winnerFlipped){
						c = c+1;
					}
				}
				if(c == b[i][j]){
					// found maximizer
					prevState.add(i);
					prevState.add(j-a[l]);
					break;
				}	
			}
			
			if(prevState.size() > 0){
				res = findMaximizer(a,k,prevState.get(0),prevState.get(1),b);
				List<Integer> currState = new LinkedList<Integer>();
				currState.add(i);
				currState.add(j);
				res.add(currState);
			}
		}
		
		return res;
	}
	
	public static void main(String[] args) {
		int a[] = { 0 , 1 , 2 , 3 };
		int s1 = 10, s2 = 6;
		
		MaxFluctuationsInTournament wrapper = new MaxFluctuationsInTournament(a,s1,s2);
		int maxFlips = wrapper.getMaxFlips();
		List<List<Integer>> res = wrapper.getMaximizer();
		int n = res.size();
		System.out.println("Result " + maxFlips);
		
		for(int i = 0; i < n; i++){
			List<Integer> state = res.get(i);
			System.out.println("State " + (i+1) + "\t(" + state.get(0) + "," + state.get(1) + ")");
		}
	}

}

- just_do_it February 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I write a DP solution and found one interesting thing. That is, the maximum lead change count is always min(S1, S2). So I guess there should be some math proof that can lead to this result. Can anyone give a math proof? Thanks.

These are some test results:

Max changes of 83 and 86 is 83
Max changes of 77 and 15 is 15
Max changes of 93 and 35 is 35
Max changes of 86 and 92 is 86
Max changes of 49 and 21 is 21
Max changes of 62 and 27 is 27
Max changes of 90 and 59 is 59
......
Max changes of 34 and 64 is 34
Max changes of 43 and 50 is 43

- T_Dog October 09, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More