Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Zigzag Traversal

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 years ago

In the Reverse Level Order Traversal problem, we still printed each level left-to-right. It only changed the top-to-bottom order to bottom-to-top.

A

Anonymous

· 3 years ago

Traceback (most recent call last): File "/box/Parsers.py", line 69, in parse return json.loads(line) File "/usr/lib/python3.7/json/init.py", line 348, in loads return _default_decoder.decode(s) File "/usr/lib/python3.7/json/decoder.py", line 337, in decode obj, end = self.raw_decode(s, idx=_w(s, 0).end()) File "/usr/lib/python3.7/json/decoder.py", line 355, in raw_decode raise JSONDecodeError("Expecting value", s, err.value) from None json.decoder.JSONDecodeError: Expecting value: line 1 column 2 (char 1)

Show 2 replies
A

Anonymous

· 3 years ago

Requirement is move right to left but did not happen for 1,7

Current output :

Zigzag traversal: [[12], [1, 7], [9, 10, 5], [17, 20]]

Instead of

Zigzag traversal: [[12], [7,1], [9, 10, 5], [17, 20]]

A

Anonymous

· 4 years ago

For the python solution, at the end of each level we run "result.append(list(currentLevel))" to convert the deque into a list. Wouldn't this effectively make the time complexity O(n^2) in the worst case since we have to copy the elements of the deque into a list?

Similar to the DFS problem "All Paths for a Sum" where the time complexity came out to O(n^2) or O(nlogn) unless I am missing something.

Show 1 reply
A

Anonymous

· 5 years ago

Or we could have a deque for currentLevel instead of a vector and alternate from push_back to push_front.

Show 2 replies

Reading Progress

0%

Vote for new content