Expedia Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
static void generatePascal(int level){
if(level >= 0){
generatePascal(level - 1);
System.out.println((int)Math.pow(11, level));
}
}
void pascal(int level, int curLevel, int **array) {
if (curLevel == level) {
return;
}
if (curLevel == 0) {
array[curLevel][curLevel] = 1;
} else {
array[curLevel][0] = 1;
array[curLevel][curLevel] = 1;
for (int i = 1; i < curLevel; i++) {
array[curLevel][i] = array[curLevel -1][i - 1] + array[curLevel - 1][i];
}
}
pascal(level, curLevel + 1, array);
}
void pascal(int level, int curLevel, int **array) {
if (curLevel == level) {
return;
}
if (curLevel == 0) {
array[curLevel][curLevel] = 1;
} else {
array[curLevel][0] = 1;
array[curLevel][curLevel] = 1;
for (int i = 1; i < curLevel; i++) {
array[curLevel][i] = array[curLevel -1][i - 1] + array[curLevel - 1][i];
}
}
pascal(level, curLevel + 1, array);
}
public class Pascals {
public static void main(String args[]){
int p[] = GetPascals(34);
for (int i = 0; i < p.length; i++){
System.out.print(p[i] + " ");
}
}
public static int[] GetPascals(int level){
if (level < 1) return null;
int curRow[] = new int[level];
int lastRow[] = new int[level];
return recursePascals(level, 1, curRow, lastRow);
}
private static int[] recursePascals(int level, int curLevel, int curRow[], int lastRow[]){
int tmp[];
int sum;
tmp = lastRow;
lastRow = curRow;
curRow = tmp;
if (curLevel == 1){
curRow[0] = 1;
}
else if (curLevel == 2){
curRow[0] = 1;
curRow[1] = 1;
}
else{
for (int i = 0; i < curLevel/2+1; i++){
if (i == 0){
curRow[0] = 1;
curRow[curLevel-1] = 1;
}
else{
sum = lastRow[i-1] + lastRow[i];
curRow[i] = sum;
curRow[curLevel-(i+1)] = sum;
}
}
}
if (level == curLevel) return curRow;
else return recursePascals(level, curLevel+1, curRow, lastRow);
}
}
Working java code for anyone who wants it.
public class Pascals {
public static void main(String args[]){
int p[] = GetPascals(34);
for (int i = 0; i < p.length; i++){
System.out.print(p[i] + " ");
}
}
public static int[] GetPascals(int level){
if (level < 1) return null;
int curRow[] = new int[level];
int lastRow[] = new int[level];
return recursePascals(level, 1, curRow, lastRow);
}
private static int[] recursePascals(int level, int curLevel, int curRow[], int lastRow[]){
int tmp[];
int sum;
tmp = lastRow;
lastRow = curRow;
curRow = tmp;
if (curLevel == 1){
curRow[0] = 1;
}
else if (curLevel == 2){
curRow[0] = 1;
curRow[1] = 1;
}
else{
for (int i = 0; i < curLevel/2+1; i++){
if (i == 0){
curRow[0] = 1;
curRow[curLevel-1] = 1;
}
else{
sum = lastRow[i-1] + lastRow[i];
curRow[i] = sum;
curRow[curLevel-(i+1)] = sum;
}
}
}
if (level == curLevel) return curRow;
else return recursePascals(level, curLevel+1, curRow, lastRow);
}
}
Working java code for anyone who wants it.
Note: this is open to integer overflow as n grows.
public class Pascals {
public static void main(String args[]){
int p[] = GetPascals(34);
for (int i = 0; i < p.length; i++){
System.out.print(p[i] + " ");
}
}
public static int[] GetPascals(int level){
if (level < 1) return null;
int curRow[] = new int[level];
int lastRow[] = new int[level];
return recursePascals(level, 1, curRow, lastRow);
}
private static int[] recursePascals(int level, int curLevel, int curRow[], int lastRow[]){
int tmp[];
int sum;
tmp = lastRow;
lastRow = curRow;
curRow = tmp;
if (curLevel == 1){
curRow[0] = 1;
}
else if (curLevel == 2){
curRow[0] = 1;
curRow[1] = 1;
}
else{
for (int i = 0; i < curLevel/2+1; i++){
if (i == 0){
curRow[0] = 1;
curRow[curLevel-1] = 1;
}
else{
sum = lastRow[i-1] + lastRow[i];
curRow[i] = sum;
curRow[curLevel-(i+1)] = sum;
}
}
}
if (level == curLevel) return curRow;
else return recursePascals(level, curLevel+1, curRow, lastRow);
}
}
| 0 1 2 3 column
--+----------------------------------------------
0 | 1 (case 1)
1 | 1 (case 2) 1 (case 2)
2 | 1 (case 3) 2 (sum) 1 (case 4)
3 | 1 (case 3) 3 (sum) 3 (sum) 1 (case 4)
row
#include <stdio.h>
int pascal(int i, int j)
{
if (i == 0 || i == j || j == 0)
return 1;
return pascal(i-1, j-1) + pascal(i-1, j);
}
int main(void) {
int i, j, level = 5;
for (i=0;i<level;i++) {
for (j=0;j<=i;j++){
//printf("i %d j %d\n", i, j);
printf("%d ", pascal(i, j));
}
printf("\n");
}
return 0;
}
public class PascalTriangle {
public static void main(String[] args) {
if (args != null && args.length > 0) {
PascalTriangle pascalTriangle = new PascalTriangle();
int level = Integer.parseInt(args[0]);
int[][] triangle = pascalTriangle.calculateTriangle(level);
System.out.println(Arrays.deepToString(triangle));
}
}
private int[][] calculateTriangle(int i) {
int [][] triangle = new int[i][i];
for (int j = 0; j < i; j++) {
triangle[j] = getHorizontalLine(j);
}
return triangle;
}
private int[] getHorizontalLine(int j) {
int[] line = new int[j + 1];
for (int i = 0; i <= j; i++) {
line[i] = getNumber(j, i);
}
return line;
}
private int getNumber(int j, int i) {
return factorialCalculator(j) / ( factorialCalculator(i) * factorialCalculator(j - i) );
}
public final int factorialCalculator(int limit) {
assert limit >= 0;
if (limit == 0) return 1;
else return limit * factorialCalculator(limit - 1);
}
}
public class PascalTriangle {
public static ArrayList<Integer> gPT(int level) {
ArrayList<Integer> rList = new ArrayList<Integer>();
rList.add(1);
if(level == 1) return rList;
ArrayList<Integer> prevList = gPT(level -1);
for(int i = 1 ; i < prevList.size(); i++) {
rList.add(prevList.get(i) + prevList.get(i-1));
}
rList.add(1);
return rList;
}
public static void main(String args[]) {
System.out.println(gPT(1));
}
}
void pascalTriangle(int level) {
if(level > 0) {
pascalTriangle(level-1);
int number = 1;
for(int index=0; index<level;index++) {
if(index==0 || index == level-1) {
System.out.print("1 ");
} else {
number = number*(level-index)/index;
System.out.print(number+" ");
}
}
System.out.println();
}
}
- senthil.aru August 05, 2015public class PascalTriangle { public static void main(String[] args) { PascalTriangle main = new PascalTriangle(); main.printPascalTriangle(5); } public int pascal(int i, int j) { if (j == 0 || i == j) { return 1; } return pascal(i - 1, j - 1) + pascal(i - 1, j); } public void printPascalTriangle(int level) { for (int i = 0; i < level; i++) { for (int j = 0; j <= i; j++) { System.out.print(pascal(i, j) + " "); } System.out.println(); } } }