CareerCup

Working solution, space O(n), about time I am not sure, looks like O(n) or at max O(n*logn)

namespace ConsoleApp {

    internal class Program {

        private static Random rnd = new Random();

        static void Main(string[] args) {

            var N = 100;

            while (N-- > 0) {

                var min_number = 1; //rnd.Next(0, 50);
                var max_number = 20;//rnd.Next(51, 61);

                var missing_number = rnd.Next(min_number, max_number + 1);

                var arr = new int[max_number-min_number];

                var needIncrementBy1 = false;

                for (int i = 0; i <= max_number - min_number-1; i++)  {
                
                    if (i + min_number == missing_number) {
                        arr[i] = i + 1 + min_number;
                        needIncrementBy1 = true;
                        continue;
                    }

                    if (!needIncrementBy1) {
                        arr[i] = i + min_number;
                    } else  {
                        arr[i] = i + 1 + min_number;
                    }
                }

                var res = GetMissingNumber(arr, min_number, max_number, out int?[] new_arr);

                if (res != missing_number)
                {
                    throw new Exception("Error!!!");
                }
            }
        }
                
        public static int GetMissingNumber(int[] A, int min_number, int max_number, out int?[] arr) {

            arr = new int?[A.Length + 1];

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

                if ( i == arr.Length - 1 ) {
                    arr[i] = null;
                    break;
                }
                arr[i] = A[i];
            }

            for (int i = 0; i <= max_number - min_number; i++) {   
                Swap(arr, rnd.Next(0, max_number - min_number+1), rnd.Next(0, max_number-min_number+1));
            }

            var counter = 0;

            while (true) {

                counter++;

                var needBreak = true;

                for (int i = 0; i <= max_number - min_number; i++) {
                    if (arr[i] != null && i != arr[i]!.Value - min_number) {
                        Swap(arr, i, arr[i]!.Value - min_number );
                    }
                }

                for (int i = 0; i <= max_number - min_number; i++) {
                    if (arr[i] == null) {
                        continue;
                    }

                    if (arr[i] - min_number != i) {
                        needBreak = false;
                        break;
                    }
                }
                if (needBreak) {
                    break;
                }
            }

            var res = -1;
            for (int i = 0; i <= max_number - min_number; i++) {
                if (arr[i] == null) {
                    Console.WriteLine(string.Empty);
                    Console.WriteLine($"min_number: {min_number}");
                    Console.WriteLine($"max_number: {max_number}");
                    Console.WriteLine($"{i+min_number} is missing");
                    Console.WriteLine($"Counter: {counter}");
                    res = i + min_number;
                    break;
                }
            }
            return res;
        }

        private static void Swap(int?[] arr, int i, int j) {
            var tmp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = tmp;
        }
    }
}

Solution in C#

public static void Main()
        {
            var k = new TreeNode { left = null, right = null, val = 1 };
            var p = new TreeNode { left = null, right = null, val = 3 };
            var t = new TreeNode { left = k, right = p, val = 2 };

            var d = new TreeNode { left = null, right = null, val = 5 };
            var g = new TreeNode { left = null, right = null, val = 7 };
            var s = new TreeNode { left = d, right = g, val = 6 };

            var root = new TreeNode { left = t, right = s, val = 4 };

            var listHeadNode = Func(root);
            Console.WriteLine(listHeadNode.val);
        }

        public static ListNode Func( TreeNode node, Dictionary<string, ListNode> dic = null! ) {

            if ( dic == null ) {
                dic = new Dictionary<string, ListNode> { { "head", null! }, { "prev", null! } };
            }
            
            if ( node == null ) {
                return dic[ "head" ];
            }
            
            var listNodeCurr = new ListNode { val = node.val };

            Func( node.left, dic);

            if (dic["prev"] == null) {
                dic["head"] = listNodeCurr;
            } else {
                dic["prev"].next = listNodeCurr;
            }

            listNodeCurr.prev = dic["prev"];

            dic["prev"] = listNodeCurr;

            Func(node.right, dic);

            return dic["head"];
        }

sorry, in previous comment I missed the fact that despite we don't know the exact times we still know the relative order of horses inside each group (the horses are sorted). So, taking this fact the assumption "FOR II position,horse will be either b1 or a2" is correct.

The answer is: 9 in worst case and 8 in best case.

Explanation:

To find 5 best horses we obviously need 5 races.
Then the 6th race is used to find the winner among those 5 best horses.
Let's say 6th race is done and {1a 2a 3a 4a 5a} - are the winners each in their respective group.
1a 2a 3a 4a 5a
1b 2b 3b 4b 5b
1c 2c 3c 4c 5c
1d 2d 3d 4d 5d
1e 2e 3e 4e 5e

Now we know for sure that 1a horse outperformed all horses and we take it as ranked #1 and exclude from consideration.
Further, we know for sure that horse 2a outperformed all horses EXCEPT of four ones: 1b 1c 1d 1e.
That is why we must test horse 2a against those {1b, 1c, 1d, 1e} horses in 7th race.
So, the 7th race is {2a, 1b, 1c, 1d, 1e}.

Here 2 variations are possible:

1) If horse 2a loses the 7th race, then we get ranked #2 horse as winner of race 7 (let's say it is 1b horse) and then we must test horse 2a against other losers for the 7th race.
This is the 8-th race: {2a, 1c, 1d, 1e}.
The winner of the 8-th race will be ranked #3 horse.
And we are done with 8 races in total.

2) But If horse 2a wins the 7th race, then we get 2a horse as ranked #2 horse.
Now we know for sure that 2a horse outperformed all horses EXCEPT of a1 and we take it as ranked #2 and exclude from consideration.
Further, we know for sure that horse 3a outperformed all horses EXCEPT of eight ones: {1b, 1c, 1d, 1e, 2b, 2c, 2d, 2e}.
That is why we must test horse 3a against all those 8 horses.
To do this we need 3 more races.
We can randomly shuffle given 9 horses and run 2 races
Race 7: {2e, 1b, 2d, 1e, 2b}
Race 8: {1c, 2c, 1d, 3a}
Race 9: {winner_of_race_7, winner_of_race_8}
Winner of race 9 will be ranked #3 horse.
And we are done with 9 races in total.

hi, friend!
"FOR II position,horse will be either b1 or a2" - looks like this is wrong, since we don't have timer and we don't know exact times at which horses arrived to finish.
So, all we know is that a1 arrived faster than {a2, a3, a4, b1}, but we don't know how faster/slower horses {a2, a3, a4, b1} were if compared to each other.
This means that for II position all 4 horses {a2, a3, a4, b1} are equally possible.

what bridge?

for @kanon
looks like, you are wrong.
"uploads.ru/AORLC.jpg"
Here I draw all the 33 variants for F(4). Look.
If I missed something, please, let me know.

O(n!) time complexity.

the task and the answer are awesome.

c#.
Time O(n).
Space O(1).
A little bit more tricky than solution with stack but it saves running space.

public static bool ValidateBrackets2( string str ) {
    const uint n = 0;
    // all possible pairs of brackets in forward order
    var dic1 = new Dictionary<char, char> { {'{', '}'}, {'(', ')'}, {'[', ']'}, {'<', '>'} };
    // all possible pairs of brackets in reverse order
    var dic2 = new Dictionary<char, char> { {'}', '{'}, {')', '('}, {']', '['}, {'>', '<'} };
    // all possible pairs of brackets coupled
    var dic3 = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
    // all possible closing brackets
    var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };

    foreach ( char ch in str ) {
        if ( dic1.ContainsKey( ch ) ) {
            dic3[ ch.ToString() + dic1[ ch ] ]++;
            dic0[ dic1[ ch ]  ] = dic0.Values.Max() + 1;
            continue;
        }
        if ( dic2.ContainsKey( ch ) ) {
            if ( dic0[ ch ] != dic0.Values.Max() ) { return false; }
            try {
                checked { dic3[ dic2[ ch ] + ch.ToString() ]--; }
                dic0[ ch ] = (dic3[ dic2[ ch ] + ch.ToString() ] == 0) 
                        ? 0 
                        : dic0.Values.Where( x => x > 0 ).Min() - 1;
            } catch ( OverflowException ) {
                return false;
            }
        }
    }
    return dic3.All( item => item.Value == 0 );
}

the "Islands Count problem",
duplicate from here: question?id=5708658983829504

the task is a bit unclear.
What do you mean?
let's have example: "Java code here".
So, in each word letters were randomly shuffled and after that words were written without spaces: "Ajavdoeceehr".
Is the task to restore initial string "Java code here"? or what?

do inorder traversal, compare current node to the previously visited one.
While traversing maintain "minDiff" variable.
If current (node - previous) is greater than "minDiff" then update "minDiff".
Return "minDiff" in the end.

no, that is not correct, my code does not contain any assumptions.
Array is expected to be arbitrary.

can be done in O(1) space.

in case of arbitrary binary tree without any order of nodes the algorithm is the following:
1) re-arrange nodes to build a min-heap (in-place due to just re-arrangement of nodes). O(n).
2) k times call extract-min O(1) and min-heapify O( k log n).
Worst case is O(n log n) in case the kth smallest element is the greatest one by coincidence.

c# implementation.
O(n) time.
O(1) space.

private static bool CheckAP( int[] arr ) {

    int[] minmaxs = new int[3]{ int.MaxValue, int.MaxValue, int.MinValue }; //globalMin, secondMin, gloabalMax
    for ( int i = 0; i < arr.Length; i++ ) {
        if ( arr[ i ] == minmaxs[ 0 ] || arr[ i ] == minmaxs[ 2 ] ) {
            return false; // AP cannot contain duplicate elements
        }
        minmaxs[ 1 ] = Math.Max( minmaxs[ 0 ], Math.Min( arr[ i ], minmaxs[ 1 ] ) );
        minmaxs[ 0 ] = Math.Min( arr[ i ], minmaxs[ 0 ] );                
        minmaxs[ 2 ] = Math.Max( arr[ i ], minmaxs[ 2 ] );
    }
    var step = minmaxs[ 1 ] - minmaxs[ 0 ];
    if ( ( minmaxs[ 2 ] - minmaxs[ 0 ] ) / step + 1 != arr.Length ) {
        return false;
    }
    int bit = ( minmaxs[ 0 ] & 1 ) == 1 ? 1 : 0;
    for ( int i = 0; i < arr.Length; i++ ) {
        if ( bit == 0 ) {
            if ( ( ~(arr[ i ] % step) & bit) == 0 ) { continue; }
            return false;
        }
        if ( bit == 1 ) {
            if ( ( (arr[ i ] % step) & bit) == 1 ) { continue; }
            return false;
        }
    }
    return true;
}

actually, I don't know. Well, by default, the more you tell the better.
As I understand the interviewer when he gives such a task, he wants to know the approach.
For example, this task can be solved with 3 approaches:
1) brute force O(n^2),
2) divide'n'conquer O(n log n)
3) DP O(n).
I think, that is the basis.
Moreover, in CLRS textbook the DP approach is described but not mentioned that it is Kadane.

actually, Kadane is a correct approach, but the algorithm should be modified to keep track of the starting and ending indices of the maximum subarray.

modified Kadane.
c#

private static int[] Kadane( int[] arr ) {

    var coords = new int[2] { 0, 0 };
    int maxByNow = arr[ 0 ], greatest = arr[ 0 ];

    for (int i = 1; i < arr.Length; i++) {
        if ( maxByNow < 0 ) { coords[ 0 ] = i; }
        maxByNow = Math.Max( arr[ i ], maxByNow + arr[ i ] );
        var tmp = Math.Max( greatest, maxByNow );
        if ( tmp > greatest ) { coords[ 1 ] = i; }
        greatest = tmp;
    }
    int[] res = new int[ coords[ 1 ] > coords[ 0 ] ? coords[ 1 ] - coords[ 0 ] + 1 : 1 ];
    res[ 0 ] = arr[ coords[ 1 ] ];
    for ( int i = coords[ 0 ]; i <= coords[ 1 ]; i++ ) {
        res[ i - coords[ 0 ] ] = arr[ i ];
    }
    return res;
}

the task is to return the subarray, not the maxSum.

quite reasonable observation.
really, in simple case (as in the task), we can maintain two variables, and that will be enough.
In general case ("get nth least common element from array"), of course it is necessary to change the solution as follows:
introduce an extra data structure, e.g. priority queue (min heap), put all the values from hashtable into priority queue, and then call delete-min n times.

use hashtable to count occurences.
Then scan the hashtable and maintain two variables: "min" and "secondMin".
Return "secondMin" in the end.

I think the author meant BST.
just "binary tree" is senseless, because he could just write "given an unsorted array".

because you use "++" operator, which modifies "x" variable.

in my algorithm first character with 0 frequency will be the first non repeated element, because both scans are done against the input string.

InOrder traversal. But counter starts incrementing after you reach the left most node (including it).
Return current node when the counter is equal to n.

c# implementation.

private static Node Find( Node node ) {

    if ( node.Parent != null ) {
        _counter = _counter + 1 ?? 1;
        return Find( node.Parent );
    }

    return InOrder( node );
}

private static Node InOrder( Node node ) {

    if ( _counter == 0 || _counter == null ) {
        return node;
    }

    if ( node.LeftChild != null && !Visited.Contains( node.LeftChild ) ) {
        _counter--;
        return InOrder( node.LeftChild );
    }

    if ( node.RightChild != null && !Visited.Contains( node.RightChild ) ) {
        _counter--;
        return InOrder( node.RightChild );
    }
    Visited.Add( node );
    _counter++;
    return InOrder( node.Parent );
}

static readonly HashSet<Node> Visited = new HashSet<Node>();
private static int? _counter = null;

the solution has complexity O(n^3), because "substr" subroutine has linear time.

the string "abchealloxyz", does not contain "hello".

yep.
It's quite obvious. The space is needed only for 2 dictionaries, both of constant size. Constant size means O(1).
That's it.

c#.
O(n) time.
O(1) space.

private static string RemoveDuplicatesFromString( string str ) {
    int[] arr = new int[256];
    for ( int i = 0; i < str.Length; i++ ) {
        arr[ str[ i ] ]++;
    }
    StringBuilder sb = new StringBuilder();
    for ( int i = 0; i < str.Length; i++ ) {
        sb.Append( arr[ str[ i ] ] == 1 ? str[ i ].ToString() : "" );
    }
    return sb.ToString();
}

more careful analysis gives O(n*m) for brute force.

right.

c# implementation.
O(n*m).

private static List<int[]> Find( int[,] arr, int[,] pattern ) {
    var pattCol = 0;
    var startCoords = new int[ 2 ] { -1, -1 };

    for ( int i = 0; i < arr.GetLength( 0 ); i++ ) {
        for ( int j = 0; j < arr.GetLength( 1 ); j++ ) {
            if ( j > pattCol + ( arr.GetLength( 1 ) - pattern.GetLength( 1 ) ) ) {
                break;
            }

            if ( arr[ i, j ] != pattern[ 0, pattCol ] ) {
                startCoords = new[] { -1, -1 };
                if ( pattCol != 0 ) {
                    j--;
                    pattCol = 0;
                }
                continue;
            }
                    
            var pattRow = 0;
            var colMatch = true;
            for ( int k = i + 1; k < pattern.GetLength( 0 ) + i && k < arr.GetLength( 0 ); k++ ) {
                pattRow++;
                if ( arr[ k, j ] != pattern[ pattRow, pattCol ] ) {
                    colMatch = false; break;
                }
            }
            if ( colMatch ) {
                if ( pattCol == pattern.GetLength( 1 ) - 1 ) {
                    return new List<int[]> { startCoords, new [] { i + pattern.GetLength( 0 ) - 1, j } };
                }
                if ( startCoords[ 0 ] == -1 ) { startCoords = new [] { i, j }; }
                pattCol++;
            } else {
                startCoords = new[] { -1, -1 };
                pattCol = 0;
            }
        }
    }
    return null;
}

what are m1,n1,m2 and n2 here in O(m1*n1 +m2*n2)?

hello, @kelly, sorry, but your math is quite unclear.
The idea of my solution is the following: when you start from 0 and begin increment by 1, you pass through a series of numbers where even and odd numbers alternate each other with equal interval, i.e. one by one.
So, imagine you started incrementing and the finish will happen in a random period of time.
So, the question is: what is the probability that the final value will be either even or odd?
The answer is obvious: the probability is 1/2.
Because of 2 reasons:
1) in the series of numbers there are no types except of "even" and "odd".
2) even and odd numbers alternate each other, i.e. no one even number stands near another even number, and no one odd number stand near another odd number.
So, this is actually the proof of correctness of my solution: the final probability is 1/2.

thank you for clarification.
If the task is about to find only pairs then it is quite straightforward O(n) solution as follows (c#).

private static List<int[]> GetCombinationsOfTwo( int[] arr, int sum ) {
    var res = new List<int[]>();
    var dic = new Dictionary<int, int>();

    for ( int i = 0; i < arr.Length; i++ ) {
        if ( arr[ i ] > sum || dic.ContainsKey( arr[ i ] ) ) { continue; }
        if ( dic.ContainsKey( sum - arr[ i ] ) ) {
            dic[ sum - arr[ i ] ]++;
            continue;
        }
        dic[ arr[ i ] ] = -1;
    }

    foreach ( var key in dic.Keys ) {
        if ( dic[ key ] >= 0 ) {
            res.Add( new [] { key, sum - key } );
        }
    }
    return res;
}

well, actually, O(n) space is not inevitable.
I improved this solution such that it is still O(n) time and O(1) space.

you are right, thank you.
This check is not performed.
So, looks like using stack with O(n) space is inevitable.

task is a bit unclear, what do you mean "If a number is used once, it must not be used again" ?
What if we have an array 6 5 4 3 2 1 and sum = 10.
What output should be?
First, it is 6 4.
But what about 6 3 1 ? We already used 6, so, can we use it in case of 6 3 1 ?
And then, what about 4 3 2 1 ? We already used 4 in first output, what should we do now?
And what about 5 3 2 ?
And so on.

variant #2.
c#.
Time O(n).
Space O(1).

public static bool ValidateBrackets2( string str ) {
    const uint n = 0;
    // all possible pairs of brackets in forward order
    var dic1 = new Dictionary<char, char> { {'{', '}'}, {'(', ')'}, {'[', ']'}, {'<', '>'} };
    // all possible pairs of brackets in reverse order
    var dic2 = new Dictionary<char, char> { {'}', '{'}, {')', '('}, {']', '['}, {'>', '<'} };
    // all possible pairs of brackets coupled
    var dic3 = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
    // all possible closing brackets
    var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };

    foreach ( char ch in str ) {
        if ( dic1.ContainsKey( ch ) ) {
            dic3[ ch.ToString() + dic1[ ch ] ]++;
            dic0[ dic1[ ch ]  ] = dic0.Values.Max() + 1;
            continue;
        }
        if ( dic2.ContainsKey( ch ) ) {
            if ( dic0[ ch ] != dic0.Values.Max() ) { return false; }
            try {
                checked { dic3[ dic2[ ch ] + ch.ToString() ]--; }
                dic0[ ch ] = (dic3[ dic2[ ch ] + ch.ToString() ] == 0) 
                        ? 0 
                        : dic0.Values.Where( x => x > 0 ).Min() - 1;
            } catch ( OverflowException ) {
                return false;
            }
        }
    }
    return dic3.All( item => item.Value == 0 );
}

c# implementation.
O(n) time.
O(1) space.
Return values: true - balanced, false - not balanced.

public static bool ValidateBrackets1( string str ) {
    const uint n = 0;
    // all possible brackets coupled
    var dic = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
    // all possible closing brackets
    var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };

    foreach ( char c in str ) {
        foreach ( var item in dic ) {
            if ( item.Key[ 0 ] == c ) {
                dic[ item.Key ]++;
                dic0[ item.Key[ 1 ]  ] = dic0.Values.Max() + 1;
                break;
            }
            if ( item.Key[ 1 ] == c ) {
                if ( dic0[ item.Key[ 1 ] ] != dic0.Values.Max() ) { return false; }
                try {
                    checked { dic[ item.Key ]--; }
                    dic0[ item.Key[ 1 ] ] = (dic[ item.Key ] == 0) 
                        ? 0 
                        : dic0.Values.Where( x => x > 0 ).Min() - 1;
                } catch ( OverflowException ) {
                    return false;
                }
                break;
            }
        }
    }
    return dic.All( item => item.Value == 0 );
}

straightforward O(n) solution:
do InOrder Traversal, and maintain two variables (a max and a counter) as follows: while traversing in depth increment counter (and while walking up decrement it), when you hit a leaf node do a check to see if a counter value is greater than the max value. If so - update max variable, then continue traversing.

external MergeSort

asymptotically not optimal solution.
In case of all distinct characters this is O(n^2) solution.
Using hashtable allows to create O(n) solution.

upd

using hashtable do 1st scan and store chars and their frequencies to that hashtable.
Then do 2nd scan and compare each char's frequency to 0. When you hit 0 for the first time - break and return the corresponding char.

this is LCS problem, where in 2D array 1st dimension is a given array, and 2nd dimension is the same array but in reverse order.
c#.

private static int GetLengthOfMaximumPalindrome( int[] arrIn ) {

    int[,] arr = new int[ arrIn.Length + 1, arrIn.Length + 1 ];
    int maxVal = 0;

    for ( int row = 0; row < arrIn.Length; row++ ) {
        for ( int col = 0; col < arrIn.Length; col++ ) {

            var leftCell = arr[ row + 1, col ];
            var upCell = arr[ row, col + 1 ];
            var leftDiagonalCell = arr[ row, col ];

            if ( arrIn[ row ] != arrIn[ arrIn.Length - col - 1 ] ) { 
                arr[ row + 1, col + 1 ] = Math.Max( leftCell, upCell );
            } else {
                arr[ row + 1, col + 1 ] = leftDiagonalCell + 1;
            }

            var currVal = arr[ row + 1, col + 1 ];

            if ( currVal > maxVal ) { maxVal = currVal; }
        }
    }
    return maxVal;
}

starting from root recursively swap left child and right child at all the nodes.