Laboratory Exercise 8
CSci 227: Programming Methods
Department of Computer Science
Hunter College, City University of New York
Spring 2024
Learning Objectives:
- To understand the map abstract data type.
- To understand the performance of the implementations of basic linear data structures (stack, queue, deque, list, and map).
Software Tools Needed: Web browser to access textbook and an IDE (on-line or on computer) with core Python 3.6+ loaded.
Hashing & Map ADT's
In Section 5.5, the textbook introduces hashing and the Map ADT. Work through the code in the section below:
Array Tricks
As we wrap up the section of our course on linear data types, let's look at other ways we can use the linear structure in efficiently solving the problems.
Here's a classic question: 442. Find All Duplicates:
While we can use a dictionary or look-up table to solve this with linear additional space, can you use less space?
The idea is to use the inputted array to store what you have seen before. When we've seen the number, we'll multiply its box by -1. Since lists 0-indexed and the numbers start with 1, we'll subtract 1 for the index. If we see a box that's negative, then we know that it's a duplicate.
Looping through the list: nums = [4,3,2,7,8,2,3,1]
- For 4: we'll set the 4th box to negative by multiplying
nums[4-1] *= -1and the array:nums = [4,3,2,-7,8,2,3,1] - For 3: we'll set the 3rd box to negative by multiplying
nums[3-1] *= -1and the array:nums = [4,3,-2,-7,8,2,3,1] - For 2: we'll set the 2nd box to negative by multiplying
nums[2-1] *= -1and the array:nums = [4,-3,-2,-7,8,2,3,1] - For 7: we'll set the 7th box to negative by multiplying
nums[7-1] *= -1and the array:nums = [4,-3,-2,-7,8,2,-3,1] - For 8: we'll set the 8th box to negative by multiplying
nums[8-1] *= -1and the array:nums = [4,-3,-2,-7,8,2,-3,-1] - For 2:
nums[2-1] < 0so we've seen it before and add 2 to the duplicates list. - For 3:
nums[3-1] < 0so we've seen it before and add 3 to the duplicates list. - For 1: we'll set the 1st box to negative by multiplying
nums[1-1] *= -1and the array:nums = [-4,-3,-2,-7,8,2,-3,-1]
Next, write out the approach as pseudocode and then translate it into Python (see Problem 22 and Problem 23).
Quizzes and Code Reviews
There are weekly written quizzes and code reviews in 1001G, 11:30-5:30, Mondays-Fridays when classes are in session. No appointments are needed for CSCI 227 students. Make sure to complete Quiz 8 and Code Review 8 by Thursday, 4 April.Additional Practice
For additional practice on core Python, see the HackerRank prepare series:
HackerRank: Prepare Python
Click the Easy option on the right hand menu, and work through their Python challenges.
For more practice on using problems that use maps, here are some popular ones from LeetCode: