Preventing backtracking

Prolog will automatically backtrack if this is necessary for satisfying a goal.

Now, consider a double-step function. The relation between X and Y can be specified by three rules:

Rule 1: if X < 3 then Y = 0

Rule 2: if 3 <= X and X < 6 then Y = 2

Rule 3: if 6 <= X then Y = 3

This can be written in Prolog as a binary relation f(X, Y) as follows:

1
2
3

f(X, 0) :- X < 3.         % Rule 1
f(X, 2) : 3 =< X, X < 6.  % Rule 2
f(X, 3) : 6 =< X.         % Rule 3

This program assumes that before f(X, Y) is executed X is already instantiated to a number as this is required by the comparison operators.

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

1
2
3
4
5
6
7
8
9

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Example

1
2

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

Example

given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Example

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

Note

You may assume that duplicates do not exist in the tree.

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example

1
2

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, ..., pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Examples

Example 1:

1
2

Input: [3,4,5,1,2] 
Output: 1

Example 2:

1
2

Input: [4,5,6,7,0,1,2]
Output: 0

Problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example

1
2
3
4
5
6
7

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Problem

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

We should return its max depth, which is 3.