Zynga Interview Question
Developer Program Engineerspublic class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
team(5,3);
}
static void formTeam(int n,int k,int a[],int index,int i)
{
if(index==k)
{
System.out.print("\n");
for(int m=0;m<k;m++)
System.out.print(a[m]+" ");
return ;
}
for(int j=i;j<=n;j++)
{
a[index]=j;
formTeam(n,k,a,index+1,j+1);
}
}
static void team(int n,int k)
{
int []a=new int[k];
formTeam(n,k,a,0,1);
}
}
Here is the same solution as before, but with indentation corrected:
int makeResultString(vector<string>& vzOutputItems, int k, int n)
{
if (n < k)
{
return 1;
}
vzOutputItems.clear();
int rflag = recursiveMakeResultString(vzOutputItems, k, n, 0, 0, "");
return rflag;
}
int recursiveMakeResultString(vector<string>& vzOutputItems,
int k,
int n,
int currentPosition,
int mostRecentNumMade,
const string& zItemThusFar)
{
for (int jj = mostRecentNumMade+1; jj <= n - (k-1) + currentPosition; ++jj)
{
char numAsChar = (char)(jj - '0');
string zTempItem = zItemThusFar + numAsChar;
if (currentPosition >= k-1)
{
vzOutputItems.push_back(zTempItem);
}
else
{
recursiveMakeResultString(vzOutputItems, k, n, currentPosition+1, jj, zTempItem);
}
}
return 0;
}
public class GenerateTeamName {
public static void main(String[] args) {
formTeam(1, 5, 3, "");
}
private static void formTeam(int c, int n, int k, String team) {
int currentLength = team.length();
if (currentLength == k) {
System.out.println(team);
return;
}
for (int idx = c; n-idx+1 >= k - currentLength;idx++) {
formTeam(idx+1, n, k, team + idx);
}
}
}
I think theres an easy solution to this.
For eg: n=5, k=3
Possible numbers to use are : 1 2 3 4 5
For a k-element array, if array indices started from 1 at any index i numbers go from i to (n - k + i)
For C-style arrays its just i +1 to (n - k + i) +1
void insert (char* str, int i, int j) {
if( i > k-1 || j > n-k+i+1 )
return;
if( i < k-1) {
str[i] = '0' + j;
insert(str, i+1, j+1);
insert(str, i, j+1);
}
if( i == k) {
str[i] = '0' + j;
printf(Team : %s \n",str);
insert(str, i, j+1);
}
}
In main on a call insert(0,1)
Output :
Team : 123
Team : 124
Team : 125
Team : 134
Team : 135
Team : 145
Team : 234
Team : 235
.
.
.
.
This is my take in Python, please critique:
def form_team(n,k):
a = [i for i in range(1,n-k+1)]
print a
a = form(a,n,k-1)
return a
def form(a,n,k):
new_list = []
for i in a:
for j in range(i%10+1,n-k+2):
new_list.append(i*10+j)
print new_list
if ( 1 == k ):
return new_list
else:
return form(new_list,n,k-1)
print form_team(100,5)
void teamName(int begin, int n, int k, vector<vector<int> > &name_seq, vector<int> &name)
{
if(n < k)
return;
if(!k)
{
name_seq.push_back(name);
return;
}
name.push_back(begin);
teamName(begin + 1, n - 1, k - 1, name_seq, name);
name.pop_back();
teamName(begin + 1, n - 1, k, name_seq, name);
}
vector<vector<int> > teamName(int n, int k)
{
vector<vector<int> > name_seq;
vector<int> name;
teamName(1, n, k, name_seq, name);
return name_seq;
}
void teamMembers(int *&a,int k, int n, int i, int j)
{
if (j == k )
{
for (int m = 0; m < k; m++)
printf("%d", a[m]);
printf("\n");
return;
}
for (int m = i+1; m <= n; m++)
{
a[j] = m;
teamMembers(a, k, n, m, j + 1);
}
}
int main()
{
const int N = 4,K = 3;
int *array = new int[K];
for (int i = 0; i < K; i++)
array[i] = 0;
teamMembers(array, K, N, 0, 0);
return 0;
}
Here is my C++ style approach assuming that instead of printing the answers, you want to save them (i.e., the output result is a vector of strings).
- Anonymous November 05, 2011