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
unclear task.
initially written: "Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path".
According to this task the answer is:
(E,F)
(E,G)
(E,H)
(E,D
(F,D)
(G,D)
(H,D)
Everything is clear.
Why is note added there?
sliding window is quite a broad range of algorithms depending on the case you program for.
Let's assume that we already given 3 arrays of start indexes.
Could you provide the based on sliding window solution that takes these 3 arrays + initial string and outputs the desired substring ?
c# implementation.
O(n).
using System;
using System.Collections.Generic;
namespace OneSubstringOfThree {
class Program {
static private string GetSubstr( string s, string t1, string t2, string t3 ) {
int[] arrT1; int[] arrT2; int[] arrT3;
GetListsOfStartIndexes(out arrT1, out arrT2, out arrT3, s, t1, t2, t3 );
Array.Sort(arrT1); Array.Sort(arrT2); Array.Sort(arrT3);
int index1 = 0; int index2 = 0; int index3 = 0;
int[] target = new int[3];
int minSum = int.MaxValue;
int length = 0;
while ( index1 < arrT1.Length && index2 < arrT2.Length && index3 < arrT3.Length ) {
int sum = Math.Abs(arrT1[index1] - arrT2[index2])
+ Math.Abs(arrT1[index1] - arrT3[index3])
+ Math.Abs(arrT3[index3] - arrT2[index2]);
var i1 = arrT1[index1]; var i2 = arrT2[index2]; var i3 = arrT3[index3];
if (sum < minSum) {
minSum = sum;
target[0] = i1;
target[1] = i2;
target[2] = i3;
var minVal = Math.Min(i1, Math.Min(i2, i3));
int maxVal = 0;
int tLen = 0;
GetMaxValAndTLen( ref maxVal, ref tLen, i1, i2, i3, t1, t2, t3 );
length = maxVal + tLen - minVal;
}
if (arrT1[index1] > arrT2[index2]) { index2++; continue; }
if (arrT1[index1] > arrT3[index3]) { index3++; continue; }
index1++;
}
var res = s.Substring( Math.Min(target[0], Math.Min(target[1], target[2])), length );
return res;
}
static private void GetMaxValAndTLen(ref int maxVal , ref int tLen, int i1, int i2, int i3, string t1, string t2, string t3 ) {
if (i1 > i2 && i1 > i3) { tLen = t1.Length; maxVal = i1; return; }
if (i2 > i1 && i2 > i3) { tLen = t2.Length; maxVal = i2; return; }
if (i3 > i1 && i3 > i2) { tLen = t3.Length; maxVal = i3; return; }
if (i1 == i2 && i1 == i3) { maxVal = i1; tLen = Math.Max(t1.Length, Math.Max(t2.Length, t3.Length)); return; }
if (i1 == i2) { maxVal = i1; tLen = Math.Max(t1.Length, t2.Length); return; }
if (i1 == i3) { maxVal = i1; tLen = Math.Max(t1.Length, t3.Length); return; }
if (i2 == i3) { maxVal = i2; tLen = Math.Max(t2.Length, t3.Length); }
}
// use KMP instead, but this func is still O(n)
private static void GetListsOfStartIndexes(out int[] arrT1 , out int[] arrT2, out int[] arrT3, string s, string t1, string t2, string t3 ) {
var listT1 = new List<int>();
var listT2 = new List<int>();
var listT3 = new List<int>();
for ( int i = 0; i < s.Length; i++ ) {
if (s[i] == t1[0]) { CheckAndAdd( s, t1, i, listT1 ); }
if (s[i] == t2[0]) { CheckAndAdd( s, t2, i, listT2 ); }
if (s[i] == t3[0]) { CheckAndAdd( s, t3, i, listT3 ); }
}
arrT1 = listT1.ToArray();
arrT2 = listT2.ToArray();
arrT3 = listT3.ToArray();
}
private static void CheckAndAdd(string s, string t, int i, List<int> _list ) {
if (t.Length <= s.Length - i && s.Substring(i, t.Length) == t) {
_list.Add(i);
}
}
static void Main(string[] args) {
var res = GetSubstr("00as0de00000as00bp1000de000bp000as000de120bp", "as", "bp1", "de");
Console.WriteLine( res );
Console.ReadLine();
}
}
}
yes, much better, but some small errors stay.
For 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.
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();
}
}
}
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();
}
}
}
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});
}
}
}
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;
}
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();
}
}
}
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();
}
}
}
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();
}
}
}
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();
}
}
}
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 0-based).
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();
}
}
}
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();
}
}
}
there is a problem is solution in line
"int present[256] = {0, };"
The problem is in hard-coded 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;
}
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.
solution does not work.
- zr.roman November 29, 2015string s = "00as0de00000as00bp1000de000bp000as000de120bp";
string t[3] = { "bp1", "de", "as" };
It says : "bp1: substring not found".