Sample Programming Questions

Below are a few programming questions that are good practice for the next test and the final (some of these questions are from past topcoder competitions. We will be solving (some of) these in class today.

1. Implement a method minCycle that takes a String s as an argument and returns the shortest string which when repeated generates s. For example:
   

   minCycle("aaaaaaaa") returns "a"
   minCycle("ababababab") returns "ab"
   minCycle("ababa") returns "ababa"
   minCycle("12345") returns "12345"
   minCycle("123123123") returns "123"
   

2. Implement a method blackJackWinner(int[] points) which takes as an argument the points each player on the table ended up with and return the index of the winner, or -1 if there is a tie. Any player with more than 21 points loses. Of the remaining players, the one with the most points wins. If there is a tie, or if there are no winners, return -1. For example:
   

   blackJackWinner({1,2}) returns 1
   blackJackWinner({1,2,3,3,2}) returns -1
   blackJackWinner({21,22,19}) returns 0 
   blackJackWinner({1,20,15,22}) returns 1 
   blackJackWinner({22,23,25}) returns -1 //no winners
   

3. Implement a method int[] findTeam(boolean[][] canWork) which takes as input a 2-dimensional array of booleans that tells us wether a particular employee (row) can work with another (col) and returns an array containing the indexes of 3 employees that can work together in a team, or null if there is none. That is canWork[2][3] is true if employee 2 can work with 3. For example:
   

   findTeam({true,true,true},
            {true,true,true},
            {true,true,true}) returns {0,1,2}
   
   findTeam({true,true,true},
            {false,true,true},
            {true,true,true}) returns null
   
   findTeam({true,false,true,true},
            {true,true,true,true},
            {true,true,true,true},
            {true,true,true,true}) returns {1,2,3}
   
   
   findTeam({true,false,true,true},
            {true,true,false,true},
            {true,true,true,true},
            {true,true,true,true}) returns null
   

4. Implement a method String decrypt(String spell) which decrypts the 'spell' by reversing the order in which the 'A' and 'Z' characters appear in it, but leaves all other characters in the same position. For example:
   

   decrypt("AZ") returns "ZA"
   decrypt("ABZ") returns "ZBA"
   decrypt("ABACDA") returns "ABACDA"
   decrypt("ZBACDA") returns "ABACDZ"
   decrypt("AAATZZ") returns "ZZATAA"