1- Make sure you check the inputs and validate them. We check your code with different inputs. In
other words, we try to
eak your code. Your code must be resistance to different kinds of user
inputs. Unless I have mentioned something is out of scope, you assume all the possible inputs.
************************************************************************************
You already have seen the Binary search algorithm on Day 07 notes. You see how we can
isect/ eliminate half of the items in the problem domain (in a list or any iterable object) in each iteration
and come up with a shorter list to explore. This is the main idea of binary search:
Eliminating part of the problem space and na
ow it down to a smaller space to find the answer faster.
In question 1, below, I want you to have this matter in your mind. You must not forget that the binary
search works on the sorted lists.
Question 1) Write a code that finds the elements of a sorted list that its index is equal to the item in that
index. For example if the list is lst= [-2,0,2,3,6,7,9] then code has to return 2 and 3 since lst[2]=2 and
lst[3]=3
Hint1: do you think the above question has any relation to the binary search? Think about it. It is a sorted
list, so it has the first condition. Do you want to search all the items on the list? What if the list has 1
million elements? Do you want to test 1 million items to see if lst[i]=i? (imagine the last item is the answer
and you have to go through the entire list to get to the last item)
Can you use this fact that if lst[j]>j then no entry after j can satisfy the given criterion? This is because
each element in the list is at least 1 greater than the previous element. For the same reason if lst[j]
entry before j can satisfy the given criterion.
The above observations can be used directly to create a binary search to find lst[i]=i
You can eliminate your search space with the two above conditions.
Hint2: you can also consider that if lst[i]=i then lst[i]-i=o. You can use this hint in your binary search too.
Now solve the above question by employing hint 1 or by hint 2.
Question 2) Let’s say I give you two strings that contain digits like “234” and “45”. How do you compare
the equivalent numeric values of those two strings without converting them to an integer by the int()
method? For example, 234>45 in the above case.
If your idea is to compare the very left positions, then you must be careful since 10>2 even though 1<2
Make sure your code does not
eak if the string is empty. Assume we do not give a negative number or
none-numeric characters to the program, so you do not need to check them. However, they can be equal
to each other or equal to zero. Print the appropriate message to use if they are equal.
Question 3) Let’s say we want to check if the sum of two numbers in a list is equal to 10. The list can be a
very big list. We do not want to iterate through the list more than once. Do not use the
ute force
method.
Hint: let’s say our list is [3,4,1,2,9]. In a
ute force approach, you can check the first item (i.e. 3) with all
the other items in the list and if that is 10, print those two items. Otherwise, try the second item and
compare it with third, fourth and so on. You have to do this comparison for all the items as it is possible
no two items in the list add up to 10. The problem is if the list has n list, you check each item with the
other n-1 items in each iteration. Since you have n items, in total you perform n(n-1) comparisons (since
you pick one of the n numbers and compare that with the remaining (n-1) numbers). But the question
asks you not to iterate through the list more than once (n). How can we do that?
You should use a more innovative solution. For example, you can use a dictionary that the keys are the
list items and the value is 1 if (value=10-item) does not exist. For example, for a list like this:
[3,4,1,2,9]
The 10-3(first value in the list)=7. We do not have 7 in the dictionary yet (we just started to populate the
dictionary). So we insert the 3 in the dictionary and put 1 in its value
Key value
3 1
Then we calculate 10-4(second value in the list)=6. We have just 3 in the dictionary, so we go ahead and
add that to the dictionary too:
Key value
3 1
4 1
Then 10-1=9. We have 3 and 4 in the dictionary. So, let’s add that to the dictionary:
Key value
3 1
4 1
1 1
The next one is 10-2=8
Key value
3 1
4 1
1 1
2 1
Now we come to the last item: 10-9=1. This time we can see that we already have 1 in the dictionary (see
the item in the last but one position. So, we found the pair (9 and 1)
The beauty of this solution is we did not iterate the list more than once.
Now you implement this solution.
Question 4) I have shown you how to make a dictionary suggestion in the Day 07 notes. Now I want you
to use that knowledge in answering the following question:
We want to implement an autocomplete feature that provides suggestions as a user types a phrase in the
search field. The autocomplete is like the Google search suggests a feature. When you start searching for
a keyword in the Google search, it suggests a few items to you to make life easier for you. The list we have
in mind cu
ently has a product catalog of around 3 million objects and only want to autocomplete the
product name. Use the products.json in the following link: https:
github.com/BestBuyAPIs/open-data-
set
That is the BestBuy product names. If you save the products.json on the local desktop and open that by
MS Excel, you get some idea about its format. This is what it looks like:
https:
github.com/BestBuyAPIs/open-data-set
https:
github.com/BestBuyAPIs/open-data-set
It has a list (i.e. the entire product is in []) that each of its elements is a python dictionary with keys and
values. You have seen a similar data model when we tried to model the Spotify website in the class. You
are just interested to pick the key =name. Column C and D sound good candidate to build the dictioney
structure. You do not care about the rest. To simplify the solution you can limit the search suggestions to
5 suggestions to users.
I have written a code for you to not to wo
y about loading the keys and values. Run this code in the same
folder that your JSON file is located:
If you run this code you get this result:
As you see in the above screenshot you have repeated names like Corliving. Please merge them into one
dictionary record. For example, one key Corliving with more than one value. So you will have a dictionary
with a key that may have many values and each value is an item in a list.
You know how to search and suggest a Python dictionary data structure when you worked on the Notes
on Day_07 Dictionary practice 1. Use the same technique to answer this question.