Grokking Oracle Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Athanasios Petsas

· 4 years ago

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

Show 3 replies
R

Richard Yuan

· 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
V

venkatlearning11

· 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

Adeel Qureshi

· 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
Bruno Ely

Bruno Ely

· 2 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.

E

eesahk

· a year ago

Can we just do the regular BFS level by level and then reverse at the end of each level?

frontier = deque()
frontier.append(root)
visited = set()
level = 0
while frontier:
    next_frontier = deque()
    curr_level = []
    for curr_node in frontier:
        visited.add(curr_node)
        curr_level.append(curr_node.val)
        if curr_node.left and curr_node.left not in visited:
            next_frontier.append(curr_node.left)
        if curr_node.right and curr_node.right not in visited:
            next_frontier.append(curr_node.right)
      
    if not level % 2 == 0:
		    curr_level = curr_level[::-1]
    result.append(curr_level)
    frontier = next_frontier
    level += 1