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
Put all the names from 2.txt into hashset (of hashtabe, in general - into structure with O(1) access).
Perform a loop against "1.txt".
In a loop: if hashset.Contains( <current word from 1.txt> ), then continue. Otherwise - display it on screen.
O(n + m), where n - number of names in 1.txt., m - number of names in 2.txt.
But, as the task says m << n, then asymptotic complexity O(n).
then this is not a matrix, it is 1 element, the other elements are just waste of space.
Moreover, we cannot do such assumptions, because we are not given input, we are given only an algorithm. The input can be whatever. Even if all the elements in the array are the same, we will get to know this only after we have visited all the elements.
с# recursive implementation.
private static string GetSmartSubstr( string str, int n ) {
if ( n > str.Length || n == 0 ) {
return null;
}
if ( n > 0 && ( str.Length == n || str[ n ] == ' ' ) ) {
return str.Substring( 0, n );
}
return GetSmartSubstr( str, --n );
}
c# implementation.
Number of iterations = n*(n+1)*(n+2)/6.
Time complexity: O(n^3).
static private List<int[]> GetAllCombinationsOfTriplets( int[] arr ) {
List<int[]> res = new List<int[]>();
for (int i = 0; i < arr.Length - 2; i++) {
for (int j = i + 1; j < arr.Length - 1; j++) {
for (int k = j + 1; k < arr.Length; k++) {
int a = arr[ i ], b = arr[ j ], c = arr[ k ];
if ( a + b > c && b + c > a && c + a > b ) {
res.Add( new [] { a, b, c } );
}
}
}
}
return res;
}
it's O(n), see the solution (c#):
(upd: actually O(n*m))
static private Hash GetCntOfPossSubstrs( string str, int n ) {
var res = new Hash(); // Hash = Dictionary<string, int>;
for ( int i = 0; i + n <= str.Length; i++ ) {
var sub = str.Substring( i, n );
if ( res.ContainsKey( sub ) ) {
res[ sub ]++;
continue;
}
res.Add( sub, 1 );
}
return res;
}
Quite straightforward.
For storage use hashtable: key - substring, value - count.
In a loop count all occurrences of all substrings of given length.
If substring (key) exists in a hashtable, increment count (value).
Otherwise, insert a new entry in hashtable with value equal to 1.
Time O(n*m).
Space O(n).
hello, ante5273,
that's because I maintain 2 indexes simultaneously: _indexByName and _indexByPhoneNumber. This causes implemented specific logic.
More detailed description I provided below in a comment to Surya's note. Please see there, so that I do not copy paste it from there to here.
looks like this is A127864 or A077917 from oeis.org
According to this reference, the formula is:
F(i) = F(i-1) + 4 * F(i-2) + 2 * F(i-3).
c# implementation.
static private long GetNumberOfCombinations( int n ) {
if ( n <= 0 ) return 0;
long[] seq = { 1, 5, 11 }; // initial items of the sequence, they cannot be calculated, they are obtained empirically.
if ( n < seq.Length + 1 ) {
return seq[ n - 1 ];
}
for ( int i = seq.Length; i < n; i++ ) {
var res = seq[ 2 ] + 4 * seq[ 1 ] + 2 * seq[ 0 ];
seq[ 0 ] = seq[ 1 ];
seq[ 1 ] = seq[ 2 ];
seq[ 2 ] = res;
}
return seq[ 2 ];
}
c# implementation.
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MinimumNumberOfTransformations {
using Graph = Dictionary<string, HashSet<string>>;
public static class WordsTransformer {
//implements BFS
public static string GetMinNumOfTransformations( string startWord, string endWord ) {
// perform here all necessary checks: the words' lengths must be equal, etc...
_startWord = startWord;
_endWord = endWord;
_graph = new Graph();
_counter = 0;
var frontier = new HashSet<string> { _startWord };
while ( frontier.Count != 0 ) {
_counter++;
var tmpHashSet = new HashSet<string>();
foreach ( var word in frontier ) {
//add node
_graph.Add( word, new HashSet<string>() );
//add its descendants
var res = AddDescendants( word );
// if endWord is among descendants - return
if ( res != null ) { return res; }
tmpHashSet.UnionWith( _graph[ word ] );
}
frontier = tmpHashSet;
}
return null;
}
private static string AddDescendants( string word ) {
for ( int i = 0; i < word.Length; i++ ) {
var wordAsCharArr = word.ToCharArray();
foreach ( var ch in Alphabet ) {
wordAsCharArr[ i ] = ch;
var newWord = wordAsCharArr.RestoreString();
AddNewWord( word, newWord );
// if endWord is among descendants of "word" - return
if ( newWord == _endWord ) {
return BuildUpPathAndNumOfSteps( word );
}
}
}
return null;
}
private static string BuildUpPathAndNumOfSteps( string word ) {
string path = word + "->" + _endWord;
var curr = word;
for ( int j = 0; j < _counter-1; j++ ) {
var kvp = _graph.FirstOrDefault( x => x.Value.Contains( curr ) );
curr = kvp.Key;
path = curr + "->" + path;
}
return _counter + ", " + path;
}
private static void AddNewWord( string key, string newWord ) {
if ( Dictionary.Contains( newWord ) &&
!_graph.Values.Any( x => x.Contains( newWord ) ) &&
!_graph.Keys.Any( y => y.Contains( newWord ) ) )
{
_graph[ key ].Add( newWord );
}
}
static string RestoreString( this IEnumerable<char> arr ) {
var chArr = arr.ToArray();
var sb = new StringBuilder();
for( int i = 0; i < chArr.Length; i++ ) {
sb.Append( chArr[ i ] );
}
return sb.ToString();
}
static readonly List<string> Dictionary = new List<string> {
"cot","cog", "sat","sad","car","bar","bag","cab","rat","ray","say","cat", "dog", // etc...
"cut", "cug"
};
static readonly List<char> Alphabet = new List<char> {
'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','r','s','t','u','v','w','x','y','z'
};
private static string _startWord;
private static string _endWord;
private static Graph _graph;
private static int _counter;
}
}
c#.
variant 5 (iterative) (BFS)
static private IEnumerable<Node> Get5( Node node ) {
var res = new List<Node>();
var currList = new List<Node> { node };
while ( currList.Count > 0 ) {
var tmpList = new List<Node>();
for ( int i = 0; i < currList.Count; i++ ) {
var children = currList[ i ].Children;
if ( children == null ) { continue; }
tmpList.AddRange( children );
}
res.AddRange( currList );
currList = tmpList;
}
return res;
}
c#.
variant 4 (recursive) (DFS) (using Linq extension methods)
static private IEnumerable<Node> Get4( Node node ) {
var res = new List<Node> { node };
if ( node.Children == null ) { return res; }
return node.Children.Aggregate( res, (curr, child) => curr.Concat( Get4( child ) ).ToList() );
}
c#.
variant 3 (recursive) (DFS) (using Linq extension methods)
static private IEnumerable<Node> Get3( Node node ) {
var result = new List<Node> { node };
if ( node.Children == null ) { return result; }
return node.Children.Aggregate(result, (current, child) =>
(List<Node>)new AggFunc( // AggFunc = Func<IEnumerable<Node>>;
() => { current.AddRange( Get3( child ) ); return current; } )() );
}
c#.
variant 2 (recursive) (DFS)
private static IEnumerable<Node> Get2( Node node ) {
var result = new List<Node> { node };
if ( node.Children == null ) { return result; }
foreach ( var child in node.Children ) {
var tmpRes = result;
result = (List<Node>)new AggFunc( // AggFunc = Func<IEnumerable<Node>>;
() => { tmpRes.AddRange( Get2( child ) ); return tmpRes; } )();
}
return result;
}
c#.
variant 1 (recursive) (DFS)
private static IEnumerable<Node> Get1( Node node ) {
var result = new HashSet<Node> { node };
if ( node.Children == null ) { return result; }
result.UnionWith( node.Children );
foreach ( var child in node.Children ) {
result.UnionWith( Get1( child ) );
}
return result;
}
c# implementation.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Hash3Columns {
using CustomHashTable = Dictionary<System.DateTime, Dictionary<string, int>>;
class Program {
static CustomHashTable _database = new CustomHashTable();
private static string GetTemperature( string city, DateTime date ) {
try {
return _database[ date ][ city ].ToString();
}
catch (KeyNotFoundException) {
return "No data in database";
}
}
private static string[] GetHottestCities( DateTime date, int n ) {
return _database[ date ]
.OrderByDescending( x => x.Value )
.Take( n )
.Select( y => y.Key )
.ToArray();
}
private static string[] GetColdestCities( DateTime date, int n ) {
return _database[ date ]
.OrderBy( x => x.Value )
.Take( n )
.Select( y => y.Key )
.ToArray();
}
static void Main(string[] args)
{
// code for testing here
}
}
}
it cannot be O(N).
It is O(N*logN), because when you get "an unsorted list", you should apply some sorting algorithm. The fastest sorting algorithms (merge sort, etc.) have complexity O(N*logN) in average and worst cases.
Of course, N is the number of cities in the database.
c# implementation.
using System;
using System.Collections.Generic;
namespace ScoreCombinations {
class Program {
private static void CreateNode( Node prevNode, int i = 0, int j = 0 ) {
Node node;
if ( i + 1 <= a ) {
node = new Node { i = i+1, j = j, Parent = prevNode };
AddToList(node);
CreateNode( node, i+1, j );
}
if ( j + 1 <= b ) {
node = new Node { i = i, j = j+1, Parent = prevNode };
AddToList( node );
CreateNode( node, i, j+1 );
}
}
private static void PrintPath() {
foreach ( var node in list ) {
Stack<Node> stack = new Stack<Node>();
Node currNode = node;
while ( currNode != null ) {
stack.Push( currNode );
currNode = currNode.Parent;
}
while ( stack.Count > 0 ) {
var elm = stack.Pop();
Console.Write( $"({elm.i},{elm.j}) " );
}
Console.WriteLine("\n-------------------");
}
}
private static void AddToList( Node node ) {
if ( node.i == a && node.j == b ) {
list.Add( node );
}
}
static void Main(string[] args) {
SetScore( 2, 3 );
CreateNode( new Node {i = 0, j = 0, Parent = null} );
PrintPath();
Console.ReadLine();
}
private static int a;
private static int b;
static List<Node> list = new List<Node>();
private static void SetScore( int a1, int b1 ) {
a = a1;
b = b1;
}
class Node {
public int i;
public int j;
public Node Parent;
}
}
}
TheShocker1999 said it was the fastest. So, my notice was for him.
I agree with you, with some note:
O(n+nlogn) is quite possible, but it is necessary then to proceed: O(n+nlogn) -> O(n*(1+logn)) -> O(nlogn).
Things like O(4n) are also possible during the process of evaluating. See, always where I use it, I write "O(4n), actually O(n)", meaning: " O(4n), but because 4 - is a constant, actually O(n)". This is ok, I show the process, how I evaluate the complexity.
another part of code for testing the solution.
private static Node<T> GetPrevNodeBeforeGroup<T>( Node<T> headNode, int k ) {
Node<T> prevNodeBeforeGroup = null;
var currNode = headNode;
for ( int i = 0; i < k - 1; i++ ) {
prevNodeBeforeGroup = currNode.NextNode;
currNode = currNode.NextNode;
if ( currNode == null ) { return null; }
}
return prevNodeBeforeGroup;
}
private const int limit = 9;
private const int K = 2;
private static Node<int> CreateSinglyLinkedList( int n = 1 ) {
var node = new Node<int> { Data = n };
if ( n < limit ) {
node.NextNode = CreateSinglyLinkedList( ++n );
}
return node;
}
public class Node<T> {
public T Data { get; set; }
public Node<T> NextNode { get; set; }
}
static void Main(string[] args) {
Node<int> headNode = CreateSinglyLinkedList();
ReverseKBatchNodes( ref headNode, K );
var currNode = headNode;
while ( currNode != null ) {
Console.Write( $"{currNode.Data} " );
currNode = currNode.NextNode;
}
Console.ReadLine();
}
c# implementation.
key function.
private static void ReverseKBatchNodes<T>( ref Node<T> headNode, int k ) {
if ( headNode == null ) { return; }
Node<T> prevNodeBeforeGroup = GetPrevNodeBeforeGroup( headNode, k );
if ( prevNodeBeforeGroup == null ) { return; }
Node<T> currNode = prevNodeBeforeGroup.NextNode;
int counter = -1;
while ( currNode != null ) {
counter++;
if ( counter < k - 1 && currNode.NextNode != null) {
currNode = currNode.NextNode;
continue;
}
var tmpHead = prevNodeBeforeGroup.NextNode;
prevNodeBeforeGroup.NextNode = currNode.NextNode;
currNode.NextNode = headNode;
headNode = tmpHead;
currNode = prevNodeBeforeGroup.NextNode;
counter = -1;
}
}
c# implementation.
the key function.
static private int[] GetSmallestWindow( int[] arr, int[] keys ) {
var occList = GetOccList( arr, keys ); // Get list of key occurences in initial array
int[] target = new int[ occList.Count ];
int minSum = int.MaxValue;
bool next = false;
foreach ( var i in occList ) {
next = i.Value < i.Key.Length;
}
while ( next ) {
int sum = GetSumOfSubtractions( occList );
if ( sum < minSum ) {
minSum = sum;
target = GetArrayOfTargetIndexes( occList );
}
MoveIndexes( occList );
next = GetIfNextIterationIsNeeded( occList );
}
var startPos = target.Min();
var endPos = target.Max();
int[] res = new int[ endPos - startPos + 1 ];
int index = 0;
for (int i = startPos; i <= endPos; i++) {
res[index] = arr[i];
index++;
}
return res;
}
c# implementation.
using System;
namespace SinglyLinkedListReverse {
class Program {
private static void ReverseAltKNodes<T>( ref Node<T> headNode, int k ) {
int i = -1;
var arr = new Node<T>[ k ];
var currNode = headNode;
Node<T> prevNodeBeforeGroup = null;
while ( currNode != null ) {
i++;
if ( i <= k*2 - 1 && i >= k) {
prevNodeBeforeGroup = currNode;
currNode = currNode.NextNode;
i = ( i == k * 2 - 1 ) ? -1 : i;
continue;
}
arr[ i ] = currNode;
if ( currNode.NextNode != null && i < k - 1 ) {
currNode = currNode.NextNode;
continue;
}
var nextNode = currNode.NextNode;
for ( int j = i; j > 0; j-- ){
arr[ j ].NextNode = arr[ j - 1 ];
}
arr[ 0 ].NextNode = nextNode;
if ( prevNodeBeforeGroup == null )
{ headNode = currNode; }
else { prevNodeBeforeGroup.NextNode = currNode; }
currNode = nextNode;
prevNodeBeforeGroup = arr[ 0 ];
arr = new Node<T>[ k ];
}
}
private const int limit = 18;
private static Node<int> CreateSinglyLinkedList( int n = 1 ) {
var node = new Node<int> { Data = n };
if ( n < limit ) {
node.NextNode = CreateSinglyLinkedList( ++n );
}
return node;
}
public class Node<T> {
public T Data { get; set; }
public Node<T> NextNode { get; set; }
}
static void Main(string[] args) {
var headNode = CreateSinglyLinkedList();
ReverseAltKNodes( ref headNode, 4 );
var currNode = headNode;
while ( currNode != null ) {
Console.WriteLine( currNode.Data );
currNode = currNode.NextNode;
}
Console.ReadLine();
}
}
}
careercup has bug with displaying answers.
- zr.roman December 08, 2015If I saw your answer I would not post mine.
The idea is common.