Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Midterm Exam Written Questions
1. Reverse a Linked List
You are given a singly-linked list, where each Node is defined as follows:
struct Node {
int val;
Node *next;
Node() : val{0}, next{nullptr} {}
Node(int x) : val{x}, next{nullptr} {}
Node(int x, Node *next_in) : val{x}, next{next_in} {}
};
Write a program that reverses this singly-linked list. Return the new head node after you’re done.
Example: Given the head node of the following list
1->2->3->4->nullptr
You would return the following list
4->3->2->1->nullptr
Complexity: O(n) time and O(1) auxiliary space, where n is the length of the list.
Implementation: Implement your solution in the space below. You may NOT use anything from the STL. Line limit: 15 lines of code.
Node * reverse_list(Node *head) {
2. Remove Duplicates from Sorted Linked List
You are given a sorted linked list, where each Node is defined as follows:
struct Node {
int val;
Node *next;
Node() : val{0}, next{nullptr} {}
Node(int x) : val{x}, next{nullptr} {}
Node(int x, Node *next_in) : val{x}, next{next_in} {}
};
Write a function that deletes all duplicates in the list so that each element ends up only appearing once.
Example: After passing the list 280->280->281->370->370 into the function, the final list should be 280->281->370.
Complexity: O(n) time and O(1) auxiliary space, where n is the length of the list.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
Node * remove_duplicates(Node *head) {
3. Previous Greater Element
You are given a non-empty vector of distinct elements, and you want to return a vector that stores the previous greater element that exists before each index. If no previous greater element exists, -1 is stored.
Example 1: Given vec = [11, 16, 15, 13], you would return [-1, -1, 16, 15].
Example 2: Given vec = [19, 18, 12, 14, 13], you would return [-1, 19, 18, 18, 14].
Complexity: O(n) time and O(n) auxiliary space, where n is the length of the vector.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
vector<int> prev_greatest_element(vector<int> &vec) {
4. Merging Intervals
You are given a collection of intervals. Write a function that merges all of the overlapping intervals.
Example 1: Given vec = [[1, 3], [2, 6], [8, 10], [15, 18]], you would return [[1, 6], [8, 10], [15, 18]].
Example 2: Given vec = [[4, 5], [1, 4]], you would return [[1, 5]].
Complexity: O(n log(n)) time and O(n) auxiliary memory, where n is the length of the vector of intervals.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 20 lines of code.
struct Interval {
int start;
int end;
};
vector merge_intervals(vector &vec) {
5. List Addition
You are given two non-empty linked lists representing two non-negative integers. The most signi cant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the result as a linked list. You may assume the two numbers do not contain any leading 0's except the number 0 itself. The structure of a Node is provided below:
struct Node {
int val;
Node *next;
Node() : val{0}, next{nullptr} {}
Node(int x) : val{x}, next{nullptr} {}
Node(int x, Node *next_in) : val{x}, next{next_in} {}
};
Example: Given the following two lists:
1->9->4->7->nullptr
9->3->9->nullptr
you would return the list 2->8->8->6->nullptr.
Complexity: O(n) time and O(n) auxiliary space, where n is the combined length of the lists.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 30 lines of code.
Node * add_lists(Node *list1, Node *list2) {
6. Single Element in Sorted Array
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Write a function that returns the single element.
Example: Given vec = [1, 1, 2, 3, 3, 4, 4], you would return 2.
Complexity: O(log(n)) time and O(1) auxiliary space, where n is the length of the vector.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
int find_single_element(vector<int> &vec) {
7. Merging Lists
You are given k sorted linked lists. Write a program that merges all k lists into a single sorted list. The structure of a Node is provided below:
struct Node {
int val;
Node *next;
Node() : val{0}, next{nullptr} {}
Node(int x) : val{x}, next{nullptr} {}
Node(int x, Node *next_in) : val{x}, next{next_in} {}
};
Example: Given the following four lists:
1->5->7->nullptr
4->9->nullptr
3->6->8->10->nullptr
2->nullptr
you would return the list 1->2->3->4->5->6->7->8->9->10->nullptr.
Complexity: O(nk log(k)) time and O(n) auxiliary space, where n is the length of the longest list.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 25 lines of code.
Node * merge_lists(vector &lists) {
8. Shifting Zeros
You are given a vector of integers, vec, and you are told to implement a function that moves all elements with a value of 0 to the end of the vector while maintaining the relative order of the non-zero elements.
Example: Given the initial vector [0, 1, 0, 4, 3], you should rearrange the contents ofthe vector so that the final ordering of elements is [1, 4, 3, 0, 0].
Complexity: O(n) time, O(1) auxiliary space, where n is the length of the vector.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
void shift_zeros(vector<int> &vec) {
9. Warmer Temperatures
You are given a vector of integers, temps, that stores the daily temperature forecasts for the next few days. Write a program that, for each index of the input vector, stores the number of days you need to wait for a warmer temperature. If there is no future day where this is possible, a value of 0 should be stored.
Example 1: Given the following vector:
[55, 62, 46, 52, 51, 50, 51, 53, 63]
you would return the vector
[1, 7, 1, 4, 3, 1, 1, 1, 0]
since you would need to wait 1 day on day 0 for a warmer temperature (55 → 62), 7 days on day 1 for a warmer temperature (62 → 63), and so on.
Example 2: Given the following vector:
[74, 74, 73, 75, 74, 73, 72, 71, 70]
you would return the vector
[3, 2, 1, 0, 0, 0, 0, 0, 0]
Your program should run in O(n) time. You may use extra space to store your output, but the rest of your program must use O(1) auxiliary space.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 20 lines of code.
vector<int> warmer_temperatures(vector<int> &temps) {
10. 2-D Matrix Search
You are given a m × n matrix in the form of a vector of vectors that has the following properties:
• integers in each row are sorted in ascending order from left to right
• integers in each column are sorted in ascending order from top to bottom
Write a function that searches for a value in this matrix and returns whether the element can be found.
Example: Given the following matrix:
[ [ 1, 4, 7, 11, 15],
[ 2, 5, 8, 12, 19],
[ 3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30] ]
and a target value of 5, you would return true. Given a target value of 20, you would return false. Complexity: O(m + n) time, O(1) auxiliary space.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 20 lines of code.
bool matrix_search(vectorint>> &matrix, int target) {
11. Rotated Vector
Suppose you are given an vector of integers that is sorted in ascending order. However, this vector has been rotated at some pivot unknown to you beforehand.
For instance, the vector [1, 2, 3, 4, 5] may be given to you in the form [3, 4, 5, 1, 2], where the vector is rotated at 3. You may assume that no duplicate exists in this array.
Write a function that finds the minimum element in the vector.
Example: Given input [3, 4, 5, 1, 2], you would return 1.
Complexity: O(log(n)) time, O(1) auxiliary space, where n is the length of the vector.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
int find_rotated_minimum(vector<int> &vec) {
12. Pair Whose Sum is Closest to Target
You are given a vector of integers and a target value k. Write a function that returns the pair of elements whose sum is closest to k. The smaller element should go first in the pair that is returned.
Example: Given the input vector [29, 30, 40, 10, 28, 22] and a target of k = 54, you would return the pair [22, 30].
Complexity: O(n log(n)) time, O(log(n)) auxiliary space, where n is the length of the vector.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 20 lines of code.
pair<int , int> closest_sum_to_k(vector<int> &vec, int k) {
13. Social Networking
The EECS 281 staff is testing a brand new social media site, Fee’s Book, to promote social interaction among EECS students! Suppose there are a total of n students that are invited to the site, and each student is assigned a unique integer ID from 0 to n — 1. You are given the number of students in the network, num_students, and a vector of activity logs, where each log stores an integer timestamp and the IDs of two students on the site:
struct Log {
int timestamp;
int id_A;
int id_B;
};
Each Log object represents the time when students id_A and id_B became friends. The timestamp is represented in YYYYMMDD format (e.g. February 26, 2020 is represented as the integer 20200226). Friendship is symmetric: if A is friends with B, then B is friends with A.
Let’s say that person A is acquainted with person B if A and B are in the same friend group; that is, if A is friends with B, or A is a friend of someone acquainted with B. Implement the earliestAcquaintance() function, which returns the earliest timestamp for which every person in the network is acquainted with every other person. Return -1 if there is no such earliest time.
Example 1: Given num_students = 5 and friendships = [{20200229, 2, 3},
{20200227, 1, 4}, {20200303, 0, 3}, {20200228, 0, 4}, {20200301, 1, 2}, {20200226, 0, 2}], you would return 20200229, since that is the first time stamp for which all 5 students are acquainted (on the 29th, person 0 is direct friends with 2 and 4, acquainted to 1 via 4, and acquainted to 3 via 2).
Example 2: Given num_students = 5 and friendships = [{20200304, 1, 4},
{20200307, 0, 2}, {20200306, 3, 4}], you would return -1. In this example, person 0 and person 2 are in a separate friend group and are never acquainted with 1, 3, or 4.
Complexity: O(n log(n)) time, O(log(n) + s) auxiliary space, where n represents the number of logs in the vector, and s represents the number of students.
Implementation: Implement your solution on the back of this page. You may use anything from the
STL. Line limit: 30 lines of code.
Hint: You may want to use additional helper functions to solve this problem.
Implement your solution to "Social Networking" below:
int earliest_acquaintance(vector &friendships, int num_students) {
14. Adding Parentheses to Balance String
You are given a string str that consists of the characters '(' and ')' . Write a function that returns the minimum number of parentheses (either '(' or ')') that need to be added to the string so that the resulting string is balanced.
Example 1: Given the input string "())", you would return 1, since only 1 new parenthesis needs to be added to balance this string (adding '(' at the beginning).
Example 2: Given the input string "()))((", you would return 4, since a minimum of 4 new parentheses are needed to balance the string: "() () ()(())").
Complexity: O(n) time, O(1) auxiliary space, where n is the length of the string.
Implementation: Implement your solution in the space below. You may use anything from the STL.
Line limit: 15 lines of code.
int min_add_to_make_string_valid(string str) {