colin@colinday.net
BAN USERThis is pretty vague and could definitely use some more explanation on what they're trying to get at ... but here's my stab at it.
using System;
using System.Collections.Generic;
// -------------------------------------------------------------
class Solution
{
// -------------------------------------------------------------
static void Main(string[] args)
{
List<Node> symbols = new List<Node>();
symbols.Add( buildX() );
symbols.Add( buildY() );
symbols.Add( buildZ() );
int result = evaluate( buildTest(), symbols );
Console.WriteLine( "Result: {0}", result );
}
// -------------------------------------------------------------
enum Type
{
// values
Int, // node defines an int value
Symbol, // node defines a symbol
// operations
Add, // add left and right children
Subtract, // sub left and right children
Multiply, // mul left and right children
// evaluations
Return, // eval right tree and return
// symbol definitions
Assign, // defines a symbol and its value, left symbol is the eval of right
}
// -------------------------------------------------------------
class Node
{
// all nodes have a type decribing what do with with
public Type Type; // the node type
// for nodes that hold values
public string SymbolValue; // symbol value
public int IntValue; // int value
// children nodes as required for anything except int and symbol nodes
public Node Left;
public Node Right;
// constructors
public Node( Type type ) { Type = type; }
public Node( string symbolValue ) { Type = Type.Symbol; SymbolValue = symbolValue; }
public Node( int intValue ) { Type = Type.Int; IntValue = intValue; }
}
// -------------------------------------------------------------
static Node buildX()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "x" );
root.Right = new Node( Type.Add );
root.Right.Left = new Node( 2 );
root.Right.Right = new Node( 3 );
return root;
}
// -------------------------------------------------------------
static Node buildY()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "y" );
root.Right = new Node( Type.Subtract );
root.Right.Left = new Node( 5000 );
root.Right.Right = new Node( 30 );
return root;
}
// -------------------------------------------------------------
static Node buildZ()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "z" );
root.Right = new Node( Type.Multiply );
root.Right.Left = new Node( 50 );
root.Right.Right = new Node( "x" );
return root;
}
// -------------------------------------------------------------
static Node buildTest()
{
Node root = new Node( Type.Return );
root.Right = new Node( Type.Subtract );
root.Right.Left = new Node( "z" );
root.Right.Right = new Node( Type.Multiply );
root.Right.Right.Left = new Node( 1 );
root.Right.Right.Right = new Node( "y" );
return root;
}
// -------------------------------------------------------------
static Node findSymbol( string symbol, List<Node> symbols )
{
// sanity
if (string.IsNullOrEmpty( symbol ) || symbols == null)
{
return null;
}
foreach (Node symbolNode in symbols)
{
if (symbolNode.Left.SymbolValue == symbol)
{
return symbolNode;
}
}
return null;
}
// -------------------------------------------------------------
static int evaluate( Node node, List<Node> symbols )
{
// sanity
if (node == null)
{
throw new System.InvalidOperationException( "Invalid node" );
}
switch (node.Type)
{
// values
case Type.Int: return node.IntValue;
case Type.Symbol:
{
Node symbolNode = findSymbol( node.SymbolValue, symbols );
if (symbolNode == null)
{
throw new System.InvalidOperationException( "Invalid symbol" );
}
return evaluate( symbolNode.Right, symbols );
}
// operations
case Type.Add: return evaluate( node.Left, symbols ) + evaluate( node.Right, symbols );
case Type.Subtract: return evaluate( node.Left, symbols ) - evaluate( node.Right, symbols );
case Type.Multiply: return evaluate( node.Left, symbols ) * evaluate( node.Right, symbols );
// actions
case Type.Return: return evaluate( node.Right, symbols );
// assignments are not evaluated, they define symbols
case Type.Assign: break;
}
throw new System.InvalidOperationException( "Node cannot be evaluated" );
}
}
I see the bulk of the work for this problem to be done just by building trees of page hits and user hits (user visits). We need a tree for all page hits, page hits for a specific user, and user hits (user visits) for a given page.
With super large data sets, additional data structures should be added to build all the users and pages and hits ... so I've added dictionaries (hash tables) to allow for the fast creation of the tree data.
- colin@colinday.net August 31, 2017