1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
Task 1: "Odd Number
You are given an array of positive integers, such that all the numbers
appear even number of times except one number.
Write a script to find that integer.
Example 1
Input: @N = (2, 5, 4, 4, 5, 5, 2)
Output: 5
as it appears 3 times in the array where as all other numbers 2 and
4 appears exactly twice.
Example 2
Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4)
Output: 4
"
My notes: easy, let's use a frequency hash.
Task 2: "Binary Search Tree
You are given a tree.
Write a script to find out if the given tree is Binary Search Tree (BST).
According to wikipedia, the definition of BST:
A binary search tree is a rooted binary tree, whose internal nodes
each store a key (and optionally, an associated value), and each has
two distinguished sub-trees, commonly denoted left and right. The tree
additionally satisfies the binary search property: the key in each node
is greater than or equal to any key stored in the left sub-tree, and less
than or equal to any key stored in the right sub-tree. The leaves (final
nodes) of the tree contain no key and have no structure to distinguish
them from one another.
Example 1
Input:
8
/ \
5 9
/ \
4 6
Output: 1 as the given tree is a BST.
Example 2
Input:
5
/ \
4 7
/ \
3 6
Output: 0 as the given tree is a not BST.
"
My notes: yet another tree question, the hardest part is to read the tree
from input, so let's reuse some tree reading logic from an earlier challenge..
To determine whether a given tree is a BST, we need to pass around a list of
constraints, where each constraint is either of the form "<=N" or ">=N", and
apply those constraints to each value we find in the tree.
I also tried a second variation (ch-2-with-constraintfunctions.pl) where the
list of textual constraints was replaced by an on-the-fly constructed constraint
function. But that wasn't as clear, even though it was a few lines shorter,
and doesn't offer as good debugging support.
|
