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
SDE-2 Algorithm
c#.
general solution for any number of given variables.
Without if statements.
static bool AreAllEqual( int num, List<int> variables ) {
try{
int[] arr = new int[1];
variables.Add( num );
for( int i = variables.Count - 1; i > 0; i-- ) {
arr[ variables[ i ] ^ variables[ i - 1 ] ] = 0;
}
return true;
} catch( IndexOutOfRangeException ){
return false;
}
}
c# implementation.
via peak finding.
Running time 3*n.
O(n) complexity.
private static int GetViaPeakFinding( int[] arr ) {
int res = 0;
int prevPeak = -2;
for ( int i = 0; i < arr.Length; i++ ) {
if ( ( i == 0 || arr[ i ] > arr[ i - 1 ] ) && ( i == arr.Length - 1 || arr[ i ] > arr[ i + 1 ] ) ) {
res += arr[ i ];
var tmpSum1 = 0; var tmpSum2 = 0;
for ( int j = prevPeak + 2, k = i - 2; ( ( j < i - 1 ) && ( k > prevPeak + 1 ) ); j += 2, k -= 2 ) {
tmpSum1 += j < i - 1 ? arr[ j ] : 0;
tmpSum2 += k > prevPeak + 1 ? arr[ k ] : 0;
}
res += tmpSum1 > tmpSum2 ? tmpSum1 : tmpSum2;
prevPeak = i;
continue;
}
if ( i == arr.Length - 1 && arr[ i ] <= arr[ i - 1 ] ) {
for ( int j = prevPeak + 2; j < arr.Length; j += 2 ) {
res += arr[ j ];
}
}
}
return res;
}
possible c# implementation.
O(logn).
using System;
namespace MissingElementAPSequence {
public class MissingElementApSequence {
static int? Find( int[] apArr ){
int step = GetStep( apArr, 0 );
if( step == 0 ) { return GetRes( apArr, 0 ); }
int begin = 0;
int end = apArr.Length - 1;
while ( end - begin != 1 ) {
if ( end - begin < 4 ) {
var res = GetRes( apArr, begin );
if( res != 0 ) { return res; }
}
int mid = ( end + begin ) / 2;
int expected = apArr[ 0 ] + mid * step;
if ( expected != apArr[ mid ] ) { end = mid; }
else { begin = mid; }
}
return null; // A.P. does not have missing elements
}
static int[] _get( int[] arr, int beg ) {
int oneMinusZero = arr[ beg + 1 ] - arr[ beg ];
int twoMinusOne = arr[ beg + 2 ] - arr[ beg + 1 ];
if ( oneMinusZero == twoMinusOne ){
return new [] { oneMinusZero, 0 };
}
if ( Math.Abs( oneMinusZero ) > Math.Abs( twoMinusOne ) ) {
return new [] { 0, arr[ beg ] + twoMinusOne };
}
return new [] { 0, arr[ beg + 1 ] + oneMinusZero };
}
static int GetRes( int[] arr, int beg ){
return _get( arr, beg )[ 1 ];
}
static int GetStep( int[] arr, int beg ) {
return _get( arr, beg )[ 0 ];
}
public static void Main() {
//int[] arr = { 10, 8,/*6,*/4, 2, 0, -2, -4, -6, -8, -10, -12, -14, -16, -18, -20, -22, -24, -26, -28, -30, };
int[] arr = { -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28,/* 30,*/ 32, 34, 36 };
var res = Find(arr);
Console.WriteLine( res );
}
}
}
c# implementation.
O(logn) time.
O(1) space.
namespace FibonacciInLogNTime {
static class Program {
// time complexity O(log n)
static private long Fib( long n ) {
n--;
long[,] res = { { 1, 0 }, { 0, 1 } }; // Identity matrix (with ones on the main diagonal and zeros elsewhere)
long[,] a = { { 1, 1 }, { 1, 0 } }; // Identity matrix for Fibonacci seq { { F(n+1), F(n) }, { F(n), F(n-1) } }
while ( n > 0 ) {
if ( ( n & 1 ) == 1 ) {
res = res.Multiply( a );
}
n /= 2;
a = a.Multiply( a );
}
return res[ 0, 0 ];
}
private static long[,] Multiply ( this long[,] arrA, long[,] arrB ) {
return new [,] { {
( arrA[ 0, 0 ] * arrB[ 0, 0 ] + arrA[ 0, 1 ] * arrB[ 1, 0 ] ), // [0,0]
( arrA[ 0, 0 ] * arrB[ 0, 1 ] + arrA[ 0, 1 ] * arrB[ 1, 1 ] ) // [0,1]
},{
( arrA[ 1, 0 ] * arrB[ 0, 0 ] + arrA[ 1, 1 ] * arrB[ 1, 0 ] ), // [1,0]
( arrA[ 1, 0 ] * arrB[ 0, 1 ] + arrA[ 1, 1 ] * arrB[ 1, 1 ] ) // [1,1]
}
};
}
static void Main( string[] args ) {
var res = Fib( 5 );
}
}
}
c# implementation.
Longest Common Subsequence's length.
Classic algo, O(m*n).
using System;
namespace LongestCommonSubsequence {
class Program {
private static int LCSsLength( string s1, string s2 ) {
int[,] arr = new int[ s1.Length + 1, s2.Length + 1];
int[] maxValCoords = new int[2];
int maxVal = 0;
for ( int row = 0; row < s1.Length; row++ ) {
for ( int col = 0; col < s2.Length; col++ ) {
var leftCell = arr[ row + 1, col ];
var upCell = arr[ row, col + 1 ];
var leftDiagonalCell = arr[ row, col ];
if ( s1[ row ] != s2[ col ] ) {
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 ) { continue; }
maxValCoords[ 0 ] = row + 1;
maxValCoords[ 1 ] = col + 1;
}
}
return GetVal( arr, maxValCoords, s1, s2 ).Length;
}
private static string GetVal( int[,] arr, int[] coords, string s1, string s2 ) {
string commonChar = string.Empty;
var row = coords[ 0 ];
var col = coords[ 1 ];
if ( arr[ row, col ] == 0 ) return string.Empty;
var leftCell = arr[ row, col - 1 ];
var upCell = arr[ row - 1, col ];
var chFromS1 = s1[ row - 1 ];
var chFromS2 = s2[ col - 1 ];
if ( chFromS1 == chFromS2 ) {
commonChar = chFromS2.ToString();
row--;
col--;
}
else if ( upCell >= leftCell ) { row--; }
else { col--; }
return GetVal( arr, new[] { row, col }, s1, s2 ) + commonChar;
}
static void Main( string[] args ) {
var res = LCSsLength("MICHAELANGELO","HIEROGLYPH");
Console.ReadLine();
}
}
}
lets do comparison analysis of a brute force method and Parallax Distance measurement method.
In case of brute force method running time will be actually infinity. Why? Let's see.
To measure a distance from earth to a star we must send a signal to a star and wait for a response (reflected signal) and divide the overall time by 2. This will be the number of light years (ly) to that star. But what if the distance to some star is 1.000 ly? This means that we have to wait 2.000 years to receive a reflected signal! Nobody lives that long. In reality most stars are millions and billions lys far from us. That is why I say that actual running time of brute force is infinity.
Now Parallax Distance measurement method: actual running time is 1 year.
The algorithm is simple: we measure the start positions of all 10.000 stars in the beginning of the year. Then during 1 year we systematically measure parallaxes of all the stars. In the end of the year we compare all the parallaxes. The star with the greatest parallax is the nearest.
better ideas can appear only when the array is somehow preprocessed (i.e. maintained in sorted order, etc.).
Or, if we limit access to array only via special API, then we can detect distortion of data immediately after each access in O(logn) in worst case or even in O(1) w.h.p. if we implement some kind of hashing.
create recursive procedure which traverses through 2D matrix, while counting all the valid paths (valid means that there are no intersections inside one path and a path is of at least needed length).
Call this procedure in loop for every element of given 2D matrix.
c# implementation.
"Divide & Conquer" approach.
result is a 2D array, where each element is the team with which team "i" must have play on day "j".
using System;
using System.Collections.Generic;
namespace Tournament {
class Program {
static private int[,] GetSchedule( int teams ) {
if ( teams == 2 ) { return new [,] { { 1 }, { 0 } }; }
var halfTeams = teams / 2;
var tmpRes = GetSchedule( halfTeams );
var days = teams - 1;
var halfDays = days / 2;
int[,] res = new int[ teams, days ];
for ( int i = 0; i < teams; i++ ) {
for ( int j = 0; j < days; j++ ) {
var val = ( i < tmpRes.GetLength( 0 ) && j < tmpRes.GetLength( 1 ) ) ? tmpRes[ i, j ] : 0;
res[ i, j ] = val;
}
}
for ( int i = halfTeams; i < teams; i++ ) {
for ( int j = 0; j < halfDays; j++ ) {
res[ i, j ] = res[ ( i - halfTeams ), j ] + halfTeams;
}
}
var list1 = new List<int> { halfTeams };
var list2 = new List<int> { halfTeams - 1 };
for ( int j = 0; j < halfDays; j++ ) {
list1.Add( res[ 0, j ] + halfTeams );
list2.Add( res[ teams - 1, j ] - halfTeams );
}
Action<int, List<int>> action = (i, lst) => {
int t = 0;
for ( int j = halfDays; j < days; j++ ) {
res[ i, j ] = lst[ t ];
t++;
}
var first = lst[ 0 ];
lst.RemoveAt( 0 );
lst.Add( first );
};
for ( int i = 0, j = teams - 1; i < halfTeams; i++, j-- ) {
action.Invoke( i, list1 );
action.Invoke( j, list2 );
}
return res;
}
static void Main( string[] args ) {
int n = 2;
var teams = (int)Math.Pow( 2, n );
var res = GetSchedule( teams );
Console.ReadLine();
}
}
}
c# implementation.
hash tables.
using System;
using System.Collections.Generic;
using System.Text;
namespace TextToNumber {
class Program {
static private string Convert( string s ) {
var res = new StringBuilder();
var arr = s.ToLower().Split(' ');
int startPos = -1; int hundredPos = -1; int tmpCalc = 0;
bool firstTimeHere = true;
for ( int i = 0; i < arr.Length; i++ ) {
int t;
if ( arr[ i ] == "hundred" ){
hundredPos = i; t = i - 1;
while ( t > startPos ) {
tmpCalc += dic1[ arr[ t ] ];
t--;
}
tmpCalc *= 100;
}
var containsVal = dic2.ContainsKey( arr[ i ] );
if ( !containsVal && i != arr.Length - 1 ) {
continue;
}
t = containsVal ? i - 1 : i;
while ( t > ( hundredPos != -1 ? hundredPos : startPos ) ) {
tmpCalc += dic1[ arr[ t ] ];
t--;
}
startPos = i;
hundredPos = -1;
if ( firstTimeHere ) {
res.Append( tmpCalc.ToString() );
if ( containsVal ) {
for ( int j = 0; j < dic2[ arr[ i ] ]; j++ ) {
res.Append( "0" );
}
}
firstTimeHere = false;
} else {
int pos = res.Length - ( containsVal ? dic2[ arr[ i ] ] : 0 ) - 3;
res.Remove( pos, 3 );
res.Insert( pos, tmpCalc.ToString().PadLeft( 3, '0' ) );
}
tmpCalc = 0;
}
return res.ToString();
}
static readonly Dictionary<string, byte> dic1 = new Dictionary<string, byte> {
{ "one", 1 }, { "two", 2 }, { "three", 3 }, { "four", 4 }, { "five", 5 },
{ "six", 6 }, { "seven", 7 }, { "eight", 8 }, { "nine", 9 },{ "ten", 10 },
{ "eleven", 11 }, { "twelve", 12 }, { "thirteen", 13 }, { "fourteen", 14 },
{ "fifteen", 15 }, { "sixteen", 16 }, { "seventeen", 17 },{ "eighteen", 18 },
{ "nineteen", 19 }, { "twenty", 20 }, { "thirty", 30 }, { "forty", 40 },
{ "fifty", 50 }, { "sixty", 60 },{ "seventy", 70 },{ "eighty", 80 },{ "ninety", 90 },
};
static readonly Dictionary<string, byte> dic2 = new Dictionary<string, byte> {
{ "thousand", 3 },{ "million", 6 }, { "billion", 9 },
{ "trillion", 12 } // any more if needed
};
static void Main( string[] args ) {
var str = "One million two hundred thousand fifty seven";
var res = Convert( str );
Console.WriteLine( res );
}
}
}
thanks, this is a great observation.
really, my solution does not handle this situation.
A small improvement is needed: when we receive 2 identical nodes sequence, then we must check if the respective levels sequence can be reduced one to another via iterative subtracting 1 from each digit of a respective seq.
Example:
{ABC, 212} and {ABC, 021} - the answer is no, because we cannot reduce 212 to 021 (and vice versa).
{ECF, 323} and {ECF, 212} - the answer is yes (the tree has duplicate sub trees), because we can reduce 323 to 212 via iterative subtracting 1 from each digit in first number (323). So, here we need 1 iteration.
Thanks again, you helped to improve the solution.
that's better, but we still have 2 log calls and 1 pow call, so complexity will depend on the cost of these remaining calls.
- zr.roman January 13, 2016