
Recently, I stumbled upon an unusual message between my Google search results.
"You're speaking our language. Up for a challenge?"
It was a Google FooBar Invitation link.

<Image 
  src={'/static/images/post/my-google-foobar-challenge-experience/google-foobar-invitation-message.png'}
  alt='Google FooBar invitation message'
  width={818}
  height={50}
  layout='intrinsic'
/>


- [What is Google FooBar?](#what-is-google-foobar)
- [How do I get the Google FooBar challenge?](#how-do-i-get-the-google-foobar-challenge)
- [What happens if you complete Google Foobar?](#what-happens-if-you-complete-google-foobar)

## What is Google FooBar?

[Google Foobar](https://foobar.withgoogle.com/) is Google’s secret hiring challenge! Google uses this to hire some of the best developers around the globe which they think can be a good match for their organization. When Google thinks you could be a good match, you are given a prompt and if you accept, you are moved to an online shell where you get access to some coding challenges.
If you get past level 3 out of 5, there is a big chance of being contacted by a Google recruiter!

The challenge consists of 5 levels consisting of algorithm problems, with increasing difficulty.
The first few levels were relatively easy, but as the levels peaked up, the difficulty gained heights. The problems needed multiple concepts ranging from number theory to graphs to complete.
Upon completing level 3, you had the opportunity to submit your personal details and contact information in the console. By doing this I got contacted by a Google recruiter, so I suggest you do this as well!

<Image 
  src={'/static/images/post/my-google-foobar-challenge-experience/google-foobar-finished.png'}
  alt='Google FooBar finished'
  width={408}
  height={76}
  layout='intrinsic'
/>

## How do I get the Google FooBar challenge?

Getting the invitation for the Google FooBar challenge is a mysterious process, and can be as hard as solving the challenges themselves.
No one knows what the exact Google FooBar invitation requirements are. The challenge is triggered to individuals when Google detects a certain search pattern, query or keywords.
Google sends the invitation based on your search history and your problem solving related keyword searches.

To get an invitation for yourself, there are a couple of things you could do:
1. Ask your network for a spare invitation referral link, maybe you get lucky.
2. Keep an eye out on Twitter: https://twitter.com/search?q=google%20foobar&src=typed_query&f=live. Sometimes people post what search query resulted in their invitation
3. Idem for LinkedIn: https://www.linkedin.com/search/results/content/?keywords=google%20foobar

When you find recent search queries resulting in an invitation, you can use them for yourself. Often you have to reload the page a couple of times (F5).

<iframe width="750" height="500" src="https://www.youtube.com/embed/oVE3lNzWFjY" frameBorder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowFullScreen loading="lazy" title="Google FooBar invitation popup video"></iframe>

Here is a list of search queries that previously resulted in invitation popups:
- python list comprehension
- high performance python
- segment trees
- mutex lock
- arraylist java
- python try catch
- C++ move semantics
- ...

## What happens if you complete Google Foobar?

Completing the challenge is a great way to show your coding talent, it means you know about Markov Chains, Backtracking, and Cellular automata by doing these problems.
This usually doesn't go unnoticed! I myself and a lot of other individuals who were able to solve all levels can confirm the got contacted by a Google recruiter.

There are a couple of testimonies stating their Google FooBar participation lead to landing them their dream you at Google, so who knows, maybe you are next? ;)

In this article, I'll talk about my Google FooBar experience, and give you a guide to scoring an invitation.

My Google FooBar Challenge Experience


<Image 
  src={'/static/images/post/my-open-summer-of-code-2020-experience/osoc_2020_logo.svg'}
  alt='osoc 2020 logo'
  width={800}
  height={800}
/>

# What is Open Summer of Code?
Open summer of code (osoc) is a international annual program where selected students form teams and build a open source projects, prototype or proof of concept for participating companies. Any type of company is welcome grab the opportunity to have a group of talented students build their next innovative project.

The project I was selected to work on was the [Serendipity Engine](https://github.com/oSoc20/SerendipityEngine/). This was a project in cooperation with [imec](https://www.imec.be/) and [IDLab](https://idlab.technology/) with the goal of exploring how to build a serendipitous mental map. They wanted us to use Linked Open Data tand open source technology where possible. You can find our final result [here](https://mymentalmap.be/).

Through this article, I wanted to relate my experience as a student participating in osoc 2020 and give some insights along the way to anyone interested to apply next year.

# My experience

## Introduction about our project
When you think about a city and try to orient yourself, you use what's called a **mental map**, a map that presents your view of that city.

With the [Serendipity Engine](https://github.com/oSoc20/SerendipityEngine/), we try to change your point of view of these cities by forming your mental map in a surprising yet pleasant way.

## Our initial research
To form a better idea of how different mental maps could look, we started a survey.
The user's place of residence was requested, as was the means of transport to the city of Brussels. These two questions gave us an idea of ​​the user's orientation. Finally, the user was also asked to draw a mental map of the city of Brussels, based on the information from the previous two questions.

(Some of the drawings we received)

<Image 
  src={'/static/images/post/my-open-summer-of-code-2020-experience/brussels_mental_map.jpg'}
  alt='Brussels mental map'
  width={800}
  height={800}
/>

<Image 
  src={'/static/images/post/my-open-summer-of-code-2020-experience/logrono_mental_map.jpg'}
  alt='Logrono mental map'
  width={800}
  height={800}
/>


The main difference between the different mental maps was how detailed the user would draw the map. This was influenced by whether or not the user lived in Brussels or was a
regular visitor. Some people drew a very simplistic map of Brussels, while others drew very specific details.

This gave us different ideas for linking certain questions to certain design elements of the website. A possible question could be whether the user visits the city often. This would result in whether the map is shown in detail or rather simplistic.

## Functionalities

### Questionnaire
Based on the questions answered in the small questionnaire the application is able to determine what location should be shown on the map. What the suggested rotation should be based on the point of origin and what layers and places could be interesting for a given user but also choose which data could be more relevant depending on their mode of transport.

### Map view
Once loaded, the user is able to interact with the map by rotating it as needed, or to fit the map to the city bounding box. When the user is pleased with the result, (s)he is able to make a permanent copy of it using the download button.

## Creating the product

<Image 
  src={'/static/images/post/my-open-summer-of-code-2020-experience/mental_map_logo.svg'}
  alt='Mental Map logo'
  width={800}
  height={800}
/>

### Branding
Final goal in mind – being able to print the designs of the different mental maps – we decided to choose for complexion reduction. This includes the use of bold, black
typography in combination with minimalistic elements. Using this style creates space for the final print-design and gives a very clear and easy to understand image.

A minimalist approach was also taken with regard to the content of the website. A call to action on the home page takes the user directly to the questionnaire to generate his or her mental map. The user can also follow the process of this questionnaire by numbering at the top of each individual question.

Finally, the user can find more information about the project on the 'about' page, if necessary.

### Frontend
For this application, we used the framework [Angular](https://angular.io/) which is a JavaScript framework to build single-page applications. We decided to use this framework because 2 out of 3 people knew it but also for the strength of this framework which is natively complete compared to similar frameworks such as React.

Regarding the map, we used [Mapbox](https://www.mapbox.com/) which is largely based on open data coming from OpenStreetMap. Mapbox has complete documentation, plenty of users, a big community to help, and is free to use up to 50.000 requests per month. Mapbox maps are also a good alternative to Google Maps and are used by many popular applications such as Snapchat or the maps for the leader brand in civil drone, DJI.

The application is hosted with GitHub pages with its own domain name, [mymentalmap.be](https://mymentalmap.be/). This was the simplest way to do it and is available for free.

### Backend
The backend is directly done through [Angular](https://angular.io/) services that access open-source APIs.

Indeed, this project doesn’t have it’s own API but uses open data, the one of OpenStreetMaps through Mapbox, and the [Open Points Of Interest (“OPOI”)](https://opoi.org/14/8412/5484) API to retrieve some points of
interests and display them as markers on the map.

### Communication plan
When achieving the ultimate map design, one could use the download button on the last page of the questionnaire to get a “ready-to-print” design of their generated map. The end goal is to print these designs and show them around on the streets, on social media, etc. The message of these print designs should be about the open-mindedness towards cities and visiting new things.

Word of mouth (by using the print-designs on social media/streets) is the best way to make sure the awareness about the project spreads. Maybe in a future stage of this project, one could add QR-codes to the print-designs which would navigate the user to the mobile application of the serendipity engine. This way, the user could get a mental map based on the location where he or she is currently.

# Conclusion

osoc2020 has gradually come to an end. The final presentation ended on the 30th of August 2020 and at the time of writing this article the final mentor evaluations are underway. So, to anyone hoping to apply for osoc 2021, I wish you all the best of luck and hope this article helped you to get an idea on how what you could be working on. If you have any questions regarding this, I would be more than happy to help.

In this article, I'll talk about my Open Summer of Code 2020 experience.

My Open Summer of Code 2020 experience


One of the most fundamental problems in the current era is being able to find and connect similar information. I challenge you to think of one application on the Web that would not benefit from being able to determine similarities between bits of information. Detection of duplicate documents is becoming increasingly important for businesses and data scientist. Near-duplicate pages found on the Web could be plagiarisms, or they could be mirrors with identical information but released on different outlets. 

In this article we'll explore a range of techniques and algorithms to determine the similarity between items. We will also explain the how and the why, and have a look at some use cases.

## How can we define similarity?
We can define similarity as a measure of how much  2 sets, collections or document have in common when we compare them. The more resemblance the 2 documents have to each other, the higher their similarity. To make this definition resemble a concrete value, we will introduce the Jaccard similarity.

### Jaccard similarity
The notion of how similar sets are is called "[Jaccard similarity](https://en.wikipedia.org/wiki/Jaccard_index)". The Jaccard similarity of two sets, A and B, can be calculated by the ratio of their intersection size divided by their union size. We shall denote the Jaccard similarity of A and B by:

J(A,B) = |A ∩ B| / |A ∪ B|

Using the above formula, we are able to calculate the exact similarity of 2 sets. To make this easy method transferable to other sources of information, we need techniques to represent these sources of data as sets.
For example:

J(A,B) = |A ∩ B| / |A ∪ B| = |2| / |6 + 4 -2| = 2 / 8 = 0.25

<Image 
  src={'/static/images/post/how-to-programmatically-calculate-similarities/jaccard-similarity.png'}
  alt='Two sets with Jaccard similarity 2/8'
  width={500 / 5 * 8}
  height={300 / 5 * 8}
  layout='intrinsic'
/>

### Jaccard distance
The Jaccard similarity is a measure of how close sets are, albeit not really a distance measure. To calculate the distance between two sets utilising the Jaccard similarity calculation, we simply take 1 minus the calculated Jaccard similarity. This is called the Jaccard distance, the closer two sets, the higher the Jaccard similarity and thus the lower the Jaccard distance.

dJ (A,B) = 1 - J(A,B)

### How to shingle documents
The best performing way to represent a document as a set, for the purpose of finding lexical matches, is to construct a set containing short strings of text that appear within the document. By doing so, same pieces of text will always be identified regardless of their position. 

### k-Shingling
A common shingling technique to represent documents as sets  is k-shingling. As a document can simply be seen as a string of characters, we can define a k-shingle of this document as all possible consecutive k length substrings existing in the document. Here you can see an example of a k=2 shingle:

```
Original: "Thank you for reading this blog"

k=2 shingled: "Thank you" "you for" "for reading" "reading this" "this blog"
```

### Shingle size
Choosing the best shingle size can be a daunting task, if you take your shingle size to large, you won't be able to find similarities between documents, only if they are a near perfect match. If you take your shingle size to small, as an extreme example k = 1, you will have a bias because the top 1000 most frequently used words represent around 85% of all word usage. All common used characters will be shared between most of the documents you will want to compare.

To avoid a bias towards too little or too much abstraction, you should pick your k size large enough that the probability of any given shingle appearing in any given document is low.

You could also decide to shingle on characters in favor of words, this way you could have a representation that is less defined by words but more by the order of words following each other.

### Shingle hashing
Instead of using using string representations as shingles directly, you should favor the use of a hash function to determine a hash representing the shingle. This can lead to memory-usage reduction and faster comparison speeds. To select the best string hashing function, please have a look at this overview by Ozan Yigit.

## Use cases
### Detecting Plagiarism: 
Detecting plagiarised content relies on our ability to find textual similarities between content. Plagiarized documents may only contain some parts of the original piece mixed in and scrambled up between his own content, or content from even more sources. Determining whether documents are plagiarized can be a daunting task because a character by character comparison won't always yield correct results.

### Same Source Articles
When using news aggregators, such as Google News, you are able to find multiple sources and news outlets reporting about the same event. Aggregators are able to cluster articles about the same topic using similarity scores. Reporter also publish articles through the Associated Press, which can then be redistributed by other websites.

## Conclusions
- Jaccard Similarity: The Jaccard similarity coefficient is a statistic used to measure the similarity between sets. It is calculated by the ratio of the size of the intersection to the size of the union.
- Jaccard Distance: The Jaccard distance is a distance measure between sets, calculated as one minus the Jaccard Similarity
- Shingling: A way of representing text documents as a set of strings. By representing a document by its set of k-shingles, we form a set of k long characters that consecutively appear in the document. By calculating the Jaccard similarity of shingled sets, we are able to measure the textual similarity of  documents.

## Resources
+ [Mining Massive Datasets Chapter 3 - Anand Rajaraman](http://infolab.stanford.edu/~ullman/mmds/ch3.pdf)
+ [Introduction to Information Retrieval - Christopher D. Manning](https://nlp.stanford.edu/IR-book/)
+ [Text Similarity - Ethen Liu](http://ethen8181.github.io/machine-learning/clustering_old/text_similarity/text_similarity.html)
+ [Hash Functions - Ozan Yigit](http://www.cse.yorku.ca/~oz/hash.html)
+ [String Hashing - E-Maxx Algorithms](https://cp-algorithms.com/string/string-hashing.html)

In this article we'll explore a range of techniques and algorithms to determine the similarity between items. We will also explain the how and the why, and have a look at some use cases.

How to programmatically calculate similarities


## Hello world!
I'm Kasper Zutterman, a 20 year old Information Engineering Technology student at Ghent University. I am born an raised in Belgium and enjoy practicing track & field in my spare time.  

Ok, let’s move on to what this blog is about. Since my other passion is coding, this will be a technology and programming related blog. I want to share my experience, helpful guides and fascinating projects.

Glad you came by.  I wanted to welcome you and let you know I appreciate you spending time here at my blog very much.
Another thing I will always appreciate is your feedback to the blog.  If you have any comments or suggestions I welcome them and would love to hear them. So please feel free to contact me via social media!

If you want to know more about me just click [here](https://kasperzutterman.com), and always feel free to leave any comment, question or feedback.
Hope you enjoy it :)

Cheers,

Kasper

I'm Kasper Zutterman, a 20 year old Information Engineering Technology student at Ghent University. And I would like to welcome you to my Blog!