Hyperface Experience

'''
PES2UG22CS281
M C KRISHNA KUMAR
SET B
q1. Find Special Substring of Length k
'''

s = "havefunon"
k = 5

'''
APPROACH: This can be done using sliding window and hash map
Time Complexity : O(N) # one loop
Space Complexity : O(N) # hashMap
'''
hashMap = {}
# For this we will make use of a window size of k
# Then as the window passes left to right incrememting by 1 we check if all the frequencies of the elements is 1
# If its not we can move to left side and recheck

n = len(s)

# base case
c = 0
if k < n:
    return c

l = 0
for r in range(len(s)):
    hashMap[s[r]] = 1 + hashMap.get(s[r], 0)
    if len(hashMap) == k and all(hashMap.values() == 1):
        c += 1
    if hashMap[s[r]] > 1:
        continue
    
    if len(hashMap) > k: # means we are exceeding k len so remove left most
        del hashMap[s[l]]
        l += 1

print(c)

-----------------------------------------------------------------------------------------------------------------
'''
PES2UG22CS281
M C KRISHNA KUMAR
SET B
q2. Next Permutation
'''

nums = [1, 2, 3]

'''
APPROACH 1:
    i) Jhonson Trotter Algorithm (generates all permutations)
    ii) Manually get the next permutation

'''

'''
APPROACH 2:
    i) Generate all permutations. [[perm1], [perm2]....]
    ii) Sort them
    iii) Iterate through the permutations
    iv) Find the given nums and return the next value from the array of arrays

Time Complexity : O(n!) + O(nlon(n)) = O(n!)
Space Complexity : O(n)
'''
''' APPROACH 2 code '''
def NextPermute(nums: List):
    res = []
    perm = []

    def dfs(i): # generates all permuations using backtracking
        if len(perm) == len(nums):
            res.append(perm.copy())
            return

        for i in range(len(nums)):
            if nums[i] not in perms:
                perms.append(nums[i])
                dfs(i+1)
                perms.pop()
    dfs(0) # 0th index

    # now the res will have all permutations
    # sort it
    res.sort()
    for i in range(len(res)):
        if res[i] == nums:
            return res[i+1]

from collections import defaultdict
import random

class ExpenseTracker:
    def __init__(self):
        # hashed for fast look-ups
        self.persons = set()
        self.groups = defaultdict(list) # (groupName, [person1, person2 etc])
    
    def availableOptions(self):
        print("1. Add people to the system")
        print("2. List Registered users")
        print("3. Create Groups")
        print("4. Add to Group")
        print("5. List Registered Groups")
        
        print("6. Exit")
    
    '''Seperate func as future hashSet can be changed to a real DB. Extensible'''
    def _add(self, p):
        if p not in self.persons:
            self.persons.add((p, 0)) # initial balance is 0 for all
        else:
            print("User exists in the system")

    def showBalance(self):
        for person, balance in self.persons:
            print(f"Balance of person {person} -> {balance}")
        print()
    
    def groupManagement(self, groupName):
        if groupName in self.groups:
            return "Group Already exists"
        self.groups[groupName] = list()
        print("successfully created group ")

                
    def addPeopletoGroup(self, groupName, person):
        if person in self.groups[groupName]:
            return "Person exists in the group already"
        self.groups[groupName].append(person)
    
    def showRegisteredGroups(self):
        for g in self.groups:
            print(g)

    def app(self):
        print("Welcome to Expesne Tracker!")
        person1 = input("Please enter your name admin ")
        self._add(person1)

    def main(self):
        while True:
            if len(self.persons) == 0: # implies first user
                self.app()
            self.availableOptions()
            print()
            option = int(input("Enter your option "))
            
            if option == 1:
                personName = input("Enter your Name ")
                self._add(personName)
                print("Successfully added\n")
            elif option == 2: # list registered users
                self.showBalance()
            elif option == 3:
                groupName = input("Enter the group name ")
                self.groupManagement(groupName)
            elif option == 4:
                groupName = input("Enter the group name to add to ")
                person = input("Enter the Person to add ")
                self.addPeopletoGroup(groupName, person)
            elif option == 5:
                self.showRegisteredGroups()
            elif option == 6: #exit
                break
            print()


class TransactionManager:
    '''TransactionManager class inherits the ExpenseTracker class'''
    '''Furthur maintains readability and extensibility'''
    def __init__(self, groupName):
        super().__init__(ExpenseTracker)
        self.groupName = groupName
        self.splitTable = defaultdict(list) # (id, groupName) -> [groupName, amount, descriptor, paidBy]

    def addNewSplit(self, groupName, amount, description, paidBy):
        _id = random.randint(1,9)
        # amount is split equally among group members but not stored
        amount / len(self.groups[groupName])
        self.splitTable[(_id, groupName)].append([groupName, amount, description, paidBy])

    def settleMent(self): 
        pass
        # future implementation


# good coding practice
if __name__ == "__main__":
    # for using first time
    ExpenseTracker().main()