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
foreach loop copies the current array to a new one for the operation.
According to the task the string may have length up to 20 GB. Let's assume, that your total space is 25 GB. Your solution will crash.
Moreover, generally foreach loop does not ensure the order of of collection' elements processing.
c# implementation with the help of algorithm of @SK and @kang.
Time complexity (worst) is O(50*k), where k  number of digits in input value. Actually, for the range of INT numbers the complexity is O(1).
using System;
namespace CountTwos {
class Program {
private static long GetCountOfTwos( int num, ref int t ) {
var lastTwoDigits = num % 100;
if ( lastTwoDigits == 99 ) {
return GetNewRes( GetNumOfTwoForBound( num, ref t ), num, i => i, ref t );
}
var numWithoutLast2Digits = (int)Math.Floor( ( num / Math.Pow( 10, 2 ) ) );
int lowerBound = numWithoutLast2Digits * 100  1;
int upperBound = num >= int.MaxValue  47 ? int.MaxValue : numWithoutLast2Digits * 100 + 99;
int bound = upperBound;
int start = upperBound;
Predicate<long> condFunc = i => i >= num;
Func<long, long> incDec = i => i;
bool lowerNear = num  lowerBound < upperBound  num;
if ( lowerNear ) {
bound = lowerBound;
start = lowerBound + 1;
condFunc = i => i < num;
incDec = i => ++i;
}
long res = GetNumOfTwoForBound( bound, ref t );
for ( long i = start; condFunc.Invoke( i ) ; i = incDec.Invoke( i ) ) {
res = GetNewRes( res, i, incDec, ref t );
}
return res;
}
private static long GetNewRes( long res, long curr, Func<long, long> incDec, ref int t ) {
while ( curr != 0 ) {
t++;
var digit = curr % 10;
if ( digit == 2 ) {
res = incDec.Invoke( res );
}
curr = curr / 10 ;
}
return res;
}
// borrowed code from @SK and @kang
private static long GetNumOfTwoForBound( int n, ref int t ) {
long ret = 0;
int digit = 0;
while (n != 0) {
t++;
int r = n % 10;
int d = n / 10;
if ( r >= 2 ) d++;
ret += (long)Math.Pow( 10, digit ) * d;
n = n / 10;
digit++;
}
return ret;
}
static void Main(string[] args) {
int t = 0;
Console.WriteLine( $"{ GetCountOfTwos( 82, ref t )}, Complexity: O({t})" );
Console.ReadLine();
}
}
}

zr.roman
November 27, 2015 transform given set of IP addresses into 2D Nx4 matrix of bytes. O(4n), actually O(n),
Then apply MergeSort 4 times according to the number of columns. O(4n*log n), actually O(n*log n).
Then transform result 2D matrix into set of IPs. O(4n), actually O(n),
Overall complexity O(2n + n*logn), actually O(n + n*logn).
c# implementation.
using System;
namespace BinarySearch {
class Program {
private static int _bsearchMostLeftIndex( int[] arr, int startIndex, int endIndex, int val ) {
var index = ( endIndex + startIndex ) / 2;
if ( _noNearestDuplicates( arr, index, val ) ) { return index; }
if ( endIndex  startIndex == 1 ) {
if ( arr[ startIndex ] == val ) {
return startIndex;
}
if ( arr[ endIndex ] == val ) {
return endIndex;
}
throw new Exception( $"No such element: {val}" );
}
if ( arr[ index ] >= val ) {
return _bsearchMostLeftIndex( arr, startIndex, index , val );
}
if ( arr[ index ] < val ) {
return _bsearchMostLeftIndex( arr, index, endIndex, val );
}
throw new Exception( $"No such element: {val}" );
}
private static int _bsearchMostRightIndex( int[] arr, int startIndex, int endIndex, int val ) {
var index = ( endIndex + startIndex ) / 2;
if ( _noNearestDuplicates( arr, index, val ) ) { return index; }
if ( endIndex  startIndex == 1 ) {
if ( arr[ endIndex ] == val ) {
return endIndex;
}
if ( arr[ startIndex ] == val ) {
return startIndex;
}
throw new Exception( $"No such element: {val}" );
}
if ( arr[ index ] <= val ) {
return _bsearchMostRightIndex( arr, index, endIndex, val );
}
if ( arr[ index ] > val ) {
return _bsearchMostRightIndex( arr, startIndex, index , val );
}
throw new Exception( $"No such element: {val}" );
}
private static bool _noNearestDuplicates( int[] arr, int index, int val ) {
return arr[ index ] == val && ( ( index > 0 && arr[ index  1 ] != val )  index == 0 ) && arr[ index + 1 ] != val;
}
private static int GetNumberOfRepeats( int[] arr, int val ) {
var mostLeftIndex = _bsearchMostLeftIndex( arr, 0, arr.Length  1, val );
var mostRightIndex = _bsearchMostRightIndex( arr, 0, arr.Length  1, val );
return mostRightIndex  mostLeftIndex + 1;
}
static void Main( string[] args ) {
var bb = GetNumberOfRepeats( new[] {0,1,1,2,3,4,5,5,5,5,5,5,5,5,5,5,5,5,6,7,8,8,9,9,9,9,9,9,9,9,9,9}, 1 );
Console.WriteLine(bb);
Console.ReadLine();
}
}
}

zr.roman
November 26, 2015 c# implementation.
namespace DigitSum {
class Program {
static private int[] GetDigitSum( int[] arr1, int[] arr2 ) {
string str = string.Empty;
int mem = 0;
int counter = 0;
while ( true ) {
var index1 = arr1.Length  counter  1;
var index2 = arr2.Length  counter  1;
if ( index1 < 0 && index2 < 0 && mem == 0 ) {
break;
}
int s1 = index1 < 0 ? 0 : arr1[ index1 ];
int s2 = index2 < 0 ? 0 : arr2[ index2 ];
if ( s1 > 9  s2 > 9  s1 < 0  s2 < 0 ) {
throw new Exception("Error");
}
int sum = s1 + s2 + mem;
if (sum > 9) {
sum = 10;
mem = 1;
} else {
mem = 0;
}
str = sum + str;
counter++;
}
int[] res = new int[ str.Length ];
for ( int i = 0; i < str.Length; i++ ) {
res[ i ] = int.Parse( str[ i ].ToString() );
}
return res;
}
static void Main(string[] args)
{
GetDigitSum(new int[] {1,2,3}, new int[] {5,5,9,9,2,3});
}
}
}

zr.roman
November 26, 2015 I emulated the case when the method receives a very very very long string, such that the loop "for" will be executed 6.000.000 times. After the loop finished I watched the value of the variable "end": is was "198937535" (negative). So, it means that starting from some moment during execution negative values were being passed to method Arrays.copyOfRange(nums, start, end)".
 zr.roman November 25, 2015c++ implementation.
#include <iostream>
#include <string>
using namespace std;
string GetSumOfBiggest( char *str_pointer ) {
int length = 4;
int sum = (int)*str_pointer  '0';
if ( sum == 13  str_pointer[ 0 ] == '\0' ) {
return "Invalid";
}
str_pointer++;
while ( str_pointer[ 0 ] != '\0' ) {
int maxVal = 0;
for ( int i = 0; i < length; i++ ) {
if ( i % 2 == 0 ) {
str_pointer++; continue;
}
int val = (int)*str_pointer  '0';
if ( val == 13  str_pointer[ 0 ] == '\0' ) {
return "Invalid";
}
maxVal = val > maxVal ? val : maxVal;
str_pointer++;
}
sum += maxVal;
length += 2;
}
return to_string( sum );
}
int main() {
//5#9##4#6#8#0#7#1
//5#9#6#4#6#8#0#7#1
//5#9#6#4#6#8#0#7#1#5
//5#9#6#4#6#8#0#7#1#5#0#7#1#5#6
//5#9#6#4#6#8#0#7#1#5#0#7#1#5#6#0#7#1#5#6#2
char *str_pointer = "5#9#6#4#6#8#0#7#1#5";
cout<< GetSumOfBiggest( str_pointer );
str_pointer = (char *)0xDEADBEEF;
getchar();
return 0;
}

zr.roman
November 25, 2015 possible c# implementation.
using 2 hash tables.
Time complexity O(c), where c  number of most repeated words.
Actually, O(1).
using System;
using System.Collections.Generic;
using System.Linq;
namespace MostRepeatedWords {
public static class WordsAggregator {
private const int MaxNum = 20;
private static readonly Dictionary<string, int> MostRepetedWords = new Dictionary<string, int>();
private static readonly Dictionary<string, int> AllWords = new Dictionary<string, int>();
public static void AddWord( string word ) {
int cnt;
var isWordPresent = AllWords.TryGetValue( word, out cnt );
cnt++;
if ( isWordPresent ) { AllWords[ word ] = cnt; }
else { AllWords.Add( word, cnt ); }
if ( MostRepetedWords.ContainsKey( word ) ) {
MostRepetedWords[ word ]++;
return;
}
int min = 0;
try {
min = MostRepetedWords.Values.Min();
if ( cnt <= min ) {
return;
}
} catch (InvalidOperationException e) when( e.Message.Equals( "Sequence contains no elements" ) ){}
if ( MostRepetedWords.Count == MaxNum ) {
MostRepetedWords.Remove( MostRepetedWords.FirstOrDefault( x => x.Value == min ).Key );
}
MostRepetedWords.Add( word, cnt );
}
public static List<string> GetMostRepeatedWords() {
return MostRepetedWords.Keys.ToList();
}
}
}

zr.roman
November 25, 2015 possible c# implementation.
using System;
using System.Collections.Generic;
using System.Threading;
namespace MaxSoldPrice {
class Program {
private static void PrintPrices() {
var hashTable = new Dictionary<double, int>();
var msp = 0;
string mspStr = null;
foreach ( var rec in GenerateRecords() ) {
int currMax;
if ( hashTable.TryGetValue( rec.Price, out currMax ) ) {
hashTable[ rec.Price ] = currMax + rec.qty;
} else {
hashTable.Add( rec.Price, rec.qty );
}
currMax = hashTable[ rec.Price ];
if ( currMax > msp ) {
msp = currMax;
mspStr = $"{rec.Price}({currMax})";
}
Console.WriteLine($"{rec.Price}, {rec.qty}, {mspStr}");
}
}
private static IEnumerable<PriceRecord> GenerateRecords() {
Random rnd = new Random();
while ( true ) {
Thread.Sleep(1000);
yield return new PriceRecord() { Price = rnd.Next( 1, 10 ), qty = rnd.Next( 1, 20) };
}
}
public struct PriceRecord {
public double Price { get; set; }
public int qty { get; set; }
}
static void Main(string[] args) {
PrintPrices();
}
}
}

zr.roman
November 25, 2015 c# implementation.
using System;
namespace NumberOfSteps {
class Program {
private static int process(int[] arr, int value, ref int i, int initVal) {
if ( arr[ value ] != initVal) {
i++;
process( arr, arr[value], ref i, initVal );
}
return i;
}
private static int length(int[] arr, int val) {
int i = 1;
return process( arr, val, ref i, val );
}
static void Main(string[] args) {
var numOfSteps = length(new int[] {5, 1, 0, 4, 2, 3}, 4);
Console.WriteLine( numOfSteps );
Console.ReadLine();
}
}
}

zr.roman
November 24, 2015 sorry, it is not java script (it is c#), but the idea is in code, you can translate it into java script.
In function I don't use parameter "rootNode". It is because my class "BSTNode" contains reference to parent node.
If it is not allowed, then to obtain parent node just create method with input parameters "rootNode" and "currentNode", and then it will be necessary to change only 1 line in below code as follows:
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), GetParent( rootNode, node ) } ) {
using System.Collections.Generic;
namespace BST {
public static class NodesFinder<T> {
public static BSTNode<T>[] FindNodes( BSTNode<T> rootNode, BSTNode<T> initNode, int distance ) {
var listOfStartNodes = new List<BSTNode<T>> { initNode };
var excList = new List<BSTNode<T>>();
for ( int i = 0; i < distance; i++ ) {
var inclList = new List<BSTNode<T>>();
foreach ( var node in listOfStartNodes ) {
excList.Add( node );
var nearestNodes = new List<BSTNode<T>>();
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), node.GetParent() } ) {
if ( item == null  excList.Contains( item ) ) { continue; }
nearestNodes.Add( item );
}
inclList.AddRange( nearestNodes );
}
listOfStartNodes = inclList;
}
return listOfStartNodes.ToArray();
}
}
}

zr.roman
November 24, 2015 but the variant «to read the 'next' and 'peek' element on initialization, and then advance them both on each 'next()' request» is bad.
Imagine, you have 1 billion elements in collection. When your iterator will point to last element, the Peek() method will work as follows:
1) invoke Next() method;
2) invoke First() method;
3) in loop invoke Next() method (1 billion  1) times.
Moreover, in the initial task there is no method "First()", so if it is really is not allowed then the variant with copying constructor in CIterator is the only one variant.
quite simple task.
O(n).
(the output index is 0based).
using System;
namespace MaxDecimalFrom2DArray {
class Program {
private static int GetMaxDecimalPerRow( int[,] arr ) {
int maxRes = 0;
int retVal = 0;
int pow = arr.GetLength(1);
for ( int i = 0; i < arr.GetLength(0); i++ ) {
int n = pow;
int res = 0;
for ( int j = 0; j < arr.GetLength(1); j++ ) {
res += (int)( arr[ i, j ] * Math.Pow( 2, n ) );
}
if ( res > maxRes ) {
maxRes = res;
retVal = i;
}
}
return retVal;
}
static void Main(string[] args)
{
int[,] arr = new int[3,3] { {0,1,0}, {1,1,0}, {1,0,1} };
Console.WriteLine( GetMaxDecimalPerRow( arr ) );
Console.ReadLine();
}
}
}

zr.roman
November 22, 2015 c# implementation.
using System;
using System.Collections.Generic;
namespace GreatestByConcatenation {
public class MyComparer : IComparer<int> {
public int Compare( int x, int y ) {
if ( x == 0 ) {
return 1;
}
if ( y == 0 ) {
return 1;
}
int numOfDigitsX = (int)Math.Floor( Math.Log10( x ) + 1 );
int numOfDigitsY = (int)Math.Floor( Math.Log10( y ) + 1 );
int XconcatY = (int) ( x * ( Math.Pow( 10, numOfDigitsY ) ) + y );
int YconcatX = (int) ( y * ( Math.Pow( 10, numOfDigitsX ) ) + x );
return XconcatY > YconcatX ? 1 : 1;
}
}
class Program {
private static string GetGreatestByConcatenation( int[] arr ) {
Array.Sort( arr, new MyComparer() );
string greatest = string.Empty;
for ( int i = 0; i < arr.Length; i++ ) {
greatest += arr[ i ];
}
return greatest;
}
static void Main(string[] args) {
//var arr = new int[] { 1, 112, 113 };
var arr = new int[] { 9, 918, 917 };
string greatest = GetGreatestByConcatenation( arr );
Console.WriteLine( greatest );
Console.ReadLine();
}
}
}

zr.roman
November 21, 2015 there is a problem is solution in line
"int present[256] = {0, };"
The problem is in hardcoded value 256. Because symbols with code greater than 255 exist.
With s2 = "1234" and s1 = "ĐÁ" the program fails: it gives the output "ĐÁ", while it should be null.
To improve this, we can create one more loop to obtain the greatest char code as follows (c#):
string bothStrings = s1 + s2;
int greatestCode = 0;
for (int i = 0; i < bothStrings.Length; i++) {
if ( greatestCode < bothStrings[i] ) {
greatestCode = bothStrings[i];
}
}
bool[] present = new bool[ greatestCode + 1 ];
Or, even better to apply sort
string bothStrings = s1 + s2;
var chArr = bothStrings.ToCharArray();
Array.Sort( chArr );
int greatestCode = chArr[ chArr.Length  1 ];
So, the complexity will be O(3n+2k) against O(2n+k) in initial solution. Almost the same, but without the bug.
 zr.roman November 20, 2015c# implementation.
O(k*n), where k, n  lengths of 2 given strings.
static private string GetLargestSubstring( string s1, string s2 ) {
var start = 1;
var end = 1;
var res = string.Empty;
var tmpRes = string.Empty;
for( int i = 0; i < s1.Length; i++ ) {
for( int j = 0; j < s2.Length; j++ ) {
if( s1[ i ] != s2[ j ] ){
end = i;
} else {
if( start == 1 ) start = i;
end = 1;
tmpRes += s1[ i ];
break;
}
}
if( end != 1 && start != 1) {
start = 1;
if( tmpRes.Length > res.Length ){
res = tmpRes;
}
tmpRes = string.Empty;
}
}
return res;
}

zr.roman
November 20, 2015 using hint from the interviewer about a binary tree.
If the number of items in array is odd, then the median will be the root node of the binary search tree.
If the problem requires average of two middle elements in case length is even, then the first element is again the root node of the BST, and the second element will occur on the bigger side of the tree.
In balanced BST with odd number of elements the both sides of the tree contain equal number of elements (obviously). But in balanced BST with even number of elements one side will be bigger by 1 element (obviously as well). (This is in case we don't have duplicates among keys, let's assume this).
So, to obtain the second element in case length is even, we should do the following:
If the left side is bigger, we should take the element from it which is nearest smaller than the root element.
And if the right side is bigger, we should take the element from it which is nearest greater than or equal to the root element.
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();
}
}
}

zr.roman
November 19, 2015 Open Chat in New Window
yes, much better, but some small errors stay.
 zr.roman November 28, 2015For example, for input 22, the output is 5, but should be 4.
For input 222, the output is 67, but should be 66.
For input 10202, the output is 4043, but should be 4042.
etc.
In general, for all the input numbers that do not contain digit "2", the output is always correct, but for the input numbers that contain digit "2", there could be error output.