On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.
The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.
Medium Question #4 involves determining whether one string can be formed by rearranging some of the characters in another string. The question reads:
ASU SoDA Coding Challenge VI Medium Question 4: The Letter
Vasya decided to write an anonymous letter cutting the letters out of a newspaper heading. He knows heading s1 and text s2 that he wants to send. Vasya can use every single heading letter no more than once. Vasya doesn't have to cut the spaces out of the heading — he just leaves some blank space to mark them. Help him; find out if he will manage to compose the needed text.
Input
The first input string contains a newspaper heading s1. The second input string contains the letter text s2. s1 и s2 are non-empty lines consisting of spaces, uppercase and lowercase Latin letters, whose lengths do not exceed 200 symbols. The uppercase and lowercase letters should be differentiated. Vasya does not cut spaces out of the heading.
Output
If Vasya can write the given anonymous letter, print YES, otherwise print NO
Test Cases:
input
Instead of dogging Your footsteps it disappears but you dont notice anything
where is your dog
output
NO
input
Instead of dogging Your footsteps it disappears but you dont notice anything
Your dog is upstears
output
YES
input
Instead of dogging your footsteps it disappears but you dont notice anything
Your dog is upstears
output
NO
input
abcdefg hijk
k j i h g f e d c b a
output
YES
This question is pretty standard for those familiar with Python dictionaries. Here’s my solution:
Solution #1: Dictionary Approach
We form a dictionary of the letters in each string where the key is the letter and the value is the number of the time the letter appears. Then we check all characters in the letter and make sure that the frequency in the letter is not greater than the frequency in the newspaper. Here’s an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Medium Problem #4
https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
'''
import time
import sys
i = 0
for x in sys:
if(i==0):
s1 = x
else:
s2 = x
i+=1
def dictString(s):
myDict = {}
for x in s:
if x in myDict:
myDict[x]+=1
else:
myDict.update({x : 1})
return myDict
def letterPossible(s1,s2):
a1 = dictString(s1)
a2 = dictString(s2)
for x in a2:
if(x!=" "):
if x in a1:
if(a1[x]<a2[x]):
return "NO"
else:
return "NO"
return "YES"
start = time.time()
print letterPossible(s1, s2)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
YES
--- 3.50475311279e-05 seconds ---
for input of s1 = "Instead of dogging Your footsteps it disappears but you dont notice anything", s2 = "Your dog is upstears"
'''
And with that, we’re done. This was a relatively standard problem. Luckily, the next problem was far less generic.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 