## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 6 vote

``````public static void printLevel(TreeNode root , int level,boolean ltr){

if(root == null) return;
if(level == 1) System.out.print(root.data+" ");

else if(ltr == true)  {

printLevel(root.left,level-1,ltr);
printLevel(root.right, level - 1,ltr);
}else {
printLevel(root.right, level - 1,ltr);
printLevel(root.left,level-1,ltr);

}

}

public static void inwardSpiral(TreeNode root){

int h = height(root);

int firstLevel = 1;
int lastLevel = h;

while (firstLevel < lastLevel){

printLevel(root, firstLevel, true);
printLevel(root, lastLevel, false);
firstLevel++;
lastLevel--;
}
}``````

Comment hidden because of low score. Click to expand.
0

In case of odd level we have to add an extra condition for printing mid-level -

``````if(firstLevel==lastLevel)
printLevel(root, firstLevel, true);``````

Comment hidden because of low score. Click to expand.
0

Highly inefficient. Time complexity is O(h^2 * w) (h - tree height, w - tree width).

Comment hidden because of low score. Click to expand.
1
of 1 vote

C#,

``````void PrintInwardSpiralTree(TreeNode root)
{
if (root == null)
return;

var list = new List<List<TreeNode>>();
var currentList = new List<TreeNode>();
var nextList = new List<TreeNode>();

while (currentList.Count > 0)
{
nextList = new List<TreeNode>();
foreach (var node in currentList)
{
if (node.Left != null)
if (node.Right != null)
}
currentList = nextList;
}

int n = list.Count;
int first = 0;
int last = n - 1;
int i = 1;

while (i <= n)
{
if (i % 2 == 1)
{
currentList = list[first];
for (int j = 0; j < currentList.Count; j++)
Console.Write(currentList[j].Value + ", ");
first++;
}
else
{
currentList = list[last];
for (int j = currentList.Count - 1; j >= 0;  j--)
Console.Write(currentList[j].Value + ", ");
last--;
}

i++;
}

Console.WriteLine();
}``````

Comment hidden because of low score. Click to expand.
1
of 3 vote

BFS.
First scan tree and store all levels in some DS (or DSs) with marking the number of level.
Then using the DS, print all nodes according to the task.
The same is for n-ary tree: BFS eats all trees kinds :)
Quite straightforward.
Space O(n).
Is an O(1) space solution possible?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I propose a two step solution here:

1. Using a Depth First Traversal, push all the elements into a stack(S1) with a stub/delimiter in between each level. This can be achieved with a queue(Q) and stack(S1) as follows:

``````Push root element into the queue and then push a delimiter/stub value into the queue
While queue not empty:
dequeue next element
if(!delimiter)
push element into stack S1
enqueue its childern into the queue
else //if delimiter
push a delimiter into both stack and queue``````

2. Using two stacks S1 and S2, pop the levels in the spiral way i.e. pop top level from S1(level 1 of the tree), then pop remaining S1 into S2. Pop first level of S2(level n of binary tree) and pop remaining S2 into S1 and repeat till empty.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printSpiral(Node root) {
final int height = getHeight(root);

int i;
for (i = 0; i < (height / 2); i++) {
printLevelLeftToRight(i + 1, 1, root);
printLevelRightToLeft(height - i, 1, root);
}
if ((height % 2) == 1) {
printLevelLeftToRight(i + 1, 1, root);
}

System.out.println();
}

void printLevelLeftToRight(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}

if (node.left != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.left);
}
if (node.right != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.right);
}
}

void printLevelRightToLeft(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}

if (node.right != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.right);
}
if (node.left != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.left);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

FP implementation in Scala. It is lazily evaluated so it should consume very little memory.

1. transform tree into rows (BFS)
2. generate sequence for traversal and map to rows

``````case class BTree[+T](left: Option[BTree[T]], right: Option[BTree[T]], value: T)

object SpiralTraversal {
def traverse[T](tree: BTree[T]): Iterator[T] = {
type BT = BTree[T]

def visit(nodes: Stream[BT]): (Stream[T], Stream[BT]) = {
nodes.foldLeft((Stream.empty[T], Stream.empty[BT])) {
case ((outT, outRow), node) =>
val nextRow = Stream(node.left, node.right).flatMap {
case Some(subtree) => Stream(subtree)
case _ => Stream.empty
}
(outT ++ Stream(node.value), outRow ++ nextRow)
}
}

def makeRows(trees: Stream[BT]): List[Stream[T]] = {
if (trees.isEmpty) {
return List.empty
}
val (rowT, nextRow) = visit(trees)
List(rowT) ++ makeRows(nextRow)
}

def comb(n: Int, m: Int): Stream[(Int, Boolean)] =
if (n > m) {
Stream.empty
} else if (n == m) {
Stream((n, false))
} else {
(n, false) #::(m, true) #:: comb(n + 1, m - 1)
}

val rows = makeRows(Stream(tree))
comb(0, rows.size - 1).flatMap {
case (rowNumber, reversed) =>
val row = rows(rowNumber)
if (reversed) row.reverse else row
}.iterator
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void inward(TreeNode* root){

int count = 0;
queue<TreeNode*> q;
vector<vector<int> > result;

if(root != NULL){
count++;
q.push(root);
}

while(count != 0){

int newcount = 0;
vector<int> level;

for(int i = 0; i < count; ++i){

TreeNode* curr = q.front();
q.pop();

level.push(curr->val);

if(curr->left){
newcount++;
q.push(curr->left);
}

if(curr->right){
newcount++;
q.push(curr->right);
}
}

result.push_back(level);
count = newcount;
}

int left = 0, right = result.size() - 1;

while(left <= right){

vector<int> level = result[left++];
for(int i : level){
cout << i << " ";
}
cout << endl;

if(left < right){
level = result[right--];

for(int i = level.size() - 1; i >= 0; i--){
cout << i << " ";
}
cout << endl;
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Serialize the tree using BFS and use 2 indexes, from start and end

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using the HashMap and Dequeue as the DS

``````public void printSpiralInwards(Node root){

Map<Integer,ArrayList<Node>> mp = new HashMap<Integer, ArrayList<Node>>();

ArrayList<Node> arrayList = null;
ArrayList<Node> arrayList1 = null;
int i = 0;
if(root == null)
return;

while(queue.size()>1){
Node temp = queue.peekFirst();

arrayList = new ArrayList<Node>();
while(temp!=null){

temp = queue.pollFirst();
System.out.println(" "+ temp.data );

if(temp.left!=null)
queue.offerLast(temp.left);
if(temp.right!=null)
queue.offerLast(temp.right);
temp = queue.peekFirst();
}
mp.put(i++, arrayList);
temp = queue.peekLast();
arrayList1 = new ArrayList<Node>();
while(temp!=null){
temp = queue.pollLast();
System.out.println(" "+ temp.data );
if(temp.right!=null)
queue.offerFirst(temp.right);
if(temp.left!=null)
queue.offerFirst(temp.left);
temp = queue.peekLast();
}
mp.put(i++, arrayList1);
}

while(!de.isEmpty()){
System.out.println(" ");
ArrayList<Node> first = de.pollFirst();
Iterator<Node> itr = first.iterator();
while(itr.hasNext()){
System.out.print(" "+itr.next().data);
}

System.out.println(" ");
ArrayList<Node> sec = de.pollLast();
Iterator<Node> itr1 = sec.iterator();
while(itr1.hasNext()){
System.out.print(" "+itr1.next().data);
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class SpiralTree {
static int getHeight(Node root) {
if (root == null) {
return 0;
}

return 1 + Math.max(getHeight(root.getLeft()), getHeight(root.getRight()));
}

static void printSpiral(Node root) {
if (root == null) {
return;
}

List<Node> nodesList = Arrays.asList(root);
Stack<List<Integer>> stack = new Stack<>();

populateStackNQueue(nodesList, queue, stack, 1, getHeight(root));

while (true) {
if (queue.isEmpty() && stack.isEmpty()) {
break;
}

if (!queue.isEmpty()) {
List<Integer> valuesList = queue.poll();
for (Integer value : valuesList) {
System.out.print(" " + value);
}
}

if (!stack.isEmpty()) {
List<Integer> valuesList = stack.pop();

for (int i = valuesList.size()-1; i >= 0; i--) {
System.out.print(" " + valuesList.get(i));
}
}
}
}

static void populateStackNQueue(List<Node> nodesList, Queue<List<Integer>> queue, Stack<List<Integer>> stack,
int level, int height) {
if (nodesList.size() == 0) {
return;
}

List<Node> childNodesList = new ArrayList<>();

List<Integer> valuesList = new ArrayList<>(nodesList.size());

for (Node node : nodesList) {

if (node.getLeft() != null) {
}

if (node.getRight() != null) {
}
}

if (level <= ((height + 1) / 2)) {
} else {
}

populateStackNQueue(childNodesList, queue, stack, level + 1, height);
}

public static void main(String[] args) {
Node root = new Node(1,
new Node(2, new Node(4, new Node(8), new Node(9)), new Node(5, new Node(10), new Node(11))),
new Node(3, new Node(6, new Node(12), new Node(13)), new Node(7, new Node(14), new Node(15))));
printSpiral(root);
}
}

class Node {
private int value;
private Node left;
private Node right;

public Node(int value) {
super();
this.value = value;
}

public Node(int value, Node left, Node right) {
super();
this.value = value;
this.left = left;
this.right = right;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public Node getLeft() {
return left;
}

public void setLeft(Node left) {
this.left = left;
}

public Node getRight() {
return right;
}

public void setRight(Node right) {
this.right = right;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.