TEST 3 Flashcards
(67 cards)
1
Q
Language
A
language defines a set of strings of comprised of characters from an “alphabet” of symbols – defines valid words and combos of words in a sentence
2
Q
Regular language
A
a language that can be formally described using a finite state machine
3
Q
Finite state machine
A
an abstract model of computation comprised of states + transitions
4
Q
Regular expression
A
a pattern used to search for a match within a string of text
5
Q
What two properties must hold in order for a finite state machine to be considered deterministic?
A
- Every transition requires that an event occur (char. be consumed)
2.There is at most one transition on the same event (character) out
of a particular state
6
Q
|
A
or
7
Q
[]
A
any single letter in word brackets
8
Q
[-]
A
match one single character from contgious range **a-c valid but c-a is not
9
Q
\
A
treat the next character literally, rather than as an operator; ie \“[cat]”\ then [cat] will be accepted
10
Q
why double \ not single
A
bc \ has special meaning as an example ie if we want to do a literal double qoute in a string and not end the string there we use \ to escape the literal
11
Q
?
A
match 0 or 1 instances of the preceding character or group;
12
Q
*
A
match 0 or more instances of the preceding character or group;
13
Q
+
A
match 1 or more instances of the preceding character or group;
14
Q
what is difference between + and *
A
+ means at least 1 * means can be 0
15
Q
Order of operations
A
- \
- [] including -
- ()
- ?
- concatenation (valid regex back to back)
- |
16
Q
public String substring(int startIdx)
A
returns the substring
from startIdx (inclusive) to the end
17
Q
String substring(int startIdx, int endIdx)
A
returns the substring from startIdx (inclusive) to endIdx (exclusive)
18
Q
public int indexOf(String str)
A
returns the start index of the
first occurrence of str in the string; returns -1 if str is not found
19
Q
public String replaceAll(String regex, String new)
A
a copy of the original string with every substring that matches regex replaced by new– can pass string literal or reg ex – reg ex adds additonal flexibality
20
Q
sentence
A
a sequence of strings in the language
21
Q
language
A
defines a set of strings of comprised of characters from an “alphabet” of symbols (does not have to be A-Z)
22
Q
sentence
A
a sequence of strings in the language
23
Q
grammar
A
definition of the structure of a valid sentence in the language
24
Q
syntax
A
the structural validity of a sentence
25
semantics
the meaning of a sentence
26
int x = “abc is
is syntactically valid, but semantically invalid
27
syntax analysis
the process of analyzing a sequence of symbols to see if they conform to a grammar
28
To implement a recursive descent parser for a given grammar, you need to define one function per [Your answer] , and each function should have one branch per [Your answer] .
production rule, delimiter
29
ad hoc pros and cons
Pros: often quicker & easier to write
when the grammar is simple
● Cons: less structured; less extensible; difficult to cover all cases for a more complex grammar
30
Recursive Descent
Pros: closely mirrors the grammar; highly
structured and easily extensible
● Cons: can be longer and more difficult to write if the grammar is simple (or if the grammar isn’t formally expressed)
31
Why JSON
Pros:
● Lightweight syntax (unlike XML)
● Designed to represent program data (unlike all others shown)
● Human readable (unlike protocol buffers)
hierarchal structure (unlike csv)
clear and concise way to rep arrays (unlike XML)
32
what are the internal representations of each of the following Java classes?
JSONArray: List
33
Creational Patterns:
Singleton, Factory, Builder
Patterns concerning creation of objects;
alternatives to invoking a constructor using new
34
Singleton Pattern:
35
Structural Patterns:
Composite, Adapter
Patterns concerning how objects and
components are structured
36
Behavioral Patterns:
Observer, Strategy, Visitor
Patterns concerning how responsibilities and algorithms are assigned and/or distributed across objects
37
Override:
38
Overload:
39
What is double dispatch? and why is it important?
40
Storage:
Long-term (files)
41
Memory:
Short-term (program data)
42
How is memory allocated?
Memory TO a program: done by OS
Memory WITHIN a program:
Manual: Programmer asks
Automatic: Runtime does it
43
Memory Organization:
Code: Instructions to be executed
Stack: One frame per function
Heap: Chunk of memory for longer-lasting data
44
How are primitive types stored?
Local variables value in stack frame
Fields/elements value in array/object
45
How are reference types stored?
Array/object always on heap
local variables address in stack frame
Fields/elements address in array/object
46
How is memory deallocated/freed?
Stack automatically after each function terminates
Heap:
Manual: Programmer frees memory
Automatic: Runtime detects and frees
variables not in use
47
Reference Counting:
Compiler: Inserts operations for incrementation
Runtime: Allocates, executes, frees
47
Reference Counting pros and cons:
Pros: Easy, happens immediately, good performance.
Cons: Single self-referencing, cycles
48
factory pattern
When to use it? When you want to create multiple instances, but
want to abstract away details of the creation process
KEYWORDS: method to use instead of constructor
49
builder
When to use it? When the logic for creating an instance of type T
involves many steps, including instantiating many objects
KEYWORDS: streamline, hierarchy, components
50
Composite Pattern
When to use it? When many parts comprise a whole, and you
want to define a functionality across the entirety of the structure
think about a figure composed of multiple shapes-- tree like structure
KEYWORDS: delegate
51
adapter pattern
When to use it? When you want to connect two incompatible
classes or interfaces (A and B)
■ Helps improve flexibility and reusability
■ If A interacts with B, you can change how one works without
changing the other
52
Trace-Based (Mark-Sweep):
Compiler: does nothing
Runtime: Allocates marks and sweeps
53
Trace-Based (Mark-Sweep) pros and cons:
Pros: Handles self-references, no overhead
Cons: "Stop the world" causes delays
54
Fragmentation:
Free space becomes non-contiguous
55
Mark-Sweep Compacts:
Removes dead objects and readdresses live objects so freed space is contiguous
56
observer pattern
When to use it? When you want one or more components to
“subscribe” to automatic updates from another component
KEYWORD: updates, notifies
57
strategy
When to use it? When you want to be able to choose from one of
multiple interchangeable algorithms or implementations
■ Decouples the algorithm from the class that it operates on
KEYWORD: single metric
58
visitor
When to use it? When you want to decouple an algorithm from
the structures that it operates on
■ Similar to the strategy pattern in this decoupling, but targets
algorithms that are distributed across multiple data types
■ More complex but more flexible than the strategy pattern
decouple, contiguous , multiple data types
59
double dispatch
instead of directly calling the method that encapsulates the algorithms we go through an extra layer of indirection thus 2 methods call are made to ensure correct algorithms executes
60
override
use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy
61
overload
use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy
62
difference between overriding and overloading
overloading differs in that one implenmentation isnt replacing another but rather they are coexisting with the context of the same class
63
The factory and builder patterns are similar in that they are each designed to
make it easier to construct a new instance of an object. What is the key
difference between them? (Hint: It has to do with the nature of the object being
constructed!)
The factory pattern is more focused on creating objects with a simple and
uniform construction process and provides a way to address the creation of
different related objects. On the other hand, the builder pattern is designed for
more complex object construction with a complex internal structure.
64
The strategy and visitor patterns are similar in that they both decouple an algorithm from the class on which it operates. What is the key difference between them?
The key difference lies in how the nature of the object influences the algorithm. In the strategy pattern, the algorithm's behavior is influenced by the strategy chosen at runtime for a specific context. In contrast, the visitor pattern is designed for scenarios where the algorithm needs to operate on various types of objects, and the double dispatch mechanism ensures that the correct algorithm is executed based on both the type of the object and the type of the visitor.
65
What is double dispatch, and why is it necessary in the visitor pattern? You should address the need for the accept() method as well as the need to re-define the accept() method within each concrete subclass of IVisitable.
Double dispatch in the Visitor pattern involves making two method calls to ensure the correct algorithm is executed. The first dispatch occurs when the accept() method is called on the object being visited, and the second dispatch happens when the visit() method is invoked on the visitor. This mechanism is necessary because the algorithm is distributed across multiple data types. The accept() method is crucial for the first dispatch, and re-defining it in each concrete subclass ensures polymorphic behavior, allowing the correct visit() method to be bound at runtime based on the types of both the object and the visitor.
66
how java determines between overriding and overloading
Overriding: The method to be executed is determined at runtime based on the actual type of the object. It's called dynamic dispatch. The JVM decides which version of the method to execute based on the actual type of the object at runtime.
Overloading: The method to be called is determined at compile time based on the method signature. The compiler selects the appropriate method to call based on the number and types of arguments used in the method invocation.
