zr.roman
BAN USER 0of 0 votes
AnswersGiven a tree.
Each node is of type:public class Node { public IEnumerable<Node> Children { get; set; } }
Write a function GetAllNodes which returns collection, containing all nodes from given tree. (Given only the root node), i.e.:
IEnumerable<Node> allNodes = GetAllNodes( rootNode );
(The task is given in C#, but this is not a restriction, you may use any language you want).
 zr.roman in Russia Report Duplicate  Flag  PURGE
Software Engineer / Developer Algorithm  0of 0 votes
AnswersImplement class Queue with help of only 2 stacks.
i.e.:
 zr.roman in Russiaclass Queue<T>{ private Stack<T> _stack1; private Stack<T> _stack2; // public methods: Enqueue, Dequeue, Peek, Count // private methods, if any. }
 Report Duplicate  Flag  PURGE
Software Engineer / Developer Algorithm  0of 0 votes
AnswerImplement class Stack with help of only 2 queues,
i.e.:
 zr.roman in Russiaclass Stack<T>{ private Queue<T> _queue1; private Queue<T> _queue2; // public methods: Push, Pop, Peek, Count // private methods, if any. }
 Report Duplicate  Flag  PURGE
Software Engineer / Developer Algorithm  3of 3 votes
AnswersImagine a man reading a book.
 zr.roman in Russia
He can perform only 2 possible actions of reading:
1) read a page in a minute (careful reading),
2) read two pages in a minute (look through).
Nothing else is permitted.
Calculate the number of all possible combinations of book reading ways with given number of pages.
Example: given 3 pages.
Answer is 3 combinations, as follows:
1st: Careful reading (1)  careful reading (1)  careful reading (1),
2nd: Careful reading (1)  look through (2),
3rd: Look through (2)  careful reading (1). Report Duplicate  Flag  PURGE
SDE2 Algorithm
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"];
}

zr.roman
February 23, 2023 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.
 zr.roman December 20, 2022The 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 8th race: {2a, 1c, 1d, 1e}.
The winner of the 8th 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.
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 );
}

zr.roman
February 29, 2016 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?
in case of arbitrary binary tree without any order of nodes the algorithm is the following:
1) rearrange nodes to build a minheap (inplace due to just rearrangement of nodes). O(n).
2) k times call extractmin O(1) and minheapify 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;
}

zr.roman
February 09, 2016 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.
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;
}

zr.roman
February 09, 2016 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 deletemin n times.
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;

zr.roman
February 06, 2016 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();
}

zr.roman
February 05, 2016 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;
}

zr.roman
February 05, 2016 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;
}

zr.roman
February 01, 2016 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 );
}

zr.roman
January 31, 2016 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 );
}

zr.roman
January 31, 2016 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.
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;
}

zr.roman
January 27, 2016
Working solution, space O(n), about time I am not sure, looks like O(n) or at max O(n*logn)
 zr.roman May 10, 2023