Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Petite Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems
> (define (but-last xs) (reverse (cdr (reverse xs))))
> (define (pair-wise f xs) (map f (but-last xs) (cdr xs)))
> (define (roll-up xs)
(when (pair? xs)
(roll-up (pair-wise + xs))
(display xs) (newline)))
> (roll-up '(4 7 3 6 7))
(81)
(40 41)
(21 19 22)
(11 10 9 13)
(4 7 3 6 7)
{
import java.util.Arrays;
public class triangle_array {
public static void print(int a[])
{
if(a.length==0)
return;
int n=a.length;
int newa[]=new int[n-1];
for(int i=0;i<n-1;i++)
{
newa[i]=a[i]+a[i+1];
}
print(newa);
if(newa.length!=0)
System.out.println(Arrays.toString(newa));
}
public static void main(String args[])
{
int a[]={4,7,3,6,7};
print(a);
System.out.println(Arrays.toString(a));
}
}
}
8 lines of code. Reverse pascal triangle.
vector<vector<int>> revPascal(vector<int> v) {
vector<vector<int>> ret;
if (!v.size()) return ret;
vector<int> nxt;
for (int i = 0; i < v.size() - 1; ++i)
nxt.push_back(v[i] + v[i + 1]);
auto ret2 = revPascal(nxt);
ret2.push_back(v);
return ret2;
}
In Java, pretty easy.
import java.lang.StringBuilder;
public class Test {
public static void main(String[] args) {
constructMathTriangle(new Integer[] {4, 7, 3, 6, 7});
}
private static void constructMathTriangle(Integer[] numbers) {
if (numbers.length > 0) {
int newLength = numbers.length-1;
Integer[] tempArray = new Integer[newLength];
for (int itr = 0; itr < numbers.length; itr++) {
if (itr + 1 != numbers.length) {
tempArray[itr] = numbers[itr] + numbers[itr+1];
}
}
printArray(numbers);
constructMathTriangle(tempArray);
}
}
private static void printArray(Object[] objArray) {
if (objArray != null) {
StringBuilder sb = new StringBuilder();
for (Object obj : objArray) {
sb.append(obj + " ");
}
System.out.println(sb.toString());
}
}
}
public class TriangleOfNumbers {
public static void main(String[] args) {
int[] input = new int[] { 4, 7, 3, 6, 7 };
compute(input);
printToConsole(input);
}
static void compute(int[] input) {
if (input != null && input.length > 0) {
int newLength = input.length - 1;
int newArray[] = new int[newLength];
for (int i = 0; i < input.length - 1; i++) {
newArray[i] = input[i] + input[i + 1];
}
compute(newArray);
printToConsole(newArray);
}
}
private static void printToConsole(int[] input) {
if (input != null && input.length > 0) {
System.out.print("{{");
for (int i = 0; i < input.length; i++) {
System.out.print(input[i]);
if (i + 1 < input.length) {
System.out.print(", ");
}
}
System.out.println("}}");
}
}
}
#include <stdio.h>
#include <stdlib.h>
void constructTriangle(int *ary, int size) {
if (size == 1) return;
for (int i=0; i<size; i++) {
int j = i + 1;
if (j < size) {
int k = *(ary+i) + *(ary + j);
printf("%d ", k);
ary[i] = k;
}
}
printf("\n");
constructTriangle(ary, size-1);
}
int main(int argc, const char * argv[]) {
int a[5] = {4, 7, 3, 6, 7};
for (int i=0; i<5; i++) {
int value = *(a+i);
printf("%d ", value);
}
printf("\n");
constructTriangle(a, 5);
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class TriangleConstruction {
public static void main(String[] args) {
int[] arr = {4,7,3,6,7};
List<int[]> op = constructArray(arr);
for(int i=op.size()-1;i>=0;i--) {
int[] temp = op.get(i);
for(Integer in : temp) {
System.out.print(in+" ");
}
System.out.println();
}
}
static List<int[]> constructArray(int[] arr) {
int len = arr.length;
List<int[]> op = new ArrayList<int[]>();
while(true) {
int ctr = --len;
if(ctr==0)
break;
int[] temp = new int[ctr];
for(int j=0;j<ctr;j++) {
temp[j] = arr[j] + arr[j+1];
}
op.add(temp);
arr = temp;
}
return op;
}
}
#include <stdlib.h>
#include <stdio.h>
int *intlist (int len)
{
return malloc (sizeof (int) * len);
}
void print_list (int *list, int len)
{
int i;
for (i = 0; i < len; i++)
printf (" %d", list[i]);
putchar ('\n');
}
void triangle (int *list, int len)
{
int *list2;
int i;
if (len == 1) {
print_list (list, len);
return;
}
list2 = intlist (len - 1);
for (i = 1; i < len; i++)
list2[i - 1] = list[i - 1] + list[i];
triangle (list2, len - 1);
print_list (list, len);
free (list2);
}
int main (int argc, char **argv)
{
int *list;
int i;
if (argc < 2)
return 0;
argv++;
argc--;
list = intlist (argc);
for (i = 0; i < argc; i++)
list[i] = atoi (argv[i]);
triangle (list, argc);
free (list);
return 0;
}
public void compressTriangles(int[] arr){
if(arr.length == 0){
return;
}
if(arr.length > 1){
int[] newArr = new int[arr.length-1];
for(int i = 0; i < newArr.length -2; i++){
newArr[i] = arr[i] + arr[i+1];
}
compressTriangles(newArr);
}
System.out.println(arrToString(arr));
}
private String arrToString(int[] arr){
StringBuilder builder = new StringBuilder();
for(int i : arr){
builder.append(Integer.toString(i));
builder.append(' ');
}
return builder.toString();
}
By using just a recursive call where we replace the array, We end up with an inverted triangle in C++. So we can append the results to an array at every iteration and print the entire array at the end.
#include <stdio.h>
#include <stdlib.h>
void printtle (int *a, int len, int len1) {
if (len == 1) return;
int fact=0;
for (int c = len; c <= len1; c++)
fact = fact + c;
for (int i=0; i<len-1; i++) {
a[fact+i] = a[i]+a[i+1];
}
printtle (a+fact,len-1,len1);
for (int i=fact;i<fact+len-1; i++) {
printf("%d\t",*(a+i));
}
printf("\n");
}
void print(int *a, int len) {
for(int i=0;i<len;i++) {
printf("%d\t", a[i]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
int a[15] = {4, 7, 3, 6, 7}, len=5;
printtle(a,5,5);
for(int i=0;i<5;i++){
printf("%d\t", a[i]);
}
return 0;
}
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = new int[] {4,7,3,6,7};
compute(input);
for(int i = 0; i < input.length; i++){
System.out.print(input[i] + " ");
}
}
public static void compute(int[] input){
if(input.length == 0)
return;
int newlength = input.length;
int newinput[] = new int[newlength - 1];
//if(input.length > 0){
for(int i = 0; i < input.length-1; i++){
//System.out.print(input[i]);
newinput[i] = input[i] + input[i+1];
}
//}
compute(newinput);
for(int i = 0; i < newinput.length; i++){
System.out.print(newinput[i] + " ");
}
System.out.print( "\n");
}
}
public class PrintTriangle {
/**
* @param args
*/
public static void main(String[] args) {
int[] array = {4,7,3,6,7};
printTriangle(array);
display(array);
}
private static void printTriangle(int[] array) {
int[] temp = new int[array.length -1];
for(int i = 0; i<array.length -1; i++){
temp[i] = array[i] + array[i + 1];
}
array = temp;
if(temp.length>1){
printTriangle(temp);
}
display(array);
}
private static void display(int[] array) {
for(int i = 0; i<array.length; i++){
System.out.print(array[i] + "\t");
}
System.out.println();
}
}
package p1;
import java.util.ArrayList;
public class triangle {
public static void main(String args[]){
int a[]={4,7,3,6,7};
boolean b=true;
int p,q,r,n=0,m=4;
ArrayList list=new ArrayList();
int var=0;
for(int i=0;i<a.length;i++)
{
list.add(a[i]);
var=i+1+var;
}
int len=list.size();
neww(list,len);
System.out.print("{{");
for(int i=0;i<len;i++){
System.out.print(list.get(i)+",");
}
System.out.print("}}");
}
static void neww(ArrayList list,int len)
{
int p,q,r,s=0;
ArrayList list1=new ArrayList();
for(int i=0;i<len-1;i++)
{
p=(int) list.get(i);
q=(int) list.get(i+1);
list1.add(p+q);
}
while(list1.size()!=0){
len=list1.size();
neww(list1,len);
System.out.print("{{");
for(int i=0;i<len;i++){
System.out.print(list1.get(i)+",");
}
System.out.print("}}");
System.out.println();
list1.clear();
}
}
}
Python Solution
def generateTriangle(curr):
output = list()
while(len(curr)>=1):
output.append(curr)
new = list()
for i in xrange(len(curr)-1,0,-1):
new.append(curr[i]+curr[i-1])
curr = new
#print reverse of output
for line in reversed(output):
print ", ".join(str(e) for e in line)
#print line
if __name__ == "__main__":
l = [4,7,3,6,7]
generateTriangle(l)
public class MainClass {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {4,7,3,6,7};
printTriangle(input);
}
public static void printTriangle(int[] a)
{
if(a.length <= 1)
{
return;
}
int[] temp = new int[(a.length-1)];
for(int i=0; i<(a.length-1); i++)
{
temp[i] = a[i] + a[i+1];
}
printTriangle(temp);
printArray(temp);
}
public static void printArray(int[] a)
{
int i= 0;
while(i <= a.length-1)
{
System.out.print(a[i]+" ");
i++;
}
System.out.println();
}
}
{
public class MainClass {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {4,7,3,6,7};
printTriangle(input);
}
public static void printTriangle(int[] a)
{
if(a.length <= 1)
{
return;
}
int[] temp = new int[(a.length-1)];
for(int i=0; i<(a.length-1); i++)
{
temp[i] = a[i] + a[i+1];
}
printTriangle(temp);
printArray(temp);
}
public static void printArray(int[] a)
{
int i= 0;
while(i <= a.length-1)
{
System.out.print(a[i]+" ");
i++;
}
System.out.println();
}
}
package Arrays;
public class ReverseTriangle {
public static void main(String[] args) {
int[] arr = {4, 7, 3, 6, 7};
printTriangle(arr);
}
public static void printTriangle(int[] arr) {
if(arr.length == 0)
return;
if(arr.length == 1) {
System.out.println(arr[0]);
return;
}
int[] newArray = new int[arr.length - 1];
for(int i = 0; i < arr.length - 1; i++)
newArray[i] = arr[i] + arr[i + 1];
printTriangle(newArray);
printArray(arr);
}
public static void printArray(int[] arr) {
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
public class triangle {
public static void print(int[] a, int n)
{
if(a.length>0)
{
int tmp[] = new int[n-1];
for(int i=0; i<n;i++)
{
if(i+1<n)
tmp[i]=a[i]+a[i+1];
}
print(tmp,tmp.length);
System.out.print("{{");
for(int i=0; i<n;i++)
{
System.out.print(a[i]+",");
}
System.out.println("}}");
}
}
public static void main(String[] args)
{
int a[] = {4,7,3,6,7};
print(a,a.length);
}
}
public class triangle {
public static void print(int[] a, int n)
{
if(a.length>0)
{
int tmp[] = new int[n-1];
for(int i=0; i<n;i++)
{
if(i+1<n)
tmp[i]=a[i]+a[i+1];
}
print(tmp,tmp.length);
System.out.print("{{");
for(int i=0; i<n;i++)
{
System.out.print(a[i]+",");
}
System.out.println("}}");
}
}
public static void main(String[] args)
{
int a[] = {4,7,3,6,7};
print(a,a.length);
}
}
public void buildSumTriangle(int[] inArray){
int len = inArray.length;
int[] revArray = new int[len*(len+1)/2];
int j = 0;
//Put the original array in reverse
for(int i=len-1;i>=0;i--){
revArray[j++] = inArray[i];
}
int beg = 0, end=len-1, iter=end+1;
// Add the rest in reverse
while(iter<revArray.length){
for(int i=beg;i<end;i++){
revArray[iter++]=revArray[i]+revArray[i+1];
}
beg=end+1;
end = iter-1;
}
//Print the array
printArray(len,revArray);
}
// Print in reverse order
public void printArray(int len,int[] revArray){
int k = revArray.length-1;
for(int i=0;i<len;i++){
for(int j=0;j<=i;j++){
System.out.print(revArray[k--]+" ");
}
System.out.println("");
}
}
}
public void buildSumTriangle(int[] inArray){
int len = inArray.length;
int[] revArray = new int[len*(len+1)/2];
int j = 0;
//Put the original array in reverse
for(int i=len-1;i>=0;i--){
revArray[j++] = inArray[i];
}
int beg = 0, end=len-1, iter=end+1;
// Add the rest in reverse
while(iter<revArray.length){
for(int i=beg;i<end;i++){
revArray[iter++]=revArray[i]+revArray[i+1];
}
beg=end+1;
end = iter-1;
}
//Print the array
printArray(len,revArray);
}
// Print in reverse order
public void printArray(int len,int[] revArray){
int k = revArray.length-1;
for(int i=0;i<len;i++){
for(int j=0;j<=i;j++){
System.out.print(revArray[k--]+" ");
}
System.out.println("");
}
}
}
import java.util.*;
public class Triangle {
/*
* Description: Given a array {{ 4,7,3,6,7}} construct a triangle like
* {{81}} {{40,41}} {{21,19,22}} {{11,10,9,13}} {{ 4,7,3,6,7}}
*/
public static void compute(int[] array) {
if (array.length == 1) {
System.out.println(Arrays.toString(array));
return;
} else {
int[] newArray = new int[array.length-1];
for(int i=0;i<array.length-1;i++){
newArray[i]=array[i]+array[i+1];
}
compute(newArray);
System.out.println(Arrays.toString(array));
}
}
public static void main(String[] args) {
int[] array = {1,2,3,4 };
// System.out.println(Arrays.toString(array));
compute(array);
}
}
As the triangle needs to be printed upside down, we need to call recursive method and then display. Below is modified code.
Output:
- Solution September 20, 2014{{81}}
{{40, 41}}
{{21, 19, 22}}
{{11, 10, 9, 13}}
{{4, 7, 3, 6, 7}}