"""
1 -> 8 -> 3  # 123              183
4 -> 5       #  45               45
                                228
1 -> 6 -> 8  # 168

carry = 1
3 -> 8 -> 1
^
5 -> 4
^

8 -> 2 -> 2

  1
99
1
00
    None<-1 <-2 <- 3     1 <- 2 <- 3   
                     ^
tmp = None
prev = 3

"""

class SLLNode:
    def _init_(self, val):
        self.val = val
        self.next = None


def reverse_sll(head):
    #Reverse List
    if not head: return None
    runner = head
    prev = None
    
    while runner:
        tmp = runner.next
        runner.next = prev
        prev = runner
        runner = tmp
    
    return prev
    
"""
Input       Expected op         Actual op
None        None                None

1->2        2                   2

None<-1<-2
        

runner = None
prev = 2
tmp = None


O(n)    n   -> len of sll
O(1)    

"""
    
def add_two_sll(l1, l2):
    if not l1: return l2
    if not l2: return l1
    
    l1 = reverse_sll(l1)
    l2 = reverse_sll(l2)
    
    dummy = ans = SLLNode('dummy')
    carry = 0
    
    while l1 or l2:
        tmp = 0
        if l1:
            tmp += l1.val
            l1 = l1.next
        if l2:
            tmp += l2.val
            l2 = l2.next
            
        ans.next = SLLNode((tmp + carry) % 10)
        carry = (tmp + carry) // 10
        
        ans = ans.next
        
        if not l1 and not l2 and carry:
            ans.next = SLLNode(carry)
            
    return reverse_sll(dummy.next)
    
"""
Input       Expected OP     Actual OP
l1 None     l1              l1
9->9 -> 1   1->0->0         reverse(0 -> 0 -> 1)

tmp = 9 + 1 % 10 = 0 

carry = 1

10

O(n)    n ->length of larger sll
O(n)    n -> 1 + len of larger sll
"""

# Question 1: First Non Repeating in String
"""
BLOOMBERG
abczabcx - z

First non repeating character
012345
abcabd
   ^

I: aaaaa
O: None

hm = {
    a: 2
    b: 2
    c: 1
    d: 1
    
}
"""
def first_non_repeating(s):
    hm = {}
    for ch in s:
        if ch in hm:
            hm[ch] += 1
        else:
            hm[ch] = 1
    
    for ch in s:
        if hm[ch] == 1: return ch
        
    return None

"""
Test1:
Input: 'a'
Expected: 'a'
Actual: 'a'

T2
Input: 'abac'
Expected: 'b'
Actual: 'b'

hm = {
    a: 2
    b: 1
    c: 1
}
Actual: 
"""

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

from collections import deque
from collections import defaultdict
def vertical_order_traversal(root):
    if not root: return []
    dq = deque([[root, 0]])
    hm = defaultdict(list)

    while dq:
        node, dist = dq.pop()
        hm[dist].append(node.val)

        if node.left: dq.appendleft([node.left, dist - 1])
        if node.right: dq.appendleft([node.right, dist + 1])

    result = []
    for key in sorted(hm.keys()): result.append(hm[key])
    return result

"""
Test1:
Input: 'a'
Expected: 'a'
Actual: 'a'

T2
Input: 'abac'
Expected: 'b'
Actual: 'b'

hm = {
    a: 2
    b: 1
    c: 1
}
Actual: 
"""
    
"""
Input: None
O: None

I:    a -> b -> c -> d
                     ^
runner = None
tmp = None
prev = d

None<-a <- b <- c <- d  <- b <- c <- d
    
O:    d -> c -> b -> a

"""
class SLLNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        
def reverse_sll(head):
    #Input validations
    
    runner = head
    prev = None
    
    while runner:
        tmp = runner.next
        runner.next = prev
        prev = runner
        runner = tmp
        
    return prev 
        
def traverse(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
        
    return ans

import unittest
class TestReverseSLL(unittest.TestCase):
    def test_generic(self):
        a = SLLNode('a')
        b = SLLNode('b')
        a.next = b
        
        self.assertEqual(traverse(reverse_sll(a)), ['b', 'a'])

if __name__ == '__main__': unittest.main()
        
"""
Testing

T1: 
Input: None
Expected: None
Adctual: None

T1: 
Input: a
Expected: a
Adctual: None

T1: 
Input: a -> b
Expected: b
Adctual: b
"""

# Question 2: Scrabble
"""
C,R,B,A,X,Q,L #7 tiles

7*6*5
[C,R,B,A,A,Q,L]
 ^
        []
      /
     [C]
     /
    [CR]    
    /    \
    [CRB]   [CRA]
   /CRBA, CRBAA
list of all the valid English words <= 7 letters

[AXE, ...., CRAB, CABAL]

AXE, AXLE


        -
    A -> EOW = False
  X
E   L
      E -> TRUE
      
axe...le
"""

def is_valid_word(word):    #Return True if word found in Trie

def scrabble(word_list):
    
def backtrack(word_list, curr, ch_idx, ans):
    if len(curr) == 7: return curr
    if not is_valid_word(curr): return
    
    for i, ch in enumerate(word_list):
        if i != ch_idx: if curr += [word_list[i]]