Cram These Algos Flashcards
Check if an year is a leap year?
def is_leap(year):
return year % 4 == 0 and (year % 400 == 0 or year % 100 != 0)Reverse a linked list in 10 secs
prev = None
current = head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
head = prev
def reverseList(self, head, prev=None):
if not head:
return prev
curr, head.next = head.next, prev
return self.reverseList(curr, head)
Remember here that prev=None and current = head are the first thing to do otherwise things will mess up.
For animation:
https://www.geeksforgeeks.org/reverse-a-linked-list/
Reverse a doubly linked list
if (not head) or (not head.next):
return head
// No node or only one node
temp = None
current = head
while current:
temp = current.prev
current.prev = current.next
current.next = temp
// Simple swapping of next with previous till here
current = current.prev
// Now as current and previous are swapped, so for // current to point to "next", it should use its swapped // value i.e. prev!
return temp.prev
// Loop runs till current is not None. In last line of last run of while loop, the current becomes None. So new loop never runs and hence the temp never gets to move forward to the last element. It is still at the second last element as it was supposed to move there in the first line of the next loop run which never happened. Hence for the last element, which is now the head as list has been reversed, we return temp.prev as the new head. Here we are using prev and not next for the same reason as stated above.
Find the merge point in two linked lists.
There are multiple solutions like
* Use two loops
* Using difference of node counts so that we can find a point from where both lists are equal and we can traverse them parallely
*Use hashing
But the genius solution is:
Make an iterating pointer like this: it goes forward every time till the end, and then jumps to the beginning of the opposite list, and so on. Create two of these, pointing to two heads. Advance each of the pointers by 1 every time, until they meet. This will happen after either one or two passes.
For those who didn’t understand, count the number of nodes traveled from head1-> tail1 -> head2 -> intersection point and head2 -> tail2-> head1 -> intersection point. Both will be equal(Draw diff types of linked lists to verify this). Reason is both pointers have to travel same distances head1-> IP + head2->IP before reaching IP again. So by the time it reaches IP, both pointers will be equal and we have the merging point.
Visualisation:
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
Inorder using stack
current = root
stack = [] # initialize stack
while True:
# Reach the left most Node of the current Node
if current:
stack.append(current)
current = current.left
# BackTrack from the empty subtree and visit
elif(stack):
current = stack.pop()
print(current.data, end=" ")
# We have visited the node and its left
# subtree. Now, it's right subtree's turn
current = current.right
else:
break
Pre order using stack
stack = []
cur = root
while True:
if cur:
stack.append(cur)
print(cur, end = ' ')
cur = cur.left
elif stack:
cur = stack.pop()
cur = cur.right
else:
break
Post Order traversal? Why is it tricky? Why is it important?
def postOrder(root):
stack = []
cur = root
pop = root
while True:
if cur:
stack.append(cur)
cur = cur.left
elif stack:
top = stack[-1]
# right subtree logic
if top.right and top.right!=pop:
cur = top.right
else:
pop = stack.pop()
print(pop, end = ' ')
cur = None
# right subtree already covered and pushed in
#stack, hence cur = None and not = cur.right as
#in other traversals
else:
break
It is tricky as we can’t just print out the popped element.
>
- Tree deletion: In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node is deleted when both of its left and right sub-trees are deleted. This can be done using post-order traversal only.
>
- It is also used in evaluating Post-fix or Reverse Polish Notation.
Height of a binary tree
def height(root):
if root:
return 1 + max(height(root.left), height(root.right))
else:
return -1Find a toeplitz matrix
for row in range(len(matrix)-1):
if matrix[row][:-1]!=matrix[row+1][1:]:
return False
return True
Convert binary to decimal.
If the binary number is 111.
dec_value = 1*(2^2) + 1*(2^1) + 1*(2^0) = 7
s = list(s)
mul = len(s)-1
result = 0
for dig in s:
result += (dig)*(2**mul)
mul -= 1
return result
Find factors of a number.
def factors(n):
d = 2
while d*d <= n:
exp = 0
while n % d == 0:
exp += 1
n //= d
if exp:
yield d, exp
d += 1
if n:
yield n, 1gcd
def gcd(a, b):
while b:
a, b = b, a % b
return aMerge Two Binary Trees
if t1 and t2:
t1.val+=t2.val
t1.left=self.mergeTrees(t1.left, t2.left)
t1.right=self.mergeTrees(t1.right, t2.right)
return t1
else:
return t1 or t2
Number of days between two dates using formula!
Write a program to count the number of days between two dates.
The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.
Input: date1 = “2019-06-29”, date2 = “2019-06-30”
Output: 1
def f(date):
y, m, d = map(int, date.split(‘-‘))
if m < 3:
m += 12
y -= 1
return 365 * y + y // 4 + y // 400 - y // 100 + d + (153 * m + 8) // 5
return abs(f(date1) - f(date2))
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].self.res = 0
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
self.res = max(self.res,left+right)
return 1+max(left,right)
dfs(root)
return self.res
