Less rigorously, you could have intuitively realized that the cube's surface area depends on N2. Therefore, you could conclude that the run time is O(N2) without doing the full calculation.
Less rigorously, you could have intuitively realized that the total length of the cube's edges depends on N. Therefore, you might conclude that the run time is O(N) without doing the full calculation.
N | CUBES |
1 | 1 |
2 | 4 |
3 | 10 |
4 | 20 |
5 | 35 |
6 | 56 |
7 | 84 |
8 | 120 |
From the way the shapes grow in length, width, and height in Figure 1-5, you can probably guess that the number of cubes involves N3 in some manner. If you assume the number of cubes is A × N3 + B × N2 + C × N + D for some constants A, B, C, and D, you can plug in the values from Table B-2 and solve for A, B, C, and D. If you do that, you'll find that the number of cubes is (N3 + 3 × N2 + 2 × N) ÷ 6, so the run time is O(N3).
Less rigorously, you could have intuitively realized that the total volume of the shapes depends on N3. Therefore, you might conclude that the run time was O(N3) without doing the full calculation.
Can you have a data structure without an algorithm? Not really. You need some sort of algorithm to build the data structure, and you need another algorithm to use it to produce some kind of result. There isn't much point to a data structure that you won't use to produce a result.
The second algorithm divides the boards in a recursive way, but eventually it paints all N boards. Dividing the boards recursively requires O(log N) steps. Painting the boards requires O(N) steps. The total number of steps is N + log N, so the run time is O(N), just like the first algorithm.
The algorithms have the same run time, but the second takes slightly longer in practice if not in Big O notation. It is also more complicated and confusing, so the first algorithm is better.
It turns out that you can calculate the Fibonacci numbers directly using the following formula:
Fibonacci (n) =
where:
So the Fibonacci function is exponential in φ. The value φ ≈ 1.618, so the function doesn't grow as quickly as 2N, but it is still exponential and does grow faster than polynomial functions.
Roll the biased die 6 times. If the rolls include all 6 possible values, return the first one. Otherwise, repeat.
Depending on how biased the die is, it could take many trials to roll all six values. For example, if the die is fair (the best case), the probability of rolling all six values is 6! ÷ 66 = 720 ÷ 46,656 ≈ 0.015, so there's only about a 1.5% chance that six rolls will give six different values. For another example, if the die rolls a 1 half of the time and each of the other five values one-tenth of the time, the probability of getting all six values in six rolls is 0.5 × 0.15 × 6! = 0.0036, or 0.36%. So you may be rolling the die for a long time.
String: PickM(String: array[], Integer: M) Integer: max_i = <Upper bound of array> For i = 0 To M − 1 // Pick the item for position i in the array. Integer: j = <pseudo-random number between i and max_i inclusive> <Swap the values of array[i] and array[j]> Next i <Return array[0] through array[M − 1]> End PickM
This algorithm runs in O(M) time. Because M ≤ N, O(M) ≤ O(N). In practice, M is often much less than N, so this algorithm may be much faster than randomizing the entire array.
To give away five books, you would pick five names to go in the array's first five positions and then stop. This would take only five steps, so it would be very quick. It doesn't matter how many names are in the array, as long as there are at least five.
It doesn't matter whether you deal one card to each player in turn or deal five cards all at once to each player. As long as the deck is randomized, each player will get five randomly selected cards.
The actual results don't consistently match the expected results until the number of trials is quite large. The program often produces more than 5% error for some values until about 10,000 or more trials are run.
// Perform the exponentiation. Integer: Exponentiate(Integer: value, Integer: exponent) // Make lists of powers and the value to that power. List Of Integer: powers List Of Integer: value_to_powers // Start with the power 1 and value^1. Integer: last_power = 1 Integer: last_value = value powers.Add(last_power) value_to_powers.Add(last_value) // Calculate other powers until we get to one bigger than exponent. While (last_power < exponent) last_power = last_power * 2 last_value = last_value * last_value powers.Add(last_power) value_to_powers.Add(last_value) End While // Combine values to make the required power. Integer: result = 1 // Get the index of the largest power that is smaller than exponent. For power_index = powers.Count - 1 To 0 Step −1 // See if this power fits within exponent. If (powers[power_index] <= exponent) // It fits. Use this power. exponent = exponent - powers[power_index] result = result * value_to_powers[power_index] End If Next power_index // Return the result. Return result End Exponentiate
last_value = last_value * last_value
to this:
last_value = (last_value * last_value) Modulus m
You would also change this line:
result = result * value_to_powers[power_index]
to this:
result = (result * value_to_powers[power_index]) Modulus m
The ExponentiateMod example program that's available for download on the book's website demonstrates this algorithm.
// "Cross out" multiples of this prime. For i = next_prime * next_prime To max_number Step next_prime Then is_composite[i] = true Next i
// Generate Carmichael numbers. GenerateCarmichaelNumbers(Integer: max_number) Boolean: is_composite[] <Make is_composite a sieve of Eratosthenes for numbers 2 through max_number> // Check for Carmichael numbers. For i = 2 To max_number // Only check nonprimes. If (is_composite[i]) Then // See if i is a Carmichael number. If (IsCarmichael(i)) Then <Output i and its prime factors> End If End If Next i End GenerateCarmichaelNumbers // Return true if the number is a Carmichael number. Boolean: IsCarmichael(Integer: number) // Check all possible witnesses. For i = 1 to number - 1 // Only check numbers with GCD(number, 1) = 1. If (GCD(number, i) == 1) Then <Use fast exponentiation to calculate i ^ (number-1) mod number> Integer: result = Exponentiate(i, number - 1, number) // If we found a Fermat witness, // this is not a Carmichael number. If (result != 1) Then Return false End If Next i // They're all a bunch of liars! // This is a Carmichael number. Return true End IsCarmichael
You can download the CarmichaelNumbers example program from the book's website to see a C# implementation of this algorithm.
This method won't help (and may even hurt) if the curve has a local minimum or maximum near the middle of a rectangle. In those cases the errors on the left and right sides of the curve will add up and give a larger total error.
Figure B-4 shows the MidpointRectangleRule example program, which is available for download on the book's website, demonstrating this technique. If you compare the result to the one shown in Figure 2-2, you'll see that using the midpoint reduced the total error from about −6.5% to 0.2%, roughly 1/30th of the error, without changing the number of rectangles.
Float: EstimateVolume(Boolean: PointIsInShape(,,), Integer: num_trials, Float: xmin, Float: xmax, Float: ymin, Float: ymax, Float: zmin, Float: zmax) Integer: num_hits = 0 For i = 1 To num_trials Float: x = <pseudorandom number between xmin and xmax> Float: y = <pseudorandom number between ymin and ymax> Float: z = <pseudorandom number between zmin and zmax> If (PointIsInShape(x, y, z)) Then num_hits = num_hits + 1 Next i Float: total_volume = (xmax − xmin) * (ymax − ymin) * (zmax − zmin) Float: hit_fraction = num_hits / num_trials * Return total_volume * hit_fraction End EstimateVolume
Cell: AddAtEnd(Cell: bottom, Cell: new_cell) bottom.Next = new_cell new_cell.Next = null // Return the new bottom cell. Return new_cell End AddAtEnd
This algorithm returns the new bottom cell, so the calling code can update the variable that points to the list's last cell. Alternatively, you could pass the bottom pointer into the algorithm by reference so that the algorithm can update it.
Using a bottom pointer doesn't change the algorithms for adding an item at the beginning of the list or for finding an item.
Removing an item is the same as before unless that item is at the end of the list, in which case you also need to update the bottom pointer. Because you identify the item to be removed with a pointer to the item before it, this is a simple change. The following code shows the modified algorithm for removing the last item in the list:
Cell: DeleteAfter(Cell: after_me, Cell: bottom) // If the cell being removed is the last one, update bottom. If (after_me.Next.Next == null) Then bottom = after_me // Remove the target cell. after_me.Next = after_me.Next.Next // Return a pointer to the last cell. Return bottom End DeleteAfter
Cell: FindLargestCell(Cell: top) // If the list is empty, return null. If (top.Next == null) Return null // Move to the first cell that holds data. top = top.Next // Save this cell and its value. Cell: best_cell = top Integer: best_value = best_cell.Value // Move to the next cell. top = top.Next // Check the other cells. While (top != null) // See if this cell's value is bigger. If (top.Value > best_value) Then best_cell = top best_value = top.Value End If // Move to the next cell. top = top.Next End While Return best_cell End FindLargestCell
AddAtBeginning(Cell: top, Cell: new_cell) // Update the Next links. new_cell.Next = top.Next top.Next = new_cell // Update the Prev links. new_cell.Next.Prev = new_cell new_cell.Prev = top End AddAtBeginning
AddAtEnd(Cell: bottom, Cell: new_cell) // Update the Prev links. new_cell.Prev = bottom.Prev bottom.Prev = new_cell // Update the Next links. new_cell.Prev.Next = new_cell new_cell.Next = bottom End AddAtEnd
DeleteCell(Cell: target_cell) // Update the next cell's Prev link. target_cell.Next.Prev = target_cell.Prev // Update the previous cell's Next link. target_cell.Prev.Next = target_cell.Next End DeleteCell
Figure B-5 shows the process graphically.
// Insert a cell in a sorted doubly linked list. InsertCell(Cell: top, Cell: new_cell) // Find the cell before where the new cell belongs. While (top.Next.Value < new_cell.Value) top = top.Next End While // Update Next links. new_cell.Next = top.Next top.Next = new_cell // Update Prev links. new_cell.Next.Prev = new_cell new_cell.Prev = top End InsertCell
This algorithm is similar to the one used for a singly linked list except for the two lines that update the Prev links.
Boolean: IsSorted(Cell: sentinel) // If the list has 0 or 1 items, it's sorted. If (sentinel.Next == null) Then Return true If (sentinel.Next.Next == null) Then Return true // Compare the other items. sentinel = sentinel.Next; While (sentinel.Next != null) // Compare this item with the next one. If (sentinel.Value > sentinel.Next.Value) Then Return false // Move to the next item. sentinel = sentinel.Next End While // If we get here, the list is sorted. Return true End IsSorted
In contrast, when selectionsort searches the unsorted input list to find the largest item, it must search the whole list. Unlike insertionsort, it can never stop the search early.
Double: FindSampleVariance(Integer: array[]) // Find the average. Integer: total = 0 For i = 0 To array.Length - 1 total = total + array[i] Next i Double: average = total / array.Length // Find the sample variance. Double: sum_of_squares = 0 For i = 0 To array.Length − 1 sum_of_squares = sum_of_squares + (array[i] − average) * (array[i] − average) Next i Return sum_of_squares / array.Length End FindSampleVariance
Integer: FindSampleStandardDeviation(Integer: array[]) // Find the sample variance. Double: variance = FindSampleVariance(array) // Return the standard deviation. Return Sqrt(variance) End FindSampleStandardDeviation
Double: FindMedian(Integer: array[]) If (array.Length Mod 2 == 0) Then // The array has even length. // Return the average of the two middle items. Integer: middle = array.Length / 2 Return (array[middle − 1] + array[middle]) / 2 Else // The array has odd length. // Return the middle item. Integer: middle = (array.Length − 1)/ 2 Return array[middle] End If End FindMedian
RemoveItem(Integer: array[], Integer: index) // Slide items left 1 position to fill in where the item is. For i = index + 1 To array.Length − 1 Array[i − 1] = Array[i] Next i // Resize to remove the final unused entry. <Resize the array to delete 1 item from the end> End RemoveItem
Integer: FindIndex(Integer: r, Integer: c) Return ((r − 1) * (r − 1) + (r − 1)) / 2 + c End FindIndex
The following pseudocode shows the new version with row and column switched:
Integer: FindIndex(Integer: r, Integer: c) Return ((c − 1) * (c − 1) + (c − 1)) / 2 + r End FindIndex
Integer: FindIndex(Integer: r, Integer: c) r = N − 1 − r Return ((r − 1) * (r − 1) + (r − 1)) / 2 + c End FindIndex
This change essentially flips the array upside-down so that small row numbers are mapped to the bottom of the array and large row numbers are mapped to the top of the array. For example, suppose N = 5. Then the entry [0, 4] is in the upper-right corner of the array. That position is not allowed in the normal lower-left triangular array, so the row is changed to N − 1 − 0 = 4. The position [4, 4] is in the lower right corner, which is in the normal array.
FillArrayLLtoUR(Integer: values[,], Integer: ll_value, Integer: ur_value) For row = 0 To <Upper bound for dimension 1> For col = 0 To <Upper bound for dimension 2> If (row >= col) Then values[row, col] = ur_value Else values[row, col] = ll_value End If Next col Next row End FillArrayLLtoUR
FillArrayULtoLR(Integer: values[,], Integer: ul_value, Integer: lr_value) Integer: max_col = <Upper bound for dimension 2> For row = 0 To <Upper_bound for dimension 1> For col = 0 To max_col If (row > max_col − col) Then values[row, col] = ul_value Else values[row, col] = lr_value End If Next col Next row End FillArrayULtoLR
FillArrayWithDistances(Integer: values[,]) Integer: max_row = values.GetUpperBound(0) Integer: max_col = values.GetUpperBound(1) For row = 0 To max_row For col = 0 To max_col values[row, col] = Minimum(row, col, max_row − row, max_col − col) Next col Next row End FillArrayWithDistances
Integer: NumCellsForTriangleRows(Integer: rows) Return (rows * rows + rows) / 2 End NumCellsForTriangleRows
The number of cells in a full tetrahedral arrangement is harder to calculate. If you make some drawings and count the cells, you can follow the approach used in the chapter. (See Table 4-1 and the nearby paragraphs.) If you assume the number of cells in the tetrahedral arrangement involves the number of rows cubed, you will find that the exact number is (N3 + 3 × N2 + 2 × N) / 6. The following pseudocode uses that formula:
Integer: NumCellsForTetrahedralRows(Integer: rows) Return (rows * rows * rows + 3 * rows * rows + 2 * rows) / 6 End NumCellsForTetrahedralRows
With these two methods, you can write a method to map [row, column, height] to an index in the storage array:
Integer: RowColumnHeightToIndex(Integer: row, Integer: col, Integer: hgt) Return NumCellsForTetrahedralRows(row) + NumCellsForTriangleRows(col) + hgt; End RowColumnHeightToIndex
This code returns the number of entries before this one in the array. It calculates that number by adding the entries due to complete tetrahedral groups before this item, plus the number of entries due to complete triangular groups before this item, plus the number of individual entries that come before this one in its triangular group of cells.
AddTriangularArrays(Integer: array1[,], Integer: array2[,], Integer: result[,]) For row = 0 To <Upper bound for dimension 1> For col = 0 To row Result[row, col] = array1[row, col] + array2[row, col] Next col Next row End AddTriangularArrays
MultiplyArrays(Integer: array1[], Integer: array2[], Integer: result[]) For i = 0 To <Upper bound for dimension 1> For j = 0 To <Upper bound for dimension 2> // Calculate the [i, j] result. result[i, j] = 0 For k = 0 To <Upper bound for dimension 2> result[i, j] = result[i, j] + array1[i, k] * array2[k, j] Next k Next j Next i End MultiplyArrays
Now consider the inner For k loop. If i < k, array1[i, k] is 0. Similarly, if k < j, array2[k, j] is 0. If either of those two values is 0, their product is 0.
The following code shows how you can modify the inner assignment statement so that it changes an entry's value only if it is multiplying entries that are present in both arrays:
If (i >= k) And (k >= j) Then result[i, j] = result[i, j] + array1[i, k] * array2[k, j] End If
You can make this a bit simpler if you think about the values of k that access entries that exist in both arrays. Those values exist if k <= i and k >= j. You can use those bounds for k in its For loop, as shown in the following pseudocode:
For k = j To i total += this[i, k] * other[k, j]; Next k
// Copy the entries starting at from_entry into // the destination entry list after to_entry. CopyEntries(ArrayEntry: from_entry, ArrayEntry: to_entry) While (from_entry != null) to_entry.NextEntry = new ArrayEntry to_entry = to_entry.NextEntry to_entry.ColumnNumber = from_entry.ColumnNumber to_entry.Value = from_entry.Value to_entry.NextEntry = null // Move to the next entry. from_entry = from_entry.NextEntry End While End CopyEntries
As long as the “from” list isn't empty, this adds a new ArrayEntry object to the “to” list.
The following AddEntries method copies entries from the two lists from_entry1 and from_entry2 into the result list to_entry:
// Add the entries in the two lists from_entry1 and from_entry2 // and save the sums in the destination entry list after to_entry. AddEntries(ArrayEntry: from_entry1, ArrayEntry: from_entry2, ArrayEntry: to_entry) // Repeat as long as either from list has items. While (from_entry1 != null) And (from_entry2 != null) // Make the new result entry. to_entry.NextEntry = new ArrayEntry to_entry = to_entry.NextEntry to_entry.NextEntry = null // See which column number is smaller. If (from_entry1.ColumnNumber < from_entry2.ColumnNumber) Then // Copy the from_entry1 entry. to_entry.ColumnNumber = from_entry1.ColumnNumber to_entry.Value = from_entry1.Value from_entry1 = from_entry1.NextEntry Else If (from_entry2.ColumnNumber < from_entry1.ColumnNumber) Then // Copy the from_entry2 entry. to_entry.ColumnNumber = from_entry2.ColumnNumber to_entry.Value = from_entry2.Value from_entry2 = from_entry2.NextEntry Else // The column numbers are the same. Add both entries. to_entry.ColumnNumber = from_entry1.ColumnNumber to_entry.Value = from_entry1.Value + from_entry2.Value from_entry1 = from_entry1.NextEntry from_entry2 = from_entry2.NextEntry End If End While // Add the rest of the entries from the list that is not empty. if (from_entry1 != null) CopyEntries(from_entry1, to_entry) if (from_entry2 != null) CopyEntries(from_entry2, to_entry) End AddEntries
This code loops through both “from” lists, adding the next entry from each list that has the smaller column number. If the current entries in each list have the same column number, the code creates a new entry and adds the values of the “from” lists.
The following code shows how the Add method uses CopyEntries and AddEntries to add two matrices:
// Add two SparseArrays representing matrices. SparseArray: Add(SparseArray: array1, SparseArray: array2) SparseArray: result = new SparseArray // Variables to move through all the arrays. ArrayRow: array1_row = array1.TopSentinel.NextRow ArrayRow: array2_row = array2.TopSentinel.NextRow ArrayRow: result_row = result.TopSentinel While (array1_row != null) And (array2_row != null) // Make a new result row. result_row.NextRow = new ArrayRow result_row = result_row.NextRow result_row.RowSentinel = new ArrayEntry result_row.NextRow = null // See which input row has the smaller row number. If (array1_row.RowNumber < array2_row.RowNumber) Then // array1_row comes first. Copy its values into result. result_row.RowNumber = array1_row.RowNumber CopyEntries(array1_row.RowSentinel.NextEntry, result_row.RowSentinel) array1_row = array1_row.NextRow Else If (array2_row.RowNumber < array1_row.RowNumber) Then // array2_row comes first. Copy its values into result. result_row.RowNumber = array2_row.RowNumber CopyEntries(array2_row.RowSentinel.NextEntry, result_row.RowSentinel) array2_row = array2_row.NextRow Else // The row numbers are the same. Add their values. result_row.RowNumber = array1_row.RowNumber AddEntries( array1_row.RowSentinel.NextEntry, array2_row.RowSentinel.NextEntry, result_row.RowSentinel) array1_row = array1_row.NextRow array2_row = array2_row.NextRow End If End While // Add any remaining rows. If (array1_row != null) Then // Make a new result row. result_row.NextRow = new ArrayRow result_row = result_row.NextRow result_row.RowNumber = array1_row.RowNumber result_row.RowSentinel = new ArrayEntry result_row.NextRow = null CopyEntries(array1_row.RowSentinel.NextEntry, result_row.RowSentinel) End If If (array2_row != null) Then // Make a new result row. result_row.NextRow = new ArrayRow result_row = result_row.NextRow result_row.RowNumber = array2_row.RowNumber result_row.RowSentinel = new ArrayEntry result_row.NextRow = null CopyEntries(array2_row.RowSentinel.NextEntry, result_row.RowSentinel) End If return result End Add
The method loops through the two “from” arrays. If one list's current row has a lower row number than the other, the method uses CopyEntries to copy that row's entries into the “to” list.
If the lists' current rows have the same row number, the method uses AddEntries to combine the rows in the output array.
After one of the “from” lists is empty, the method uses CopyEntries to copy the remaining items in the other “from” list into the output list.
You can make it easier to iterate over the entries in a column by using a linked list of columns, each holding a linked list of entries, just as the text describes using linked lists of rows.
Instead of building a whole new class, however, you can reuse the existing SparseArray class. If you reverse the roles of the rows and columns, you get an equivalent array that lets you traverse the fields in a column. Of course, the class will treat the rows as columns and vice versa, so this can be confusing.
The following pseudocode shows a high-level algorithm for multiplying two sparse matrices:
Multiply(SparseArray: array1, SparseArray: array2, SparseArray: result) // Make a column-major version of array2. SparseArray: new_array2 For Each entry [i, j] in array2 new_array2[j, i] = array2[i, j] Next [i, j] // Multiply. For Each row number r in array1 For Each "row" number c in array2 // These are really columns. Integer: total = 0 For Each <k that appears in both array1's row and array2's column> total = total + <The row's k value> * <the column's k value> Next k result[r, c] = total Next c Next r End Multiply
Stack: ReverseStack(Stack: values) Stack: new_stack While (<values is not empty>) new_stack.Push(values.Pop()) End While Return new_stack End ReverseStack
Of course, with real trains, you don't need to look only at the top car in a stack. Instead, you can look at the unsorted cars and figure out which has the largest number before you start moving any cars. Then you can simply move the cars to the holding track, except for the selected car, which you can move to the output track. That will remove any need to put incorrect cars on the output track and reduce time-consuming shuffling.
The average wait time is very sensitive to the number of tellers. If you have even one fewer than the optimum number of tellers, the number of customers in the queue quickly grows long, and the average wait time soars. Adding a single teller can make the queue practically disappear and reduce average wait time to only a few seconds. (Some retailers have learned this lesson. Whenever more than a couple of customers are waiting, pull employees from other jobs to open a new register and quickly clear the queue.)
For performance reasons, all of the sorting example programs display at most 1,000 of the items they are sorting. If the program generates more than 1,000 items, all of the items are processed but only the first 1,000 are displayed in the output list.
Starting the loop at 1 doesn't change the algorithm's run time.
For i = 0 To <length of values> − 2
This would not change the algorithm's run time.
A faster but more complicated approach would be to perform a binary search or interpolation search starting at the location where the first target item was found and look for the next-smaller item. This would not change the run time of the original algorithm: O(log N) for binary search and O(log(log N)) for interpolation search.
It's not obvious from the graph, but the exact values added to the tables make a big enough difference to change which algorithms are faster than the others.
The ordered quadratic probing and ordered double hashing algorithm provide almost exactly the same average probe sequence length. Their values are much smaller than the average lengths of the other algorithms, although inserting items in the ordered hash tables takes longer.
// Draw down on the right. SierpDown(Integer: depth, Float: dx, Float: dy) If (depth > 0) Then depth = depth − 1 SierpDown(depth, gr, dx, dy) DrawRelative(gr, -dx, dy) SierpLeft(depth, gr, dx, dy) DrawRelative(gr, 0, 2 * dy) SierpRight(depth, gr, dx, dy) DrawRelative(gr, dx, dy) SierpDown(depth, gr, dx, dy) End If End SierpDown // Draw left across the bottom. SierpLeft(Integer: depth, Float: dx, Float: dy) If (depth > 0) Then depth = depth − 1 SierpLeft(depth, gr, dx, dy) DrawRelative(gr, -dx, -dy) SierpUp(depth, gr, dx, dy) DrawRelative(gr, −2 * dx, 0) SierpDown(depth, gr, dx, dy) DrawRelative(gr, -dx, dy) SierpLeft(depth, gr, dx, dy) End If End SierpLeft // Draw up along the left. SierpUp(Integer: depth, Float: dx, Float: dy) f (depth > 0) Then depth = depth - 1 SierpUp(depth, gr, dx, dy) DrawRelative(gr, dx, − dy) SierpRight(depth, gr, dx, dy) DrawRelative(gr, 0, −2 * dy) SierpLeft(depth, gr, dx, dy) DrawRelative(gr, -dx, -dy) SierpUp(depth, gr, dx, dy) End If End SierpUp
// Draw the gasket. SierpinskiGasket(Integer: depth, Point: point1, Point: point2, Point: point3) // If this is depth 0, fill the remaining triangle. If (depth == 0) Then Point: points[] = { point1, point2, point3 } FillPolygon(points) Else // Find points on the left, right, and bottom of the triangle. Point: lpoint = new Point( (point1.X + point2.X) / 2, (point1.Y + point2.Y) / 2) Point: bpoint = new Point( (point2.X + point3.X) / 2, (point2.Y + point3.Y) / 2) Point: rpoint = new Point( (point3.X + point1.X) / 2, (point3.Y + point1.Y) / 2) // Draw the triangles at the corners. SierpinskiGasket(depth − 1, gr, point1, lpoint, rpoint) SierpinskiGasket(depth − 1, gr, lpoint, point2, bpoint) SierpinskiGasket(depth − 1, gr, rpoint, bpoint, point3) End If End SierpinskiGasket
// Draw the carpet. SierpinskiCarpet(Integer: depth, Rectangle: rect) // If this is depth 0, fill the remaining rectangle. If (depth == 0) Then FillRectangle(rect) Else // Fill the 8 outside rectangles. Float: width = rect.Width / 3 Float: height = rect.Height / 3 For row = 0 To 2 For col = 0 To 2 // Skip the center rectangle. If ((row != 1) || (col != 1)) Then SierpinskiCarpet(depth − 1, New Rectangle( rect.X + col * width, rect.Y + row * height, width, height)) End If Next col Next row End If End SierpinskiCarpet
Inductive step: Suppose the property is true for binary trees containing N nodes, and consider such a tree. If you add a new node to the tree, you must also add a new branch to the tree to connect the node to the tree. Adding one branch to the N − 1 branches that the tree already had means that the new tree has N + 1 nodes and (N − 1) + 1 = (N + 1) − 1 branches. This is the statement of the property for a tree with N + 1 nodes, so the property holds for binary trees containing N + 1 nodes.
That proves B = N − 1 by induction.
Inductive step: Suppose the property is true for perfect binary trees of height H. A perfect binary tree of height H + 1 consists of a root node connected to two perfect binary subtrees of height H. Because we assume the property is true for trees of height H, the total number of leaf nodes in each subtree is 2H. Adding a new root node above the two subtrees doesn't add any new leaf nodes to the tree of height H + 1, so the total number of leaf nodes is (2 × 2H) = 2H+1, so the property holds for perfect binary trees of height H + 1.
That proves L = 2H by induction.
Inductive step: Suppose the property is true for binary trees containing N nodes, and consider such a tree. If you add a new node to the tree, that node is attached to its parent by a branch that replaces a formerly missing branch, decreasing the number of missing branches by 1. The new node has two missing branches of its own. Adding these to the tree's original N + 1 missing branches gives the new number of missing branches, M = (N + 1) − 1 + 2 = (N + 1) + 1. This is the statement of the property for a tree containing N + 1 nodes, so the property holds for binary trees containing N + 1 nodes.
That proves M = N + 1 by induction.
ReverseInorderWithThreads(BinaryNode: root) // Start at the root. BinaryNode: node = root // Remember whether we got to a node via a branch or thread. // Pretend we go to the root via a branch so we go right next. Boolean: via_branch = True // Repeat until the traversal is done. While (node != null) // If we got here via a branch, go // down and to the right as far as possible. If (via_branch) Then While (node. RightChild != null) node = node. RightChild End While End If // Process this node. <Process node> // Find the next node to process. If (node. LeftChild == null) Then // Use the thread. node = node. LeftThread via_branch = False Else // Use the left branch. node = node. LeftChild via_branch = True End If End While End ReverseInorderWithThreads
The tree grows irregularly, depending on the order in which animals are added and the questions used to differentiate them, so the tree is neither complete nor perfect.
A B+tree node of order K would occupy 100 × (2 × K) + 8 × (2 × K + 1) = 200 × K + 16 × K + 8 = 216 × K + 8 bytes. To fit in four blocks of 2 KB each, this must be less than or equal to 4 × 2 × 1,024 = 8,192 bytes, so 216 × K + 8 ≤ 8,192. Solving for K gives K ≤ (8,192 − 8) ÷ 216, or K ≤ 37.9. K must be an integer, so you must round this down to 37.
Each tree could have a height of at most log(K+1)(10,000) while holding 10,000 items. For the B-tree, that value is log4(10,000) ≈ 6.6, so the tree could be seven levels tall. For the B+tree, that value is log38(10,000) ≈ 2.5, so the tree could be three levels tall.
The numbers would favor player X if each player moved randomly, but because most nonbeginners have a strategy that forces a tie, a tie is the most common outcome.
Because the tic-tac-toe board is symmetric, you don't really need to count the games from each starting position. All the corners give the same number of possible games, and all the middle squares also give the same number of possible games. You only really need to count the games for one corner, one middle, and the center to get all the values.
This cannot happen to the label-setting algorithm, because each node's distance is set exactly once and never changed.
However, the algorithm cannot improve a distance that is shorter than the distances provided by the links in the candidate list. That means you can periodically check the links in the list. If none of them leads to a distance less than the donut shop's distance, the donut shop's shortest path is final.
This change is complicated and slow enough that it probably won't speed up the algorithm unless the network is very large and the start and destination nodes are very close together. You may be better off using a label-setting algorithm.
Unfortunately, the algorithm doesn't have a good way to identify the nodes that have in-degree 0, so it would slow down the algorithm without some major revisions.
To find the number of paths that don't share links or nodes, replace each node with two nodes—an in-node and an out-node. Connect the two new nodes with a link of capacity 1. Make the links that entered the original node now enter the in-node. Make the links that exited the original node now exit the out-node. Now find the maximal flow. Because each original node is now represented by two nodes connected with a link of capacity 1, only one path can use each in-node/out-node pair.
You can use three colors to color a work assignment network. Use one color for the employee nodes, one color for the job nodes, and one color for the source and sink nodes.
In contrast, suppose you use objects to represent the states, similar to how you can use node objects to represent locations in a network. Each state object could have a list giving the new state object for various inputs. In that case, state transitions would be relatively quick and simple. If some states can read many possible inputs (in other words, there are many links leaving them in the state diagram), you might still spend some time looking up new states. In that case you might want to use a tree, hash table, or some other data structure to make finding the new states faster, but at least you won't have to search the whole transition table.
One solution is to use only the first occurrence of each letter, so PIZZA becomes PIZA and BOOKWORM becomes BOKWRM. This actually has the small benefit of increasing obscurity if the attacker doesn't know the rule, because it disguises the number of columns in the encryption array.
However, if the attacker figures out only the column ordering, the rows will be out of order, but each row in the array will contain valid words. By recognizing the valid words, the attacker can recover the column ordering and then try to swap rows to recover the full message.
If each row begins with a new word, finding the row ordering could be difficult. But if words span rows, the pieces of the words will give the attacker extra clues for finding the row ordering. For example, suppose the first row ends with GREA, the second row begins with NT, and the third row begins with TLY. In that case, it's likely that the third row should follow the first row.
This is an example in which what seems like a perfectly reasonable attempt to add one encryption method to another doesn't really help much. Although adding row transpositions to column transpositions greatly increases the number of possible combinations, it doesn't greatly increase the number of combinations the attacker must consider.
Using the CaesarSubstitution example program with offset 6 to decipher the message produces gibberish. Using the program again with offset 17 gives the plain-text message THERE WASAT IMEWH ENCAE SARSU BSTIT UTION WASTH ESTAT EOFTH EART. (There was a time when Caesar substitution was the state of the art.)
Conversely, suppose you have an unbreakable encryption scheme. You could use it to encrypt a message consisting of nothing but instances of the letter A to generate a sequence of random letters. You could then use those letters to generate the random numbers for a secure random-number generator.
The two-coloring algorithm described in Chapter 14 runs in polynomial time (actually, it's quite fast), so it's in P, and the bipartite detection is also in P.
Note that the converse is not necessarily true. If the graph has no cycles of length 3, it is still not bipartite if it has a cycle with an odd length.
Exercise 2 shows that the bipartite detection problem is in P, so the three-cycle problem is also in P.
Note that for this case, the converse is also true. If the graph has no cycles of odd length, it is bipartite.
Exercise 2 shows that the bipartite detection problem is in P, so the odd-cycle problem is also in P.
To reduce HAM to HAMC, you must find a way to use a HAMC algorithm to solve HAM problems. In other words, if a network contains a Hamiltonian path, you must use a HAMC algorithm to detect it.
First, note that a network that contains a Hamiltonian cycle contains a Hamiltonian path. Simply take a Hamiltonian cycle and remove the final link to form a Hamiltonian path.
Now suppose the network doesn't contain a Hamiltonian cycle, and suppose it does contain a Hamiltonian path. How could you turn the path into a cycle? Simply add the path's starting node to the end of the path. If a link from the ending node to the starting node was already in the network, it would have already contained a Hamiltonian cycle, so that link must not be present.
To look for a Hamiltonian cycle, add a new link LABbetween two nodes A and B. Now if there is a Hamiltonian cycle, the same ordering gives you a Hamiltonian path in the original network. Suppose the Hamiltonian cycle passes through the nodes N1, N2, ..., A, B, Nk, Nk+1, ... N1. Then the original network contains the Hamiltonian path B, Nk, Nk+1, ... N1, N2, ..., A.
The complete algorithm for solving HAM is as follows:
Figure B-30 shows the idea. The original network is on the left. This network clearly has no Hamiltonian cycle, because node L has only one link, so a path that enters that node cannot leave it again.
As the reduction algorithm progresses, it eventually tries adding a link between nodes I and L. The HAMC algorithm finds the Hamiltonian path shown on the right in Figure B-30. If you remove the link between nodes I and L, you get a Hamiltonian path in the original network.
Note that this may be an inefficient algorithm for finding Hamiltonian paths. If the network contains N nodes, you may need to repeat Step 2 up to N2 times. That's still polynomial time, however, so this is a polynomial time reduction.
The HAMC algorithm is NP-complete so it has no known fast solutions. That means running it N2 times will be very slow indeed.
Unfortunately, you can extend a Hamiltonian path to form a cycle only if the last node in the path has a link leading to the first node in the path. A HAM algorithm might find a path that does not have such a link, so it could not form a cycle.
Suppose the network contains a Hamiltonian cycle that includes the link LAB connecting nodes A and B. Now suppose you connect a new node A' to node A and a new node B' to node B. Then the new network contains a noncyclic Hamiltonian path starting at node A' and ending at node B'.
Conversely, any Hamiltonian path must start at node A' and end at node B' (or vice versa in an undirected network). Suppose the HAM algorithm finds a path that visits the nodes A', A, N1, N2, ..., B, B'. Then the path A, N1, N2, ..., B, A is a Hamiltonian cycle.
The complete algorithm for solving HAMC is as follows:
Figure B-31 shows the idea. You can probably find a Hamiltonian cycle easily enough, but pretend you can't. In the image on the right, the reduction algorithm is considering the link LQR connecting nodes Q and R. It has added node Q', connected to node Q, and node R', connected to node R. The Hamiltonian path algorithm finds the path shown in bold in the modified network on the right. Removing the Q' and R' nodes and their links and adding the LQR link to the path gives a Hamiltonian cycle.
When the loop has finished, the items that are still in the set form the solution.
When the loop in Step 2b has finished, the set should contain only Omax, and Vmax should be 0. The steps you took to get there tell you which items belong in Subset A and which belong in Subset B.
Sorting two lists of numbers takes only one tick longer than sorting a single list.
In this case, the solution saved by process A is worse than the one saved by process B. The route length saved by process A matches the solution saved by process A, so this is a little better than the original race condition example, but the best solution is still overwritten. Process B also has a local copy of what it thinks is the best route length, 70, so it would not report a new solution with a route length of 70 if it found one.
Process A can save itself if it checks the shared route length again after it acquires the mutex. You can void that extra step if you acquire the mutex first, but there may actually be a benefit to checking the value twice.
Acquiring a mutex can be a relatively slow operation, at least compared to checking a memory location. If process A's value isn't as good as the value already stored in the shared variable, process A can learn that quickly and not bother acquiring the mutex.
When the philosophers all try to eat at the same time, philosopher 1 already has two forks, so he succeeds and is the first to eat. The others (except for philosopher 4) already hold dirty left forks, so they request right forks. Philosopher N has no forks, so he requests both forks. Because all the forks are dirty, those who have them clean their left forks and give them away (except philosopher 1, who is eating). The result is shown in the middle of Figure B-33.
In this example, two of the philosophers now have a clean right fork and no left fork, so they ask for the left fork. (In a large problem, most of the philosophers would have a clean right fork and no left fork.) Their neighbors hold clean forks, so they refuse to give them up, and everyone waits.
When philosopher 1 finishes eating, he cleans his forks and gives them to his neighbors, philosophers 2 and 4. The result is shown on the right in Figure B-33. Philosopher 4 now has two forks, so he is the second to eat.
When philosopher 4 finishes eating, he gives his right fork to philosopher 3, who then eats.
When philosopher 3 finishes eating, he gives his right fork to philosopher 2, who then eats last.
More generally, the philosophers eat in the order 1, N, N − 1, N − 2, ..., 2.
If general A receives any acknowledgments, he calculates PBA. The content of the acknowledgments tells him PAB. He uses PAB to decide how many messages to send to get a desired level of certainty, and he sends messages saying, “PBA = <calculated value>. Acknowledgment received.”
After the first batch of messages, if general A doesn't receive any acknowledgments (when he sent them, he didn't know PAB, so he didn't know how many to send), he assumes general B didn't receive any. So he sends another, larger batch.
Similarly, if general B doesn't receive a reply to the acknowledgments (when he sent them, he didn't know PBA, so he didn't know how many to send), he assumes general A didn't receive any. So he sends another, larger batch.
Eventually general A will send enough messages for general B to receive some and calculate PAB. After that, general B will eventually send enough acknowledgments for general A to receive some and calculate PBA. Finally, general A will eventually send enough replies to give general B the value PBA, and both generals will know both probabilities.
In the situation shown on the left of Figure 18-2, however, each lieutenant makes a decision. In some sense it doesn't matter what each does, because the general is a traitor, and there's no rule that they need to obey a traitorous general. However, there is a rule that two loyal lieutenants must decide on the same action, and in this case they don't.
However, suppose the general is loyal (as in the situation on the right of Figure 18-2). The general orders an attack, and the traitorous lieutenant on the right lies about it. In that case, the lieutenant on the left receives conflicting orders, so he retreats, violating the general's orders.
For the second scenario, suppose the first lieutenant is a traitor. The general tells all the lieutenants to retreat, but the traitor tells the others that the general told him to attack.
The lieutenants receive the same information in both scenarios, so they cannot tell whether the traitor is the general or the first lieutenant.
These two scenarios hold no matter how many lieutenants there are, so there is no way to identify the traitor.
(The traitor could also simply act as if he is loyal and not give conflicting orders. Then there is no way to detect him, although he won't cause any harm that way either.)
If this occurs, the lieutenants don't need to obey the traitor, but they still need to agree on a common decision. They can do that with a predefined rule that says, “If the commanding general is a traitor, retreat.”
Now, if you subtract the second equation from the first, you get this:
In the previous analysis where DAB = DBA, those two terms cancel. If you leave the terms in the equation and solve for E, you get this:
The error in E due to the difference between DBA and DAB is half of their difference. In the worst case, where one of these is close to 0 and the other is close to the total roundtrip delay D, the error is D ÷ 2.
After running the clock algorithm, TB = TA ± D ÷ 2.
This problem is simple if you have seen a similar problem before, so it doesn't really test the reasoning ability of anyone who has seen something similar. It's also easy if you write down some possible combinations. Overall it's not too bad a question, but it doesn't really tell the interviewer much.
A better solution is to put a single white marble in one bowl and all the other marbles in the other bowl. When you pick a marble, there is a 50% chance that you'll get lucky and pick the bowl that holds the single white marble. If you're unlucky and pick the other bowl, there's still a 9 in 19 chance that you'll get lucky and pick a white marble. Your total odds are as follows:
This problem involves a little probability but is mostly a clever trick. It would be easier, quicker, and potentially less frustrating to ask the candidate how much he or she knows about probability.
This problem is easy if you get the trick, but if you don't, you may waste a lot of time on it. In either case, the interviewer doesn't learn much about the candidate.
First, notice that you don't need to consider arrangements in which you swap marbles of the same color. All red marbles are the same, and all blue marbles are the same.
Next, to simplify the procedure, assume you have straightened out the circle of marbles so that you have a row of 12 slots where a marble can be positioned. Now place a blue marble in the first slot. Positioning the other 11 marbles in the remaining 11 slots is equivalent to positioning the original 12 marbles in 12 slots arranged in a circle. This situation is easier to handle because you don't need to worry about the effects of the arrangement wrapping around the circle so that the first marble is adjacent to the last marble. Now a blue marble separates the first and last red marbles.
Now you can think of the problem as having 11 slots where you will place the remaining 11 marbles. If you pick slots for the four red marbles, the blue ones will fill in the remaining empty slots. If you think of it this way, the number of possible arrangements is as follows:
To see how many “good” arrangements are possible, start by placing the four red marbles in a row. To ensure that no two red marbles are adjacent, you must put three of the seven remaining blue marbles between each pair of red marbles.
At this point, four blue marbles are left, and they can go anywhere. If you think of the red marbles as defining walls, the remaining blue marbles must go between the walls. (It doesn't matter how the marbles between the walls are ordered, because you can't tell the blue marbles apart.)
One way to think about this is to imagine eight slots where you will put either a blue marble or a wall. Now you can pick slots for the walls and fill in the remaining slots with blue marbles. The number of ways you can do that is as follows:
The number of “good” arrangements is 70, and the total number of possible arrangements is 330, so the odds that a random arrangement is “good” are 70 ÷ 330 = 7/33 ≈ 21%.
This problem is pretty interesting, but it's quite difficult. This kind of problem is fairly common in probability and statistics courses, so a candidate who has taken such a course will probably know the basic approach. Even then it would be a tough calculation, and if the candidate hasn't taken that kind of course, this problem will be extremely hard.
All that the interviewer will really learn from this question is whether the candidate has seen a problem like this before or has taken such a course.
This is actually a relevant question! You may never need to reverse a list of customers in this way, but answering this question shows that you know about at least one type of data structure. Mentioning both the linked list and array solutions shows you know about at least two data structures and that you can look for more solutions even after you find one.
Plugging the first equation into the second gives you this:
Rearranging and solving for B gives you this:
Inserting this value into the first equation gives M = 3 × 2 = 6, so I am 6 right now.
A second approach is to make a table similar to the following, starting with a guess of age 30 for yourself:
After filling in the first row, you compare the last two columns. In this case, My Age + 2 is too big, so you guess again with smaller ages:
In the second row, the difference between the last two columns is closer but still is too big, so you guess again with even smaller ages:
In this example, the third row finds the solution. (If you overshoot and My Age + 2 turns out too small, try larger ages.)
This problem is almost worth asking because it lets you see whether the candidate is more comfortable using algebra or a table. I'm not sure how useful that information will be, though. Many problems like this one are more involved, so a table won't work well, but just because the candidate used a table doesn't mean he or she can't use algebra if it's required.
If you use a problem like this, it's probably best to ask the candidate why he or she chose a particular approach and what other approaches might also work.
For this problem, the minute hand passes the hour hand a bit after 1:05, a bit longer after 2:10, and so on up to some time after 10:50. The next time the hands meet after 11:00 is 12:00 midnight. That means the hands cross between 1:00 and 2:00, between 2:00 and 3:00, and so on up to a time between 10:00 and 11:00. (At this point, perhaps you can see the fencepost problem.)
If you only count times strictly between noon and midnight, the hands cross 10 times. If you also count the times they cross at noon and midnight, the hands cross 12 times.
How the candidate approaches this question may tell you a bit about how methodical he or she is, but that may be all it tells you. At least a careful candidate can come up with some solution either right or wrong without knowing a sneaky trick.
The couples whose first child is a girl have a second child. Of those children, half are boys and half are girls, so the population of second children is half boys and half girls.
The couples whose first and second children are girls have a third child. Of those children, half are boys and half are girls, so the population of third children is half boys and half girls.
At this point it should be clear that each cohort is half boys and half girls, so the population as a whole must be half boys and half girls.
If the couple's first child is a girl, they have a second child. Again, there's a 50% chance of a girl and a 50% chance of a boy. The expected contribution to the family of this child is the chance of having a second child in the first place (0.5) times the chance of having a boy or a girl. That adds another 0.5 × 0.5 = 0.25 expected boys and 0.5 × 0.5 = 0.25 expected girls to the family, making a total expected 0.75 boys and 0.75 girls.
Hopefully at this point you can see a pattern.
In general, to have an Nth child, the couple must previously have had N − 1 girls in a row. The chance of that happening is 1/2N–1.
Assuming they did have N − 1 girls in a row, there is a 50% chance that the next child is a boy and a 50% chance that the next child is a girl. Therefore, the expected contribution to the family of the Nth child is 0.5 × 1/2N–1 = 1/2N boys and 0.5 × 1/2N = 1/2N girls.
If you add up the expected number of children through child N, you get the following:
These values are the same. Each couple has the same expected number of boys and girls, and so does the population as a whole.
If you take the limits of these sums as N goes to infinity, these equations also show that the expected number of children for each family is one boy and one girl.
This is an interesting problem, but it's fairly easy if you've seen it before and rather tricky if you haven't. (In the real world, the chances of having a boy or girl are not exactly 50% and even depend on the ages of the parents. For more information, see the Psychology Today article “Why Are Older Parents More Likely to Have Daughters” at http://www.psychologytoday.com/blog/the-scientific-fundamentalist/201104/why-are-older-parents-more-likely-have-daughters.)
Clearly you could cut the brick into seven pieces and hand out one for each day worked.
There are several ways you can arrive at the best solution. In one approach, you consider how you can pay the contractor after each possible ending day.
If the job ends after one day, you must give the contractor 1/7th of the brick, so clearly you need a piece that is 1/7th of the brick.
If the job ends after two days, you must give the contractor 2/7ths of the brick. You could give him another 1/7th piece, but that won't give you any extra flexibility later. A better solution is to give him a piece that is 2/7ths of the brick and keep the 1/7th piece.
Because you have the 1/7th piece in reserve, you can use it and the 2/7ths piece to pay the contractor if the job ends after three days. If you had used two 1/7th pieces to pay the contractor after two days, this solution wouldn't work. You would need a third 1/7th piece so you would need to have three pieces instead of just two.
If you remove two pieces from the brick that are 1/7th and 2/7ths of the whole brick, the remaining brick contains 4/7th of the brick. If the job ends after four days, you can give the contractor that piece and keep the others.
If the job ends after five days, you can give the contractor the 4/7ths piece and the 1/7th piece.
If the job ends after six days, you can give the contractor the 4/7ths piece and the 2/7ths piece.
Finally if the job ends after seven days, you can give the contractor all the pieces.
When a problem involves magic numbers such as powers of 2 or 1 less than a power of 2, you should think about binary. In this example, the three pieces of the brick represent 1, 2, and 4 sevenths of the brick. The numbers 1 through 7, which are 001, 010, 011, 100, 101, 110, and 111 in binary, tell you which pieces of the brick to give to the contractor on each day. A 1 means you should give the contractor the corresponding piece, and a 0 means you should keep that piece.
For example, 6 is 110 in binary. That means on day 6 you give the contractor the 4/7ths piece (for the initial 1) and the 2/7ths piece (for the second 1) but not the 1/7th piece (for the final 0). The total payment on that day is 4/7 + 2/7 = 6/7.
This problem is easy if you've seen it before and can be confusing if you haven't, although you probably can come up with a solution if you work through it starting from day 1. Being aware of magic numbers can help.
In this problem, that doesn't quite work. If you put four eggs on each side of the balance, you can eliminate half of the eggs from consideration in one weighing. Then you can place the remaining four eggs, two on each side of the balance, and eliminate two more from consideration. At that point, you're still left with two eggs, and you've used up your two weighings.
The key to this problem is noticing that the balance doesn't define only two sets containing eggs in the left pan and eggs in the right pan. It also defines a third set containing eggs that are not in either pan. Instead of using binary division to divide the eggs into two groups and eliminating one, you can use ternary division to divide the eggs into three groups and eliminate two.
Suppose you have only three eggs. You could put one in the left pan, one in the right, and omit one. If the two pans balance, you know the third egg is goldplated. If the two pans don't balance, you know the egg in the lighter pan is the gold-plated egg.
That explains how you perform the second weighing to finalize your choice. You still need to figure out how to use the first weighing to reduce the number of remaining eggs to three (or fewer).
The balance lets you eliminate two of the three groups. After one weighing, the set of eggs still under consideration must include only three eggs. That means the groups you weigh in the first weighing should contain three eggs each.
(Note that, if the pans balance in the first weighing, you have narrowed the number of possibilities to two eggs. The second weighing can find the gold-plated egg in a set of three eggs, so it would work even if you had only narrowed the possibilities to three eggs. That means you can use the same technique even if you start with nine eggs instead of eight.)
This is an interesting problem, but it requires you to know the trick: You can use a pan balance to divide objects into three groups—those in the left pan, those in the right pan, and those that are not in any pan. If you have seen this kind of puzzle before, it's fairly easy.
The trick to this puzzle is obvious if you've seen a similar puzzle before.