Time Portals - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To count the number of pairs of indices such that the concatenation of portals[i] + portals[j] equals destination.
  • What input is provided?
    • An array of digit strings portals and a digit string destination.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to store the frequency of each portal string, then iterate through the list and check for valid pairs.

1) Create a dictionary `portal_count` to store the frequency of each portal string.
2) Iterate through `portals` to populate the dictionary.
3) Iterate through `portals` again to count valid pairs:
   - Calculate the required matching string for each portal.
   - Check if the required string exists in the dictionary and update the count accordingly.
4) Return the total count of valid pairs.

⚠️ Common Mistakes

• Not correctly handling the case where the portal string is equal to the required string.

I-mplement

def num_of_time_portals(portals, destination):
    # Create a dictionary to store the frequency of each portal string
    portal_count = {}
    
    for portal in portals:
        if portal in portal_count:
            portal_count[portal] += 1
        else:
            portal_count[portal] = 1
    
    count = 0
    
    # Iterate through each portal string
    for portal in portals:
        # Determine the required matching string
        required = destination[len(portal):]
        
        # Check if the required string exists in the dictionary
        if required in portal_count:
            # Decrease count if portal == required to avoid counting same index pairs
            if portal == required:
                count += portal_count[required] - 1
            else:
                count += portal_count[required]
    
    return count