Algorithms
What algorithm halves the search space of the array it's operating on at each step?
binary search
In an array of size N, what is the valid range of nonnegative indices in Python?
0 to N - 1
What programming language is known for using indentation instead of braces?
Python
Who invented the Turing machine?
Alan Turing
What does CPU stand for?
Central Processing Unit
Which sorting algorithm repeatedly takes the minimum element and moves it towards the left?
Selection sort
Which data structure follows a first-in-first-out (FIFO) order?
queue
What is the minimum code length (in characters) required to print "Hello World" in Python 3?
20
Who is known as the "father of the computer"?
Charles Babbage
What does HTML stand for?
Hyper Text Markup Language
What is the theoretical optimal time complexity for comparison-based sorting algorithms?
O(n log n)
What data structure maintains elements in sorted order, taking worst case O(log(n)) per operation? Be specific.
balanced binary search tree (eg. AVL tree, B tree, C++ set, C++ PBDS)
What programming language only uses the following characters? <>.,+-[]
Brainf***
What woman is often considered the first computer programmer?
Ada Lovelace
What does API stand for?
Application Programming Interface
What is the optimal time complexity to solve the following problem? Determine whether a graph (V vertices, E edges) is bipartite (can be colored with black and white such that no 2 adjacent vertices have the same colour).
O(V + E)
The names of which two recursively-structured data structures differ only by a single letter?
tree and trie
Which family (of functional programming languages) is famous (for its (many) parentheses)?
Lisp
Who invented Python?
Guido van Rossum
What does URL stand for?
Uniform Resource Locator
In a tree with N nodes (N > 2), what is the maximum possible number of unique paths with a length equal to the diameter (longest path in the tree)? Express in terms of N.
(N - 1)(N - 2)/2 or (N - 1 choose 2)
What properties are needed in a function to use prefix values to do range [L, R] queries?
associative + invertible
What 2D esoteric programming language was invented in 1993 by Chris Pressey?
Befunge
What was the name of the first general-purpose electronic computer, built in 1945?
ENIAC
What does ACID stand for in database transactions?
Atomicity, Consistency, Isolation, Durability