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: "Pythagorean Triples
You are given a positive integer $N.
Write a script to print all Pythagorean Triples containing $N as a
member. Print -1 if it can't be a member of any. i
Triples with the same set of elements are considered the same, i.e. if
your script has already printed (3, 4, 5), (4, 3, 5) should not be
printed.
The famous Pythagorean theorem states that in a right angle triangle,
the length of the two shorter sides and the length of the longest
side are related by a2+b2 = c2.
A Pythagorean triple refers to the triple of three integers whose lengths
can compose a right-angled triangle.
Example
Input: $N = 5
Output:
(3, 4, 5)
(5, 12, 13)
Input: $N = 13
Output:
(5, 12, 13)
(13, 84, 85)
Input: $N = 1
Output:
-1
"
My notes: the tricky part here is knowing how to generate all Pythagorean
triples that MIGHT contain $N, i.e. when to stop generating triples..
Task 2: "Binary Tree Diameter
You are given binary tree as below:
1
/ \
2 5
/ \ / \
3 4 6 7
/ \
8 10
/
9
Write a script to find the diameter of the given binary tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn't have to pass through the root.
For the above given binary tree, possible diameters (6) are:
3, 2, 1, 5, 7, 8, 9
or
4, 2, 1, 5, 7, 8, 9
UPDATE (2021-08-10 17:00:00 BST): Jorg Sommrey corrected the example.
The length of a path is the number of its edges, not the number of the vertices it connects. So the diameter should be 6, not 7.
"
My notes: Looks quite tricky. We can use generate and test - if we can
generate all paths, then we could do a "max" test. Also, how to represent
the binary tree? let's hard-code it for now.
|
