Dictionary autoarranging?

Question

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return None
        start = head
        prev = head.val
        a = {prev:1}
        #o = [prev]
        head = head.next
        while head != None:
            if head.val == prev:
                a[prev] += 1
            else:
                prev = head.val
                a[prev] = 1
                #o.append(prev)
            head = head.next
        b = ListNode(0)
        ans = b
        for i in a: # can use for i in o
            if a[i] == 1:
                c = ListNode(i)
                b.next = c
                b = b.next
        return ans.next

I am trying to remove duplicate items from a sorted linked list, eg.[1,2,3,3,4,4,5,6,6,6] -> [1,2,5]. Can someone walk through the code and tell me what will be the final value of a is for the linked list 2->1->None. It should be {2:1, 1:1} but answer comes out to be {1:1, 2:1}...why?

Don't make needless classes. Solution is a totally useless class. — juanpa.arrivillaga, Sep 26 '17 at 19:47
That was the format of the solution to be submitted on a website, ignore that. — Nikhil Ranjan, Sep 26 '17 at 19:49
Looks like some of that silly automated tests some companies use for hiring programmers. — Paulo Scardine, Sep 26 '17 at 19:51
Do you only want to remove adjacent duplicates? Is the linked list sorted prior to the removal of duplicates? What do you expect in the case of `[1, 2, 1]`? — Zach Gates, Sep 26 '17 at 19:56
So the question boils down to this: given a list `[1,2,3,3,4,4,5,6,6,6]` return another list with just the unique elements. Is this correct? — Paulo Scardine, Sep 26 '17 at 19:56
No no, you don't understand. It isn't our job to *ignore extraneous stuff*, it is *your job* to provide a [mcve] — juanpa.arrivillaga, Sep 26 '17 at 20:01
But, fundamentally, your question: "{2:1,1:1} but answer comes out to be {1:1, 2:1}" doesn'tmake any sense: **those are equivalent dictionaries**. Python `dict` is *unordered*. — juanpa.arrivillaga, Sep 26 '17 at 20:14

score 2 · Answer 1 · answered Sep 26 '17 at 20:17

2

dict object doesn't remember the order of elements which are added to the dictionary. If you want to preserve the ordering of the elements you can use OrderedDict.

answered Sep 26 '17 at 20:17

Alireza Mika

71
1
4

Thanks, this is what I was searching for. – Nikhil Ranjan Sep 26 '17 at 20:22

score 1 · Answer 2 · answered Sep 26 '17 at 20:04

1

O(N) option using groupby

>>> from itertools import groupby
>>> [k for k,g in groupby([1,2,3,3,4,4,5,6,6,6]) if len(list(g)) == 1]
[1, 2, 5]

answered Sep 26 '17 at 20:04

Luka Rahne

10,336
3
34
56

1

that requires the list to be sorted, though – Jean-François Fabre Sep 26 '17 at 20:06
Sure, but if I understand question, it is precondition. – Luka Rahne Sep 27 '17 at 05:58

a_guest · Answer 3 · 2017-09-26T19:56:38.257

0

Try the following:

>>> l = [1,2,3,3,4,4,5,6,6,6]
>>> [i for i in l if l.count(i) == 1]

This preserves the order of items in l.

edited Sep 26 '17 at 19:56

answered Sep 26 '17 at 19:51

a_guest

34,165
12
64
118

2

That's O(N^2). I'm trying to solve it in linear time. – Nikhil Ranjan Sep 26 '17 at 19:53
1

If you are concerned about performance then you need to be more specific about your situation, e.g. if the items in the list are always sorted, etc. – a_guest Sep 26 '17 at 19:58
@NikhilRanjan people are trying to help here. Why should they have patience with you if you are not willing to do the same for them? – Paulo Scardine Sep 26 '17 at 20:03
1

Looks like you think it is everybody's fault they can't guess what you want from your awesome question. – Paulo Scardine Sep 26 '17 at 20:14

SwiftsNamesake · Answer 4 · 2017-09-26T21:50:06.650

This answer assumes that all you want to do is to create another list, only keeping the values that occur once.

One way of doing it would be to use groupby from itertools and then filter based on the length of each group.

# Assuming 's' holds our list
[i for i,k in itertools.groupby(s) if len(list(k)) == 1]

EDIT Reading your question again, it seems this solution might not work, unless the linked list type you're using conforms to the iterator protocol. At any rate, it certainly won't produce a list as output, although you could replace the list comprehension with a generator expression and build a linked list from that.

It is hard to say what the OP wants: "autoarranging dict" is a bit vague. — Paulo Scardine, Sep 26 '17 at 20:10

Zach Gates · Answer 5 · 2017-09-26T20:55:59.047

Here's an approach in O(n) time (in Python 3), regardless of whether the list is sorted.

>>> lst = [1, 2, 3, 3, 4, 4, 5, 6, 6, 6]
>>> unique = {}
>>> for item in lst:
...     if item in unique:
...         unique[item] += 1
...     else:
...         unique[item] = 1
... 
>>> [k for k, v in unique.items() if v == 1]
[1, 2, 5]

The statement for item in lst: ... is O(n).
- The expression item in unique is O(1).
- The statement unique[item] = 1 is O(1), and so is unique[item] += 1.
The expression [k for k, v in unique.items() if v == 1] is O(n).

So, calculating the time complexity of the for statement:

O(n) * (O(1) + max(O(1), O(1)))
O(n) * (O(1) + O(1))
O(n) * O(1)
O(n)

Add that to the time complexity of the list comprehension, and you have O(n) + O(n), which is O(2n). Drop the constant, and you have O(n).

Dictionary autoarranging?

5 Answers5