Microsoft Interview Question for SDE-2s


Country: United States




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

do zig-zag breadth first search and connect right or left at each level

- Anonymous November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

task is written unclear.

- zr.roman November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do zig-zag breadth first search and connect right or left at each level

import random as rd

K = 2
k_bckup = K
''' it means we will first connect current node to the left node and then vice versa'''
left = 1

class node:
			def __init__(self, data):
				self.data = data
				self.l = None
				self.r = None
				self.n = None
				self.next = None
				
class tree:
		def __init__(self):
			self.root = None
		
		def get_root(self):
			return self.root
		
		def add_node(self, node):
			if (self.root == None):
				self.root = node
			else:
				self.__add_node(self.root, node)
		
		def __add_node(self, root, node):
			if (node.data < root.data):
				if (root.l != None):
					self.__add_node(root.l, node)
				else:
					root.l = node
			else:
				if (root.r != None):
					self.__add_node(root.r, node)
				else:
					root.r = node
		
		def printTree(self):
			if self.root != None:
				return self._printTree(self.root)
		
		def _printTree(self, node):
			if node != None:
				self._printTree(node.l)
				print(node.data)
				self._printTree(node.r)
		
		def printNext(self):
			if self.root != None:
				return self._printNext(self.root)
		
		def _printNext(self, node):
			if node != None:
				self._printNext(node.l)
				if node.next != None:
					print(node.data, "->", node.next.data)
				self._printNext(node.r)

def insert(q, node):
		if node != None and node.l != None:
			q.append(node.l)
		if node != None and node.r != None:
			q.append(node.r)			
			
i = tree()
print("adding data to the tree")
for j in range(0, 10):
	number = rd.randint(0, 100)
	print(number)
	i.add_node(node(number))

print("printing inorder tree")
i.printTree()

print("debug")
q = []
q.append(i.get_root())
while len(q) > 0:
	size = len(q)
	prev = None
	if K == 0:
		K = k_bckup
	K -= 1
	if left == 0:
		q.sort(key=lambda x:x.data)
		q.reverse()

	while size:
		temp1 = q.pop(0)
		insert(q, temp1)
		size -= 1
		if prev != None:
			prev.next = temp1
		if size == 0:
			break
		temp2 = q.pop(0)
		insert(q, temp2)
		size -=1 
		if K == 0:
			temp1.next = temp2
			temp2.next = None
			prev = temp2
			left = not left
	
print("next printing")
i.printNext()

- aka November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS and track of the level of each node

- Neelavan April 06, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More