Interview Question
Country: United States
I like your solution, it doesn't require explicit extra-memory, however pascal method does the whole re-processing for every new row, having an array of previous values would dramatically improve performance. However this is the requirement.
Same implementation but with more meaningful variable names for people who haven't seen it before.
void DrawPascalTriangle(int maxRows)
{
int columnValue;
// Loop rows
for (int currentRow = 0; currentRow < maxRows; currentRow++)
{
// Create row, have height number of entries per row
for (int currentColumn = 0; currentColumn <= currentRow; currentColumn++)
{
columnValue = Pascal(currentRow, currentColumn);
printf("%3d", columnValue);
}
printf("\n");
}
}
int Pascal(int currentRow, int currentColumn)
{
if (currentColumn == 0 || currentRow == currentColumn)
return 1;
else
return Pascal(currentRow - 1, currentColumn - 1) + Pascal(currentRow - 1, currentColumn);
}
#include<stdio.h>
main()
{
int i,j,k,h,p;
printf("Enter height : ");
scanf("%d",&h);
for(i=0;i<h;i++)
{
for(k=i;k<h;k++)
printf(" ");
for(j=0;j<=i;j++)
{
p = pascal(i,j);
printf("%3d",p);
}
printf("\n");
}
}
int pascal(int r,int c)
{
if(c==0 || r==c)
return 1;
else
return pascal(r-1,c-1)+pascal(r-1,c);
}
public String printCrazy(int n){
if(n == 1){
System.out.println("1");
return "1";
}
if(n > 1){
String returnPrev = printCrazy(n-1);
String [] parts = returnPrev.split(" ");
StringBuffer returnCur = new StringBuffer();
for(int i=0;i<parts.length;i++){
if(i==0){
returnCur.append(parts[0]);
returnCur.append(" ");
}
if(i > 0 && i < parts.length){
int calculatedValue = Integer.parseInt(parts[i-1]) + Integer.parseInt(parts[i]);
returnCur.append(calculatedValue);
returnCur.append(" ");
}
if(i == parts.length-1){
returnCur.append(parts[parts.length-1]);
returnCur.append(" ");
}
}
System.out.println(returnCur.toString().trim());
return returnCur.toString().trim();
}else
return "";
}
public static void main(String[] args) {
pascalTriangle(0, 5, null);
}
private static void pascalTriangle(int start, int end, int [] old) {
if(start == end + 1)
return;
int [] arr = new int[start + 1];
arr[0] = 1;
arr[arr.length - 1] = 1;
for(int i = 1; i < arr.length - 1; i++)
arr[i] = old[i - 1] + old[i];
for(int i : arr)
System.out.print(i + " ");
System.out.println("");
pascalTriangle(start + 1, end, arr);
}
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
using extra memory O(N) N == row number
public void generateAll (int row){
int [] memory = new int [row];
memory[0] = 1;
generate (row, 0, memory) ;
}
private void generate (int row, int count , int [] memory){
if (row == count) {
System.out.println();
return ;
}
if (count == 0) {
System.out.println(memory[0] + " ");
generate (row, count + 1 , memory);
} else {
int pre = 0 ;
for (int i = 0 ; i <= count ; ++i) {
int rear = i == count ? 0 : memory[i] ;
int c = pre + rear ;
pre = rear ;
memory[i] = c ;
}
for (int i = 0 ; i <= count ;++i) {
System.out.print(memory[i] + " ");
}
System.out.println();
generate (row, count + 1 , memory);
}
}
C code using recursion to print pascals triangle
#include <stdio.h>
#include <stdlib.h>
int fact(int n){
int j=1,fact=1;
while(j<=n){
fact=fact*j;
j++;
}
return fact;
}
void draw_line(int i,int j){
printf("1 ");
for(;j<i;j++){
printf("%d ",fact(i)/(fact(i-j)*fact(j)));
}
puts("1");
}
void rec_pascal(int i,int n){
if(i==n)
return;
if(i==1){
printf("1\n");
}
draw_line(i,1);
rec_pascal(i+1,n);
}
int main()
{
int n=5;
rec_pascal(1,n);
return 0;
}
class Pattern {
private void generatePattern(int rowCounter, int row) {
if (rowCounter > row) {
return;
}
int[] arr = new int[rowCounter + 1];
for (int i = 0; i < rowCounter; i++) {
arr[i] = getFactorial(rowCounter - 1)
/ (getFactorial(i) * getFactorial(rowCounter - i - 1));
}
display(arr, rowCounter);
rowCounter++;
generatePattern(rowCounter, row);
}
private void display(int[] arr, int rowCounter) {
for (int i = 0; i < rowCounter; i++) {
System.out.print(arr[i] + "\t");
}
System.out.println();
}
private int getFactorial(int num) {
if (num <= 1) {
return 1;
}
return num * getFactorial(num - 1);
}
public void getPattern(int row) {
generatePattern(0, row);
}
}
public class DisplayTrainglePattern {
public static void main(String[] args) {
Pattern mPattern = new Pattern();
mPattern.getPattern(7);
mPattern.getPattern(9);
}
}
- gAumz March 18, 2015#include<stdio.h> main() { int i,j,k,h,p; printf("Enter height of the triangle : "); scanf("%d",&h); for(i=0;i<h;i++) { for(k=i;k<h;k++) printf(" "); for(j=0;j<=i;j++) { p = pascal(i,j); printf("%3d",p); } printf("\n"); } } int pascal(int r,int c) { if(c==0 || r==c) return 1; else return pascal(r-1,c-1)+pascal(r-1,c); }