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
use Boyer–Moore (BM) search algorithm.
O(n/m).
In loop in each iteration use BM twice:
1) find nearest "from:" entry,
2) find nearest "to:" entry. (Start from position found in search from step #1).
Collect a pair and go to next iteration, which starts at the position found in search #2 from previous iteration.
true shift implementation.
c#.
private static void ShiftRight( int[,] arr ) {
int n = arr.GetLength( 0 );
if ( n != arr.GetLength( 1 ) ) {
throw new Exception( "This is not a square matrix" );
}
for ( int first = 0; first < n/2; first++ ) {
var last = n - 1 - first;
int[] tmp1 = new int[4]
{
arr[ first, first ], arr[ first, last ], arr[ last , last ], arr[ last , first ]
};
for ( int i = first; i < last; i++ ) {
var offset1 = i + 1;
var offset2 = last - 1 - i + first;
var tmp2 = arr[ first, offset1 ];
arr[ first, offset1 ] = tmp1[ 0 ];
tmp1[ 0 ] = tmp2;
tmp2 = arr[ offset1, last ];
arr[ offset1, last ] = tmp1[ 1 ];
tmp1[ 1 ] = tmp2;
tmp2 = arr[ last, offset2 ];
arr[ last, offset2 ] = tmp1[ 2 ];
tmp1[ 2 ] = tmp2;
tmp2 = arr[ offset2, first ];
arr[ offset2, first ] = tmp1[ 3 ];
tmp1[ 3 ] = tmp2;
}
}
}
this is rotate clockwise solution.
Shift solution see below.
c#.
private static void Rotate( int[,] arr ) {
int n = arr.GetLength( 0 );
if ( n != arr.GetLength( 1 ) ) {
throw new Exception( "This is not a square matrix" );
}
for ( int first = 0; first < n/2; first++ ) {
var last = n - 1 - first;
for ( int i = first; i < last; i++ ) {
var offset = n - 1 - i;
var tmp = arr[ first, i ];
arr[ first, i ] = arr[ offset, first ];
arr[ offset, first ] = arr[ last, offset ];
arr[ last, offset ] = arr[ i, last ];
arr[ i, last ] = tmp;
}
}
}
msdn says "The HashSet<T> class provides high-performance set operations similar to accessing the keys of the Dictionary<TKey, TValue> or Hashtable collections".
So, depending on complexity of Overlaps, total complexity is from at least O(n^2) to at most O(n^2*m^2)
in fact, the idea is the same, the only difference is that the for loop will be in bounds of given subset and ret value without compulsory pairs of "0".
And in loop the will be restriction not to exceed the boundaries of subset, while calculating combinations.
c#.
O(2^k).
static private int Get( int k ) {
int res = 0;
for ( int i = 1; i <= Math.Pow( 2, k ) - 1; i++ ) {
string bin = Convert.ToString( i, 2 );
int cnt = 0;
foreach ( var ch in bin ) {
if ( ch == '0' ) {
cnt++;
}
}
res += (int)Math.Pow( 2, cnt ) - 1;
}
return res + (int)Math.Pow(2, k) - 1;
}
c#.
Brute force.
static private int Get( string[] arr ) {
int greatest = 0;
var list = new List<Tuple<int, HashSet<char>>>();
foreach ( var word in arr ) {
list.Add( new Tuple<int, HashSet<char>>( word.Length, new HashSet<char>( word ) ) );
}
for ( int i = 0; i < list.Count - 1; i++ ) {
for ( int j = i + 1; j < list.Count; j++ ) {
if ( list[ i ].Item2.Overlaps( list[ j ].Item2) ) {
continue;
}
var res = list[ i ].Item1 * list[ j ].Item1;
if ( res > greatest ) {
greatest = res;
}
}
}
return greatest;
}
c#.
Brute force.
static private int Get( string[] arr ) {
int greatest = 0;
for ( int i = 0; i < arr.Length - 1; i++ ) {
var hashSet1 = new HashSet<char>( arr[ i ] );
for ( int j = i + 1; j < arr.Length; j++ ) {
var hashSet2 = new HashSet<char>( arr[ j ] );
var cnt = hashSet1.Count + hashSet2.Count;
hashSet1.UnionWith( hashSet2 );
var res = arr[ i ].Length * arr[ j ].Length;
if ( cnt == hashSet1.Count && res > greatest ) {
greatest = res;
}
}
}
return greatest;
}
c# implementation.
Time: O(nlogn).
Space: O(n).
static private int GetGreatestNumberOfSurpassers( int[] arr ) {
var initIndexes = new Dictionary<int, Queue<int>>();
for ( int i = 0; i < arr.Length; i++ ) {
var currElm = arr[ i ];
if ( initIndexes.ContainsKey( currElm ) ) {
initIndexes[ currElm ].Enqueue( i );
continue;
}
var queue = new Queue<int>();
queue.Enqueue( i );
initIndexes[ currElm ] = queue;
}
Array.Sort( arr ); arr = arr.Reverse().ToArray(); // Merge Sort
int res = 0;
for ( int i = 0; i < arr.Length; i++ ) {
var curr = i - initIndexes[ arr[ i ] ].Dequeue();
if ( curr > res ) {
res = curr;
}
}
return res;
}
multiples of 4 give sequence:
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...
multiples of 6 give sequence:
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...
Combine 2 sequences (but eliminate duplicates):
4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 48, 52, 54, 56, 60, 64, 66, 68, 72, ...
The task is to get the Nth element from combined sequence.
c#.
DFS.
Direction: right to left.
public class Node<T> {
public Node<T> LeftChild;
public Node<T> RightChild;
public T Data;
public Node<T> Neighbor;
public static void SetNeighbors( Node<T> root ) {
_dic = new Dictionary<int, Node<T>>();
_currLevel = -1;
_setNeighbors( root );
}
static private void _setNeighbors( Node<T> node ) {
_currLevel++;
if ( _dic.ContainsKey( _currLevel ) ) {
node.Neighbor = _dic[ _currLevel ];
}
if ( node.RightChild != null ) {
_setNeighbors( node.RightChild );
}
if ( node.LeftChild != null ) {
_setNeighbors( node.LeftChild );
}
_dic[ _currLevel ] = node;
_currLevel--;
}
static private Dictionary<int, Node<T>> _dic;
static private int _currLevel;
}
c#.
Time: O(n*logm + m), where m - arr.Length.
Space: O(m).
static private int GetNthSmallestMultiple( int[] arr, int n ) {
var sortedHash = new SortedList<int, int>();
for ( int i = 0; i < arr.Length; i++ ) {
sortedHash.Add( arr[ i ], i );
}
int current = 0;
while( n > 0 ) {
n--;
current = sortedHash.Keys[ 0 ];
var i = sortedHash[ current ];
var key = current + arr[ i ];
sortedHash.RemoveAt( 0 );
if ( sortedHash.ContainsKey( key ) ) {
key += arr[ i ];
}
sortedHash.Add( key, i );
}
return current;
}
partial overlap cannot be treated the same as "include" relation.
Let's have query (0,1).
Case #1 (include): given [23, 72, 0], [34, 53, 1]. The answer to query is [34, 53].
Case #2 (partial): given [23, 72, 0], [20, 53, 1]. What will be the answer to query (0,1)?
[23, 72] ?
[20, 53] ?
or both?
How to determine answer?
Could you clarify that a little more in detail.
in general good solution.
Collections.sort(col) is O(n*log n).
But Query has running time of 2*n*k, complexity is O(n*k) in all cases (best and worst) because of set.contains (n - number of entries, k - number of tags in query).
set.contains has linear time, and you call it in every iteration.
But this is a possible trade-off for such a task.
now I see your idea, thank you.
But in case of checking only general "overlaps", we gain new problems, for example:
{34, 53, 1} overlaps with {23, 72, 0} ? True.
But what then to give as an answer in case of query (0,1) ?
{34, 53} ? or {23, 72} ? or both ?
No information. We need in worst case 2 more checks to determine which of them contains another one.
So, worst case:
#1: {34, 53} contains {23, 72} ? NO.
#2: {23, 72} contains {34, 53} ? YES.
So, the answer to query (0,1) is {34, 53}.
(But keep in mind we made 2 extra "contains" checks in addition to 1 "overlaps" check to obtain the result. So, we have to take this into consideration, and overall complexity will increase dramatically, n^2 or n^3 or so, need to count).
Examples.
Example1: query: 0,1,2.
We have such path in tree#2: 0 -> 1-> 2. The last node in the path is [40, 50]. This is the answer.
Example2: query: 0, 2. The answer is same as in Example1 ( [40, 50] ), 'cause only 1 path contains 0 and 2 tags.
Example3: query: 1,3. The answer is null. Because in all the trees there are no paths containing both 1 and 3.
Example4: query: 0. The answer is [23, 72] and [100, 128], because 2 trees possess paths containing tag 0, and the last nodes in those paths are [23, 72] and [100, 128].
Example5: query: 2. The answer is [40, 50] and [75, 80], because 2 trees possess path containing tag 2, and the last nodes in those paths are [40, 50] and [75, 80].
thanks for description, but I don't understand why you eliminate the mentioned items from the list of iterations. (NB: I corrected the post a little).
Let's see closer and assume the following situation:
1) 00 contains 10 ? NO.
2) 00 contains 11 ? NO.
Here you say that I can eliminate next iteration, which is:
3) 10 contains 00 ?
But how can I eliminate it if the check will detect YES? But you eliminated it and never got to know that 10 contains 00. In fact before the check you really do not know whether 10 contains 00 or not! We know that 00 does not contain 10 (#1), but this says nothing about the reverse situation. So, we cannot skip it. The same is about the rest iterations from my list (in total 8 iterations).
Let's take the example right from task.
{34, 53} contains {23, 72} ? NO.
And then you skip reverse check: {23, 72} contains {34, 53} ?
The check result is YES, but you never got to know that, you've skipped it.
sorry too, but let's see.
Assume we have tags query 0,1,2,3,4.
Each tag has 2 elements. Assume there are no overlaps at all.
0 with 1 => 12 iterations:
As follows:
1) 00 contains 10
2) 00 contains 11
3) 01 contains 10
4) 01 contains 11
5) 10 contains 00
6) 10 contains 01
7) 11 contains 00
8) 11 contains 01
So, we have 4 elements.
Go to next check: 4 elements with tag 2:
I counted, you will need 14*2 = 28 iterations. (count yourself to verify).
The rest 3 checks even worse.
You have 4 elements in first 2 tags and 8 iterations to check their mutual overlaps.
When you have 6 elements, you need 28 iterations to check their mutual overlaps.
Can you count number of iterations at further checks? It is possible, but it is a combinatorial task.
You have combinatorial complexity, looks like.
here we need data structure called "forest", i.e. set of trees.
Steps:
1) We are given 2D array with 3 columns [startIndex, endIndex, tag].
We take this array, and build forest.
Example: given: [23, 72, 0], [34, 53, 1], [100, 128, 0], [75, 80, 2], [55, 60, 3], [40, 50, 2].
The forest is:
#1 tree: 2 [75, 80]
#2 tree: 0 [23, 72] -> ( 1 [34, 53] -> 2 [40, 50] ) and 3 [55, 50]
#3 tree: 0 [100, 128]
The complexity is O(n* log n): O(log n) for inserting a node into a tree performed n times.
2) Processing queries.
the task is starting from roots find all paths in all trees, containing all the tags from query, and take the last nodes in those paths.
(See examples below in comment).
Complexity of query processing is O(n * log n), n - total number of all nodes in all trees.
c# implementation with DFS. Full testable solution.
O(log n) - insert 1 entry to forest.
O(n) - processing 1 query.
using System;
using System.Collections.Generic;
using System.Linq;
namespace TaggedSubstrs {
public class TaggedPiecesContainer {
// public members
public TaggedPiecesContainer( IEnumerable<int[]> tags ) {
BuildForest( tags );
}
public void AddEntry( int[] entry ) {
// try to add entry to any tree from forest
for (int i = 0; i < _forest.Count; i++) {
if ( _checkTagEntryAgainstNode( entry, _forest[ i ] ) ) {
AddToNode( _forest[ i ], entry );
return;
}
}
// if not added to any tree, then create a new tree
_forest.Add( _addNode( entry) );
}
public IEnumerable<int[]> Query( int[] tags ) {
_resList.Clear();
for ( int i = 0; i < _forest.Count; i++ ) {
_tagsVisited.Clear();
DFS( _forest[ i ], new HashSet<int>( tags ) );
}
foreach ( var node in _resList ) {
yield return node.Value;
}
}
// private members
private void BuildForest( IEnumerable<int[]> input ) {
var inputList = input as IList<int[]> ?? input.ToList();
for ( int i = 0; i < inputList.Count; i++ ) {
AddEntry( inputList[ i ] );
}
}
private void AddToNode( Node node, int[] entry ) {
foreach ( var child in node.Children ) {
if ( _checkTagEntryAgainstNode( entry, child ) ) {
AddToNode( child, entry );
return;
}
}
node.Children.Add( _addNode( entry) );
}
private void DFS( Node node, HashSet<int> tags ) {
_tagsVisited.Add( node.Tag );
// count if path tags match input tags,
// the rule of match specified in task
if ( _tagsVisited.Count >= tags.Count ) {
int cnt = GetTagsMatchesCnt( tags, _tagsVisited );
// we found the target path, so take the node and return
if ( cnt == tags.Count ) {
_resList.Add( node );
return;
}
}
foreach ( var child in node.Children ) {
DFS( child, tags );
// when we go 1 level up, remove the last visited tag
if ( _tagsVisited.Count > 0 ) {
_tagsVisited.RemoveAt( _tagsVisited.Count - 1 );
}
}
}
private int GetTagsMatchesCnt( IEnumerable<int> tags, IEnumerable<int> tagsVisited) {
int cnt = 0;
foreach ( var tagVisited in tagsVisited ) {
if ( tags.Contains( tagVisited ) ) {
cnt++;
}
}
return cnt;
}
private readonly List<Node> _forest = new List<Node>();
private readonly List<int> _tagsVisited = new List<int>();
private readonly List<Node> _resList = new List<Node>();
private readonly Func<int[], Node> _addNode = tagEntry => new Node {
Value = new[] { tagEntry[ 0 ], tagEntry[ 1 ] }, Tag = tagEntry[ 2 ]
};
private readonly Func<int[], Node, bool> _checkTagEntryAgainstNode = (tagEntry, node) => {
return node.Value[ 0 ] <= tagEntry[ 0 ] && node.Value[ 1 ] >= tagEntry[ 1 ];
};
}
public class Node {
public int[] Value;
public int Tag;
public readonly List<Node> Children = new List<Node>();
}
}
BFS.
First scan tree and store all levels in some DS (or DSs) with marking the number of level.
Then using the DS, print all nodes according to the task.
The same is for n-ary tree: BFS eats all trees kinds :)
Quite straightforward.
Space O(n).
Is an O(1) space solution possible?
c#, 2 variants.
using System;
namespace DisplaySeries {
class Program {
// Variant 1
static private void DisplaySeriesV1( int n ) {
for ( int i = 0; i <= n; i++ ) {
var res = (i + 2) * (2 * i * i - i + 3) / 6;
Console.Write($"{res} ");
}
}
// Variant 2
static private void DisplaySeriesV2( int n ) {
var prev = 1;
for (int i = 0; i <= n; i++) {
var res = prev + i * i;
prev = res;
Console.Write($"{res} ");
}
}
static void Main(string[] args)
{
DisplaySeriesV1(10);
Console.WriteLine();
DisplaySeriesV2(10);
Console.ReadLine();
}
}
}
да: "Unicode can be implemented by different character encodings. The most commonly used encodings are UTF-8, UTF-16" (wikipedia).
но суть не в этом, похоже, это задачка на смекалку: как подобрать раздлитель, когда набор символов один и тот же и для разделителя и для самих строк.
c# implementation.
public class BSTBuilder<T> {
public BSTNode<T> BuildTree( IEnumerable<T> collection ) {
var array = collection.ToArray();
Array.Sort( array ); // let's sort just to make sure
var rootNode = _createBSTNode( array, 0, array.Length - 1 );
return rootNode;
}
private static BSTNode<T> _createBSTNode( IReadOnlyList<T> arr, int startPos, int endPos ) {
if ( endPos < startPos ) { return null; }
int midPos = ( startPos + endPos ) / 2;
var bstNode = new BSTNode<T>( arr[ midPos ] );
var leftNode = _createBSTNode( arr, startPos, midPos - 1 );
bstNode.SetLeft( leftNode );
var rightNode = _createBSTNode( arr, midPos + 1, endPos );
bstNode.SetRight( rightNode );
return bstNode;
}
}
"strings can contain any unicode character" - so, there are no exotic characters, because the task says ANY character is possible to be in string. It is the same as: ALL the characters are there among the strings of the array (quite possible variant). So, rare exotic hard coded character will not work.
Frankly, I don't understand your Checkstring() function, looks like, after it you will not be able to restore the array in Deserialize function.
let's see.
In your solution you do "Check(string[i])". - this will cause O(n^2) complexity. And in case of fault (i.e. string contains your delimiter), you will have to start ab ovo: choose another delimiter and start again. And so on. This is not good, not to say bad.
There are no such problems in my solution: my delimiter is by 1 longer than any string of the array => so automatically I do not do any checks, I just go through array, and incrementally create the output. This is O(n) against your O(n^2).
And I use the hint of the interviewer - does not matter how long the delimiter is (as well as the array), I do not worry about the string overflow.
So, I offer O(n) solution. Is it possible to find better solution?
1) Serialize function: you just go through an array and form 1 big string inserting some delimiter string between items of the array. The delimiter string must be exotic in order not to repeat some part of array's items, e.g. "~`*&#]^". The key problem here is to choose the delimiter string.
(Another solution for creating the delimiter string is the following: you scan an array and get the longest possible length of all array's items. Then in loop you create a delimiter string of random characters, which will be longer by 1 then the longest string from array. In this case the total complexity will be O(n), 'cause of 2 loops only). By the way, here goes the hint from the interviewer, if your delimiter string occurs to be quite long as well as with large initial array, you can face string overflow problems, but interviewer knows about that and hints you not to take this into consideration.
That's all.
2) Deserialize function: you take this big string and in loop restore the array, you just take the sequences of chars in between the delimiter strings.O(n).
(The implementation is quite straightforward. If you want, I can provide it.)
modesty.
- zr.roman December 16, 2015