You are given several independent coding tasks. Implement each as described.
A) Print a root-to-target path with column indentation (binary tree)
Given a binary tree where each node has val, left, and right, and a target value t that exists in the tree:
-
Find the path from the root to the node with value
t
.
-
Print each node on that path on its own line.
-
Indentation rule: treat the root as being at column
0
. For each step:
-
going to a left child decreases the column by
1
-
going to a right child increases the column by
1
When printing the path, prefix each node’s value with spaces so that nodes appear aligned by their column. (For example, a node that is one column to the right of another should have one more leading space.)
Clarification: you may shift all columns by a constant so the leftmost printed node has 0 leading spaces.
B) Add two decimal numbers represented as strings
Given two strings a and b representing non-negative decimal numbers (each may or may not contain a decimal point), return their sum as a string.
Constraints / rules:
-
You may not convert the whole string to an integer/float using built-ins like
int()
,
float()
,
Decimal
, etc.
-
Perform digit-wise addition.
-
The output should not contain unnecessary trailing zeros in the fractional part.
-
Example:
"12.340" + "0.660" -> "13"
(not
"13.000"
)
-
Example:
"1.2300" + "2" -> "3.23"
-
Do not output a trailing decimal point (e.g., output
"3"
, not
"3."
).
C) Find values within a range in a sorted array
Given a sorted integer array nums (ascending) and two integers L and R, return all values in nums that fall within the inclusive range [L, R].
Requirements:
-
Use the sorted property to do better than scanning the entire array (e.g., via binary search to find boundaries).
D) Evaluate an expression with + and *
Given a string expression containing non-negative integers, +, *, and optional spaces (no parentheses), compute the result.
Rules:
-
*
has higher precedence than
+
.
-
Example:
"2+3*4+5" -> 19
.
E) Shortest path in a graph with increasing constraints
You are given an unweighted graph representing intersections and roads.
-
Compute the shortest path between
start
and
end
(return the actual path, not just distance).
-
Variant: roads may be one-way (directed). Compute the shortest path respecting direction.
-
Variant: some nodes are locked “doors” that require keys. Keys are picked up by visiting certain nodes, and each door requires a specific key id.
-
You may traverse a door node only if you have already collected its required key.
-
Find the shortest valid path from
start
to
end
.
Provide time/space complexity for each part.