A data structure is a group of data organized in the computer's memory by certain specific rules defining predictable relationships between the data. Arrays, hashes and relational databases are all examples of data structures.
Word: A certain number of bits that the computer can handle as a single datum. Modern operating systems use 64-bit words.
Verb: An operator, function or method
Noun: An object, data type or argument passed to a verb
Theta, or Θ, also sometimes referred to as 'Big O,' looks scary, but isn't. Θ is a constant, representing the amount of CPU time it takes the computer to perform one operation (on one word). You can think of Θ as the number 1, meaning you can ignore it.
A single operation represented in terms of Θ is
Θ(1)
Iterating over n values in a data structure represented in terms of Θ is
Θ(n)
Big words, simple concept. Assume that an algorithm performs in the slowest way it theoretically can. (For example, if it iterates over an array, you would assume the last value in the array were the answer). Then find the slope (also known as the derivative) of the curve of the time the algorithm takes to handle n objects.
An iteration over the entire data structure would be a line
Θ(n)
An iteration over the entire data structure with another nested iteration over the entire structure for each value would be an exponential curve
Θ(n^2)
Two iterations over the entire data structure would be a line
2Θ(n)
etc. etc.
Really don't overthink this, but look up 'asymptote' on Wikipedia if you want a refresher on what the word means.
Suppose you wished to find a 'peak' on an array of integers of size n. A 'peak' is here defined as an value in the array which is >= any neighboring values, if they exist. Any array of at least size 1 must necessarily have at least one peak.
One way that we could find a peak is to iterate over the array, comparing the current value to all neighboring values, and returning the current value if it is greater than or equal to all neighboring values. We can call this the 'naive algorithm,' and its asymptotic complexity can be represented as
Θ(n)
But there is a better way! Suppose we select the value at the midpoint of the array and compare it to all neighboring values. If it is a peak, return it. Otherwise, select the neighboring value that is greater than the midpoint, and compare it to its neighbor which is further from the midpoint, etc. etc. This is known as a 'binary search algorithm', and introduces two efficiencies over the naive algorithm. First, at most, only half the values in the array need be evaluated, and second, after the initial comparison of the midpoint to its neighbors, each value is only compared to one neighboring value rather than two. All this means that it has a significantly lower asymptotic complexity of approximately
Θ(log2(n))
We can also do it a worse way. Suppose, to put it in Ruby terms, we did this:
@arr.each { |val| return val if val >= @arr.sort.last }This way, during each step of the iteration over @arr, there is another, nested iteration (the #sort method). This will result in a severe performance penalty, because the asymptotic complexity now is approximately the square of the size of the array.
Θ(n^2)
Watch out for methods that iterate over an entire data structure, including but not limited to #sort, #reverse, #map, and #any?
| formula | algorithm |
|---|---|
| Θ(n^2) | nested iterations (plus one power of n for each additional nested iteration) |
| Θ(n) | iteration over a data structure |
| Θ(log2(n)) | binary search |
| Θ(1) | single operation |
- Nested iterations. These may not be immediately obvious.
- Iterations that can be replaced by a binary search.
- Steps after the solution is found or that aren't necessary to find it.
- Iterations and binary searches that can be replaced by a single operation.
For the purposes of algorithms, the best way to think about log2(n) is that it is the number of times n must be divided by 2 before n == 1.
Computers think in binary, so the only logarithm you're ever likely to see when determining the asymptotic complexity of an algorithm is log2. Θ(log2(n)) is common enough that it is sometimes abbreviated to just Θ(log2).
A pointer is the numeric address of a specific location in the computer's memory. For example, the character 'A' might be stored at the address 00000009, meaning the 9th byte in the computer's memory. The pointer '00000009' would therefore point to the value 'A'.
A pointer is also known as a reference.
If you have a map of the location of buried treasure, the X marking the spot on the map is a pointer, and the treasure itself is the value.
Note: It's a good idea to learn how to implement linked lists and binary trees in Ruby.
A linked list is a data structure where there is stored in a specific memory address both a value and a pointer to the next entry on the list, which in turn contains both a value and a pointer, until the last value on the list is reached.
A single linked list has pointers only to the next value on the list, so one entry on the list does not provide enough information to find any previous values in memory.
('A', -->) ('B', -->) ('C', -->) ('D')
A double linked list has pointers both to the next value and to the previous value, so any point on a double linked list can be found using the information in any entry.
('A', -->) (<--, 'B', -->) (<--, 'C', -->) (<--, 'D')
It takes only one computation to select any value of an array. To select a specific value of a linked list, the computer must start from the beginning (or end, with a double linked list) and iterate through the list until the value is reached. So, for example, the CPU time required to select value 500,000 in an array is
Θ(1)
while the CPU time required to select the same value in a linked list is
Θ(500,000)
Or, more generally
Θ(n)
A binary tree is a flow chart that the computer uses to find values at the end. You may recall them from the Huffman algorithm if you looked at the data compression assignment. Each branch of the binary tree is the result of a conditional and leads either to another conditional or an endpoint value, just like any other flowchart.
For example, in this binary tree, the branch True => False has the value 'bananas', and the branch False => False => True has the value 'spinach'.
True False
/ \
True False True False
/ \ / \
apples bananas microsofts True False
/ \
spinach brussels_sprouts
'True' and 'False' are sometimes referred to as 'left' and 'right' - same thing. Binary trees are a powerful data structure because they can be represented in terms of 1s and 0s; the lowest-level data the computer can understand. The same binary tree shown above can be represented with 1s and 0s, like below. This is why binary trees are useful for compression - the two bits '11' take up a far smaller amount of memory than the whole string 'apples'.
1 0
/ \
1 0 \
/ \ \
apples bananas \
1 0
/ \
microsofts \
1 0
/ \
spinach brussels_sprouts
Of course, some places will let you off pretty easy. The most common interview problem, believe it or not, is FizzBuzz(!) Still, good to review just to make sure you don't get tripped up on the easy stuff.
This is a good solution to FizzBuzz, pretty much as good as it gets in Ruby. Marginally faster than using 1.upto(100). In compiled languages you can get slightly faster by being showoffy and using fancy bit arithmetic, but not in Ruby.
(1..100).each do |i|
if i % 15 == 0
puts 'FizzBuzz'
elsif i % 3 == 0
puts 'Fizz'
elsif i % 5 == 0
puts 'Buzz'
else
puts i
end
endA solution like this is marginally faster in a non-garbage collected language like C++, but not in Ruby. Ruby has to create and destroy a new 'str' variable for each value of 'i', so it's more than twice as slow as the solution above. It is slightly fewer lines of code.
(1..100).each do |i|
str = ''
str = 'Fizz' if i % 3 == 0
str += 'Buzz' if i % 5 == 0
puts str.empty? ? i : str
endPoint is that it isn't a trick question and there's no secret clever way to do it.
Pretty comprehensive list (don’t let the title fool you) of dozens of common interview questions plus answers (in Java):
http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/
Shorter list of especially common questions:
Entire MIT algorithms course online:
Khan academy (explained at a slower pace and in something closer to layman’s terms, other courses on this site are also great for brushing up on your math skills):
https://www.khanacademy.org/computing/computer-science/algorithms
books discussed around algorithms: http://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/098478280X/ref=sr_1_4?ie=UTF8&qid=1427236073&sr=8-4&keywords=algorithms+unlocked
for advanced (or bed time reading) http://www.amazon.com/Introduction-Algorithms-3rd-Thomas-Cormen/dp/0262033844/ref=sr_1_2?ie=UTF8&qid=1427236073&sr=8-2&keywords=algorithms+unlocked (this was a text I used in my Computer Science program - despite my obsession with academic achievement, I’m not ashamed that I got a C in this class :-( Ok, maybe I’m still a bit bitter lol