What is wrong even if I am checking bottom is not None

Question

Hi

I am trying to flatten a LinkedList . It has next and bottom pointers. Sorted list should have bottom pointer set.

Below is my trial:
https://www.sololearn.com/en/compiler-playground/cL5Kan9S1LDZ

Why it results in runtime error? It should not compare Node class as I am doing heappush with int data only if bottom pointer is not null. What is missing here?

Answer 1

curiously, doing the opposite works...
if not cur.bottom:
heapq.heappush(pq, (cur.bottom.data, cur.bottom))

https://sololearn.com/compiler-playground/cEii3MLS49KI/?ref=app

Answer 2

Thanks..!

I solved this issue here:

Class __Lt__ method was needed as int value was same for two objects and hence it was throwing error.
https://sololearn.com/compiler-playground/c93Tz8I87eXF/?ref=app

Answer 3

Bob_Li agree about value assignment. Purpose of the exercise is to solve the issue of what I was facing,so had not focused on this. But yeah, it should have been better.

For __lt__, in this excersize, it does not matter. Even if you will return true, result will not change. Attribute comparison also don't change result. But to be honest , attribute comparison does not make sense in this case as class comparison will hit only if both attribute are same

Answer 4

Ketan Lalcheta
python's constructor can be multi modal

https://sololearn.com/compiler-playground/cGW8Ncu29GI6/?ref=app

The result will change if your values are not ordered. Try changing one Node data to an out of sequence value. It's placement in the solution will change.

I still feel simply always returning True or False for __lt__ is hard to reason about. For custom classes, you are supposed to define which attribute that will be used the basis for value comparison.

Answer 5

Internally all lists are sorted. In other words , input is guaranteed that all values for Next pointer are sorted 👍

Like if root.next.data is 10 then it is guaranteed that root.next.next.data will always be more than 10

internally all values are also sorted within the bottom pointers. so if you maintain this constraints , then only solution will work.

This is very famous problem of flattening sorted list and true or false from class lt method solving the need.

If you are making it very generic solution, then please let me know test case and output expected from code. I hope your large value does not violate the constraints I shared about sorted value

Answer 6

Ketan Lalcheta
good to know you've solved it.
one thing that's bothering me is the confusing way the values are being assigned. A long string of attributes is hard to read.

😅
root.next.next.bottom.bottom.bottom.bottom.bottom.bottom.bottom.bottom = Node(27)
🤔❓

maybe a better initializer or appending method is needed?

also, knowing that an __lt__ override is needed for ordering, I can't quite understand the logic for return False. wouldn't it be more sensible to provide an attribute comparison?