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
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 Open Chat in New Window
what bridge?
 zr.roman June 14, 2016