friends pairing problem

Given n friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.

Examples:

Input : n = 3 Output : 4 Explanation {1}, {2}, {3} : all single {1}, {2,3} : 2 and 3 paired but 1 is single. {1,2}, {3} : 1 and 2 are paired but 3 is single. {1,3}, {2} : 1 and 3 are paired but 2 is single. Note that {1,2} and {2,1} are considered same.

Thinking process:

for n =0 , there are no friends to pair , so return 0 for n=1, there is only one person, only way is that he being single, so return 1 for n=2, there are two ways. {{1}, {2}} and {{1,2}} for n =3 , there are 4 ways {{1},{2},{3}} {{1,2},{3}} {{1,3},{2}} {{2,3},{1}} for n=4, There are 10 ways. for n=5, there two ways. One is we can keep the 5th member single and pair others and the other one is pair the 5th guy with some guy

= f[4] (5th guy is single and we pair the rest) + (n-1)C1 * (f[3]) (select one from the remaining guys and pair with him and multiply it with the number of ways of the rest) f[n] = f[n-1] + (n-1)*f[n-2]

def findpairs(num):
    if num<=0:
        return 0
    if num==1:
        return 1
    if num==2:
        return 2
    res = [0]*(num+1)
    res[0] = 0
    res[1] = 1
    res[2] = 2

    for i in range(3,num+1):
        res[i] = res[i-1] + (i-1)*res[i-2]

    return res[num]

Length of maximum palindrome list in a given linked list

Given a linked list, find length of the longest palindrome list that exist in that linked list.

Examples:

Input : List = 2->3->7->3->2->12->24 Output : 5 The longest palindrome list is 2->3->7->3->2

Input : List = 12->4->4->3->14 Output : 2 The longest palindrome list is 4->4

Brute force is approach is to generate all possible lists in O(n^2) and check if each list is a palindrome O(n). That would be a O(n^3) solution.

Another interesting approach , I came across , is that during the iterative reversal of linkedlist, at each node , we can check for the palindrome nodes by passing reversed half of the list and the rest from that node. To count nodes, it would take O(n) and iterative traversal would take O(n). It's a O(n^2) solution.

class ListNode():
  def __init__(self,val):
    self.val = val
    self.next = None

class solution():
  def maxLinkedList(self,head):
    if not head:
      return 0
    res = 1
    next = prev = None
    curr = head

    while curr:
      next = curr.next
      curr.next = prev
      res = max(res, self.countNodes(curr,next) , self.countNodes(prev,next)+1)
      prev = curr
      curr = next
    return res

  def countNodes(self,start1,start2):
    res = 0
    while start1 and start2:
      if start1.val == start2.val:
        res+=1
        start1 = start1.next
        start2 = start2.next
      else:
        return 2*res
    return 2*res

def main():
  head = ListNode(1)
  print solution().maxLinkedList(head)

if __name__=='__main__':
  main()

Top view of a binary tree

Given a root of a binary tree, print the top view of a binary tree

This problem is similar to the vertical order traversal of the binary tree. The only catch is here is that , when we are storing the level wise elements in the hashmap , we check if there is already a value exists in the hashmap for that level. If it exists, we wouldn't storing again at that level because as we are coming from the top (root), the first element at each level is what appears in the output.

class TreeNode():
def __init__(self,val):
    self.val = val
    self.left = None
    self.right = None

class solution():
def topview(self,root):
    if not root:
    return []
    hmap ={}
    minlevel=2**31-1
    maxlevel = -2**31
    q = [(root,0)]

    while q:
    (node,level) = q.pop(0)

    if level not in hmap:
        hmap[level] = node.val

    minlevel = min(minlevel,level)
    maxlevel = max(maxlevel,level)

    if node.left:
        q.append((node.left,level-1))

    if node.right:
        q.append((node.right,level+1))
    res = []

    for level in range(minlevel,maxlevel+1):
    res.append(hmap[level])

    return res

def main():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(9)
root.left.right = TreeNode(3)
root.left.right.left = TreeNode(4)
root.left.right.left.left = TreeNode(5)
root.right.left = TreeNode(6)
root.right.left.right = TreeNode(7)

print solution().topview(root)

if __name__=='__main__':
main()

GitHub – sainadhreddy92

sainadhreddy92