This problem appears in both Cracking the Cracking Interview and Leetcode. The problem is this: given a linked list, delete duplicates such that each number appears only once.
For example:
input: 1 -> 1 -> 2
output: 1 -> 2
Here's a hint. Use a hashset to store your unique numbers in, and if the number exists already in the hashset, set the pointer of the previous node equal to the next node of current node.
class Node:
self.data = data
self.next = None
class Solution:
def removeDuplicates(self, head:Node) -> Node:
hashSet = set()
node = head
prev = None
while node:
if node.data not in hashSet:
hashSet.add(node.data)
prev = node
else:
prev.next = node.next
node = node.next
return head
Top comments (9)
Apologies as I’m usually really bad at these Leetcode challenges, but where is traversal of the linked list happening? Is the while loop implicitly setting node equal to node.next? Thanks for the article! Always great to have these solution in the tool box!
Oops, I forgot a line! Thanks for noticing! Traversal happens when node = node.next, after the if and else statements! Sorry for forgetting haha.
Aww! Great! I was like another magical python thing 😂😂😂 once again thanks for the article!
The interesting question would be how to solve that problem without using a hashset.
EDIT: To clarify, the original question really just tests for knowledge: Do you know what a hash-set is and can you identify its benefits in a very simple example. Removing the hashset from the toolbox suddenly confronts you with a more uncomfortable situation where there is no clear answer. By removing the "universal" right answer, you need more information, so this tests communication skills, intuition for spotting problematic edge-cases, etc.
Map, set or array can be used. But when using array we must insert and search efficiently like Set to minimize the complexity.
My idea is start from head and go to tail. When processing nodes, put some a list and
for each next node, search that it is exist or not in this list, if exists delete current node from list. Else insert this to list.
A set can be implemented as a map to boolean values, so that should be forbidden as well, otherwise the question doesn't become more interesting.
The array solution is where things become complicated: If you have a very long list of few numbers (say 10 million numbers all between 1 and 1000), you could allocate an array of 1000 boolean values to serve as an improvised int to bool map.
Another followup question could then be "How can we optimize that solution for memory and what would be the downsides of this?" and you've now covered everything from very high-level concepts to bit-level optimization techniques without doing anything too difficult or specific.
However, if it's a list of 100 numbers of any size that fits a 64bit integer, saving them in a sorted list for binary search would be a good solution.
I'd recommend adding some space and time analysis to the article since you can expect questions about this during your interviews.
Also, how would you solve it without a hash set? There's an obvious brute force solution with O(n^2) time complexity and O(1) space complexity.
PS: I liked your clean code!
Can anyone give me leetcode link of this problem ?
got it,
-> leetcode.com/problems/remove-dupli...
-> leetcode.com/problems/remove-dupli...