GLA-01: Java, Big O and Lists

Overview and Submission Requirements

Your task is to work individually to create a series of methods that can solve tech interview questions, as well as analyze the computational complexity of these solutions. You should complete your entire lab in a single file named InterviewQuestions.java. Once you have completed the lab, you should submit InterviewQuestions.java to D2L.

External Resources and Code

As per the Academic Integrity guidelines, you may not copy code (even with modification) from anywhere, including the internet, other students, or your textbook. You may not consult other students or look at their code. You may not share your code with other students. Any submission that violates the academic honesty guidelines will receive an automatic 0 and will be considered an academic honesty violation.

Background: Tech Interviews

Technical interviews are a common part of the hiring process in the software development field. Although they can range in format, one of the most common techniques is to ask candidates to solve a couple of programming problems on a whiteboard and then explain their solutions. This GLA takes the form of a number of small programming problems that could appear in such an interview.

For each problem, implement the method in InterviewQuestions.java, explain what n is, and state the Big(O) complexity of your solution.

Problem One: Pricey Neighbours

Suppose you have an array of doubles that represents the value of each house on a long block of houses. Find the three adjacent houses that have the largest combined value, and return the smallest index of the array (leftmost house). Your solution should be of the form: (Note: you may use the provided template) public int findPriceyNeighbours(double[] prices)

The method header should state what n is (Java Commented form), and what the Big(O) complexity of your solution is.

Problem Two: Common Friends

Suppose you have two ArrayLists, each of which represents the friends of a single person. Write a method to find the common friends between those two people-- that is, a list of Strings that appear in both input lists. Your solution should be of the form: (Note: you may use the provided template) public ArrayList commonFriends(ArrayList friendListOne, ArrayList friendListTwo)

The method header should state what n is (Java Commented form), and what the Big(O) complexity of your solution is.

Problem Three: Count Divisors (Note: you may use the provided template)

Suppose you have an array of integers. Count each pair of indices in that array in which the value at the first index is evenly divisible by the values at the following indices.

Your solution should be of the form: public int countDivisors(int[] values)

The method header should state what n is (Java Commented form), and what the Big(O) complexity of your solution is.

Problem Four: First Odd Number

Suppose you have an array of integers. All of the integers from indexes 0 up to (But not including) a target index are even. All integers from that target index onwards are odd. Given such an array, find the index of the first odd number.

Your solution should be of the form: (Note: you may use the provided template) public int findIndexOfFirstOddNumber(int[] numbers)

The method header should state what n is (Java Commented form), and what the Big(O) complexity of your solution is.

I have a starter code: do not change anything on the second file of code:

FIRST file would be named InterviewQuestions.java:

import java.util.ArrayList;

public class InterviewQuestions {

public int findPriceyNeighbours(double[] prices)

{

//ToDo

return -1;

}

public ArrayList commonFriends(ArrayList friendListOne, ArrayList friendListTwo)

{

ArrayList common=new ArrayList();

//ToDo

return common;

}

public int countDivisors(int[] values)

{

//ToDo

return -1;

}

public int findIndexOfFirstOddNumber(int[] numbers)

{

//ToDo

return -1;

}

}

SECOND FILE named InterviewQuestionsTest.java(DO NOT CHANGE ANYTHING)

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Random;

public class InterviewQuestionsTest {

private static Random r;

static

{

r=new Random(2);

}

public static int [] GetRandomArray(int n, int min, int max)

{

int []a=new int[n];

for(int i=0; i

{

a[i]=r.nextInt(max-min+1)+min;

}

return a;

}

public static void displayDoubleArray(double []a)

{

for(int i=0; i

{

System.out.printf("%.2f ",a[i]);

}

}

public static void displayIntArray(int []a)

{

for(int i=0; i

{

System.out.print(a[i]+" ");

}

}

public static ArrayList getNRandomNames(int n, ArrayListnameList)

{

ArrayList friendList=new ArrayList();

for(int i=0; i

{

friendList.add(nameList.get(r.nextInt(nameList.size())));

}

return friendList;

}

public static void displayNames(String name, ArrayListnameList)

{

System.out.print(name+"'s Friend List: ");

for(var n : nameList)

{

System.out.print(n+", ");

}

System.out.println();

}

public static void makeEvenAllThenOddAll(int []numbers, int pos)

{

for(int i=0; i

{

if(numbers[i]%2==1)

{

numbers[i]++;

}

}

for(int i=pos; i

{

if(numbers[i]%2==0)

{

numbers[i]++;

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

InterviewQuestions solution=new InterviewQuestions();

int n=10;

double []HousePrice= Arrays.stream(GetRandomArray(n, 500000, 1000000)).asDoubleStream().toArray();

System.out.println("Problem One: Pricey Neighbours");

System.out.println("House Prices: ");

displayDoubleArray(HousePrice);

System.out.println("First index of Pricey Neighbours is: "+ solution.findPriceyNeighbours(HousePrice));

System.out.println(" Problem Two: Common Friends");

ArrayListnameList= new ArrayList<>(List.of(

"Liam", "Noah", "Oliver", "William","Elijah","James","Benjamin","Lucas","Mason","Ethan","Alexander","Henry","Jacob","Michael", "Daniel",

"Logan","Jackson","Sebastian","Jack","Aiden","Owen","Samuel","Matthew","Joseph","Levi","Mateo","David","John","Wyatt"));

ArrayList davidsFriends=getNRandomNames(10,nameList);

displayNames("David", davidsFriends);

ArrayList susansFriends=getNRandomNames(10,nameList);

displayNames("Susan", susansFriends);

ArrayList commonFriends=solution.commonFriends(davidsFriends, susansFriends);

displayNames("Common Friends", commonFriends);

System.out.println(" Problem Three: Count Divisors");

n=6;

int []values=GetRandomArray(n, 5, 20);

displayIntArray(values);

System.out.println(" Count: "+solution.countDivisors(values));

n=10;

System.out.println(" Problem Four: First Odd Number");

int []numbers=GetRandomArray(n, 10, 50);

makeEvenAllThenOddAll(numbers, r.nextInt(n));

displayIntArray(numbers);

System.out.println(" First odd number's index is: "+solution.findIndexOfFirstOddNumber(numbers));

}

}

/*If you have implemented your GLA correctly, the following will be your program's output:

Problem One: Pricey Neighbours

House Prices:

622968.00

520112.00

840169.00

925050.00

916256.00

909680.00

650372.00

979577.00

656166.00

891104.00

First index of Pricey Neighbours is: 3

Problem Two: Common Friends

David's Friend List: Jacob, Benjamin, Joseph, Owen, Michael, Lucas, Wyatt, Owen, Jacob, Alexander,

Susan's Friend List: Jack, Alexander, Samuel, Henry, Daniel, Logan, Joseph, Benjamin, Sebastian, Wyatt,

Common Friends's Friend List: Benjamin, Joseph, Wyatt, Alexander,

Problem Three: Count Divisors

10 13 20 15 13 10

Count: 3

Problem Four: First Odd Number

16 20 40 12 35 19 23 31 35 11

First odd number's index is: 4

*/