1 of 74

Introduction to Java

Theoretical Lab 1

CS 61BL Summer 2024

2 of 74

Announcements

Quiz 1 opens Friday at 10 AM, closes Monday at 11:59 PM

Time limit of 1 hour
Closed book, closed notes, closed IDE

Project 0 due Sunday 6/23 11:59 PM

Being a Good Classmate is required

Weekly survey will be due Monday 11:59 PM

CS 61BL Summer 2024

3 of 74

Content Review (Java Basics)

CS 61BL Summer 2024

4 of 74

Quick Java Basics

public class Hello {

public static void main(String[] args) {

System.out.println(“Hello world!”);

}

In Java, pretty much everything is defined in a class
Type declarations: Java is statically typed, so we have to tell the computer what type of value every variable holds and what every function returns (ie. int, void)
Don’t forget the brackets and semicolons!

CS 61BL Summer 2024

5 of 74

Worksheet (Q1)

CS 61BL Summer 2024

6 of 74

1 Our First Java Program

size = 27;
name = "Fido";
Dog myDog = new Dog(name, size);
Dog yourDog = new Dog("Scruffy", 1000);
Dog[] dogList = new Dog[3];
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

7 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
name = "Fido";
Dog myDog = new Dog(name, size);
Dog yourDog = new Dog("Scruffy", 1000);
Dog[] dogList = new Dog[3];
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

8 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size);
Dog yourDog = new Dog("Scruffy", 1000);
Dog[] dogList = new Dog[3];
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

9 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000);
Dog[] dogList = new Dog[3];
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

10 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3];
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

11 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog;
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

12 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog;
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

13 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5;
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

14 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5; // dogList can only contain Dog objects!
dogList[3] = new Dog("Cutie", 8);
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

15 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5; // dogList can only contain Dog objects!
dogList[3] = new Dog("Cutie", 8); // Index 3 out of bounds for array of size 3
int x;
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

16 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5; // dogList can only contain Dog objects!
dogList[3] = new Dog("Cutie", 8); // Index 3 out of bounds for array of size 3
int x; // declared a new int variable x
x = size - 5;
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

17 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5; // dogList can only contain Dog objects!
dogList[3] = new Dog("Cutie", 8); // Index 3 out of bounds for array of size 3
int x; // declared a new int variable x
x = size - 5; // x is now 22
if (x < 15) {
myDog.bark(8);
}

CS 61BL Summer 2024

18 of 74

1 Our First Java Program

int size = 27; // variables need to be declared with correct type
String name = "Fido"; // variables need to be declared with correct type
Dog myDog = new Dog(name, size); // a new Dog instance myDog
Dog yourDog = new Dog("Scruffy", 1000); // a new Dog instance yourDog
Dog[] dogList = new Dog[3]; // new length 3 array of Dog objects
dogList[0] = myDog; // put myDog in position 0 of dogList
dogList[1] = yourDog; // put yourDog in position 1 of dogList
dogList[2] = 5; // dogList can only contain Dog objects!
dogList[3] = new Dog("Cutie", 8); // Index 3 out of bounds for array of size 3
int x; // declared a new int variable x
x = size - 5; // x is now 22
if (x < 15) { // evaluates to false, so myDog.bark(8) is never called
myDog.bark(8);
}

CS 61BL Summer 2024

19 of 74

1 Our First Java Program

myDog.evolve(200);
Dog.evolve(300);
Dog.bark(10);

class Dog {

public static int cuteness = 100;

public Dog(String name, int size) { … }

public void bark(int loudness) { … }

public static void evolve(int newCuteness) {

System.out.println("Becoming cuter...");

cuteness = newCuteness;

}

CS 61BL Summer 2024

20 of 74

1 Our First Java Program

myDog.evolve(200); // Calling static method as instance OK, all dogs have cuteness 200 now
Dog.evolve(300);
Dog.bark(10);

class Dog {

public static int cuteness = 100;

public Dog(String name, int size) { … }

public void bark(int loudness) { … }

public static void evolve(int newCuteness) {

System.out.println("Becoming cuter...");

cuteness = newCuteness;

}

CS 61BL Summer 2024

21 of 74

1 Our First Java Program

myDog.evolve(200); // Calling static method as instance OK, all dogs have cuteness 200 now
Dog.evolve(300); // Calling static method with class name OK, all dogs have cuteness 300 now
Dog.bark(10); // Cannot call instance method using class name, need to know what instance of the Dog class is barking

class Dog {

public static int cuteness = 100;

public Dog(String name, int size) { … }

public void bark(int loudness) { … }

public static void evolve(int newCuteness) {

System.out.println("Becoming cuter...");

cuteness = newCuteness;

}

CS 61BL Summer 2024

22 of 74

Content Review (Conditionals, Loops, and Arrays)

CS 61BL Summer 2024

23 of 74

While Loops

(Taken from lab spec) Pay close attention to when the while loop terminates.

CS 61BL Summer 2024

24 of 74

For Loops

CS 61BL Summer 2024

25 of 74

break and continue keywords

Break keyword exits the entire loop as soon as the keyword is processed (if there are multiple loops, it exits the innermost loop)
Continue keyword exits that iteration of the loop (still increments and checks the loop test)
Why do we do this?

Save time (you’ll learn about runtime later in the class), but TLDR is you want your programs to be as efficient as possible

CS 61BL Summer 2024

26 of 74

Arrays in Java

Different than Python - you have to specify a type for every element in the array (no more Python lists with [3, “cheese”, Puppy])
Immutable length! You have to choose a length when you instantiate the array

This is a headache - and we’ll find out how to get around this when we explore more data structures.

CS 61BL Summer 2024

27 of 74

Arrays

Structure for declaration: <type of object in the array>[] <variable name>;

One way to instantiate:

Declare and instantiate at once:

CS 61BL Summer 2024

28 of 74

Worksheet (Q2 & Q3)

CS 61BL Summer 2024

29 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

29

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

30 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

30

3

0

4

6

3

2

inputArray

k

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

31 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

31

3

0

4

6

3

2

inputArray

k

4

x

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

32 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

32

3

0

4

6

3

2

inputArray

k

4

x

2

answer

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

33 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

33

3

0

4

6

3

2

inputArray

k

4

x

2

answer

3

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

34 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) { // True
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

34

3

0

4

6

3

2

inputArray

k

4

x

2

answer

3

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

35 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) { // False
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

35

3

0

4

6

3

2

inputArray

k

4

x

2

answer

3

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

36 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index]; // Skip this line
answer = index; // and this one
}
index = index + 1;
}
return answer;
}

36

3

0

4

6

3

2

inputArray

k

4

x

2

answer

3

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

37 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

37

3

0

4

6

3

2

inputArray

k

4

x

2

answer

4

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

38 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) { // still True
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

38

3

0

4

6

3

2

inputArray

k

4

x

2

answer

4

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

39 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) { // True
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

39

3

0

4

6

3

2

inputArray

k

4

x

2

answer

4

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

40 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

40

3

0

4

6

3

2

inputArray

k

3

x

2

answer

4

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

41 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

41

3

0

4

6

3

2

inputArray

k

3

x

4

answer

4

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

42 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

42

3

0

4

6

3

2

inputArray

k

3

x

4

answer

5

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

43 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) { // False
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

43

3

0

4

6

3

2

inputArray

k

3

x

4

answer

5

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

44 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) { // Skip
x = inputArray[index]; // all
answer = index; // of
} // these
index = index + 1; // lines
}
return answer;
}

44

3

0

4

6

3

2

inputArray

k

3

x

4

answer

5

index

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

45 of 74

2 Mystery

public static int mystery(int[] inputArray, int k) {
int x = inputArray[k];
int answer = k;
int index = k + 1;
while (index < inputArray.length) {
if (inputArray[index] < x) {
x = inputArray[index];
answer = index;
}
index = index + 1;
}
return answer;
}

45

Return: 4

The returned value is the index of the smallest value in the array that occurs at or after index k.

What does this return when the input array is [3, 0, 4, 6, 3] and k is 2?

What does mystery do, in plain English?

CS 61B Summer 2023

46 of 74

2 Mystery

public static void sortArray(int[] inputArray) {
int index = 0;
while (index < inputArray.length) {
int targetIndex = __________________________;
int temp = _________________________________;
____________________________________________;
____________________________________________;
index = index + 1;
}
}

Use mystery to sort a given array of integers in ascending order.

Hint: Can you use what mystery returns to swap integers within the array?

CS 61BL Summer 2024

47 of 74

2 Mystery

public static void sortArray(int[] inputArray) {
int index = 0;
while (index < inputArray.length) {
int targetIndex = mystery(inputArray, index);
int temp = _________________________________;
____________________________________________;
____________________________________________;
index = index + 1;
}
}

Use mystery to sort a given array of integers in ascending order.

Hint: Can you use what mystery returns to swap integers within the array?

CS 61BL Summer 2024

48 of 74

2 Mystery

public static void sortArray(int[] inputArray) {
int index = 0;
while (index < inputArray.length) {
int targetIndex = mystery(inputArray, index);
int temp = inputArray[targetIndex];
____________________________________________;
____________________________________________;
index = index + 1;
}
}

Use mystery to sort a given array of integers in ascending order.

Hint: Can you use what mystery returns to swap integers within the array?

CS 61BL Summer 2024

49 of 74

2 Mystery

public static void sortArray(int[] inputArray) {
int index = 0;
while (index < inputArray.length) {
int targetIndex = mystery(inputArray, index);
int temp = inputArray[targetIndex];
inputArray[targetIndex] = inputArray[index];
____________________________________________;
index = index + 1;
}
}

Use mystery to sort a given array of integers in ascending order.

Hint: Can you use what mystery returns to swap integers within the array?

CS 61BL Summer 2024

50 of 74

2 Mystery

public static void sortArray(int[] inputArray) {
int index = 0;
while (index < inputArray.length) {
int targetIndex = mystery(inputArray, index);
int temp = inputArray[targetIndex];
inputArray[targetIndex] = inputArray[index];
inputArray[index] = temp;
index = index + 1;
}
}

Use mystery to sort a given array of integers in ascending order.

Hint: Can you use what mystery returns to swap integers within the array?

CS 61BL Summer 2024

51 of 74

2 Mystery (Extra)

public static int mysteryRecursive(int[] inputArray, int k) {
return ___________________________;
}
public static int mysteryRecursiveHelper(int[] inputArray, int minIndex, int index) {
if (_____________________) {
return ________;
}
if (__________________) {
return ________;
}
return _______;
}

Implement mystery recursively.

CS 61BL Summer 2024

52 of 74

2 Mystery (Extra)

public static int mysteryRecursive(int[] inputArray, int k) {
return mysteryRecursiveHelper(inputArray, k, k + 1);
}
public static int mysteryRecursiveHelper(int[] inputArray, int minIndex, int index) {
if (index == inputArray.length) {
return minIndex;
}
if (inputArray[index] < inputArray[minIndex]) {
return mysteryRecursiveHelper(inputArray, index, index + 1);
}
return mysteryRecursiveHelper(inputArray, minIndex, index + 1);
}

Implement mystery recursively.

CS 61BL Summer 2024

53 of 74

2 Mystery (Extra)

public static int mysteryRecursive(int[] inputArray, int k) {
return mysteryRecursiveHelper(inputArray, k, k + 1);
}
public static int mysteryRecursiveHelper(int[] inputArray, int minIndex, int index) {
if (index == inputArray.length) {
return minIndex;
}
if (inputArray[index] < inputArray[minIndex]) {
return mysteryRecursiveHelper(inputArray, index, index + 1);
}
return mysteryRecursiveHelper(inputArray, minIndex, index + 1);
}

Implement mystery recursively.

the index of min. element seen so far.

the index of the next element to examine.

If examined element is smaller, change minIndex

Otherwise, don’t change minIndex

CS 61BL Summer 2024

54 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = ____; ____________; ____________) {

for (int j = ____; ____________; ____________) {

if (____________________________) {

return ______________________________;

}

Given an array of numbers nums, find two numbers in nums such that adding them would

result in the value target. Assume that only one such pair exists, and there is

always a pair that fulfills the condition. Return the numbers as an array with two

terms.

CS 61BL Summer 2024

55 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = ____; ____________; ____________) {

for (int j = ____; ____________; ____________) {

if (____________________________) {

return ______________________________;

}

Algorithm idea: iterate through the array, and for every element in the array, sum that element with all combination of elements. If the result equals target, then we can return those two elements.

Better Algorithm Idea: iterate through the array, and for every element in the array, sum that element with all combination of elements to the right. If the result equals target, then we can return those two elements.

CS 61BL Summer 2024

56 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (____________________________) {

return ______________________________;

}

Algorithm idea: iterate through the array, and for every element in the array, sum that element with all combination of elements to the right. If the result equals target, then we can return those two elements.

CS 61BL Summer 2024

57 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

return new int[]{nums[i], nums[j]};

}

return new int[]{0, 0};

}

Algorithm idea: iterate through the array, and for every element in the array, sum that element with all combination of elements to the right. If the result equals target, then we can return those two elements.

CS 61BL Summer 2024

58 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

return new int[]{nums[i], nums[j]};

}

Algorithm idea: iterate through the array, and for every element in the array, sum that element with all combination of elements to the right. If the result equals target, then we can return those two elements.

CS 61BL Summer 2024

59 of 74

3 Two Sum

int[] twoSum(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

return new int[]{nums[i], nums[j]};

}

Note: This is a common problem used in interviews, but this approach isn’t optimized. Later in the course, you’ll learn how to use data structures to make your code even faster!

CS 61BL Summer 2024

60 of 74

Worksheet (Q4)

CS 61BL Summer 2024

61 of 74

4 Reversals

In this problem, we are trying to implement a reverseString method. This method

takes in a string and reverses it.

1 public static String reverseString(String s) {

2 // Implementation to be filled in

3 }

(a) For each of the test cases we have written below, write down whether it’s a

correct and useful test case, and briefly explain why.

CS 61BL Summer 2024

62 of 74

4 Reversals

assertThat(“hello world”).isEqualTo(“dlrow olleh”);

This wouldn’t work because we didn’t actually call the method reverseString. Key takeaway: always call the method you are trying to test!

assertThat(reverseString(“Hello”)).isEqualTo(“olleH”);

This works well and tests the reversal of a given word.

assertThat(reverseString(1234)).isEqualTo(4321);

This would give a compiler error: the method reverseString is supposed to take in a String, while an int is given.

assertThat(reverseString(“@#_!”)).isEqualTo(“!_#@”);

This works well and tests whether reversals work for special characters.

assertThat(reverseString(“”)).isEqualTo(“”);

This works well and tests whether reversals work for empty strings - a common edge case.

assertThat(reverseString(“baaaa”)).isEqualTo(“aaaab”);

This would also work as a test case.

CS 61BL Summer 2024

63 of 74

4 Reversals

We have the current implementation for reverseString.

1 public static String reverseString(String s) {

2 return s.substring(1) + s.charAt(0);

3 }

assertThat(reverseString(“Hello”)).isEqualTo(“olleH”);

This test would fail because our implementation would return "elloH".

assertThat(reverseString(“”)).isEqualTo(“”);

This test would fail because our implementation would be trying to access index 1 for a string of length 0, resulting in an IndexOutOfBoundsException.

assertThat(reverseString(“baaaa”)).isEqualTo(“aaaab”);

This test would pass because our implementation would return "aaaab", which is the same as the expected answer. The key takeaway from this is that buggy implementations sometimes won’t be caught if your test cases are not comprehensive.

CS 61BL Summer 2024

64 of 74

4 Reversals

We will now write a correct implementation for reverseString.

public static String reverseString(String str) {

________________________________

for (_________________; _________________; _________________) {

_________________

}

________________________________

}

CS 61BL Summer 2024

65 of 74

4 Reversals

We will now write a correct implementation for reverseString.

1 public static String reverseString(String str) {

2 String reversed = "";

3 for (int i = str.length() - 1; i >= 0; i--) {

4 reversed += str.charAt(i);

5 }

6 return reversed;

7 }

CS 61BL Summer 2024

66 of 74

Worksheet (Q5, Extra)

CS 61BL Summer 2024

67 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = _______________________________;

if (_________________________) {

_____________________________________________;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

68 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (_________________________) {

_____________________________________________;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

69 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

70 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

71 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

72 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = (i + rightShift) % A.length;

_____________________________________________;

}

return newArr;

}

CS 61BL Summer 2024

73 of 74

5 Rotate

We’d like to implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, wrapping to the other side as necessary.

Negative k means shifting towards the left.

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = (i + rightShift) % A.length;

newArr[newIndex] = A[i];

}

return newArr;

}

CS 61BL Summer 2024

74 of 74

bit.ly/su24-tlab-1

CS 61BL Summer 2024