Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
public class TreeNode
{
public TreeNode Left;
public TreeNode Right;
public int Value;
}
private struct ViewHelper
{
public int Level;
public int Value;
}
public static List<int> GetUpperView(TreeNode root)
{
var list = new List<int>();
if (root == null)
return list;
int leftCount = 0;
int rightCount = 0;
GetLimits(root, 0, ref leftCount, ref rightCount);
leftCount = Math.Abs(leftCount);
int n = leftCount + rightCount + 1;
var a = new ViewHelper[n];
a[leftCount].Value = root.Value;
GetUpperView(root, 0, 0, leftCount, a);
foreach (var item in a)
list.Add(item.Value);
return list;
}
// Iterates one on the tree to get the limits, left and right count
private static void GetLimits(TreeNode node, int index, ref int leftCount, ref int rightCount)
{
if (node == null)
return;
leftCount = Math.Min(leftCount, index);
rightCount = Math.Max(rightCount, index);
GetLimits(node.Left, index - 1, ref leftCount, ref rightCount);
GetLimits(node.Right, index + 1, ref leftCount, ref rightCount);
}
private static void GetUpperView(TreeNode node, int row, int level, int leftCount, ViewHelper[] a)
{
if (node == null)
return;
int index = leftCount + row;
if (a[index].Level < level)
{
a[index].Level = level;
a[index].Value = node.Value;
}
GetUpperView(node.Left, row - 1, level + 1, leftCount, a);
GetUpperView(node.Right, row + 1, level + 1, leftCount, a);
}
void top_view(Node root)
{
printleft(root);
printright(root.right);
}
void printleft(Node root){
if (root == null){
return;
}
printleft(root.left);
System.out.print(root.data+" ");
}
void printright(Node root){
if(root == null){
return;
}
System.out.print(root.data+" ");
printright(root.right);
}
public void printTopView(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedBlockingQueue<>();
root.weight = 0;
q.add(root);
Map<Integer, Node> nodeMap = new TreeMap<>();
while (!q.isEmpty()) {
Node node = q.poll();
int weight = node.weight;
//insert weight wise nodes so the latest from below weight will replace the node on vertical
// above weight
if (!nodeMap.containsKey(weight)) {
nodeMap.put(weight, node);
}
if (node.left != null) {
node.left.weight = weight - 1;
q.add(node.left);
}
if (node.right != null) {
node.right.weight = weight + 1;
q.add(node.right);
}
}
nodeMap.forEach((k, v) -> {
System.out.println("" + v.data + " , ");
});
}
struct Node {
int val;
Node *left;
Node *right;
};
vector<int> printTopView(Node *root) {
if (!root) return vector<int>();
vector<int> result;
Node *node = root;
while (!node) {
result.push_back(node->value);
node = node->left;
}
result = reverse(result);
node = root->right;
while(!node) {
result.push_back(node->value);
node = node->right;
}
return result;
}
- Fa1987 March 19, 2017