algorithms/src/interview/build-tree/with-replies-sort/solution.test.ts at 23ee3743d5fb5f2171dfd92744d94270c6936f60 · TheGeniusOfEternity/algorithms · GitHub

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import { buildTree } from './solution';

describe('Build Tree: Sorted Replies (numeric)', () => {
  test('#1 Should sort children numerically: 1.2 before 1.10', () => {
    const messages = [
      { message: 'Root', pass: '1' },
      { message: 'Child 10', pass: '1.10' },
      { message: 'Child 2', pass: '1.2' },
    ];
    const result = buildTree(messages);
    expect(result[0].replies?.map((r) => r.message)).toEqual([
      'Child 2',
      'Child 10',
    ]);
  });

  test('#2 Should sort children on multiple levels', () => {
    const messages = [
      { message: 'Root', pass: '1' },
      { message: 'Child 10', pass: '1.10' },
      { message: 'Child 2', pass: '1.2' },
      { message: 'Child 1', pass: '1.1' },
      { message: 'Grandchild 10', pass: '1.1.10' },
      { message: 'Grandchild 2', pass: '1.1.2' },
    ];
    const result = buildTree(messages);
    const root = result[0];
    expect(root.replies?.map((r) => r.message)).toEqual([
      'Child 1',
      'Child 2',
      'Child 10',
    ]);
    const rootReplies = root.replies ?? [];
    expect(rootReplies[0].replies?.map((r) => r.message)).toEqual([
      'Grandchild 2',
      'Grandchild 10',
    ]);
  });

  test('#3 Should sort children when children have different depths', () => {
    const messages = [
      { message: 'Root', pass: '1' },
      { message: 'A', pass: '1.2' },
      { message: 'B', pass: '1.10' },
      { message: 'C', pass: '1.1' },
      { message: 'D', pass: '1.1.1' },
      { message: 'E', pass: '1.1.10' },
      { message: 'F', pass: '1.1.2' },
    ];
    const result = buildTree(messages);
    expect(result[0].replies?.map((r) => r.message)).toEqual(['C', 'A', 'B']);
    expect((result[0].replies ?? [])[0].replies?.map((r) => r.message)).toEqual(
      ['D', 'F', 'E'],
    );
  });

  test('#4 Should not sort roots (preserve original order)', () => {
    const messages = [
      { message: 'Root2', pass: '2' },
      { message: 'Root1', pass: '1' },
      { message: 'Child 10', pass: '1.10' },
      { message: 'Child 2', pass: '1.2' },
    ];
    const result = buildTree(messages);
    expect(result.map((r) => r.message)).toEqual(['Root2', 'Root1']);
    const root1 = result.find((r) => r.message === 'Root1');
    expect(root1?.replies?.map((r) => r.message)).toEqual([
      'Child 2',
      'Child 10',
    ]);
  });

  test('#5 Should sort children even if parent appears after children', () => {
    const messages = [
      { message: 'Child 10', pass: '1.10' },
      { message: 'Child 2', pass: '1.2' },
      { message: 'Root', pass: '1' },
    ];
    const result = buildTree(messages);
    expect(result[0].replies?.map((r) => r.message)).toEqual([
      'Child 2',
      'Child 10',
    ]);
  });

  test('#6 Should handle numeric sorting with more than two digits', () => {
    const messages = [
      { message: 'Root', pass: '1' },
      { message: 'Child 2', pass: '1.2' },
      { message: 'Child 10', pass: '1.10' },
      { message: 'Child 1', pass: '1.1' },
      { message: 'Child 100', pass: '1.100' },
    ];
    const result = buildTree(messages);
    expect(result[0].replies?.map((r) => r.message)).toEqual([
      'Child 1',
      'Child 2',
      'Child 10',
      'Child 100',
    ]);
  });
});