UWB-ACM/CTCI

Graphs: Write-up for question 1

Closed this issue · 1 comments

etcadinfinitum commented

Procedure for completing a problem & solution writeup for UWB ACM CTCI sessions:

  • Assign an issue to yourself
  • Pick a problem to write up. Please check the prior quarter's session to ensure we don't have duplicates between quarters. Some good places to look are LeetCode, HackerRank, and of course CTCI. Communicate with your colleagues to ensure we have good topic coverage and nobody is writing up duplicate questions.
  • Clone this repository to your computer, if you haven't already. If you have, cd into the repo's directory, run git checkout master, and run git pull origin master.
  • Run git checkout -b <my-topic-name>, and name the branch something logical. (Pick a short name for the problem you are writing up, for example.)
  • cd into the directory with the solutions file for the session. The naming conventions should make the file's location fairly self-evident.
  • Add the problem description in the appropriate numbered selection in the solutions file.
  • Add the solution writeup in the appropriate numbered selection in the solutions file.
  • Add a driver program (which includes your solution) in a subdirectory that produces the output included in the solutions file.
  • Run git commit. Add a useful commit description, so that reviewers know what they're looking at.
  • Run git push origin <my-topic-name>, using the branch name you chose earlier.
  • Navigate to the GitHub repository and open a Pull Request for your submitted branch.
  • Request a review from one or more designated PR reviewers for the session.
  • If your reviewer requests changes, please address all suggestions.

As always, if you experience issues or have questions, talk to your peers. We are here to help each other!

etcadinfinitum commented

For Question 1, let's do something easy that I cooked up myself:

Telephone Strangers

Source: Lizzy

Scenario

You are given a map m which represents a graph of phone calls between distinct numbers. Each entry in m maps a phone number to an array of all individual phone calls on that line from the previous 30 days.

Find all the pairs of phone numbers which didn't have any calls placed to each other.

Additional info:

  • You may assume that map entries are reflexive; if a call between Line A and Line B is placed, the map entry for Line B will contain Line A, and vice versa.
  • A phone number cannot place a call to itself.

Example Input

We shorten phone numbers in the examples for readability.

Example 1

Input:   m = { '206': [], '940': ['425'], '425': ['940'] }
Output:  [('206', '940'), ('206', '425')]

Reasoning: '206' did not speak to anyone on the phone, and is therefore a stranger to '425' and '940'. This produces the two pairs of telephone strangers.

Example 2

Input:   m = { '1': ['2', '3', '4'], '2': ['1', '4'], '3': ['1'], '4': ['1', '2'] }
Output:  [('2', '3'), ('3', '4')]

'1' had phone calls with all other phone numbers in the map. '2' and '4' are missing phone calls with '3', forming two pairs of telephone strangers.

Function Signature

Python:

def findStrangers(m: dict) -> list:
    # your code here