# Difference between revisions of "Data-structures-TADM2E"

(Recovering wiki) |
|||

(3 intermediate revisions by 2 users not shown) | |||

Line 5: | Line 5: | ||

'''Stacks, Queues, and Lists''' | '''Stacks, Queues, and Lists''' | ||

− | + | <br>3-1. | |

A common problem for compilers and text editors is determining whether the | A common problem for compilers and text editors is determining whether the | ||

parentheses in a string are balanced and properly | parentheses in a string are balanced and properly | ||

nested. | nested. | ||

− | For example, the string | + | For example, the string <math>((())())()</math> contains properly nested |

− | pairs of parentheses, which the strings | + | pairs of parentheses, which the strings <math>)()(</math> and <math>())</math> |

do not. | do not. | ||

Give an algorithm that returns true if a string contains properly | Give an algorithm that returns true if a string contains properly | ||

Line 20: | Line 20: | ||

[[TADM2E 3.1|(Solution 3.1)]] | [[TADM2E 3.1|(Solution 3.1)]] | ||

− | + | <br>3-2. | |

Write a program to reverse the direction of a given singly-linked list. | Write a program to reverse the direction of a given singly-linked list. | ||

In other words, after the reversal all | In other words, after the reversal all | ||

Line 29: | Line 29: | ||

[[TADM2E 3.2|(Solution 3.2)]] | [[TADM2E 3.2|(Solution 3.2)]] | ||

− | + | <br>3-3. | |

We have seen how dynamic arrays enable arrays to grow | We have seen how dynamic arrays enable arrays to grow | ||

while still achieving constant-time amortized performance. | while still achieving constant-time amortized performance. | ||

Line 43: | Line 43: | ||

'''Trees and Other Dictionary Structures''' | '''Trees and Other Dictionary Structures''' | ||

− | + | <br>3-4. | |

Design a dictionary data structure in which search, insertion, and deletion | Design a dictionary data structure in which search, insertion, and deletion | ||

− | can all be processed in | + | can all be processed in <math>O(1)</math> time in the worst case. You |

may assume the set elements are integers drawn from a finite set | may assume the set elements are integers drawn from a finite set | ||

− | + | <math>{1,2,..,n}</math>, and initialization can take <math>O(n)</math> time. | |

[[TADM2E 3.4|(Solution 3.4)]] | [[TADM2E 3.4|(Solution 3.4)]] | ||

− | + | <br>3-5. | |

Find the overhead fraction (the ratio of data space over total space) | Find the overhead fraction (the ratio of data space over total space) | ||

for each of the following binary tree | for each of the following binary tree | ||

− | implementations on | + | implementations on <math>n</math> nodes: |

#All nodes store data, two child pointers, and a parent pointer. The data field requires four bytes and each pointer requires four bytes. | #All nodes store data, two child pointers, and a parent pointer. The data field requires four bytes and each pointer requires four bytes. | ||

#Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes. | #Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes. | ||

Line 60: | Line 60: | ||

[[TADM2E 3.5|(Solution 3.5)]] | [[TADM2E 3.5|(Solution 3.5)]] | ||

− | + | <br>3-6. | |

Describe how to modify any balanced tree data structure such | Describe how to modify any balanced tree data structure such | ||

− | that search, insert, delete, minimum, and maximum still take | + | that search, insert, delete, minimum, and maximum still take <math>O(\log n)</math> |

time each, | time each, | ||

− | but successor and predecessor now take | + | but successor and predecessor now take <math>O(1)</math> time each. |

Which operations have to be modified to support this? | Which operations have to be modified to support this? | ||

− | + | [[TADM2E 3-6|(Solution 3.6)]] | |

+ | |||

+ | <br>3-7. | ||

Suppose you have access to a balanced dictionary | Suppose you have access to a balanced dictionary | ||

data structure, which supports each of the operations | data structure, which supports each of the operations | ||

search, insert, delete, minimum, maximum, successor, and predecessor | search, insert, delete, minimum, maximum, successor, and predecessor | ||

− | in | + | in <math>O(\log n)</math> time. |

Explain how to modify the insert and delete operations so they still take | Explain how to modify the insert and delete operations so they still take | ||

− | + | <math>O( \log n)</math> but now minimum and maximum take <math>O(1)</math> time. | |

(Hint: think in terms of using the abstract dictionary operations, instead of | (Hint: think in terms of using the abstract dictionary operations, instead of | ||

mucking about with pointers and the like.) | mucking about with pointers and the like.) | ||

Line 79: | Line 81: | ||

[[TADM2E 3.7|(Solution 3.7)]] | [[TADM2E 3.7|(Solution 3.7)]] | ||

− | + | <br>3-8. | |

Design a data structure to support the following operations: | Design a data structure to support the following operations: | ||

− | #''insert(x,T)'' -- Insert item | + | #''insert(x,T)'' -- Insert item <math>x</math> into the set <math>T</math>. |

− | #''delete(k,T)'' -- Delete the | + | #''delete(k,T)'' -- Delete the <math>k</math>th smallest element from <math>T</math>. |

− | #''member(x,T)'' -- Return true iff | + | #''member(x,T)'' -- Return true iff <math>x \in T</math>. |

− | All operations must take | + | All operations must take <math>O(\log n)</math> time on an <math>n</math>-element set. |

+ | |||

+ | [[TADM2E 3.8 |(Solution 3.8)]] | ||

− | + | <br>3-9. | |

− | A ''concatenate'' operation takes two sets | + | A ''concatenate'' operation takes two sets <math>S_1</math> and <math>S_2</math>, where every |

− | key in | + | key in <math>S_1</math> is |

− | smaller than any key in | + | smaller than any key in <math>S_2</math>, and merges them together. |

Give an algorithm to concatenate two binary search trees into | Give an algorithm to concatenate two binary search trees into | ||

one binary search tree. | one binary search tree. | ||

− | The worst-case running time should be | + | The worst-case running time should be <math>O(h)</math>, where <math>h</math> is the maximal |

height of the two trees. | height of the two trees. | ||

Line 101: | Line 105: | ||

'''Applications of Tree Structures''' | '''Applications of Tree Structures''' | ||

− | + | <br>3-10. | |

− | In the ''bin-packing problem'', we are given | + | In the ''bin-packing problem'', we are given <math>n</math> metal |

objects, each weighing between zero and one kilogram. | objects, each weighing between zero and one kilogram. | ||

Our goal is to find the smallest | Our goal is to find the smallest | ||

− | number of bins that will hold the | + | number of bins that will hold the <math>n</math> objects, |

with each bin holding one kilogram at most. | with each bin holding one kilogram at most. | ||

− | #The ''best-fit heuristic'' for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room ''after'' the object is inserted.. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the | + | #The ''best-fit heuristic'' for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room ''after'' the object is inserted.. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the <math>n</math> weights <math>w_1,w_2,...,w_n</math> and outputting the number of bins used) in <math>O(n \log n)</math> time. |

#Repeat the above using the ''worst-fit heuristic'', where we put the next object in the partially filled bin with the largest amount of extra room ''after'' the object is inserted. | #Repeat the above using the ''worst-fit heuristic'', where we put the next object in the partially filled bin with the largest amount of extra room ''after'' the object is inserted. | ||

− | + | <br>3-11. | |

Suppose that we are given | Suppose that we are given | ||

− | a sequence of | + | a sequence of <math>n</math> values <math>x_1,x_2,...,x_n</math> and seek to quickly |

answer repeated queries of the form: | answer repeated queries of the form: | ||

− | given | + | given <math>i</math> and <math>j</math>, find the smallest value in <math>x_i,\ldots,x_j</math>. |

− | #Design a data structure that uses | + | #Design a data structure that uses <math>O(n^2)</math> space and answers queries in <math>O(1)</math> time. |

− | #Design a data structure that uses | + | #Design a data structure that uses <math>O(n)</math> space and answers queries in <math>O(\log n)</math> time. For partial credit, your data structure can use <math>O(n \log n)</math> space and have <math>O(\log n)</math> query time. |

[[TADM2E 3.11|(Solution 3.11)]] | [[TADM2E 3.11|(Solution 3.11)]] | ||

− | + | <br>3-12. | |

− | Suppose you are given an input set | + | Suppose you are given an input set <math>S</math> of <math>n</math> numbers, and a black box |

− | that if given any sequence of real numbers and an integer | + | that if given any sequence of real numbers and an integer <math>k</math> |

instantly and correctly answers | instantly and correctly answers | ||

− | whether there is a subset of input sequence whose sum is exactly | + | whether there is a subset of input sequence whose sum is exactly <math>k</math>. |

Show how to use the black box | Show how to use the black box | ||

− | + | <math>O(n)</math> times to find a subset of <math>S</math> that adds up to <math>k</math>. | |

[[TADM2E 3.12|(Solution 3.12)]] | [[TADM2E 3.12|(Solution 3.12)]] | ||

− | + | <br>3-13. | |

− | Let | + | Let <math>A[1..n]</math> be an array of real numbers. |

Design an algorithm to perform any sequence | Design an algorithm to perform any sequence | ||

of the following operations: | of the following operations: | ||

− | #''Add(i,y)'' -- Add the value | + | #''Add(i,y)'' -- Add the value <math>y</math> to the <math>i</math>th number. |

− | #''Partial-sum(i)'' -- Return the sum of the first | + | #''Partial-sum(i)'' -- Return the sum of the first <math>i</math> numbers, i.e. |

− | + | <math>\sum_{j=1}^i A[j]</math>. | |

There are no insertions or | There are no insertions or | ||

deletions; the only change is to the values of the numbers. | deletions; the only change is to the values of the numbers. | ||

− | Each operation should take | + | Each operation should take <math>O(\log n)</math> steps. |

− | You may use one additional array of size | + | You may use one additional array of size <math>n</math> as a work space. |

[[TADM2E 3.13|(Solution 3.13)]] | [[TADM2E 3.13|(Solution 3.13)]] | ||

− | + | <br>3-14. | |

Extend the data structure of the previous problem to support insertions | Extend the data structure of the previous problem to support insertions | ||

and deletions. | and deletions. | ||

Line 152: | Line 156: | ||

accessed by its key. | accessed by its key. | ||

The ''Partial-sum'' operation is different. | The ''Partial-sum'' operation is different. | ||

− | #''Add(k,y)'' -- Add the value | + | #''Add(k,y)'' -- Add the value <math>y</math> to the item with key <math>k</math>. |

− | #''Insert(k,y)'' -- Insert a new item with key | + | #''Insert(k,y)'' -- Insert a new item with key <math>k</math> and value <math>y</math>. |

− | #''Delete(k)'' -- Delete the item with key | + | #''Delete(k)'' -- Delete the item with key <math>k</math>. |

#''Partial-sum(k)'' -- | #''Partial-sum(k)'' -- | ||

Return the sum of all the elements currently in the set whose | Return the sum of all the elements currently in the set whose | ||

− | key is less than | + | key is less than <math>y</math>, i.e. <math>\sum_{x_j<y} x_i</math>. |

− | The worst case running time should still be | + | The worst case running time should still be <math>O(n \log n)</math> for any |

− | sequence of | + | sequence of <math>O(n)</math> |

operations. | operations. | ||

[[TADM2E 3.14|(Solution 3.14)]] | [[TADM2E 3.14|(Solution 3.14)]] | ||

− | + | <br>3-15. | |

Design a data structure that allows one to search, insert, and | Design a data structure that allows one to search, insert, and | ||

− | delete an integer | + | delete an integer <math>X</math> in <math>O(1)</math> time (i.e., constant time, independent of the total |

number of integers stored). | number of integers stored). | ||

− | Assume that | + | Assume that <math>1 \leq X \leq n</math> |

− | and that there are | + | and that there are <math>m+n</math> units |

− | of space available, where | + | of space available, where <math>m</math> is the maximum number of |

integers that can be in the table at any one time. | integers that can be in the table at any one time. | ||

− | (Hint: use two arrays | + | (Hint: use two arrays <math>A[1..n]</math> and <math>B[1..m]</math>.) |

− | You are not allowed to initialize either | + | You are not allowed to initialize either <math>A</math> or <math>B</math>, as that would take |

− | + | <math>O(m)</math> or <math>O(n)</math> operations. | |

This means the arrays are full of random garbage to begin with, so you must | This means the arrays are full of random garbage to begin with, so you must | ||

be very careful. | be very careful. | ||

Line 184: | Line 188: | ||

'''Implementation Projects''' | '''Implementation Projects''' | ||

− | + | <br>3-16. | |

Implement versions of several different dictionary data structures, | Implement versions of several different dictionary data structures, | ||

such as linked lists, binary trees, balanced binary search trees, | such as linked lists, binary trees, balanced binary search trees, | ||

Line 198: | Line 202: | ||

[[TADM2E 3.16|(Solution 3.16)]] | [[TADM2E 3.16|(Solution 3.16)]] | ||

− | + | <br>3-17. | |

A Caesar shift (see '''cryptography''') is a very simple | A Caesar shift (see '''cryptography''') is a very simple | ||

class of ciphers for secret messages. | class of ciphers for secret messages. | ||

Line 209: | Line 213: | ||

'''Interview Problems''' | '''Interview Problems''' | ||

− | + | <br>3-18. | |

What method would you use to look up a word in a dictionary? | What method would you use to look up a word in a dictionary? | ||

[[TADM2E 3.18|(Solution 3.18)]] | [[TADM2E 3.18|(Solution 3.18)]] | ||

− | + | <br>3-19. | |

Imagine you have a closet full of shirts. What | Imagine you have a closet full of shirts. What | ||

can you do to organize your shirts for easy retrieval? | can you do to organize your shirts for easy retrieval? | ||

Line 220: | Line 224: | ||

[[TADM2E 3.19|(Solution 3.19)]] | [[TADM2E 3.19|(Solution 3.19)]] | ||

− | + | <br>3-20. | |

Write a function to find the middle node of a singly-linked list. | Write a function to find the middle node of a singly-linked list. | ||

[[TADM2E 3.20|(Solution 3.20)]] | [[TADM2E 3.20|(Solution 3.20)]] | ||

− | + | <br>3-21. | |

Write a function to compare whether two binary trees are identical. | Write a function to compare whether two binary trees are identical. | ||

Identical trees have the same key value at each position and the same | Identical trees have the same key value at each position and the same | ||

Line 232: | Line 236: | ||

[[TADM2E 3.21|(Solution 3.21)]] | [[TADM2E 3.21|(Solution 3.21)]] | ||

− | + | <br>3-22. | |

Write a program to convert a binary search tree into a linked list. | Write a program to convert a binary search tree into a linked list. | ||

Line 238: | Line 242: | ||

[[TADM2E 3.22|(Solution 3.22)]] | [[TADM2E 3.22|(Solution 3.22)]] | ||

− | + | <br>3-23. | |

Implement an algorithm to reverse a linked list. Now do it without | Implement an algorithm to reverse a linked list. Now do it without | ||

recursion. | recursion. | ||

Line 244: | Line 248: | ||

[[TADM2E 3.23|(Solution 3.23)]] | [[TADM2E 3.23|(Solution 3.23)]] | ||

− | + | <br>3-24. | |

What is the best data structure for maintaining URLs that have been | What is the best data structure for maintaining URLs that have been | ||

visited by a Web crawler? | visited by a Web crawler? | ||

Line 252: | Line 256: | ||

[[TADM2E 3.24|(Solution 3.24)]] | [[TADM2E 3.24|(Solution 3.24)]] | ||

− | + | <br>3-25. | |

You are given a search string and a magazine. You seek to generate all | You are given a search string and a magazine. You seek to generate all | ||

the characters in search string by cutting them out from the | the characters in search string by cutting them out from the | ||

Line 260: | Line 264: | ||

[[TADM2E 3.25|(Solution 3.25)]] | [[TADM2E 3.25|(Solution 3.25)]] | ||

− | + | <br>3-26. | |

Reverse the words in a sentence---i.e., ''My name is Chris'' becomes | Reverse the words in a sentence---i.e., ''My name is Chris'' becomes | ||

''Chris is name My.'' Optimize for time and space. | ''Chris is name My.'' Optimize for time and space. | ||

Line 266: | Line 270: | ||

[[TADM2E 3.26|(Solution 3.26)]] | [[TADM2E 3.26|(Solution 3.26)]] | ||

− | + | <br>3-27. | |

Determine whether a linked list contains a loop as quickly as possible | Determine whether a linked list contains a loop as quickly as possible | ||

without using any extra storage. | without using any extra storage. | ||

Line 273: | Line 277: | ||

[[TADM2E 3.27|(Solution 3.27)]] | [[TADM2E 3.27|(Solution 3.27)]] | ||

− | + | <br>3-28. | |

− | You have an unordered array | + | You have an unordered array <math>X</math> of <math>n</math> integers. Find the array <math>M</math> |

− | containing | + | containing <math>n</math> elements where <math>M_i</math> is the product of all integers in <math>X</math> |

− | except for | + | except for <math>X_i</math>. You may not use division. You can use extra |

− | memory. (Hint: There are solutions faster than | + | memory. (Hint: There are solutions faster than <math>O(n^2)</math>.) |

[[TADM2E 3.28|(Solution 3.28)]] | [[TADM2E 3.28|(Solution 3.28)]] | ||

− | + | <br>3-29. | |

Give an algorithm for finding an ordered word pair (e.g., ''New York'') | Give an algorithm for finding an ordered word pair (e.g., ''New York'') | ||

occurring with the greatest | occurring with the greatest |

## Latest revision as of 00:09, 22 July 2018

# Data Structures

**Stacks, Queues, and Lists**

3-1.
A common problem for compilers and text editors is determining whether the
parentheses in a string are balanced and properly
nested.
For example, the string $ ((())())() $ contains properly nested
pairs of parentheses, which the strings $ )()( $ and $ ()) $
do not.
Give an algorithm that returns true if a string contains properly
nested and balanced parentheses, and false if otherwise.
For full credit,
identify the position of the first
offending parenthesis if the string is not properly nested and balanced.

3-2.
Write a program to reverse the direction of a given singly-linked list.
In other words, after the reversal all
pointers should now point backwards.
Your algorithm should take linear time.

3-3.
We have seen how dynamic arrays enable arrays to grow
while still achieving constant-time amortized performance.
This problem concerns extending dynamic arrays to let them both
grow and shrink on demand.

- Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.
- Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.

**Trees and Other Dictionary Structures**

3-4.
Design a dictionary data structure in which search, insertion, and deletion
can all be processed in $ O(1) $ time in the worst case. You
may assume the set elements are integers drawn from a finite set
$ {1,2,..,n} $, and initialization can take $ O(n) $ time.

3-5.
Find the overhead fraction (the ratio of data space over total space)
for each of the following binary tree
implementations on $ n $ nodes:

- All nodes store data, two child pointers, and a parent pointer. The data field requires four bytes and each pointer requires four bytes.
- Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.

3-6.
Describe how to modify any balanced tree data structure such
that search, insert, delete, minimum, and maximum still take $ O(\log n) $
time each,
but successor and predecessor now take $ O(1) $ time each.
Which operations have to be modified to support this?

3-7.
Suppose you have access to a balanced dictionary
data structure, which supports each of the operations
search, insert, delete, minimum, maximum, successor, and predecessor
in $ O(\log n) $ time.
Explain how to modify the insert and delete operations so they still take
$ O( \log n) $ but now minimum and maximum take $ O(1) $ time.
(Hint: think in terms of using the abstract dictionary operations, instead of
mucking about with pointers and the like.)

3-8.
Design a data structure to support the following operations:

*insert(x,T)*-- Insert item $ x $ into the set $ T $.*delete(k,T)*-- Delete the $ k $th smallest element from $ T $.*member(x,T)*-- Return true iff $ x \in T $.

All operations must take $ O(\log n) $ time on an $ n $-element set.

3-9.
A *concatenate* operation takes two sets $ S_1 $ and $ S_2 $, where every
key in $ S_1 $ is
smaller than any key in $ S_2 $, and merges them together.
Give an algorithm to concatenate two binary search trees into
one binary search tree.
The worst-case running time should be $ O(h) $, where $ h $ is the maximal
height of the two trees.

**Applications of Tree Structures**

3-10.
In the *bin-packing problem*, we are given $ n $ metal
objects, each weighing between zero and one kilogram.
Our goal is to find the smallest
number of bins that will hold the $ n $ objects,
with each bin holding one kilogram at most.

- The
*best-fit heuristic*for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room*after*the object is inserted.. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the $ n $ weights $ w_1,w_2,...,w_n $ and outputting the number of bins used) in $ O(n \log n) $ time. - Repeat the above using the
*worst-fit heuristic*, where we put the next object in the partially filled bin with the largest amount of extra room*after*the object is inserted.

3-11.
Suppose that we are given
a sequence of $ n $ values $ x_1,x_2,...,x_n $ and seek to quickly
answer repeated queries of the form:
given $ i $ and $ j $, find the smallest value in $ x_i,\ldots,x_j $.

- Design a data structure that uses $ O(n^2) $ space and answers queries in $ O(1) $ time.
- Design a data structure that uses $ O(n) $ space and answers queries in $ O(\log n) $ time. For partial credit, your data structure can use $ O(n \log n) $ space and have $ O(\log n) $ query time.

3-12.
Suppose you are given an input set $ S $ of $ n $ numbers, and a black box
that if given any sequence of real numbers and an integer $ k $
instantly and correctly answers
whether there is a subset of input sequence whose sum is exactly $ k $.
Show how to use the black box
$ O(n) $ times to find a subset of $ S $ that adds up to $ k $.

3-13.
Let $ A[1..n] $ be an array of real numbers.
Design an algorithm to perform any sequence
of the following operations:

*Add(i,y)*-- Add the value $ y $ to the $ i $th number.*Partial-sum(i)*-- Return the sum of the first $ i $ numbers, i.e.

$ \sum_{j=1}^i A[j] $. There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take $ O(\log n) $ steps. You may use one additional array of size $ n $ as a work space.

3-14.
Extend the data structure of the previous problem to support insertions
and deletions.
Each element now has both a *key* and a *value*.
An element is accessed by its key.
The addition operation is applied to the values, but the elements are
accessed by its key.
The *Partial-sum* operation is different.

*Add(k,y)*-- Add the value $ y $ to the item with key $ k $.*Insert(k,y)*-- Insert a new item with key $ k $ and value $ y $.*Delete(k)*-- Delete the item with key $ k $.*Partial-sum(k)*--

Return the sum of all the elements currently in the set whose key is less than $ y $, i.e. $ \sum_{x_j<y} x_i $. The worst case running time should still be $ O(n \log n) $ for any sequence of $ O(n) $ operations.

3-15.
Design a data structure that allows one to search, insert, and
delete an integer $ X $ in $ O(1) $ time (i.e., constant time, independent of the total
number of integers stored).
Assume that $ 1 \leq X \leq n $
and that there are $ m+n $ units
of space available, where $ m $ is the maximum number of
integers that can be in the table at any one time.
(Hint: use two arrays $ A[1..n] $ and $ B[1..m] $.)
You are not allowed to initialize either $ A $ or $ B $, as that would take
$ O(m) $ or $ O(n) $ operations.
This means the arrays are full of random garbage to begin with, so you must
be very careful.

**Implementation Projects**

3-16.
Implement versions of several different dictionary data structures,
such as linked lists, binary trees, balanced binary search trees,
and hash tables.
Conduct experiments to assess the relative performance of these data
structures in a simple application that reads a large text file
and reports exactly one instance of each word that appears within it.
This application can be efficiently implemented by maintaining a dictionary
of all distinct words that have appeared thus far in the text and
inserting/reporting each word that is not found.
Write a brief report with your conclusions.

3-17.
A Caesar shift (see **cryptography**) is a very simple
class of ciphers for secret messages.
Unfortunately, they can be broken using statistical properties of English.
Develop a program capable of decrypting Caesar shifts of sufficiently
long texts.

**Interview Problems**

3-18.
What method would you use to look up a word in a dictionary?

3-19.
Imagine you have a closet full of shirts. What
can you do to organize your shirts for easy retrieval?

3-20.
Write a function to find the middle node of a singly-linked list.

3-21.
Write a function to compare whether two binary trees are identical.
Identical trees have the same key value at each position and the same
structure.

3-22.
Write a program to convert a binary search tree into a linked list.

3-23.
Implement an algorithm to reverse a linked list. Now do it without
recursion.

3-24.
What is the best data structure for maintaining URLs that have been
visited by a Web crawler?
Give an algorithm to test whether a given URL has already
been visited, optimizing both space and time.

3-25.
You are given a search string and a magazine. You seek to generate all
the characters in search string by cutting them out from the
magazine. Give an algorithm to efficiently determine whether the
magazine contains all the letters in the search string.

3-26.
Reverse the words in a sentence---i.e., *My name is Chris* becomes
*Chris is name My.* Optimize for time and space.

3-27.
Determine whether a linked list contains a loop as quickly as possible
without using any extra storage.
Also, identify the location of the loop.

3-28.
You have an unordered array $ X $ of $ n $ integers. Find the array $ M $
containing $ n $ elements where $ M_i $ is the product of all integers in $ X $
except for $ X_i $. You may not use division. You can use extra
memory. (Hint: There are solutions faster than $ O(n^2) $.)

3-29.
Give an algorithm for finding an ordered word pair (e.g., *New York*)
occurring with the greatest
frequency in a given webpage.
Which data structures would you use?
Optimize both time and space.