# Score Gathering

• We have a system that records scores. We care about how many times we see the same score, and we want to maintain a rough ordering. We also want to send this information over the wire so that it can be collated with other results. As such we have decided to represent the stream of scores, and the count of how many times we see the same score, as an unbalanced binary search tree.

Your job is to write a method that will take a stream of integer scores, and put them into a tree while counting the number of times each score is seen. The first score from the given list should occupy the root node. Then you need to traverse the tree breadth-first to generate a string representation of the tree. Scores are to be inserted into the tree in the order that they are given.

For example, if you were given the stream of scores: `[4, 2, 5, 5, 6, 1, 4]`.

That would result in the tree with the following structure where each node is represented as `score:count`.

``````     4:2
/ \
2:1 5:2
/     \
1:1     6:1
``````

When serialized this tree is represented by the string: `4:2,2:1,5:2,1:1,,,6:1`

Each `score:count` entry is delimited with a comma. Empty children with a sibling do not output anything, but retain the comma delimiter.

• Is that binary search tree? Should we consider about the tree rotations as in AVL tree?

• I think that it is BST, in each node we store frequency of the vertex.Then raverse by levels. Time complexity will be nlog(n) if it was Red Black or AVL as you mentioned, but I don't expect somebody to write Red Black tree as a part of a task for 45 minutes.

• I got this question in AMXXXX Interview and I got mad for giving a question like this for my experience, did the people think that I am a fresh out of college grad? The last I read about trees is in 2005, its 11 years ago. They gave only 1 question to solve in 1 hour, this question, no MCQs. they need to test skill of people mentioned on the job description or on the Resume but Not a puzzle. Amazon needs to get its shxx together.

Any way after the test, I take a day to cool off and was able to code it in 1.5 hours. Here is the solution, you can figure out a way to get rid of the excess "," at the end. this 50 lines of code costed me a full time job in Seattle. Bull shit.

import java.util.*;

public class ScoreGathering {

``````public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int[] scores = new int[count];
for (int i = 0; i < count; i++) {
scores[i] = sc.nextInt();
}
String stream = gatherScores(scores);
System.out.println(stream);
}

private static String gatherScores(int[] scores) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
Double maxSize = Math.pow(2, scores.length);
int[] tree = new int[maxSize.intValue()];// max possible length
boolean first = true;
for (int score : scores) {
if (counts.containsKey(score)) {
int value = counts.get(score);
counts.put(score, ++value);
} else {
// score doesn't exist, insert Scores to a binary tree in BFS
if (first) {
tree[0] = score;
counts.put(score, 1);
first = false;
} else {
insertScoreToTree(score, tree, 0, scores.length);
counts.put(score, 1);

}
}

}
return constructStream(tree, counts);
}

private static String constructStream(int[] tree, Map<Integer, Integer> counts) {
StringBuilder sb = new StringBuilder();
for (int node : tree) {
if (node > 0) {
sb.append(node).append(":").append(counts.get(node)).append(",");
} else {
sb.append(",");
}
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}

private static void insertScoreToTree(int score, int[] tree, int start, int end) {
if (tree[start] > 0) {
// node exists
if (tree[start] > score) {
insertScoreToTree(score, tree, 2 * start + 1, end);
} else {
insertScoreToTree(score, tree, 2 * start + 2, end);
}
} else {
tree[start] = score;
return;
}
}
``````

}

• @giantleach thank you very much for your code. Don't blame yourself for the interview, just this position has never been your position. Train a lot and you will find your full time job.

• This is a basic BST construction question and BFS tree traversal.
The implementation is following.

``````public class ScoreGathering {
class BST {
int key;
int count;
BST left;
BST right;
BST(int score) {
key = score;
count = 1;
}
public String toString(){
return ""+key+":"+count;
}
}
BST root;
private BST add(int score, BST rt){
if (rt == null) {
return new BST(score);
} else {
if (rt.key == score) {
rt.count++;
} else if (rt.key < score) {
} else {
}
}
return rt;
}

public String getScores(){
if (root == null) return "";
StringBuilder ret = new StringBuilder();
while (! queue.isEmpty() ) {
BST node = queue.pollFirst();
if (ret.length() > 0) {
ret.append(",");
}
if (node != null) {
ret.append(node.toString());
}
}
while (ret.charAt(ret.length()-1) ==',') {
ret.deleteCharAt(ret.length()-1);
}
return ret.toString();
}

public void put(int score){
}

public static void main(String[] args) {
ScoreGathering sol = new ScoreGathering();
int[] input = {3,3,1,4,1,12,9};
for (int i: input) {
sol.put(i);
}
System.out.println(sol.getScores());
}
}
``````

• Here is my solution:

``````static String gatherScores(int[] scores) {
if (scores == null || scores.length == 0)
return "";

Node root = new Node(scores[0], 1);
for (int i = 1; i < scores.length; i++)

StringBuilder sb = new StringBuilder("");
levelOrder(root, sb);
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}

static void addNode(Node root, int score) {
if (root.score == score) {
root.count += 1;
} else if (score < root.score) {
if (root.left == null)
root.left = new Node(score, 1);
else
} else {
if (root.right == null)
root.right = new Node(score, 1);
else
}
}

static void levelOrder(Node root, StringBuilder sb) {
while (!queue.isEmpty()) {
if (queue.getFirst() == null)
sb.append(",");
else {
sb.append(queue.getFirst().toString() + ",");
if (queue.getFirst().left != null || queue.getFirst().right != null) {
}
}
queue.removeFirst();
}
}

private static class Node {
int score, count;
Node left, right;

public Node(int score, int count) {
this.score = score;
this.count = count;
left = right = null;
}

public String toString() {
return score + ":" + count;
}
}
``````

• @elmirap said in Score Gathering:

I think that it is BST, in each node we store frequency of the vertex.Then reverse by levels. Time complexity will be nlog(n) if it was Red Black or AVL as you mentioned, but I don't expect somebody to write Red Black tree as a part of a task for 45 minutes.

The problem statement mentioned an unbalanced binary tree. We don't require AVL trees I think. This just reduces to creating a BST, updating it as required and finally printing it level order.

• C# code, seems to be working, but not sure if filling the left and right branches of the tree is not stupid. Also I didn't use a Stringbuilder, which is a drag :)

``````static void Main(string[] args)
{

int[] scores = { 4, 2, 5, 5, 6, 1, 4 };

var s = scores.ToList();

string result = "";

Node root = new Node() { value = scores[0], occurances = scores.Count(sc => sc == scores[0]) };

var curr = root;

foreach (var score in s.Distinct().Skip(1).Where((c, i) => i % 2 == 0))
{
curr.Right = new Node() { value = score, occurances = scores.Count(sc => sc == score)};
curr = curr.Right;
}

curr = root;

foreach (var score in s.Distinct().Skip(1).Where((c, i) => i % 2 != 0))
{

curr.Left = new Node() { value = score, occurances = scores.Count(sc => sc == score) };
curr = curr.Left;
}

Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0)
{
Node current = q.Dequeue();
if (current == null)
{
result += ',';
continue;
}

if (current.Left != null || current.Right != null)
{
q.Enqueue(current.Left);
q.Enqueue(current.Right);
}

result += current.value.ToString() + ':' + current.occurances.ToString()+',';

}

result=result.TrimEnd(',');

Console.WriteLine(result);
}

public class Node
{
public int value { get; set; }
public int occurances { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
``````

• Here's my untested code:

``` static void Main(string[] args){ FillTree(args); } public void FillTree(int[] scores){ treeNode root; for (int score: scores){ if (root == null){ root = new treeNode(score); continue; } addNode(root, score); } } public String SerializeScoresTree(treeNode root){ // traverse the tree breadth-first treeNode current = root; int currentLevel = 0; ArrayList<TreeNode> fullSerializedList = new ArrayList<TreeNode>(); do { ArrayList<TreeNode> serializedList = new ArrayList<TreeNode>(); SerializeScoresLevelTree(root, currentLevel, 0, serializedList) // check if any non-null nodes are found in the list boolean foundNode = false; for (TreeNode node: serializedList){ if (node != null) { foundNode = true; currentLevel++; // Append values to full result set for (TreeNode node1: serializedList) fullSerializedList.add(node1); break; } } } while (foundNode); // convert array list to string values String result = null; for (TreeNode node: fullSerializedList){ String serializedNode = ""; if (node != null) serializedNode = node.serialize(); if (result == null) result = serializedNode; else result += "," + serializedNode; } return result; } /// It'll return null when level has no more nodes /// Level zero is for root node private void SerializeScoresLevelTree(treeNode node, int targetLevel, int currentLevel, ArrayList<TreeNode> serializedList){ // traverse the tree breadth-first if (targetLevel == currentLevel) serializedList.add(node); else if (node != null) { SerializeScoresLevelTree(node.left, targetLevel, currentLevel + 1); SerializeScoresLevelTree(node.right, targetLevel, currentLevel + 1); } } private void addNode(treeNode current, int value){ if (current.value == score){ current.count++; } else if (score < current.value){ // Add node on left side if (current.left == null) current.left = new treeNode(score); else addNode(current.left, value); } else { // add node on right side if (current.right == null) current.right = new treeNode(score); else addNode(current.right, value); } } public class treeNode{ public treeNode(value){ this.value = value; this.count = 1; } public serialize(){ return value + ":" + count; } int value; int count; treeNode left; treeNode right; } ```

• Java Solution

``````package Amazon;

import java.util.ArrayDeque;
import java.util.Deque;

class TrNode {
int score, count;
TrNode left, right;

public TrNode(int score, int count) {
this.score = score;
this.count = count;
}
}

public class ScoreGathering {

private TrNode getParent(TrNode TrNode, int score) {
if (null == TrNode) {
return null;
}

if (TrNode.score == score) {
return TrNode;
}

TrNode parent;

if (TrNode.score > score) {
parent = getParent(TrNode.left, score);
} else {
parent = getParent(TrNode.right, score);
}

if (null == parent)
return TrNode;

return parent;
}

private void insertToBST(TrNode root, int score) {
TrNode parent = getParent(root, score);

if (parent.score == score) {
++parent.count;
} else if (parent.score > score) {
parent.left = new TrNode(score, 1);
} else {
parent.right = new TrNode(score, 1);
}
}

private String serializeTree(TrNode root) {
Deque<TrNode> q = new ArrayDeque<>();

StringBuilder serializeStr = new StringBuilder();
boolean first = true;

while (!q.isEmpty()) {
int size = q.size();

while (size > 0) {
TrNode TrNode = q.poll();

if (TrNode.count == -1) {
serializeStr.append(",");
} else {
if (!first) {
serializeStr.append(",");
} else {
first = false;
}

serializeStr.append(TrNode.score + ":" + TrNode.count);

if (null != TrNode.left) {
} else {
}

if (null != TrNode.right) {
} else {
}
}
--size;
}
}

return serializeStr.toString();
}

private String insertToTree(int[] stream) {
if (null == stream || stream.length < 1) {
return "";
}

TrNode root = new TrNode(stream[0], 1);

for (int i = 1; i < stream.length; i++) {
insertToBST(root, stream[i]);
}

return serializeTree(root);
}

public static void main(String[] args) {
ScoreGathering sg = new ScoreGathering();
int stream[] = { 4, 2, 5, 5, 6, 1, 4 };

System.out.println(sg.insertToTree(stream));

}

}

``````

• Here's my solution in Python 2.7, though I think it'll work with Python 3 too,

``````from __future__ import print_function
from collections import deque

def insert(number, bs_tree):
if bs_tree:
value = bs_tree.get("value")
if number > value:
insert(number, bs_tree.get("right"))
elif number < value:
insert(number, bs_tree.get("left"))
elif number == value:
bs_tree["count"] = bs_tree.get("count") + 1
else:
bs_tree["value"] = number
bs_tree["count"] = 1
bs_tree["left"] = {}
bs_tree["right"] = {}

if __name__ == '__main__':

bs_tree = {}
values = [4, 2, 5, 5, 6, 1, 4]

for i in values:
insert(i, bs_tree)

queue = deque([bs_tree])

while queue:
node = queue.popleft()
if node:
print(str(node.get("value")) + ":" + str(node.get("count")), end="")
if node.get("left") or node.get("right"):
queue.append(node.get("left"))
queue.append(node.get("right"))
if queue:
print(",", end="")
else:
print(",", end="")
``````

• @dietpepsi

Here is a working Python 3 implementation:

``````import collections

class Node:
def __init__(self, v, count=None):
self.value = v
if count:
self.count = count
else:
self.count = 1
self.left = None
self.right = None

def __str__(self):
return '{}:{}'.format(self.value, self.count)

def insert(self, v):
if v == self.value:
self.count += 1
return
if v < self.value:
if self.left == None:
self.left = Node(v)
else:
self.left.insert(v)
return
if v > self.value:
if self.right == None:
self.right = Node(v)
else:
self.right.insert(v)
return

def to_str(self):
result = ''
open = collections.deque()
open.append(self)
while len(open) > 0:
n = open.popleft()
if n:
result += str(n)
if n.left or n.right:
open.append(n.left)
open.append(n.right)
if len(open) != 0:
result += ','
return result

class BST:
def __init__(self, stream=None):
self.root = None
if stream:
for value in stream:
self.insert(value)

def __str__(self):
return self.root.to_str()

def insert(self, v):
if self.root == None:
self.root = Node(v)
return
self.root.insert(v)
``````

The print function is really the only tricky part of this. You need to do a level print, which means you essentially need to do a breadth first search. It's all there, though.

• ``````public class ScoreGathering {

@Test
public void testScoreGathering() {
int[] score = new int[] { 4, 2, 5, 5, 6, 1, 4 };
Assert.assertThat(gatherScore(score), Is.is("4:2,2:1,5:2,1:1,,,6:1"));
}

private String gatherScore(int[] score) {
if (score == null || score.length < 1) {
return "";
}
Tree<ScoreGathering.Node> bst = new EmptyTree<>();
for (int i = 0; i < score.length; i++) {

Node node = new Node(score[i]);

}
return bst.serialize();
}

public class Node {
public int score;
public int freq;

public Node(int data) {
this.score = data;
this.freq = 1;
}

public Node(int data, int f) {
this.score = data;
this.freq = f;
}

@Override
public String toString() {
if (score == 0) {
return "";
}
return score + ":" + freq;
}
}

interface Tree<D extends Node> {

String serialize();

boolean isEmpty();

D root();

Node[] getChilds(D node);
}

class EmptyTree<Node> implements Tree<ScoreGathering.Node> {

@Override
return new BST<>(node, new EmptyTree<>(), new EmptyTree<>());
}

@Override
public String serialize() {
return "";
}

@Override
public boolean isEmpty() {
return true;
}

@Override
public ScoreGathering.Node root() {
return null;
}

@Override
public ScoreGathering.Node[] getChilds(ScoreGathering.Node node) {
return null;
}
}

class BST<Node> implements Tree {
ScoreGathering.Node root;
Tree<ScoreGathering.Node> leftTree;
Tree<ScoreGathering.Node> rightTree;

public BST(ScoreGathering.Node node, Tree left, Tree right) {
this.root = node;
this.leftTree = left;
this.rightTree = right;
}

@Override
if (root.score == node.score) {
root.freq += 1;
return this;
}
if (root.score > node.score) {
return this;
}
return this;
}

// BFS traverse serialize
@Override
public String serialize() {
if (this.root == null) {
return "";
}

StringBuilder buff = new StringBuilder("");
while (!queue.isEmpty()) {
ScoreGathering.Node node = queue.poll();
if (visited.contains(node)) {
continue;
}
buff.append(node.toString()).append(",");
ScoreGathering.Node[] childs = this.getChilds(node);
if (childs != null) {
}
}
buff.deleteCharAt(buff.length() - 1);
return buff.toString();
}

public ScoreGathering.Node EMPTYNode = new ScoreGathering.Node(0, 0);

public ScoreGathering.Node[] getChilds(ScoreGathering.Node node) {
if (leftTree.isEmpty() && rightTree.isEmpty()) {
return null;
}
ScoreGathering.Node[] childs = new ScoreGathering.Node[2];
if (root.score == node.score) {
if (leftTree.isEmpty()) {
childs[0] = EMPTYNode;
} else {
childs[0] = leftTree.root();
}
if (rightTree.isEmpty()) {
childs[1] = EMPTYNode;
} else {
childs[1] = rightTree.root();
}
return childs;
}
if (root.score > node.score) {
return leftTree.getChilds(node);
}
return rightTree.getChilds(node);
}

@Override
public boolean isEmpty() {
return this.root == null;
}

@Override
public ScoreGathering.Node root() {
return this.root;
}
}
}

``````

• Here is my very basic 48 line Java solution. Unbalanced BST makes this easy. For balanced BST you can in-order serialize the BST to an array then build from that. Or you can store the scores in a HashMap as you read, write the entry set out to an array, sort it and build a balanced BST. Both would be `O(nlogn)` bound

``````public class ScoreGathering {

class Node {
int data, count = 1;
Node left, right;
public Node(int d) { data = d; }
}

Node addToBst(Node bst, int data) {
if (bst == null) {
return new Node(data);
} else {
if (data == bst.data) {
bst.count++;
} else if (data < bst.data) {
} else {
}
return bst;
}
}

String printBFS(Node bst) {
StringBuilder str = new StringBuilder();
while (!queue.isEmpty()) {
if ((bst = queue.poll()) != null) {
str.append(bst.data + ":" + bst.count);
}
str.append(",");
}
while (str.charAt(str.length() - 1) == ',')
str.deleteCharAt(str.length() - 1);
return str.toString();
}

@Test
public void solve() {
Node bst = null;
for (Integer i : new int[] {4,2,5,5,6,1,4}) {
}
assertEquals("4:2,2:1,5:2,1:1,,,6:1", printBFS(bst));
}
}
``````

• This is very helpful to prepare for technical interview!

• @giantleach what role did you apply to?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.