CareerCup

public class frequency {
	public static int[] digitFreq = int[10];

	public static void treeFreq (BTNode tree) {
		/* Base Case */
		if (tree == null) {
			return;
		}

		/* Visit Node, check digit frequency */
		int number = tree.data;
		do {
			digitFreq[number % 10]++;
			number /= 10;
		} (while number != 0);

		treeFreq(tree.left);	/* Check left sub-tree */
		treeFreq(tree.right);	/* Check right sub-tree */
	}
}

public class BTNode {
	int data;
	BTNode left;
	BTNode right;

	public BTNode {
		data = null;
		left = null;
		right = null;
	}
}

Hrmm... My first thought was just using a hashtable or make your own data structure.
Do an ___-order traversal and every time you get to a node, look at the digit, see if your data structure has it:
a. Has it? K, increment the count of it.
b. Doesn't have it? First time it's come up so start it at zero.

For each digit we use our modified version of put/add. O(n)?

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class BTreePreOrder {

	private Node root;
	private Map<String, Integer> frequencyCounter = null;

	private void treeTravelAndeFindFrequency(Node root) {
		if (root == null)
			return;
		findFrequency(root.getNodeValue());
		treeTravelAndeFindFrequency(root.getLeftNode());
		treeTravelAndeFindFrequency(root.getRightNode());
	}

	private void findFrequency(int value) {
		String valueString = "" + value;
		for (char ch : valueString.toCharArray()) {
			Integer intValue = frequencyCounter.get(""+ch);
			if (intValue != null)
				frequencyCounter.put(""+ch, ++intValue);
			else
				frequencyCounter.put(""+ch, 1);
		}
	}
	
	public void add(int array[]){
		for (int value : array) {
			add(new Node(value));
		}
	}

	public void add(Node node) {
		Node x, y;
		// Assume root is initialized to null
		x = y = root;

		while (x != null) {
			if (x.getNodeValue() > node.getNodeValue()) {
				y = x;
				x = x.getLeftNode();
			} else {
				y = x;
				x = x.getRightNode();
			}
			
		}

		// y will be the parent of node
		if (y == null) {
			root = node;
			return;
		}

		if (y.getNodeValue() > node.getNodeValue())
			y.setLeftNode(node);
		else
			y.setRightNode(node);

		node.setParent(y);
	}

	public void getFrequencyOfEachDigit() {
		frequencyCounter = new HashMap<String, Integer>();
		treeTravelAndeFindFrequency(root);
		for (Entry<String, Integer> entrySet : frequencyCounter.entrySet()) {
			System.out.println(entrySet.getKey() + " " + entrySet.getValue());
		}
	}
	
	class Node {
		private Node rightNode;
		private Node leftNode;
		private Node parent;
		private int nodeValue;
		
		public Node(int nodeValue){
			this.nodeValue = nodeValue;
		}
		
		
		/**
		 * @return the parent
		 */
		public Node getParent() {
			return parent;
		}


		/**
		 * @param parent the parent to set
		 */
		public void setParent(Node parent) {
			this.parent = parent;
		}
		
		
		/**
		 * @return the rightNode
		 */
		public Node getRightNode() {
			return rightNode;
		}


		/**
		 * @param rightNode the rightNode to set
		 */
		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}


		/**
		 * @return the leftNode
		 */
		public Node getLeftNode() {
			return leftNode;
		}


		/**
		 * @param leftNode the leftNode to set
		 */
		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}


		/**
		 * @param nodeValue the nodeValue to set
		 */
		public void setNodeValue(int nodeValue) {
			this.nodeValue = nodeValue;
		}


		/**
		 * @return nodeValue
		 */
		public int getNodeValue() {
			return nodeValue;
		}
	}

	public static void main(String[] args) {
		int[] array = { 1, 2, 9, 12, 123, 123, 4 };
		BTreePreOrder btree = new BTreePreOrder();
		btree.add(array);
		btree.getFrequencyOfEachDigit();
	}
}

A binary Search tree is an ordered binary tree with *NO* duplicates. So, every digit will occur only once in the tree. So, frequency is 1/(total nodes in the tree). So, the problem, to me, boils down to counting the total number of nodes in the tree.

Am I missing anything people? Lemme know please. Thanks.

call this method in any ***order traversal :

Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
public void findFrequency(int data){
if(hash.containsKey(data)){
Integer temp = (Integer) hash.get(data);
temp++;
hash.put((Integer)data,temp);
}
else{
hash.put((Integer)data, 1);
}
}

Hey Brother,


Best thing I have read in a while on this Amazon Interview Question for SDE1s. There should be a standing ovation button. This is a great piece.


When creating a crawler that reads from S3, it would be nice if you could specify the Athena table name. At the moment it takes the name of the S3 folder it crawls.



By the way do you have any YouTube videos, would love to watch it. I would like to connect you on LinkedIn, great to have experts like you in my connection (In case, if you don’t have any issues).


Shukran,
Ajeeth