CareerCup

how to understand "multi-player" ?

sorry, now I get it.

To calculate cube root of 900000000 it takes 30 steps.
To calculate cube root of 999990000 it hangs forever.

task is written quite unclear.
As I understand it, the implementation could be the following (c#).
No parsing logic, only data structure and string representation.

using System;
using System.Collections.Generic;

namespace TreeDataStructure {
    
    public class TreeNode {

        public Operation? Operation { get;  }
        public string Operand { get; }
        public List<TreeNode> Children { get; }
        public TreeNode Parent { get; private set; }

        public TreeNode( Operation? operation, string operand = null ){
            Operation = operation;
            Operand = operand;
            Children = new List<TreeNode>();
            Parent = null;
        }

        public void AddChild( TreeNode child ) {
            Children.Add( child );
            child.Parent = this;
        }

        public void AddChildren( params TreeNode[] children ) {
             foreach ( var child in children ) {
                Children.Add(child);
                child.Parent = this;
            }
        }
    }

    public static class TreePrinter {

        private static string _expression;

        public static string GetStringRepresentation( TreeNode anyNode ) {

            var startNode = _getStartNode( anyNode );
            _printTree( startNode );
            return _expression.TrimEnd(", ".ToCharArray());
        }

        private static TreeNode _getStartNode( TreeNode anyNode ) {

            if (anyNode.Parent == null) {
                return anyNode;
            }
            return _getStartNode( anyNode.Parent);
        }

        private static void _printTree( TreeNode startNode ) {

            if ( startNode.Operand == null ) {
                _expression += startNode.Operation + "(";
                
                for(int i = 0; i < startNode.Children.Count; i++ ) {
                    _printTree( startNode.Children[ i ] );
                    if ( i != startNode.Children.Count - 1 && startNode.Operation == null ) {
                        _expression += ", ";
                    }
                }
                _expression += "), ";
            }
            if (startNode.Operation == null) {
                _expression += startNode.Operand  + ", ";
            }
            _expression = _expression.Replace(", )", ")");
        }
    }

    public enum Operation{
        AND,
        OR,
        NOT
    }

    class Program {

        static void Main( string[] args ) {
//Test case
// ((name = "smith" OR name = "Johnes") AND age > 9) OR (age < 8 AND name != "Williams") OR ( Not(city = "New York") OR city = "London" )
// return representation:
// OR(AND(OR(name = "Smith", name = "Johnes"), age > 9), AND(age < 8, name != "Williams"), OR(NOT(city = "New York"), city = "London"))

            TreeNode node212 = new TreeNode(null, "name = \"Johnes\"");
            TreeNode node211 = new TreeNode(null, "name = \"Smith\"");
            TreeNode node21 = new TreeNode( Operation.OR );
            node21.AddChildren( node211, node212 );

            TreeNode node22 = new TreeNode(null, "age > 9");
            TreeNode node2= new TreeNode( Operation.AND );
            node2.AddChildren( node21, node22 );

            TreeNode node31 = new TreeNode(null, "age < 8");
            TreeNode node32 = new TreeNode(null, "name != \"Williams\"");
            TreeNode node3 = new TreeNode( Operation.AND );
            node3.AddChildren( node31, node32 );

            TreeNode node411 = new TreeNode(null, "city = \"New York\"");
            TreeNode node41 = new TreeNode( Operation.NOT );
            node41.AddChildren( node411 );

            TreeNode node42 = new TreeNode(null, "city = \"London\"");
            TreeNode node4 = new TreeNode( Operation.OR );
            node4.AddChildren( node41, node42 );

            TreeNode node1 = new TreeNode( Operation.OR );
            node1.AddChildren( node2, node3, node4 );

            Console.WriteLine(TreePrinter.GetStringRepresentation( node31 ) );

            Console.ReadLine();
        }
    }
}

how could it be O(1), while we have deal with at least N elements ?
O(1) is when we read 1 element by index from an array, or get 1 element by key from hash-table.

pretty simple:
1) get sum of elements of array,
2) get count of elements of array,
3) {1} / {2}.
O(n).

no, it is obvious that MAXLEN is a global variable and initialized in proper place.
You see, the code is just a separate function.

the error is in line:

if (str[j] == temp[i])

It should be:

if (str[j] == temp[0])

No, it is something different.
By empirical way I discovered the following first answers:
n = 1, answer = 1.
n = 2, answer = 5.
n = 3, answer = 11.
n = 4, answer = 33.
So, what rule could it be?

why in the example for "appletablet" "t" is a word, but for "thing" "t" is not a word ?

some correction: we take Fibonacci sequence as base, but we cannot use it as is, we should use some coefficient.
Below I provide the solution.

no, it is incorrect.
for n = 2 it gives 10, but it should be 5.
Also, for n = 3 it gives 17, but it should be 11.
(where n is that from 4*n).

it does not work.
for n = 2 it gives 4, but it should be 5.
Also, for n = 3 it gives 8, but it should be 11.
(where n is that from 4*n).

thanks!

Compilation error time: 0 memory: 0 signal:0

prog.cpp: In function 'int main()':
prog.cpp:7:30: warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]
char *chr_pointer = {"abcdef"};
^
prog.cpp:8:11: error: cannot convert 'char*' to 'int*' in initialization
int *a = chr_pointer;
^
prog.cpp:11:8: error: cannot convert 'char*' to 'int*' in assignment
a = (char *)a + 1;
^

c#.

variant 1.

char[] arr = new[]
            {
                'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't','u', 'v', 'w', 'x', 'y', 'z'
            };

            int pointer = 0;

            while ( pointer < arr.Length )
            {
                Console.Write($"{arr[pointer]} ");
                pointer++;
            }

variant 2.

string str = "abcdefghijklmnopqrstuvwxyz";

            int pointer = 0;

            while ( pointer < str.Length )
            {
                Console.Write($"{str[pointer]} ");
                pointer++;
            }

thanks for the discussion!

really, the solution doesn't work.
On the input array {2, 1, 3, 5, 4, 0} it returns {0, 1, 3, 5, 4, 0}, but the correct output is { 3,1, 5, 0, 4, 2 }.

yes, that is true, the program uses extra stack space in memory, but there are no restrictions in the initial task about this issue.
And I didn't understand: "moreover can u give the algo for what u wrote".

c# implementation.
O(n^2).

using System;

namespace NearestBiggerValue {

    class Program {

        private static int FindBigger( int[] arr, int i ) {

            int indexL = i;
            int indexR = i;
            int? rightVal = null;
            int? leftVal = null;

            while ( indexL >= 0 || indexR < arr.Length ) {

                indexR++;
                indexL--;

                if (indexR < arr.Length ) {
                    rightVal = arr[ indexR ];
                } else {
                    rightVal = null;
                }

                if ( indexL >= 0 ) {
                    leftVal = arr[ indexL ];
                } else {
                    leftVal = null;
                }

                if ( ( rightVal != null && rightVal > arr[ i ] ) || ( leftVal != null && leftVal > arr[ i ] ) ) {
                    break;
                }
            }

            if ( ( rightVal == null && leftVal == null) || ( rightVal <= arr[ i ] && leftVal <= arr[ i ] ) ) {
                return -1;
            }
            if ( rightVal != null && leftVal != null ) {
                return rightVal > leftVal ? indexR : indexL;
            }
            return rightVal == null ? indexL: indexR;
        }

        private static void Process( int[] arr ) {

            for ( int i = 0; i < arr.Length; i++ ) {

                int val = FindBigger( arr, i );

                string str = val == -1 ? -val + " (doesn't exist)" : val.ToString();

                Console.WriteLine($"For index {i} nearest bigger value is at index {str}");
            }
            Console.ReadLine();
        }

        static void Main( string[] args ) {

            int[] arr = new int[] { 77, 2, 15, 16, 5, 3, 19, 2, 0, -2, 77, 7, 77 };

            Process(arr);
        }
    }
}

Let's think.
How can it be n^2 ? And why will loop run n*n times ?
This program contains only 1 loop. As you know, 1 loop performs exactly N iterations, where N is the number of items in collection. So, the time complexity of 1 loop is O(n).
N*N times is true for nested loops, when 1 loop is outer one and the 2nd loop is inner one. Where do you see nested loops in the program? Nothing of that kind.
It is very easy to check the number of times of loop execution.
Do you see the incrementor there (i++), so if time complexity is O(n^2), then the value of "i" will be exactly n*n at the last iteration. In my program its value at the last iteration is exactly 6, which is N in my case (but not 36, which is N*N).
So, the time complexity is O(n).
This is absolutely definitely.
So, your statement is incorrect.

Second.
You write here the result of first 1st iteration = {3,1,3,5,4,0}.
This is not true.
Here is the full list of iterations' results:
1 - {2,1,3,5,4,2}
2 - {2,1,3,5,4,2}
3 - {2,1,3,0,4,2}
4 - {2,1,5,0,4,2}
5 - {2,1,5,0,4,2}
6 - {3,1,5,0,4,2}

So, you tested some other program, but not mine.

Then, what is it - "The result is incorrect after the 1st iteration" ??
This is bullshit.
Because the result of the algorithm must be verified only after the whole algorithm is finished. These are basics of computer science.

So: I observed all your restrictions, and created the solution with time complexity O(n). Your task is to wait until the algorithm finishes its work and gives you the output, then you can check the output with predefined correct value.
For input array { 2,1,3,5,4,0 } my solution gives output array {3,1,5,0,4,2}.
And it is absolutely correct.
The task is fulfilled.

this is a Fibonacci sequence task,
the answer is 34 if n = 4.
For the other values of n, we should take the respective value from Fibonacci sequence.

below I provide the solution without dynamical modifications of the initial array's size.

ok, here is the solution you wanted.
c# implementation.
All restrictions are observed. No additional data structures, no dynamical modifications of the initial array's size.
Time complexity O(n).

using System;

namespace ArrayTrick {

    class Program {

        static void Main(string[] args) {

            var arr = new[] { 2, 1, 3, 5, 4, 0 }; // output should be { 3, 1, 5, 0, 4, 2 }

            Process( arr );

            for ( int i = 0; i < arr.Length; i++ ) {
                Console.Write($"{arr[i]} ");
            }

            Console.ReadLine();
        }

        private static void Process( int[] arr, int i = 0 ) {
            int index = i;
            if (i < arr.Length ) {
                var val = arr[ arr[ i ] ];
                i++;
                Process( arr, i );
                arr[ index ] = val;
            }
        }
    }
}

the idea is the following:
at each iteration we dynamically increase the size of the array and write new values a[ a[ i ] ] to the end of that array.
After the cycle we just move the array head pointer to the middle of the array.
O(n).
But I suspect you will say, that it is not permitted to dynamically increase the size of the array, though there is no such prohibition in the initial task.

Thank you for answers,
really, the trick is to understand that the task is about Fibonacci sequence.

yes, great solution.

could you please write the task normally, it is impossible to understand it.

c# implementation.
Time complexity: O(n).
Running time of worst case (when all integers are positive) - 2*n,
Running time of best case (when all integers are negative) - n.
Running time average 1,5*n.

using System;
using System.Collections.Generic;

namespace ReversePositiveIntegers {

    static class Program {

        static private void ProcessArray( int[] arr ) {

            int i = 0;
            int startPos = -1;

            Stack<int> stack = new Stack<int>();

            while ( true ) {
                if ( arr[ i ] < 0 ) {
                    CheckAndReverse( arr, stack, ref startPos, i );
                } else {
                    stack.Push( arr[ i ] );
                }

                i++;

                try {
                    int nextIndex = arr[ i ];
                }
                catch (IndexOutOfRangeException) {
                    CheckAndReverse( arr, stack, ref startPos, i );
                    break;
                }
            }
        }

        static private void CheckAndReverse( int[] arr, Stack<int> stack, ref int startPos, int endPos ) {

            var length = endPos - startPos - 1;
            if ( length > 1 ) {
                int t = 0;
                while ( stack.Count > 0 ) {
                    arr[ startPos + 1 + t ] = stack.Pop();
                    t++;
                }
            }
            stack.Clear();
            startPos = endPos;
        }

        static void Main(string[] args) {

            int[] arr = new[] {-5, 100, 200, -2, 0, 1, 2, 3, 4, -6, -5, 10, 20, -2, 30, 40 };

            ProcessArray( arr );

            for ( int j = 0; j < arr.Length; j++ ) {
                Console.Write($"{arr[j]} ");
            }
            Console.ReadLine();
        }
    }
}

c# implementation.
Complexity: less than O(n*log n).
I use the merging part of MergeSort algorithm. (According to the task - all the arrays are sorted.)
As the complexity of the whole MergeSort algorithm is O(n*log n), so the solution is at least not worse, and even faster, due to the absence of sorting step.

using System;
using System.Collections.Generic;
using System.Threading;

namespace MergeOfSortedArrays {

    static class Program {

        private static int[] Merge( int[] arr1, int[] arr2, SortOrder sortOrder ) {

            if ( arr1 == null ) { return arr2; }
            if ( arr2 == null ) { return arr1; }

            int[] tail = null;

            if ( arr1.Length > 1 ) {
                tail = new int[arr1.Length - 1];    
            }
            
            if ( GetConditionWithSortOrder( arr1[ 0 ], arr2[ 0 ], sortOrder) ) {
                for ( int i = 0; i + 1 < arr1.Length; i++ ) {
                    tail[ i ] = arr1[ i + 1 ];
                }
                return Concat( arr1[ 0 ], Merge( tail, arr2, sortOrder) );
            }
            
            tail = null;
            if ( arr2.Length > 1 ) {
                tail = new int[arr2.Length - 1];
            }

            for ( int i = 0; i + 1 < arr2.Length; i++ ) {
                tail[i] = arr2[ i + 1 ];
            }
            return Concat( arr2[ 0 ], Merge( arr1, tail, sortOrder ) );            
        }

        private static bool GetConditionWithSortOrder( int i1, int i2, SortOrder sortOrder ) {
            return sortOrder.Equals(SortOrder.Desc) ? i1 > i2 : i1 < i2;
        }

        private static int[] Concat( int firstElm, int[] arr ) {
            
            var res = new int[ arr.Length + 1 ];
            res[ 0 ] = firstElm;

            for ( int i = 0; i < arr.Length; i++ ) {
                res[ i + 1 ] = arr[ i ];
            }
            return res;
        }

        static void Main(string[] args) {

            foreach ( var arr in GetResult() ) {
                for ( int i = 0; i < arr.Length; i++ ) {
                    Console.Write( $"{arr[i]} " );
                }
                Console.WriteLine($"{Environment.NewLine}-------------------------------");
            }
            Console.ReadLine();
        }

        private static IEnumerable<int[]> GetResult() {
                        
            var listOfArrays = new List<int[]> ();

            while ( listOfArrays.Count < 11 ) {

                Thread.Sleep( 1000 );

                var order = SortOrder.Asc;
                listOfArrays.Add( GetNewSortedArrayFromStream( order ) );
                
                int[] res = null;
                foreach ( var item in listOfArrays ) {
                    res = Merge( res, item, order );
                }

                yield return res;
            }
        }

        private static int[] GetNewSortedArrayFromStream( SortOrder order ) {

            Random rand = new Random();
            var startVal = rand.Next( 0, 101 );
            var step = rand.Next( 1, 20 );
            var length = rand.Next( 3, 10 );

            var arr = new int[ length ];
            for ( int i = 0; i < length; i++ ) {
                arr[ i ] = startVal + ( order.Equals( SortOrder.Asc ) ? i : -i ) * step;
            }
            return arr;
        }

    }

    public enum SortOrder {
        Asc,
        Desc
    }
}

c# implementation.
This is the emulation as much as I understand the task.
The emulation is actually in form of adding random float numbers to list in cycle.
Then I take the last K (or less, if total number of elements is less than K) numbers from the list, and calculate their average.

using System;
using System.Collections.Generic;
using System.Threading;

namespace MovingAverage {

    static class Program {

        static void Main(string[] args) {

            Console.WriteLine("Input the K value and hit <Enter>");
            foreach ( var item in GetEverage( int.Parse(Console.ReadLine()) ) ) {
                Console.WriteLine(item);
            }
        }

        private static readonly List<float> StreamOfFloats = new List<float>();

        private static IEnumerable<float> GetEverage( int K ) {

            const int limit = 100;
            var rand = new Random();

            while ( true ) {
                Thread.Sleep( 1000 );
                StreamOfFloats.Add( (float)rand.NextDouble() );
                if ( StreamOfFloats.Count > limit ) {
                    StreamOfFloats.RemoveAt( 0 );
                }
                float sum = 0;
                var cnt = StreamOfFloats.Count;
                for ( int i = cnt - 1; ( cnt >= K && i >= cnt - K ) || ( cnt < K && i >= 0 ) ; i-- ) {
                    sum += StreamOfFloats[ i ];
                }
                yield return sum / (StreamOfFloats.Count >= K ? K : StreamOfFloats.Count );
            }
        }
    }
}

I tried to run your code on ideone.com, and it said there was a mistake in 18 line (elif list_length % 2 == 1 and return_list[list_length >> 1)] == median:),
Maybe, some additions to code are necessary before running. I'm not specialist at python. Can you provide code which can be executed as is on ideone.com?

Now I've caught your idea. Thank you for explanation!
First, let me say that I totally rely on the task. It is written there: "the smallest possible number of summands". And my solution reaches this aim. I think, you will agree, that "the biggest possible number of summands" is totally different story, and in that case the solution will be absolutely different.
But nevertheless, I find you notice quite positive, which can lead to some improvements to my code.
1) hard-coded shift array. Really, I made it hard-coded, because the input values according to the task are limited by 109. And the maximal number of summands belongs to 104 (13 summands).
But it is not a problem, below I provide the calculation of shift values (with caching) without hard-coding. So, it will work on the whole range 0..Int32.MaxValue.
2) stack overflow is a real problem when we deal with a huge number of summands. That's true, and I agree totally (once again, I didn't understand your first notice, because I tried to link it to the initial task).
So, I tested my solution on the range 2kkk..Int32.MaxValue, and I got StackOverflowException. It is because with the input numbers which are near to Int32.MaxValue we can get the result of app. 65.000 summands!
But this is also not a problem, below I provide iterative variant of my solution.
(but once again: the solution will not find the biggest possible number of summands, but only will work on the range that is greater than 109, actually it will work on the whole range 0..Int32.MaxValue).
So, your comment exceeds the initial task requirements, but it is still positive because it encourages to think about general programming issues. Thank you for the discussion.

The improvements:

private static int[] _sum(int integer, params int[] arr) {

           //1. iteration instead of recursion
            while (true) {

                int sum = 0;

                for ( int i = 0; i < arr.Length; i++ ) {
                    sum += arr[i];
                }

                if ( sum == integer ) {
                    return arr;
                }

                var startVal = _getStartVal(integer, arr.Length + 1);

                Array.Resize(ref arr, arr.Length + 1);

                for ( int i = 0; i < arr.Length; i++ ) {
                    arr[i] = startVal + i;
                }
            }
        }

        private static int _getStartVal( int integer, int arrLength ) {
            return integer / arrLength - _getShiftValue( arrLength - 1 );
        }

        private static readonly Dictionary<int, int> Dic = new Dictionary<int, int>();
        
        // 2. Calculation instead of hard-coding
        private static int _getShiftValue( int v ) {
           
            int shiftValue;
            if ( Dic.TryGetValue( v, out shiftValue ) ) {
                return shiftValue;
            }

            shiftValue = 0;
            int t = 0;
            for( int i = 0; i < v; i++ ) {
                t++;
                if ( t == 2 ) {
                    shiftValue++;
                    t = 0;
                }
            }
            Dic.Add( v, shiftValue );
            return shiftValue;
        }

famish99, what do you mean by "The solution wouldn't work though if you were allowed numbers larger than 109" ? I didn't quite catch your idea. My solution allows all integer numbers. You can test yourself.
Also, what do you mean by "the issue of blowing up the stack for large sum values" ? I tested my solution with input integer that is Int32.MaxValue (2147483647). The result was: 2147483647 = 1073741823 + 1073741824.
All the three integers need 12 bytes of memory! 12 bytes! Where is blowing up the stack ??

c# implementation, very quick algorithm.
Complexity: O(c), where c is a constant, which can be calculated as follows:
c = n*2 + (n-1)*2 + (n-2)*2 + ... + 2, where n is a resulting number of summands.
For n = 8, c = 68.
For n = 2, c = 2.

using System;

namespace SumOfConsecutiveIntegers {

    class Program {

        // tihs ShiftVector is for maximum up to 22 summands, but it is quite with reserve, because the real practical number of summands is up to 8
        private static readonly int[] ShiftVector = { 0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10 };

        private static string Sum( int integer ) {
            
            // for all the integers which are power of 2 - impossible
            if ( (integer & (integer - 1) ) == 0) { return "IMPOSSIBLE"; }

            var startVal = _getStartVal( integer, 2 );

            var res = _sum( integer, startVal, startVal + 1 );

            var str = string.Empty;

            for ( int i = 0; i < res.Length; i++ ) {
                str += res[ i ] + " + ";
            }

            return $"{integer} = {str.TrimEnd(" + ".ToCharArray())}";
        }

        private static int[] _sum( int integer, params int[] arr ) {

            int sum = 0;

            for ( int i = 0; i < arr.Length; i++ ) {
                sum += arr[ i ];
            }

            if ( sum == integer ) { return arr; }

            var startVal = _getStartVal( integer, arr.Length + 1 );

            Array.Resize( ref arr, arr.Length + 1 );

            for ( int i = 0; i < arr.Length; i++ ) {
                arr[ i ] = startVal + i;
            }

            return _sum( integer, arr );
        }

        private static int _getStartVal( int integer, int arrLength ) {
            return integer / arrLength - ShiftVector[ arrLength - 1 ];
        }

        static void Main(string[] args) {

            Console.WriteLine("To exit type \"exit\"");
            while (true) {

                var input = Console.ReadLine();
                try {
                    if ( input.ToLower().Equals("exit") ) {
                        break;
                    }
                    var integer = int.Parse( input );
                    if ( integer <= 0 ) {
                        Console.WriteLine( "Don't be naughty! Only positive integers are permitted!" );
                    } else {
                        Console.WriteLine( Sum( integer ) );
                    }
                }
                catch (FormatException) {
                    Console.WriteLine( "Don't be naughty! Only numbers are permitted!" );
                }
            }
        }
    }
}

c# implementation, quite straightforward.

using System;

namespace IteratorProducingElementsNTimes {

    public interface IIterator<T> {
        void First();
        void Next();
        bool IsDone();
        T CurrentItem();
    }

    public class Iterator<T> : IIterator<T> {
        private readonly T _obj;
        private readonly int _total;
        private int _current = 0;

        public Iterator( T obj, int total ) {
            _obj = obj;
            _total = total;
        }

        public void First() {
            _current = 0;
        }

        public void Next() {
            _current++;
        }

        public bool IsDone() {
            return _current > _total - 1;
        }

        public T CurrentItem() {
            return _obj;
        }
    }

    public struct Person {
        public string Name;
        public string Surname;

        public override string ToString() {
            return $"{Name}, {Surname}";
        }
    }

    public static class Program {

        private static Iterator<T> _repeate<T>( T obj, int n ) {
            return new Iterator<T>(obj, n);
        }

        static void Main(string[] args) {

            var iter = _repeate( new Person { Name = "John", Surname = "Coombes" }, 3 );
            iter.First();
            while ( !iter.IsDone() ) {
                Console.WriteLine( iter.CurrentItem() );
                iter.Next();
            }
            Console.ReadLine();
        }
    }
}

I also tested on the initial matrix from the task, and I got different final groupMatrix and GroupID, as follows:
groupID: { 1(1), 2(0), 3(2), 4(4), 5(5), 6(0), 7(7), 8(8), 9(9) }
groupMatrix:
0 1 0 2 0
0 0 3 2 2
4 0 0 5 0
0 6 6 0 0
7 0 8 0 9
Why so?
Though the result is correct - 6 islands.

If we take input matrix with 24.000 islands, you algorithm is 2.5 times faster than the algorithm provided by ikoryf. Thanks! But the ikoryf's algorithm is a little more understandable, to my mind.

I deleted this message, don't know why it is still on the site.
I misunderstood the task.
So, it should not be taken into account.

c# implementation.
Complexity: O(c*n), c is a constant - a number of all possible brackets pairs, so roughly O(n).
Space: O(c), for dictionary with all possible brackets pairs, roughly - 0 ( in the example below - 32 bytes).
Return values: true - balanced, false - not balanced.

public bool ValidateBrackets( string str ) {
            const uint n = 0;
            var dic = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} }; // here must be all the possible brackets
            
            foreach ( char c in str ) {
                foreach ( var item in dic ) {
                    if ( item.Key[0] == c ) {
                        dic[item.Key]++;
                        break;
                    }
                    if ( item.Key[1] == c ) {
                        try {
                            checked { dic[item.Key]--; }
                        } catch ( OverflowException ) {
                            return false;
                        }
                        break;
                    }
                }
            }
            return dic.All(item => item.Value == 0);
        }

Yes, good question, and frankly, my first version was exactly as you described in your question: the method "AddPerson" contained only 2 method calls - _indexByName.AddOrUpdate and _indexByPhoneNumber.AddOrUpdate.
But - tests failed!
The reason is the following:
imagine, the phone book contains the entry "Tom, 123-456-789", and you try to insert entry "Tom, (+1)123-456-789", i.e. the update of the existing record (phone number should be updated).
The method _indexByName.AddOrUpdate works OK: it detects that the key "Tom" already exists in _indexByName, and it overwrites the whole record.
But method _indexByPhoneNumber.AddOrUpdate is a problem. Because before calling this method, _indexByPhoneNumber contains record "123-456-789, {Tom}" and when you put "(+1)123-456-789, {Tom}" into method, it detects that there is no key "(+1)123-456-789" and creates a new entry "(+1)123-456-789, {Tom}", so _indexByPhoneNumber will contain two entries:
"(+1)123-456-789, {Tom}"
and
"123-456-789, {Tom}",
and it is incorrect, because we intended to update the record, not to insert another one. So, I explicitly remove the old record and insert the new one, which is actually the update of the removed record.
The same (mirror situation) is with _indexByName, when you try to update the name of a person, while the phone number is not changed (I assume that there are no 2 or more persons with the same phone number, and it makes sense).
So, I added TryRemove and TryAdd statements with If conditions.

Sorry, I posted it 2 times here.

c# implementation

using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;

namespace PhoneBook {

    public struct Person {

        public Person( string name, string phoneNumber ) {
            Name = name;
            PhoneNumber = phoneNumber;
        }

        public string Name { get; }
        public string PhoneNumber { get; }
    }

    public class Phonebook {

        private readonly object _lock = new object();

        private readonly ConcurrentDictionary<string, Person> _indexByName;

        private readonly ConcurrentDictionary<string, Person> _indexByPhoneNumber;

        public Phonebook( IEnumerable<Person> people ) {
        
            _indexByName = new ConcurrentDictionary<string, Person>();
            _indexByPhoneNumber = new ConcurrentDictionary<string, Person>();

            foreach ( var p in people ) {
                _indexByName.AddOrUpdate( p.Name, p, (s, pers) => pers );
                _indexByPhoneNumber.AddOrUpdate( p.PhoneNumber, p, (s, pers) => pers );
            }
        }

        public Person? LookupByName( string name ) {

            Person pers;
            var res = _indexByName.TryGetValue( name, out pers );
            return res ? (Person?)pers : null;
        }

        public Person? LookupByPhoneNumber( string phoneNumber ) {

            Person pers;
            var res = _indexByPhoneNumber.TryGetValue( phoneNumber, out pers );
            return res ? (Person?)pers : null;
        }

        public void AddPerson( Person person ) {

            Monitor.Enter( _lock );

            var res1 = LookupByName( person.Name );
            var res2 = LookupByPhoneNumber( person.PhoneNumber );

            if ( res1 != null && res2 != null ) {
                Monitor.Exit( _lock );
                return;
            }

            Person p;

            if ( res1 != null ) {
                
                _indexByPhoneNumber.TryRemove( ((Person)res1).PhoneNumber, out p );
                _indexByPhoneNumber.TryAdd( person.PhoneNumber, person );
            }
            
            if ( res2 != null ) {

                _indexByName.TryRemove( ((Person)res2).Name, out p );
                _indexByName.TryAdd( person.Name, person );
            }

            _indexByName.AddOrUpdate( person.Name, person, (s, pers) => person );
            _indexByPhoneNumber.AddOrUpdate( person.PhoneNumber, person, (s, pers) => person );

            Monitor.Exit( _lock );
        }
    }

}