[CC150] Chapter 2 Linked Lists

2.1 Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?

Related problems: Remove Duplicate from Sorted List and Remove Duplicate from Sorted List II.

Following code defines a class LinkedList, which provides several methods:
CreateList: create a linked list from a given vector of integers
PrintList: print out the linked list for debugging
removeDuplicates: remove duplicates using a hash set
removeDupNoBuffer: remove duplicates without buffer (O(n^2) in time)
2.2 Implement an algorithm to find the kth to last element of a singly linked list.

 This problem is in leetcode as Remove Nth Node From End of List.

2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

 The only way is to copy the next node to the current node, and then delete the next node. If the node to be deleted is the last one, you cannot delete it. Probably we could change the value to a specific value (mark the node as unused).
2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

 This problem is in leetcode as Partition List.

2.5 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
FOLLOWUP:
Suppose the digits are stored in forward order. Repeat the above problem.

 This problem is in leetcode as Add Two Numbers. The follow up is essentially the same, although the implementation details change.

2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.

 This problem is in leetcode as Linked List Cycle II. Related problem: Linked List Cycle.

2.7 Implement a function to check if a linked list is a palindrome.

Using stack is straightforward. Other solutions include recursion and reverse the linked list.
Note that if the linked list contains odd numbers, the middle one should be ignored.

Comments

Post a Comment

Popular posts from this blog

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted array can only be the gap between
Read more

[ITint5] Maximum Subarray for a Circular Array

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this.
Read more

[CC150] Chapter 8 Object-Oriented Design

8.1 Design the data structure for a generic deck of cards. Explain how you would subclass the data structures to implement blackjack. Following codes implement blackjack. Note that syntax highlighter automatically changes some upper case letters to lower case.   8.2 Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can't handle the call, he or she must escalate the call to a manager. If the manager is not free or not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first available employee. 8.3 Design a musical jukebox using object-oriented principles. 8.4 Design a parking lot using object-oriented principles. 8.5 Design the data structures for an online book reader system. 8.6 Implement a ji
Read more