Google Interview Question
Developer Program EngineersKeep 2 arrays with n cells; first[0] = 1; second[0..n-1] = 0;
1. determine the second by using the first using the rule from Pascal Triangle; second[current_row] = 1;
2. print the second; copy the second over the first.
3 repeat 1. until current_row = n;
Time Compelxity: O(n^2); Space Complexity: O(n) - 2 arrays.
void Pascal_triangle(int n)
{
int i, j,num_of_spaces;
for(j = 1;j<=n;j++)
{
num_of_spaces = n-j;
for(i=0;i<(n-j);i++)
printf(" ");
for(i=1;i<j;i++)
printf("%d",i);
for(i=j;i>=1;i--)
printf("%d",i);
printf("\n");
}
}
void PascalTriangle::generatePascalTriangle(int p_ilevel)
{
std::vector<std::vector<int> > l_apascalList;
std::vector<int>::const_iterator it;
for(int i=0; i<p_ilevel; ++i)
{
std::vector<int> l_asubList;
if(i == 0)
{
l_asubList.push_back(1);
}
else
{
l_asubList.push_back(1);
for(it=l_apascalList[i-1].begin(); it!=l_apascalList[i-1].end(); ++it)
{
if(it!=(l_apascalList[i-1].end()-1))
l_asubList.push_back((*it)+(*(it+1)));
else
l_asubList.push_back((*it));
}
}
l_apascalList.push_back(l_asubList);
}
std::vector<std::vector<int> >::const_iterator it2;
for(it2=l_apascalList.begin(); it2!=l_apascalList.end(); ++it2)
{
for(it=it2->begin(); it!=it2->end(); ++it)
std::cout << (*it) << " ";
std::cout << std::endl;
}
}
<pre lang="java" line="1" title="CodeMonkey35374" class="run-this">class PascalTriangle {
/**
* @param args
*/
public static void main(String[] args) {
int n =10;
int[][] triangle = new int[n][n];
for(int i=0;i<n;i++){
for(int j =0;j<=i;j++){
if(j==0 || j==i){
triangle[i][j] = 1;
}else{
triangle[i][j] = triangle[i-1][j-1] +triangle[i-1][j];
}
System.out.print(triangle[i][j] +" ");
}
System.out.println();
}
}
}
</pre><pre title="CodeMonkey35374" input="yes">
</pre>
O(1) algorithm (triangle represents coefficients of the binomial expansion, just calculate them):
using System;
namespace ConsoleApplication1
{
class Program
{
static void PrintPascalN(int n)
{
if (n < 0)
return;
int nom = n;
int denom = 1;
int C = 1;
while (C>0)
{
Console.Write("{0} ", C);
C = C * nom / denom;
nom--;
denom++;
}
}
static void Main(string[] args)
{
for (int i = 0; i < 10; i++)
{
PrintPascalN(i);
Console.WriteLine();
}
}
}
}
#include <iostream>
#include <vector>
using namespace std;
void main()
{
vector< vector <int> > matrix;
int n = 6;
matrix.resize(n);
for(int i = 0; i < n ; i++)
matrix[i].resize(n*2-1);
for (i = 0; i < n ; i++)
{
for(int k = 0 ; k < (n*2-1); k++)
{
matrix[i][k] = 0;
}
}
for(i = 0; i < n ; i++)
{
if(i == 0)
{
cout << "1" << endl;
matrix[0][((2*n-1)/2)] = 1;
}
else
{
for(int j = ((2*n-1)/2)-i ; j <= ((2*n-1)/2)+i;j+=2)
{
if ((j-1) >= 0 && (j + 1) < ((2*n)-1))
{
matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j+1];
cout << matrix[i][j] << " ";
}
else if((j-1) < 0)
{
matrix[i][j] = matrix[i-1][j+1];
cout << matrix[i][j] << " ";
}
else if((j+1) >= ((2*n)-1))
{
matrix[i][j] = matrix[i-1][j-1];
cout << matrix[i][j] << " ";
}
}
cout << endl;
}
}
return;
}
void pascal_triangle(int level)
{
int a[level][level];
a[0][0]=1;
a[1][0] = 1; a[1][1] = 2; a[1][2] = 1;
for(int i=2; i<level; i++ )
{
a[i][0]=1;
for(int j=1; j<(i+1); j++)
{
a[i][j] = a[i-1][j-1]+a[i-1][j];
}
a[i][i+1]=1;
}
cout<<a[0][0];
for(int i=1;i<level;i++)
{
cout<<endl;
for(int j=0;j<(i+2);j++)
{
cout<<a[i][j]<<" ";
}
}
}
int main()
{
int level;
cout<<"level: ";
cin>>level;
pascal_triangle(level);
return 0;
}
private void print(int n) {
if( n <= 0){
return;
}
System.out.println(1);
if(n == 1){
return;
}
int a[] = new int[n/2+1];
int len = 1;
a[0]=1;
int prev=0,temp;
for(int level=2;level<=n;level++){
prev = 0;
for(int i=0;i<len;i++){
temp = a[i];
a[i] = a[i]+prev;
System.out.print(a[i]+" ");
prev = temp;
}
if((level & 1) == 0){
a[len] = a[len-1];
System.out.print(a[len]+" ");
}
for(int i = len-2;i>=0;i--){
System.out.print(a[i]+" ");
}
//if level is even.
if((level & 1) == 0){
len++;
}
System.out.println();
}
}
Easiest Method (KISS)
#include<stdio.h>
#include<stdlib.h>
void print_pascal(int n)
{
int i, j;
int *a;
a = malloc(sizeof(int)*i*j);
for(i = 1; i <= n; i++) {
for(j = 1; j <= i; j++) {
if(j != 1 && j != i && i > 2)
a[i*j] = a[(i-1)*j] + a[(i-1)*(j-1)];
else
a[i*j] = 1;
printf("%3d", a[i*j]);
}
printf("\n");
}
free(a);
}
int main()
{
print_pascal(7);
return 0;
}
one -- good solution. But ... it uses too much space. You can do the same thing "in place", essentially, allocate an array of level+1 elements (that's the last row's size), then (for each level) populate it from the back (that's important), then print the elements. The main loop would essentially look something like this:
- czpete September 23, 2010