Score Gathering


  • 4

    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.


  • 0

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


  • 0

    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.


  • 0
    G

    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;
    	}
    }
    

    }


  • 0

    @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.


  • 5

    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) {
    				rt.right = add(score, rt.right); 
    			} else {
    				rt.left = add(score, rt.left);
    			}
    		}
    		return rt;
    	}
    	
    	public String getScores(){
    		if (root == null) return "";
    		StringBuilder ret = new StringBuilder(); 
    		LinkedList<BST> queue = new LinkedList<BST>();
    		queue.addLast(root);
    		while (! queue.isEmpty() ) {
    			BST node = queue.pollFirst();
    			if (ret.length() > 0) {
    				ret.append(",");
    			} 
    			if (node != null) { 
    				ret.append(node.toString());
    				queue.addLast(node.left);
    				queue.addLast(node.right);
    			}
    		}
    		while (ret.charAt(ret.length()-1) ==',') {
    			ret.deleteCharAt(ret.length()-1);
    		}
    		return ret.toString();
    	}
    	
    	public void put(int score){
    		root = add(score, root);
    	}
    	
    	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());
    	}
    }
    

  • 0
    R

    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++)
    			addNode(root, scores[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
    				addNode(root.left, score);
    		} else {
    			if (root.right == null)
    				root.right = new Node(score, 1);
    			else
    				addNode(root.right, score);
    		}
    	}
    
    	static void levelOrder(Node root, StringBuilder sb) {
    		LinkedList<Node> queue = new LinkedList<Node>();
    		queue.addLast(root);
    		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.addLast(queue.getFirst().left);
    					queue.addLast(queue.getFirst().right);
    				}
    			}
    			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;
    		}
    	}
    

  • 0

    @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.


  • 0
    J

    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);
                Console.ReadLine();
            }
    
            public class Node
            {
                public int value { get; set; }
                public int occurances { get; set; }
                public Node Left { get; set; }
                public Node Right { get; set; }
            }
    

  • 0
    B

    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;
    } 
    

  • 0

    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<>();
    		q.add(root);
    
    		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) {
    						q.add(TrNode.left);
    					} else {
    						q.add(new TrNode(-1, -1));
    					}
    
    					if (null != TrNode.right) {
    						q.add(TrNode.right);
    					} else {
    						q.add(new TrNode(-1, -1));
    					}
    				}
    				--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));
    
    	}
    
    }
    
    

  • 0
    A

    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="")
    

  • 0
    M

    @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.


  • 0
    E
    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]);
          bst = bst.add(node);
    
        }
        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> {
    
        BST<D> add(D node);
    
        String serialize();
    
        boolean isEmpty();
    
        D root();
    
        Node[] getChilds(D node);
      }
    
      class EmptyTree<Node> implements Tree<ScoreGathering.Node> {
    
        @Override
        public BST add(ScoreGathering.Node node) {
          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
        public BST add(ScoreGathering.Node node) {
          if (root.score == node.score) {
            root.freq += 1;
            return this;
          }
          if (root.score > node.score) {
            leftTree = leftTree.add(node);
            return this;
          }
          rightTree = rightTree.add(node);
          return this;
        }
    
        // BFS traverse serialize
        @Override
        public String serialize() {
          if (this.root == null) {
            return "";
          }
          LinkedList<ScoreGathering.Node> queue = new LinkedList<>();
          LinkedList<ScoreGathering.Node> visited = new LinkedList<>();
    
          queue.add(root);
          StringBuilder buff = new StringBuilder("");
          while (!queue.isEmpty()) {
            ScoreGathering.Node node = queue.poll();
            if (visited.contains(node)) {
              continue;
            }
            buff.append(node.toString()).append(",");
            visited.add(node);
            ScoreGathering.Node[] childs = this.getChilds(node);
            if (childs != null) {
              queue.add(childs[0]);
              queue.add(childs[1]);
            }
          }
          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;
        }
      }
    }
    
    
    

  • 0
    T

    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) {
                    bst.left = addToBst(bst.left, data);
                } else {
                    bst.right = addToBst(bst.right, data);
                }
                return bst;
            }
        }
    
        String printBFS(Node bst) {
            Queue<Node> queue = new LinkedList<Node>(Collections.singletonList(bst));
            StringBuilder str = new StringBuilder();
            while (!queue.isEmpty()) {
                if ((bst = queue.poll()) != null) {
                    str.append(bst.data + ":" + bst.count);
                    queue.add(bst.left);
                    queue.add(bst.right);
                }
                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}) {
                bst = addToBst(bst, i);
            }
            assertEquals("4:2,2:1,5:2,1:1,,,6:1", printBFS(bst));
        }
    }
    

  • 0
    M

    This is very helpful to prepare for technical interview!


  • 0
    S

    @giantleach what role did you apply to?


Log in to reply
 

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