Gradescope Coding Challenges
Add class using entry code:9ZYK52
Gradescope expects solutions in C++
01. Implementing Queue using Stacks
Difficulty Level: Easy
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue (you may assume x is an int).
pop() -- Removes the element from in front of queue and returns it.
peek() -- Get the front element without removing it from the queue.
size() -- Return the number of elements in the queue.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.size(); // returns 2
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes: You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). You may assume the queue stores integers. Submission: Submit a single file, your class should be implemented within its definition:
class MyQueue { public: /** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
}
/** Get the front element. */
int peek() {
}
/** Returns whether the queue is empty. */
bool empty() {
}
};
02. Valid Parentheses
Difficulty Level: Easy
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1:Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Submission: Submit a single-file implementation of a class named Solution with public member function: *bool isValid(std::string s)* You may have additional helper functions if you like, isValid is required.
03. Bubble Sort
Difficulty Level: Easy
Check out https://www.hackerrank.com/topics/bubble-sort to learn more about bubble sort. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview. Also on wikipedia: https://en.wikipedia.org/wiki/Bubble_sort Consider the following version of Bubble Sort:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
// Swap adjacent elements if they are in decreasing order
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
Given an array of integers, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following three lines:
1. Array is sorted in numSwaps swaps, where numSwaps is the number of swaps that took place.
2. First Element: firstElement, where firstElement is the first element in the sorted array.
3. Last Element: lastElement, where lastElement is the last element in the sorted array.
Hint: To complete this challenge, you must add a variable that keeps a running tally of all swaps that occur during execution.
For example, given a worst-case but small array to sort: a = [6, 4, 1] we go through the following steps:
swap a
0 [6,4,1]
1 [4,6,1]
2 [4,1,6]
3 [1,4,6]
It took 3 swaps to sort the array. Output would be
Array is sorted in 3 swaps.
First Element: 1
Last Element: 6
Submission: Submit a single-file implementation of a class named Solution with public member function: void countSwaps(std::vector) countSwaps should print the three required lines to standard output (std::cout), then return. You may have additional helper functions if you like, countSwaps is required.
Output Format countSwaps must print the following three lines of output:
Array is sorted in numSwaps swaps., where numSwaps is the number of swaps that took place.
First Element: firstElement, where firstElement is the first element in the sorted array.
Last Element: lastElement, where lastElement is the last element in the sorted array.
Sample Input 0
3
1 2 3
Sample Output 0
Array is sorted in 0 swaps.
First Element: 1
Last Element: 3
Explanation 0
The array is already sorted, so 0 swaps take place and we print the necessary three lines of output shown above.
Sample Input 1
3
3 2 1
Sample Output 1
Array is sorted in 3 swaps.
First Element: 1
Last Element: 3
Explanation 1 The array is not sorted, and its initial values are: {3, 2, 1}. The following 3 swaps take place:
{3, 2, 1} -> {2, 3, 1}
{2, 3, 1} -> {2, 1, 3}
{2, 1, 3} -> {1, 2, 3}
At this point the array is sorted and we print the necessary three lines of output shown above.
04. Course Schedule [NM]
Difficulty Level: Medium
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.
Submission: Submit a single-file implementation of a class named Solution with public member function: bool canFinish(int numCourses, std::vector < std::pair < int, int >>& prerequisites). You may have additional helper functions if you like, canFinish is required.
05. String to Integer (atoi)
Difficulty Level: Medium
Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned. Note: •Only the space character ' ' is considered as whitespace character. •Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned. Submission: Submit a single-file implementation of a class named Solution with public member function:int myAtoi(std::string str) You may have additional helper functions if you like, myAtoi is required.
Example 1:
Input: "42"
Output: 42
Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign. Then take as many numerical digits as possible, which gets 42.
Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer. Therefore INT_MIN (−231) is returned.
06.E Two Sums
Difficulty Level: Easy
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Submission: Submit a single-file implementation of a class named Solution with public member function:
std::vector< int> twoSum(std::vector< int>& nums, int target) which returns a vector containing the two indices. You may have additional helper functions if you like, twoSum is required.
07.H Median of Two Sorted Arrays
Difficulty Level: Hard
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Submission: Submit a single-file implementation of a class named Solution with public member function:
double findMedianOfSortedArrays(std::vector< int>& nums1, std::vector< int>& nums2)
You may have additional helper functions if you like, findMedianOfSortedArrays is required.
08.M Sort List [NM]
Difficulty Level: Medium Sort a linked list in O(n log n) time using constant space complexity. Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
Submission:
Submit a single-file including the following struct:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
and the implementation of a class named Solution with public member function:
ListNode* sortList(ListNode* head) which returns a pointer to the sorted list and takes a pointer to the first node as parameter.
You may have additional helper functions if you like, sortList is required.
09.E Merge Two Sorted Lists
Difficulty Level: Easy
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Submission: Submit a single-file including the following struct:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
and the implementation of a class named Solution with public member function:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) which returns a pointer to the merged list and takes pointers to the two lists as parameter.
You may have additional helper functions if you like, mergeTwoLists is required.
10.M Add Two Numbers
Difficulty Level: Medium
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Submission: Submit a single-file including the following struct:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
and the implementation of a class named Solution with public member function:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) which returns a pointer to the list representing the sum and takes pointers to the two number-lists as parameters
You may have additional helper functions if you like, addTwoNumbers is required.
11.E Maximum Subarray
Difficulty Level: Easy
Maximum Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6
Submission: Submit a single-file including the implementation of a class named Solution with public member function.int maxSubArray(std::vector< int>& nums)
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
12.H Reverse Pairs
Difficulty Level: Hard Reverse Pairs Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j]. You need to return the number of important reverse pairs in the given array. Example 1:
Input: [1,3,2,3,1]
Output: 2
Example 2:
Input: [2,4,3,5,1]
Output: 3
Note:
1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
int reversePairs(std::vector< int >& nums)
You may have additional helper functions if you like, reversePairs is required.
13.E Find the Town Judge
Difficulty Level: Easy
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts the town judge. 3. There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1. Example 1:
Input: N = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: N = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Example 4:
Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Note:
1. 1 <= N <= 1000
2. trust.length <= 10000
3. trust[i] are all different
4. trust[i][0] != trust[i][1]
5. 1 <= trust[i][0], trust[i][1] <= N
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
int findJudge(int N, std::vector< std:: vector< int>>& trust)
You may have additional helper functions if you like, findJudge is required.
14.M Rotate Image
Difficulty Level: Medium You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9, 11],
[ 2, 4, 8, 10],
[13, 3, 6, 7],
[15, 14, 12, 16]
],
rotate the input matrix in-place such that it becomes:
[
[15, 13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7, 10, 11]
]
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
void rotate(std::vector < std::vector < int> >& matrix) postcondition: rotate outputs the rotated matrix to the standard output (cout) in the form:
"[15,13,2,5]\n[14,3,4,1]\n[12,6,8,9]\n[16,7,10,11]"
You may have additional helper functions if you like, rotate is required.
15.M Longest Substring Without Repeating Characters
Difficulty Level: Medium Given a string, find the length of the longest substring without repeating characters. Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
int lengthOfLongestSubstring(std::string s)
You may have additional helper functions if you like, lengthOfLongestSubstring is required.
16.M Subsets
Difficulty Level: Medium Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets and must contain the empty set. Subsets may appear in any order. Example:
Input: nums = [1,2,3]
Return:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
std::vector< std::vector< int >> subsets(std::vector< int>& nums)
You may have additional helper functions if you like, subsets() is required.
17.M Word Search
Difficulty Level: Medium Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
* Given word = **"ABCCED"**, return **true**.
* Given word = "**SEE**", return **true**.
* Given word = "**ABCB**", return **false**.
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
bool exists(std::vector< std::vector< char>>& board, std::string word)
You may have additional helper functions if you like, exists() is required.
18.H Regular Expression Matching
Difficulty Level: Hard Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
•s could be empty and contains only lowercase letters a-z.
•p could be empty and contains only lowercase letters a-z, and characters '.' or '*'.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
Submission: Submit a single-file including the implementation of a class named Solution with public member function:
bool isMatch(std::string s, std::string p)
You may have additional helper functions if you like, isMatch() is required.