Data Representation
How many bytes are in an int datatype in C?
4 bytes (32 bits)
In C, the "/" symbol performs a special type of division known as
Floor division
How many algorithmic cycles does an O(1) algorithm take to complete?
one.
How is memory represented in digital computers?
Binary! 0110011
What is the difference between a high-level and low-level programming language?
Bonus points if you give examples that aren't Python or C! (or C derivatives... or web development... web development languages aren't real languages....)
A high-level language utilizes much hardware and software abstraction to provide a more intuitive programming syntax.
Low-level languages are closer to machine code, and require more intentional manipulation of hardware.
How does a string (which is just an array of characters) know when it ends?
The \0 character, the NULL character, the terminating character.
This is the "logical or" operator. It will output a "true" boolean value if either value it is fed is true.
What are the advantages of having a sorted dataset? Is it always necessary to sort your dataset? If you sort your dataset once, when, if ever, do you have to sort it again?
more open-ended
What are the two "main" types of memory? How are they different?
Static memory (Hard drive memory) is made to be permanent and is made by physically altering electronic components.
Dynamic memory is made to be temporary and exists as a voltage in memory cells.
Explain the difference between global and local variables.
In actual written code, how do you differentiate global and local variables?
Global variables can be seen and accessed by all parts of your program. They are not bound by the narrow walls of any function. Local variables are automatically deallocated (freed) when their function closes.
Global variables are written outside of function declarations and local variables are written within them.
How many codes are there in the ASCII table?
128. This is because chars are only 1 byte, 8 bits, or 128 combinations large.
The "%" symbol is called the ____ and performs ____.
Modulo operator
Calculates the remainder of a division
What is the difference between O(n) and Ω(n)?
O(n) describes the worst-case scenario (we usually care more about this one)
Ω(n) describes the best-case scenario
What is the difference between the stack and heap? (i.e., what "type" of data does each one store?)
The stack stores static memory (automatic variables, software memory, etc)
The heap stores dynamic memory (file i/o, memory allocations!)
*note that the stack is stored in Last-In/First-Out (LIFO) format.
Describe recursion. (100 pts)
How can we implement recursion in code? (100 pts)
What is it called when a recursive function has no way to exit? What is the exit path for a recursive function called? (100 pts)
Recursion is the act of a function calling itself.
Define a function and within the function definition write the function call.
It is an infinite loop. The base case is the exit path for a recursive function.
What is two's complement and why do we use it? (200 pts)
Translate this value from two's complement binary to decimal: 11010011 (200 pts)
Two's complement is a way to represent signed binary data. You take a positive value, flip the bits, and add +1. It makes addition, subtraction, and other basic operations much easier in binary.
The "&" symbol is called the ______.
Address-of-operator
Explain how hash tables work and why we use them. (200 pts)
Come up with a creative new hash function. (200 pts)
Hash tables work by splitting data into sub-arrays (buckets) based on an unchanging categorization of the data itself (hash value). They reduce time complexity by allowing us to iterate over smaller sub-arrays.
I'll judge your hash function!
What is a segmentation fault? (300 pts)
How do you go about fixing one? (100 pts)
A segmentation fault is a memory error where your program tried to access (read or write) memory that is "outside of the scope of its jurisdiction", i.e., it is an illegal memory access.
Describe how floating-point representation works.
Floating-point representation is a signed datatype that takes a scientific notation exponent value and a regular binary value to represent extremely large values or decimal values.
How many bytes make up this struct:
typedef struct {
char symbol[2];
uint16_t atomic_num;
float atomic_weight;
int* next_element;
} periodic_table;
12 bytes
OR
16 bytes (with padding)
The "<<" operator is known as the _______ and is used in computer hardware to perform _______.
Left-bitwise shift operator
Multiplication
Start at an initial value, the "root" (100 pts)
Move "left" or "right" in the tree depending on the condition of the current value (200 pts)
Check the value at each node and repeat until you have found your desired value (100 pts)
Binary search trees reduce algorithmic time complexity by splitting arrays in "half" and have a Big-O Notation of O(log(n)).
For an image that is 1920x1080 pixels large and uses a (primitive) color encoding of 2-bits per color channel per pixel,
1. How many color combinations are there?
2. How much memory does this image take up in bytes? (what is its file size)
1. 64 different color combinations; 2 bits per R, G, B channel, 6 bits total, 2^6 = 64 combinations.
2. 6 bits * 2,073,600 pixels = 12,441,600 bits, 12,441,600 / 8= 1,555,200 bytes, which can be abbreviated as 1.55 MB.
int main()
int a[3] = {1, 2, 3}, *p = a, *m = &p;
(*p)++; p++; a[1] = *p + **m;
int b = a[p - a]; p = &a[b - 2];
printf("%d %d %d\n", a[0], a[1], *p);
}
What does this code do?
An array of size 3 {1, 2, 3} is made. p is made pointing to the very beginning of a[]. m points to p. p is dereferenced and incremented. p moves to the next index. The 2nd index (a[1]) is set to p (a[1]) plus **m (still a[0], that one hasn't changed!) a[p - a] is tricky, but since p is just 1 index more than a, it is just saying a[1]. Finally, p is set to the address of a[4-2], or a[2].
print result = "2 4 3"