Chapter 3

Data Structure

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 [math]\displaystyle{ ((())())() }[/math] contains properly nested pairs of parentheses, which the strings [math]\displaystyle{ )()( }[/math] and [math]\displaystyle{ ()) }[/math] 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.

Solution

3.2. Give an algorithm that takes a string [math]\displaystyle{ S }[/math] consisting of opening and closing parentheses, say )()(())()()))())))(, and finds the length of the longest balanced parentheses in [math]\displaystyle{ S }[/math], which is 12 in the example above. (Hint: The solution is not necessarily a contiguous run of parenthesis from [math]\displaystyle{ S }[/math].)

3.3. Give an algorithm 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.

Solution

3.4. Design a stack [math]\displaystyle{ S }[/math] that supports S.push(x), S.pop(), and S.findmin(), which returns the minimum element of [math]\displaystyle{ S }[/math]. All operations should run in constant time.

3.5. 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.

(a) 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.

(b) Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.

Solution

3.6. Suppose you seek to maintain the contents of a refrigerator so as to minimize food spoilage. What data structure should you use, and how should you use it?

3.7. Work out the details of supporting constant-time deletion from a singly linked list as per the footnote from page 79, ideally to an actual implementation. Support the other operations as efficiently as possible.

Solution

Elementary Data Structures

3.8. Tic-tac-toe is a game played on an [math]\displaystyle{ n * n }[/math] board (typically [math]\displaystyle{ n = 3 }[/math]) where two players take consecutive turns placing “O” and “X” marks onto the board cells. The game is won if n consecutive “O” or ‘X” marks are placed in a row, column, or diagonal. Create a data structure with [math]\displaystyle{ O(n) }[/math] space that accepts a sequence of moves, and reports in constant time whether the last move won the game.

3.9. Write a function which, given a sequence of digits 2–9 and a dictionary of [math]\displaystyle{ n }[/math] words, reports all words described by this sequence when typed in on a standard telephone keypad. For the sequence 269 you should return any, box, boy, and cow, among other words.

Solution

3.10. Two strings [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are anagrams if the letters of [math]\displaystyle{ X }[/math] can be rearranged to form [math]\displaystyle{ Y }[/math] . For example, silent/listen, and incest/insect are anagrams. Give an efficient algorithm to determine whether strings [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are anagrams.

Trees and Other Dictionary Structures

3.11. Design a dictionary data structure in which search, insertion, and deletion can all be processed in [math]\displaystyle{ O(1) }[/math] time in the worst case. You may assume the set elements are integers drawn from a finite set [math]\displaystyle{ 1, 2, .., n }[/math], and initialization can take [math]\displaystyle{ O(n) }[/math] time.

Solution

3.12. The maximum depth of a binary tree is the number of nodes on the path from the root down to the most distant leaf node. Give an [math]\displaystyle{ O(n) }[/math] algorithm to find the maximum depth of a binary tree with [math]\displaystyle{ n }[/math] nodes.

3.13. Two elements of a binary search tree have been swapped by mistake. Give an [math]\displaystyle{ O(n) }[/math] algorithm to identify these two elements so they can be swapped back.

Solution

3.14. Given two binary search trees, merge them into a doubly linked list in sorted order.

3.15. Describe an [math]\displaystyle{ O(n) }[/math]-time algorithm that takes an [math]\displaystyle{ n }[/math]-node binary search tree and constructs an equivalent height-balanced binary search tree. In a height-balanced binary search tree, the difference between the height of the left and right subtrees of every node is never more than 1.

Solution

3.16. Find the storage efficiency ratio (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:

(a) All nodes store data, two child pointers, and a parent pointer. The data field requires 4 bytes and each pointer requires 4 bytes.

(b) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.

3.17. Give an [math]\displaystyle{ O(n) }[/math] algorithm that determines whether a given [math]\displaystyle{ n }[/math]-node binary tree is height-balanced (see Problem 3-15).

Solution

3.18. Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take [math]\displaystyle{ O(log n) }[/math] time each, but successor and predecessor now take [math]\displaystyle{ O(1) }[/math] time each. Which operations have to be modified to support this?

3.19. Suppose you have access to a balanced dictionary data structure that supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in [math]\displaystyle{ O(log n) }[/math] time. Explain how to modify the insert and delete operations so they still take [math]\displaystyle{ O(log n) }[/math] but now minimum and maximum take [math]\displaystyle{ O(1) }[/math] time. (Hint: think in terms of using the abstract dictionary operations, instead of mucking about with pointers and the like.)

Solution

3.20. Design a data structure to support the following operations:

• insert([math]\displaystyle{ x,T }[/math]) – Insert item [math]\displaystyle{ x }[/math] into the set [math]\displaystyle{ T }[/math].

• delete([math]\displaystyle{ k,T }[/math]) – Delete the [math]\displaystyle{ k }[/math]th smallest element from [math]\displaystyle{ T }[/math].

• member([math]\displaystyle{ x,T }[/math]) – Return true iff [math]\displaystyle{ x \in T }[/math].

All operations must take [math]\displaystyle{ O(log n) }[/math] time on an [math]\displaystyle{ n }[/math]-element set.

3.21. A concatenate operation takes two sets [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math], where every key in [math]\displaystyle{ S_1 }[/math] is smaller than any key in [math]\displaystyle{ S_2 }[/math], and merges them. Give an algorithm to concatenate two binary search trees into one binary search tree. The worst-case running time should be [math]\displaystyle{ O(h) }[/math], where [math]\displaystyle{ h }[/math] is the maximal height of the two trees.

Solution

Applications of Tree Structures

3.22. Design a data structure that supports the following two operations:

• insert([math]\displaystyle{ x }[/math]) – Insert item [math]\displaystyle{ x }[/math] from the data stream to the data structure.

• median() – Return the median of all elements so far.

All operations must take [math]\displaystyle{ O(log n) }[/math] time on an [math]\displaystyle{ n }[/math]-element set.

3.23. Assume we are given a standard dictionary (balanced binary search tree) defined on a set of [math]\displaystyle{ n }[/math] strings, each of length at most [math]\displaystyle{ l }[/math]. We seek to print out all strings beginning with a particular prefix [math]\displaystyle{ p }[/math]. Show how to do this in [math]\displaystyle{ O(ml log n) }[/math] time, where [math]\displaystyle{ m }[/math] is the number of strings.

Solution

3.24. An array [math]\displaystyle{ A }[/math] is called [math]\displaystyle{ k }[/math]-unique if it does not contain a pair of duplicate elements within [math]\displaystyle{ k }[/math] positions of each other, that is, there is no [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] such that [math]\displaystyle{ A[i] = A[j] }[/math] and [math]\displaystyle{ |j - i| \leq k }[/math]. Design a worst-case [math]\displaystyle{ O(n log k) }[/math] algorithm to test if [math]\displaystyle{ A }[/math] is [math]\displaystyle{ k }[/math]-unique.

3.25. In the bin-packing problem, we are given [math]\displaystyle{ n }[/math] objects, each weighing at most 1 kilogram. Our goal is to find the smallest number of bins that will hold the [math]\displaystyle{ n }[/math] objects, with each bin holding 1 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 [math]\displaystyle{ n }[/math] weights [math]\displaystyle{ w_1, w_2, ..., w_n }[/math] and outputting the number of bins used) in [math]\displaystyle{ O(n log n) }[/math] time.

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

Solution

3.26. Suppose that we are given a sequence of [math]\displaystyle{ n }[/math] values [math]\displaystyle{ x_1, x_2, ..., x_n }[/math] and seek to quickly answer repeated queries of the form: given [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math], find the smallest value in [math]\displaystyle{ x_i, . . . , x_j }[/math].

(a) Design a data structure that uses [math]\displaystyle{ O(n^2) }[/math] space and answers queries in [math]\displaystyle{ O(1) }[/math] time.

(b) Design a data structure that uses [math]\displaystyle{ O(n) }[/math] space and answers queries in [math]\displaystyle{ O(log n) }[/math] time. For partial credit, your data structure can use [math]\displaystyle{ O(n log n) }[/math] space and have [math]\displaystyle{ O(log n) }[/math] query time.

3.27. Suppose you are given an input set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers, and a black box that if given any sequence of integers and an integer [math]\displaystyle{ k }[/math] instantly and correctly answers whether there is a subset of the input sequence whose sum is exactly [math]\displaystyle{ k }[/math]. Show how to use the black box [math]\displaystyle{ O(n) }[/math] times to find a subset of [math]\displaystyle{ S }[/math] that adds up to [math]\displaystyle{ k }[/math].

Solution

3.28. Let [math]\displaystyle{ A[1..n] }[/math] be an array of real numbers. Design an algorithm to perform any sequence of the following operations:

• Add([math]\displaystyle{ i,y }[/math]) – Add the value [math]\displaystyle{ y }[/math] to the [math]\displaystyle{ i }[/math]th number.

• Partial-sum([math]\displaystyle{ i }[/math]) – Return the sum of the first [math]\displaystyle{ i }[/math] numbers, that is, [math]\displaystyle{ \sum_{j=1}^i A[j] }[/math].

There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take [math]\displaystyle{ O(log n) }[/math] steps. You may use one additional array of size [math]\displaystyle{ n }[/math] as a work space.

3.29. 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, but the addition operation is applied to the values. The Partial_sum operation is different.

• 'Add([math]\displaystyle{ k,y }[/math]) – Add the value [math]\displaystyle{ y }[/math] to the item with key [math]\displaystyle{ k }[/math].

• Insert([math]\displaystyle{ k,y }[/math]) – Insert a new item with key [math]\displaystyle{ k }[/math] and value [math]\displaystyle{ y }[/math].

• Delete([math]\displaystyle{ k }[/math]) – Delete the item with key [math]\displaystyle{ k }[/math].

• Partial-sum([math]\displaystyle{ k }[/math]) – Return the sum of all the elements currently in the set whose key is less than [math]\displaystyle{ k }[/math], that is, [math]\displaystyle{ \sum_{i \lt k} x_i }[/math].

The worst-case running time should still be [math]\displaystyle{ O(n log n) }[/math] for any sequence of [math]\displaystyle{ O(n) }[/math] operations.

Solution

3.30. You are consulting for a hotel that has [math]\displaystyle{ n }[/math] one-bed rooms. When a guest checks in, they ask for a room whose number is in the range [math]\displaystyle{ [l, h] }[/math]. Propose a data structure that supports the following data operations in the allotted time:

(a) Initialize([math]\displaystyle{ n }[/math]): Initialize the data structure for empty rooms numbered [math]\displaystyle{ 1, 2, . . . , n }[/math], in polynomial time.

(b) Count([math]\displaystyle{ l, h }[/math]): Return the number of available rooms in [math]\displaystyle{ [l, h] }[/math], in [math]\displaystyle{ O(log n) }[/math] time.

(c) Checkin([math]\displaystyle{ l, h }[/math]): In [math]\displaystyle{ O(log n) }[/math] time, return the first empty room in [math]\displaystyle{ [l, h] }[/math] and mark it occupied, or return NIL if all the rooms in [math]\displaystyle{ [l, h] }[/math] are occupied.

(d) Checkout([math]\displaystyle{ x }[/math]): Mark room [math]\displaystyle{ x }[/math] as unoccupied, in [math]\displaystyle{ O(log n) }[/math] time.

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

Solution

Implementation Projects

3.32. 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 new word that appears in the stream. Write a brief report with your conclusions.

3.33. A Caesar shift (see Section 21.6 (page 697)) 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.

Solution

Interview Problems

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

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

Solution

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

3.37. [4] Write a function to determine whether two binary trees are identical. Identical trees have the same key value at each position and the same structure.

Solution

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

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

Solution

3.40. 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.41. You are given a search string and a magazine. You seek to generate all the characters in the 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.

Solution

3.42. Reverse the words in a sentence—that is, “My name is Chris” becomes “Chris is name My.” Optimize for time and space.

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

Solution

3.44. You have an unordered array [math]\displaystyle{ X }[/math] of [math]\displaystyle{ n }[/math] integers. Find the array [math]\displaystyle{ M }[/math] containing [math]\displaystyle{ n }[/math] elements where [math]\displaystyle{ M_i }[/math] is the product of all integers in [math]\displaystyle{ X }[/math] except for [math]\displaystyle{ X_i }[/math]. You may not use division. You can use extra memory. (Hint: there are solutions faster than [math]\displaystyle{ O(n^2) }[/math].)

3.45. 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.

Solution

Back to Chapter List