Warning This class is being recorded.
Getting started (this will be our normal start-of-class sequence)
Approximate overview
Academic
Cultural
Peer
Wellness
When will the mentors survey us about mentor sessions?
Soon. We learned about timeliness from Sam and PM.
The most common forms of technical interviews are unjust and inequitable.
In this class, we’re going to practice because
As an interviewee, there are normally three parts to each tech interview
Reminder of TLAs:
Queue: A collection of values that you visit one-by-one that follow the first-in, first-out principle.
Stack: A collection of values that you visit one-by-one that follow the last-in, first-our principle.
Map/Hash: A collection of values indexed by strings.
Priority Queue: A collection of values that you visit one-by-one that follow the “most important out” principle.
Set: A collection of values which exists primarily to check membership.
Tree: A hierachical collection of values.
An automatically expandable collection of data indexed by numbers, usually from 0 to the size.
Note: At least for this example, we’re willing to sacrifice constant-time access in order to get expandability.
void arr.set(int index, Value v) - set or change a valueValue arr.get(int index)int arr.length()Array makeArray(Value default) or
Array makeArray(Type t) or
Array makeArray().arr.remove(int index) - remove a value and then shift everything down
one. (SamR says no; can be implemented with simpler operations)int indexOf(Value v) = for (int i = 0; i < arr.length(); i++) { if arr.get(i) == v) return i; }mapvoid addToEnd(Value v) = arr.set(arr.length()+1, v)boolean isEmpty() = arr.length() == 0boolean hasRoom()pop : Remove the last element and decrease the size by one.
(Not relevant to the core goal of “collection indexed by number”)void remove(int index) - remove the value at the given index
without shifting. Requires we change get to signal empty cells.get? (We’ll set a default value.)Should you use return and break in the middle of loops?
No: It makes analysis much harder.
Yes: 99% of programmers do so.
for (int i = 0; i < arr.length; i++) {
if predicate(arr.get(i)) {
return i;
}
} // for
// Signal failure
This is fast, but the early break from the loop can be hard to analyze. (You’ll learn a bit about loop invariants here and in 301.)
int result = -1;
for (int i = 0; i < arr.length; i++) {
if predicate(arr.get(i)) {
result = i;
}
} // for
if (result == -1)
// signal failure
else
return result;
This one is easier to analyze, but potentially much slower.
int result = -1;
for (int i = 0; i < arr.length && result == -1; i++) {
if predicate(arr.get(i)) {
result = i;
}
} // for
The last one is fast and analyzable, but hard to read.
How do we structure memory so that we have set(i,v), get(i), length(), and create(val).
Suppose you’ve decided to implement arbitrary size arrays using the built-in (fixed-size) arrays. How do you now implement the four key operations?
Value get(int i)set(int i, Value v)size()create(Value initial)Hmmm … since I’m using the fixed-size arrays, I’ll need a variable
to keep track of that array. I’ll call it arr.
What is the size after we initialize? Assume the default size is 0.
Okay, that means that I’ll likely have two different sizes at play, the
“size” that the client sees and the “size” of the underlying array.
Let’s call the first one size and the second one capacity.
Can I assume that the built-in arrays have their own size function?
Yes, you’re working in Java.
Awesome. So I don’t need capacity. That’s just the size of the
underlying array.
At some point, I’ll need to allocate more space because someone will index beyond the end of the array. Do you have a preferred policy for how large the new array should be? What do you think you should do?
Hmmm. One option is to just enlarge to just big enough to support the new element. That’s easy. But I seem to recall learning in data structures that when I expand an array, I should double the size of the array. I don’t remember why, though. I’ll figure