sumitgaur.iiita
BAN USERclass NodeLockUnlock:
def __init__(self, d):
self.val = d
self.left = self.right = self.parent = None
self.Count_of_locked_descendants = 0
self.isLocked = False
def isLock(self):
return self.isLocked
def _increase_lock_count_ancestor(self):
node = self
while node:
node.Count_of_locked_descendants += 1
def _decrease_lock_count_ancestor(self):
node = self
while node:
node.Count_of_locked_descendants -= 1
def lock(self):
cur = self
while cur and not cur.isLocked:
cur = cur.parent
if cur == None and self.Count_of_locked_descendants == 0:
self.isLocked = True
self._increase_lock_count_ancestor()
return True
return False
def unLock(self):
self.isLocked = False
self._decrease_lock_count_ancestor()
return True
def array_split(arr, k):
res = [[] for _ in range(k)]
i = len(arr) - 1
for l in xrange(k):
res[l].append(arr[i])
i -= 1
while i >= 0:
min_list = get_list_with_min_sum(res)
min_list.append(arr[i])
i -= 1
return res
def get_list_with_min_sum(res):
min_list = None
for l in res:
if min_list == None or sum(l) < sum(min_list):
min_list = l
return min_list
print array_split([1, 3, 6, 9, 10], 3)
def row_max_1s(mat):
m = len(mat)
n = len(mat[0])
j = len(mat[0]) - 1
cur_row = 0
while cur_row < len(mat):
while j >= 0 and mat[cur_row][j] == 1:
j -= 1
if j < 0:
return cur_row
cur_row += 1
return cur_row
def combinations(s):
if s:
ind_s = index_of(s, 's')
ind_a = index_of(s, 'a')
i = ind_a
if ind_s != -1:
i = ind_s
if ind_a != -1:
i = min(ind_s, ind_a)
if i != -1:
combs = combinations(s[i + 1:])
return [s] + [s[:i] + rep[s[i]] + c for c in combs]
return [s]
return []
def index_of(s, ch):
try:
return s.index(ch)
except:
return -1
largest = None
max_node_count = 0
def largest_bst(root, allowed_min, allowed_max):
global largest, max_node_count
if root == None:
return 0, None
if allowed_min < root.key < allowed_max:
leftnodes, left_child = largest_bst(root.left, allowed_min, root.key)
rightnodes, right_child = largest_bst(root.right, root.key, allowed_max)
p = Node(root.key)
p.left = left_child
p.right = right_child
if leftnodes + rightnodes + 1 > max_node_count:
max_node_count = leftnodes + rightnodes + 1
largest = p
return leftnodes + rightnodes + 1, p
else:
_, _ = largest_bst(root, -sys.maxint, sys.maxint)
return 0, None
printing in reverse order but in single pass to tree using power of recursion
def longest_path(tree, longest_path_arr):
if tree:
lh = longest_path(tree.left, longest_path_arr)
rh = longest_path(tree.right, longest_path_arr)
if lh > rh:
if tree.left:
longest_path_arr.append(tree.left.val)
return 1 + lh
else:
if tree.right:
longest_path_arr.append(tree.right.val)
return 1 + rh
return 0
def return_parent(tree, x, par):
if tree:
if tree.val == x:
return par
return return_parent(tree.left, x, tree) or return_parent(tree.right, x, tree)
return None
class Trie:
def __init__(self):
self.root = {'words_count': 0}
def add(self, word):
cur = self.root
for letter in word:
if letter not in cur:
cur[letter] = {'words_count': 1}
else:
cur[letter]['words_count'] += 1
cur = cur[letter]
cur['END'] = True
self.root['words_count'] += 1
def find(self, word):
cur = self.root
for letter in word:
if letter not in cur:
return 0
cur = cur[letter]
return cur['words_count']
class Trie:
def __init__(self):
self.root = {'words_count': 0}
def add(self, word):
cur = self.root
for letter in word:
if letter not in cur:
cur[letter] = {'words_count': 1}
else:
cur[letter]['words_count'] += 1
cur = cur[letter]
cur['END'] = True
self.root['words_count'] += 1
def find(self, word):
cur = self.root
for letter in word:
if letter not in cur:
return 0
cur = cur[letter]
return cur['words_count']
class Trie:
def __init__(self):
self.root = {'words_count': 0}
def add(self, word):
cur = self.root
for letter in word:
if letter not in cur:
cur[letter] = {'words_count': 1}
else:
cur[letter]['words_count'] += 1
cur = cur[letter]
cur['END'] = True
self.root['words_count'] += 1
def find(self, word):
cur = self.root
for letter in word:
if letter not in cur:
return 0
cur = cur[letter]
return cur['words_count']
def convert_to_LL_util(num):
if num:
last_digit = num % 10
node = ListNode(last_digit)
head, tail = convert_to_LL_util(num / 10)
if not tail:
return node, node
tail.next = node
return head, node
else:
return None, None
def convert_to_LL(num):
sign = 1
if num < 0:
sign = -1
h, _ = convert_to_LL_util(num * sign)
h.val *= sign
return h
def convert(n):
res=''
for j in range(len(n) - 1, -1, -2):
if j==0:
res=str(int(n[j]))+res
else:
res = str(int(n[j-1] + n[j],2)) + res
return res
def isPermutaion(s,dict):
for each in dict:
s=s.replace(each,'')
return s ==''
def sort_stack(st):
res_st = []
while len(st):
elt = st.pop()
while len(res_st) and res_st[-1] < elt:
st.append(res_st.pop())
res_st.append(elt)
return res_st
def height_n_ary(tree):
if tree:
return 1 + max(height_n_ary(x) for x in tree.children)
return 0
def cloneGraph(self, node):
clone_node = UndirectedGraphNode(node.label)
cloned_map = {node: clone_node}
self.__cloneGraph(node, clone_node, cloned_map,set())
return clone_node
def __cloneGraph(self, node, clone_node, cloned_map,visited):
#import pdb;pdb.set_trace()
if node in visited:
return
visited.add(node)
for neighbor in node.neighbors:
if neighbor in cloned_map:
clone_neighbor = cloned_map[neighbor]
else:
clone_neighbor = UndirectedGraphNode(neighbor.label)
cloned_map[neighbor] = clone_neighbor
clone_node.neighbors.append(clone_neighbor)
self.__cloneGraph(neighbor, clone_neighbor, cloned_map,visited)
def primes(n):
primfac = []
d = 2
while d * d <= n:
factor = False
pow=0
while (n % d) == 0:
factor = True # supposing you want multiple factors repeated
n /= d
pow+=1
if factor:
primfac.append((d,pow))
d += 1
if n > 1:
primfac.append(n)
return primfac
def make_perfect_square(n):
prime_factors=primes(n)
smallest=1
for (prime,pow) in prime_factors:
#pow is odd
if pow &1 :
smallest*=prime
return smallest
def multiple(n):
q = Queue.Queue()
q.put('1')
while True:
cur_num = q.get()
if int(cur_num) % n == 0:
return cur_num
q.put(cur_num+'0')
q.put(cur_num+'1')
def connect(self, root):
import Queue
q = Queue.Queue()
q.put(root)
while not q.empty():
size = q.qsize()
head=None
while size > 0:
r = q.get()
if head:
head.next=r
head=r
if r.left:
q.put(r.left)
if r.right:
q.put(r.right)
size -= 1
return root
def flatten_util(self,root):
if root:
# if root.left == None and root.right == None:
# return root, root
append = root
x=root.right
if root.left:
left_ll, left_last = self.flatten_util(root.left)
root.right = left_ll
root.left = None
append = left_last
if x:
right_ll, right_last = self.flatten_util(x)
append.right = right_ll
append.left = None
append = right_last
#print_ll(root)
#print
return root, append
def closesPoints(points, k):
priority_queue = []
for point in points:
dist_from_origin = math.pow(point[0], 2) + math.pow(point[1], 2)
priority = dist_from_origin
heapq.heappush(priority_queue, (priority, point))
k_closest = []
while k:
k_closest.append(heapq.heappop(priority_queue))
k -= 1
return k_closest
import math
class Data(object):
def __init__(self, name):
self.__name = name
self.__links = set()
@property
def name(self):
return self.__name
@property
def links(self):
return set(self.__links)
def add_link(self, other):
self.__links.add(other)
other.__links.add(self)
# The function to look for connected components.
def connected_components(nodes):
# List of connected components found. The order is random.
result = []
# Make a copy of the set, so we can modify it.
nodes = set(nodes)
# Iterate while we still have nodes to process.
while nodes:
# Get a random node and remove it from the global set.
n = nodes.pop()
# This set will contain the next group of nodes connected to each other.
group = {n}
# Build a queue with this node in it.
queue = [n]
# Iterate the queue.
# When it's empty, we finished visiting a group of connected nodes.
while queue:
# Consume the next item from the queue.
n = queue.pop(0)
# Fetch the neighbors.
neighbors = n.links
# Remove the neighbors we already visited.
neighbors.difference_update(group)
# Remove the remaining nodes from the global set.
nodes.difference_update(neighbors)
# Add them to the group of connected nodes.
group.update(neighbors)
# Add them to the queue, so we visit them in the next iterations.
queue.extend(neighbors)
# Add the group to the list of groups.
result.append(group)
# Return the list of groups.
return result
# The test code...
def minimalCost(n, pairs):
nodes_map = {x: Data(x) for x in xrange(1, n + 1)}
for pair in pairs:
p, q = int(pair.split(' ')[0]), int(pair.split(' ')[1])
nodes_map[p].add_link(nodes_map[q])
# Find all the connected components.
cost = 0
for components in connected_components(nodes_map.values()):
# names = sorted(node.name for node in components)
# print names
cost += math.ceil(math.sqrt(len(components)))
return long(cost)
def closest_key(root):
bst_itr = BstIterator(root)
prev_key = sys.maxint
while bst_itr.has_next():
node_key = bst_itr.next().key
if key < node_key:
break
prev_key = node_key
if abs(node_key - key) < abs(prev_key - key):
closest = node_key
else:
closest = prev_key
return closest
def maxConsecutivePathLength(root, path, prev_max, path_len):
if root:
if root.key > prev_max:
left_length, left_path = maxConsecutivePathLength(root.left, path + [root.key], root.key, path_len + 1)
right_length, right_path = maxConsecutivePathLength(root.right, path + [root.key], root.key, path_len + 1)
return (left_length, left_path) if max(left_length, right_length) == left_length \
else (right_length, right_path)
else:
left_length, left_path = maxConsecutivePathLength(root.left, [], root.key, 1)
right_length, right_path = maxConsecutivePathLength(root.right, [], root.key, 1)
p = [path, left_path, right_path]
l = [path_len, left_length, right_length]
return max(l), p[l.index(max(l))]
return path_len, path
def can_connect(s1, s2):
ALLOWED_DIFF = 1
l1 = len(s1)
l2 = len(s2)
if l1 > l2:
l = l2
else:
l = l1
diff = 0
ALLOWED_DIFF -= abs(l1 - l2)
for i in xrange(l):
if s1[i] != s2[i]:
diff += 1
if diff > ALLOWED_DIFF:
return False
return True
string_node_map = {}
d = DoubleList()
def first_non_repeated(input_str):
if input_str in string_node_map:
val_ = string_node_map[input_str]
if val_[0]:
d.remove(input_str)
string_node_map[input_str] = (True, None)
else:
new_node = d.append(input_str)
string_node_map[input_str] = (True, new_node)
return d.head.data
def are_all_leaves_at_same_level(root, l):
if root:
left_height, is_balance_left = are_all_leaves_at_same_level(root.left, l + 1)
right_height, is_balance_right = are_all_leaves_at_same_level(root.right, l + 1)
if not (is_balance_left and is_balance_right):
return -1, False
return (left_height, True) if left_height == right_height else (-1, False)
return l, True
def height_diff(root, n1, n2, l, height):
if root:
if root.key == n1 or root.key == n2:
height.append(l)
height_diff(root.left, n1, n2, l + 1, height)
height_diff(root.right, n1, n2, l + 1, height)
def get_height_diff(root, n1, n2):
height = []
height_diff(root, n1, n2, 0, height)
return abs(height[0] - height[1])
instead of using hashmap requiring auxiliary space , we can use two integers - 1 bit vector(check) to keep whether a character has already been appeared or not and a parallel bit vector to keep track of candidate repeating chars .
int check = 0x00000000;
int candidate = 0xFFFFFFFF;
for each char in string
int ch = 1<<char-'a'
if(candidate&ch)
if check & ch
candidate&=~ch
check|=ch
iterate over the string again and check the first candidate
for each char in string
int ch=1<<char-'a'
if(candidate&ch)
return char
make a hashMap: Z+ -> {-1,0,+1}
0 if not exists
+1 if +ve value exists
-1 if -ve value exists
for each elt in array
if map[|elt|]
return (map[|elt|]*|elt| + elt ==0)
if elt<0
map[|elt|]=-1
else
map[|elt|]=+1
RepGigiTaylor, abc at 8x8
Dedicated English Mandarin Chinese translator with years of experience working in professional and scientific communities.Voracious reader and participant in ...
Replindagwingard, Android test engineer at ABC TECH SUPPORT
Hello, my name is Larry and I am a commercial loan officer. We are commercial loan officers who specialize in ...
Repanayadonal67, Animator at ABC TECH SUPPORT
AnayaDonal and I am a City planners. I have completed all my studies from Chicago. It's been a long ...
Repbarrondanielle057, Android test engineer at A9
My name is Danielle and I am working as a Contract manager. I love this job.and nowadays I am ...
Repandrealmoore45, Analyst at 247quickbookshelp
My name is Andrea and I Live in california. I like to read articles from some interesting topics.And today ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
Repnetteyoder22, Applications Developer at 247quickbookshelp
Nette, transportation inspector inspects goods and equipment associated with transporting people or cargo to ensure safety. I typically work for ...
RepAlicaKnight, Blockchain Developer at ABC TECH SUPPORT
Alica , an Employment Consultant with extraordinary achievements in providing beneficial career consultation, organizing various workshops and webinars, and helping clients ...
RepShivelyFauver, Animator at AMD
Project Management Assistant with a proven record in developing and managing project budgets, completing presentations and reports. As nowadays astrology ...
Repearlenecnicely77, Animator at 247quickbookshelp
Hey, I'm a Receiving clerk. And I love my work. Apart from this, I am doing some new experiments ...
Repdelioshorn, Member Technical Staff at Atmel
Attentive Teller Supervisor with 4 years of experience in assisting customers to meet financial needs and referring customers to partners ...
RepEmilioOtten, Applications Developer at ASU
I am Emilio, and I am currently the Medical Interpreter at Suy bank Hospital in Ohio , where I confidentially interpret ...
a1a2|a3a4 b1b2|b3b4 c1c2|c3c4
- sumitgaur.iiita February 12, 2018a1a2|b1b2|a3a4|b3b4|c1c2c3c4
a1a2|b1b2|a3a4|c1c2|b3b4c3c4
(a1a2b1b2c1c2)(a3a4b3b4c3c4)