<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Endre Sukosd on Medium]]></title>
        <description><![CDATA[Stories by Endre Sukosd on Medium]]></description>
        <link>https://medium.com/@endre.sukosd?source=rss-b521b6d638f2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*dmbNkD5D-u45r44go_cf0g.png</url>
            <title>Stories by Endre Sukosd on Medium</title>
            <link>https://medium.com/@endre.sukosd?source=rss-b521b6d638f2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 04:53:24 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@endre.sukosd/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Could a language model graduate high school in Romania in 2024?]]></title>
            <link>https://medium.com/@endre.sukosd/could-a-language-model-graduate-high-school-in-romania-in-2024-ac4b398babe5?source=rss-b521b6d638f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/ac4b398babe5</guid>
            <category><![CDATA[language-model]]></category>
            <category><![CDATA[evaluating-llm]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[standardized-tests]]></category>
            <dc:creator><![CDATA[Endre Sukosd]]></dc:creator>
            <pubDate>Thu, 11 Jul 2024 01:39:25 GMT</pubDate>
            <atom:updated>2024-07-11T01:39:25.788Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>TLDR</strong>: No. Or at least not in one-shot.</p><pre>Table of contents:<br>  - Intro<br>  - The models<br>  - The test<br>  - The prompt<br>  - The results<br>  - Philosophical digression<br>  - Full chat logs for ChatGPT<br>  - Full chat logs for Claude<br>  - Screenshot of ChatGPT taking the exam - partial<br>  - Screenshot of Claude taking the exam - partial</pre><h3>Intro</h3><p>We are living in exciting times, as ever more capable language models are being released. However, the biggest pain point for me with language models is that it’s really hard to objectively evaluate these models. Many of the standard benchmarks used are of questionable usefulness and some are also suspect of being leaked in the training data. So we are left wondering how good these models really are?</p><p>Well, I decided to do my own little evaluation experiment. As the high school graduation exams just finished in Romania, I was curious to put the two most hyped language models to the test, and see how they would perform.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/0*1GP5LJo0gtdsvR2u.png" /></figure><p>(image generated by <a href="https://semmi88.github.io/blog_posts/hotpot.ai/art-generator">hotpot.ai</a>)</p><h3>The models</h3><p>The models I’ve chosen to evaluate are:</p><ul><li><a href="https://openai.com/index/gpt-4o-and-more-tools-to-chatgpt-free">ChatGPT 4o</a> — (by OpenAI released on May 13, 2024)</li><li><a href="https://www.anthropic.com/news/claude-3-5-sonnet">Claude 3.5 Sonnet</a> — (by Anthropic released on June 21, 2024)</li></ul><p>Why these models?</p><ul><li>they have been recently release, and in close proximity to each other</li><li>they were developed by two of the leading “AI” companies</li><li>they make bold promises</li></ul><h3>The test</h3><p>The test I’ve used is a standardized exam called “Bacalaureat” (BAC for short), taken at high school graduation in several subjects, nationwide in Romania. Passing the exam is generally required for admission to higher education. From all possible subjects, I’ve settled on using the math exam, as it is objective to evaluate and the math syntax and grammar are international, easy to understand for anyone.</p><p>There are several levels at which the math exam can be taken (M1,M2,M3,M4), and I went for the second hardest (M2), which was given to students who studied in classes focused on natural sciences. I did not go for the most advanced level (M1), as I don’t think I could have fully understood the solutions and verified it myself.</p><p>These exams are published in several different languages, for all the significant minorities living in Romania, however they are not published in English. So just to keep things simple for myself, and to give an extra challenge to the language models, I’ve left the exam questions in the original Romanian language.</p><p>As for the evaluation, I’ve used the official solution and scoring guides published by the government, and I went through the language model answers, manually, to grade the solutions myself.</p><p>Why the Math M2 BAC 2024 exam in Romanian?</p><ul><li>because it’s a standardized test, with official scoring guidelines</li><li>that was published and written recently (so low probability of leakage in the training data) by high school graduate students</li><li>because it’s objective, and international</li><li>the M2 level is easier for me to understand and I’m able to follow the solutions and evaluate them manually</li><li>a multilingual math tests is more challenging, however math equations are language independent, so this should not be a huge obstacle for these models</li></ul><p>Links:</p><ul><li><a href="http://subiecte2024.edu.ro/2024/bacalaureat/Subiecte_si_bareme/">official goverment website for the Bacalaureat exam</a></li><li>exam questions reuploaded to github — <a href="https://github.com/semmi88/semmi88.github.io/blob/master/blog_posts/mat_st-nat_2024_LRO.pdf">Math M2 BAC 2024</a></li><li>evaluation and grading guide reuploaded to github — <a href="https://github.com/semmi88/semmi88.github.io/blob/master/blog_posts/mat_st-nat_2024_bar_LRO.pdf">Math M2 BAC 2024 eval</a></li></ul><h3>The prompt</h3><p>I’ve uploaded the pdf file containing the exam questions and used just one, simple zero-shot prompt to ask the language model to solve the exam:</p><pre>Hello, I want to test your knowledge on a standardized mathematics test. <br>I&#39;m going to share with you the exam questions and expect you to <br>solve them to the best of your knowledge. <br>The questions are in Romanian, and I will expect the answers also <br>to be in Romanian. This is an extra complication, but the reason for it <br>is that I want to test your foreign language understanding as well. <br>And finally, it&#39;s okay to skip a question or not to answer a questions <br>if you don&#39;t know how. Best of luck!</pre><h3>The results</h3><p><strong>Drum roll!</strong></p><p>The exam scores go from 10 to 100 points.</p><ul><li><strong>ChatGPT-4o</strong> scored <strong>25 points</strong></li><li><strong>Claude 3.5 Sonnet</strong> scored <strong>43 points</strong></li></ul><p>Okay, I have to admit that I expected more, I expected these language models to pass the exam (by scoring more than 50 points, although Claude got close to this). But probably this is me having unrealistic expectations, because of all the hype around language models.</p><p>Thinking about this rationally, this is an exceptionally hard task. Multilingual, high school math exam, on the first try, using just one prompt and the raw exam file — with all the intricate math notation (square roots, integrals, matrices). Given all this, this is a great try on the first attempt. The questions were understood by the models (despite being in Romanian and using lots of math notation), and the answers were coherent and some of the answers followed the correct math calculation and reasoning.</p><p>These low exam scores could probably be drastically improved, by iterating on the prompts, asking follow-up questions and guiding the models. However, I don’t have time for that experiment this time.</p><p><a href="https://github.com/semmi88/semmi88.github.io/blob/master/blog_posts/llm_eval_scores.pdf">Here</a> are the breakdowns for the points scored on each exercise by the models. The main takeaway is that many mistakes can be attributed to the inability of both models to correctly read math syntax from the pdf file, resulting in incorrect formulas and calculations. Probably this is something that will greatly improve in the future.</p><p>Some interesting differences:</p><ul><li>ChatGPT understood the task right away, while Claude needed an extra prompt to start solving the exam</li><li>ChatGPT gave answers in a friendlier, “mathy” format</li><li>ChatGPT skipped many of the questions, which contributed to its worse performance. (On the other hand this was instructed in the propmt and inadvertedly could have impacted the final results)</li><li>Claude answered the questions by sections, and asked for feedback to continue on to the next section</li><li>Claued concluded in two cases that solving the equation is too complex in the limited time of an exam :)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*MDGmyPEm7G_dZY4R.png" /></figure><h3>Philosophical digression</h3><p>So a language model cannot graduate high school in Romania. Or at least not yet. Phew, that’s reassuring. But let’s imagine for a moment that it could. Let’s assume that next year or the year after, the same evaluation will result in test scores of 99%.</p><p>What would that mean? Would language models be smarter than high school students? Not necessarily. Is a calculator smarter than me, because it can calculate the nth root of a number, which I could not? Standardized tests offer a common way to evaluate and rank students, but just as any kind of evaluation, they are not perfect. They are a tool to measure some skills, because the education system needs to somehow rank and grade students, but they do not measure all skills.</p><p>But is there any value in making students write an exam, which could be aced by a language model? There might be some value to it still. Is there any value in learning and playing chess, even though the very best players (by far) are computer algorithms? Chess is still a popular game with a huge fanbase, and playing chess improves skills which can be used in other areas of life (focus ability, pattern matching, memorisation). The same way, exams where language models are superior, could still be beneficial to sharpen skills for us, little humans.</p><h3>Full chat logs for ChatGPT</h3><ul><li><a href="https://chatgpt.com/share/ad0aa15a-866b-4089-8a6e-17dd321ef752">OpenAI shareble link — ChatGPT multilingual math exam chat</a></li><li><a href="https://github.com/semmi88/semmi88.github.io/blob/master/blog_posts/chatgpt_full_math_exam_chat_log.md">Markdown verison</a></li></ul><h3>Full chat logs for Claude</h3><ul><li>No shareable link from Anthropic :(</li><li><a href="https://aiarchives.org/id/yEYka1cLaJqBqobx5BOV">AIArchives link to Claude multilingual math exam chat</a></li><li><a href="https://github.com/semmi88/semmi88.github.io/blob/master/blog_posts/claude_full_math_exam_chat_log.md">Markdown version</a></li></ul><h3>Screenshot of ChatGPT taking the exam — partial</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/910/0*tF4AN7xSyk3al6SA.png" /></figure><h3>Screenshot of Claude taking the exam — partial</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0U2frdYktRxc5CIS.png" /></figure><p><em>Originally published at </em><a href="https://semmi88.github.io/blog_posts/llm_eval.html"><em>https://semmi88.github.io</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ac4b398babe5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Nuggets of Wisdom — from NormConf 2022]]></title>
            <link>https://medium.com/@endre.sukosd/nuggets-of-wisdom-from-normconf-2022-9987ec6f43e0?source=rss-b521b6d638f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/9987ec6f43e0</guid>
            <dc:creator><![CDATA[Endre Sukosd]]></dc:creator>
            <pubDate>Wed, 21 Dec 2022 23:59:02 GMT</pubDate>
            <atom:updated>2022-12-23T16:20:50.914Z</atom:updated>
            <content:encoded><![CDATA[<h3>Nuggets of Wisdom — from ormConf 2022</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-yNuRQqNDhdqvr-gE7KlFw.jpeg" /></figure><pre><br>Table of contents:<br><br>    Vicki Boykis - Most ML work is not glamorous<br><br>    Vincent Warmerdam - Must have skills are fake news<br><br>    Matthijs Brouns - Small Docker and Python Wheels<br><br>    Luca Belli - The great overlap between senior engineers and managers<br><br>    Joel Grus - What&#39;s the simplest possible thing that might work, <br>                and why didn&#39;t you try that first?<br><br>    Peter Sobot - Thinkg about costs of engineering and ML<br><br>    Katie Bauer - Translate PM speak<br><br>    Jamed David Long - Substractive thinking<br><br>    James Kirk - Building Recommender Systems<br><br>    Chris Albon - Don&#39;t do invisible work</pre><p>A week ago I attended <a href="https://normconf.com/">NormConf — The Normcore Tech Conference</a> — and I truly enjoyed it. In fact, I’ve enjoyed it so much, that I’ve decided to write a blog post about it, in order to summarize some learnings, but also to promote the conference. All talks mentioned here are short (20 minutes) and punchy and make for a great listen in my opinion.</p><p>The whole idea behind NormConf is simple: let’s highlight the mundane, unsexy, normcore, day-to-day stuff that is actually done by data scientists and machine learning engineers. So instead of talking about how our awesome recommendation engine uses the latest and greatest algorithms, let’s talk about how did we actually solve our Python dependency issues.</p><p>This idea is really powerful, it frees you from the necessity to show off, to brag about your system, and gives space to talk about basic engineering struggles. Thinking about it in a philosophical way, I could say that this allows the speakers to show vulnerability in a technical sense, humanizing them, bringing them close to the audience, we have all been there. It’s a fresh take on tech conferences, and in my opinion a very welcomed one.</p><p>While the conference is mainly targeting data and ml people, most of the learnings can be applied to a wide range of jobs, so don’t be discouraged by that. I’ve got to say big kudos to the whole organizing team and to the speakers, who come off as really kind people and great educators. All images and ideas are taken directly form the conference, with the original author mentioned and linked. So with that let’s dive in.</p><h3>Vicki Boykis — Keynote</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=556">Vicki Boykis — NormConf talk</a></li><li><a href="https://vickiboykis.com/">Vicki Boykis — tech blog</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_KIv0jGBz113Tukd.jpg" /></figure><p>As the mastermind behind the whole conference, Vicki’s keynote talk perfectly sums up its main ideas. In the data science and machine learning space — the advertised map (of what we do at work) is not the true territory. The interviews and medium articles do not encompass most of what is done on a day-to-day basis, like creating dictionaries and adding things to lists. Building machine learning systems is just building software, engineering work, and it’s fragile, and lot’s of things can break, and it’s not glamorous. Solid fundamentals, which seem boring, actually build to advanced work, so we should not be discouraged.</p><h3>Vincent Warmerdam — Group-by statements that save the day</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=2187">Vincent Warmerdam — NormConf talk</a></li><li><a href="https://calmcode.io/">Vincent is the creator of — CalmCode blog</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*8Fjs1A6_l8pOn20b.jpg" /></figure><p>This talk leaves you with a great sense of calmness. Today there are lot’s of headlines and course marketing materials promoting must have skills for data scientists. But, Vincent argues, we should not worry about these too much. The real must have skills are common sense and critical thinking. Of course tools can be super useful, but there is too much emphasis on learning technical tools, which are just tricks to help us get through the day. Keep the calm in mind, stop bragging about the tools and start sharing anecdotes.</p><h3>Matthijs Brouns — How small can I get that Docker container?</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=7645">Matthijs Brouns — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7UcSoo9PXVXl7t7n.jpg" /></figure><p>Matthijs shared tricks on making Docker images smaller, like using dockerignore, small base image, few layers and multi-stage builds to remove build-time dependencies. However, for me the most important part of the talk is the explanation of Python Wheels and why don’t they don’t work on Alpine Linux OS. Wheels are the reason that downloading and installing most Python packages just works nowadays. Wheels are a binary distribution format, which means that they contain all external C code dependencies pre-built for your OS. This contrasts with source distribution formats (tar.gz), where you need to compile the C dependencies on your machine, when you install the package. Wheels are based on a standard (called standard manylinux), a subset of kernel and user space APIs that is assumed to work on many different types of linux distributions (debian, ubuntu, etc). However, because Alpine wants to be so small, it does not conform to this standard and uses a slightly different set of base packages, leaving you no choice but to compile C code dependencies. This often does not make sense, because it’s a lot of time investment and complicates building your images.</p><h3>Luca Belli — Geriatric data science: life after senior</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=11217">Luca Belli — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*TbzIkND8ssbNsS6S.jpg" /></figure><p>Luca talks about senior leadership roles. One popular myth is that senior manager roles are very different from senior engineer, individual contributor roles (IC roles). People who pursue the IC career ladder, tell themselves that they don’t like meetings, they want to work with computers, not people, they want to spend time coding, and that the hard parts of each project is the technical work. These statements turn out to be mostly false. There is lot’s of overlap in the necessary skills, and any sufficiently advanced engineer is indistinguishable from management.</p><h3>Joel Grus — What’s the simplest possible thing that might work, and why didn’t you try that first</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=16892">Joel Grus — NormConf talk</a></li><li><a href="https://joelgrus.com/">Joel Grus — tech blog</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*bzp7EnBtyaBdKT8C.jpg" /></figure><p>Joel is the author of some fantastic books (like <a href="https://joelgrus.com/2019/05/13/data-science-from-scratch-second-edition/">Data Science from Scratch</a>), and just the title of his talk is a fantastic advice. It’s a powerful argument and you can’t really argue with it, you should always try the simplest approach first. However he argues, the simplest solution it’s not always the least complex one. Instead it could just be the simplest one to use. Complexity can be abstracted away in smart ways, tools can be created that allow you to use complex machinery in a simple way. As an example, when doing text classifications low complexity models like logistic regression or naive bayes seem the simplest. However with huggingface libraries you can use pretrained language models with just a few lines of code, and get a significantly better results, and so you should use this approach.</p><h3>Peter Sobot — It’s all about cost: how to think about machine learning products</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=18388">Peter Sobot — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*NYtpA6MyU343le1P.jpg" /></figure><p>As engineers, we should strive to build the best thing given the constraints (like Time and Cost). Machine learning solutions are costly, so we should only use them in specific places where we benefit from it the most, and use them in an economical way. An inventive way to minimize costs is to use a cheap, inaccurate ML model to pre-filter our data, before applying the expensive heavy ML model.</p><h3>Katie Bauer — How to translate to PM speak and back</h3><ul><li><a href="https://youtu.be/pR3QUegElmA?t=29146">Katie Bauer — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*lulaORQjfGMW0Jxp.jpg" /></figure><p>Often there is a misunderstanding between engineers and product people (PMs — Product Managers). Why is this the case? One common pattern is that engineers give very technical answers, overwhelming with the level of details, when actually what product managers are interested in are simple high level summaries, and explanations of the levers that can be pulled to change outcomes. A helpful advice is to assume good intent. People you work with are on the same team as you, and even though they might think and work in a different way, they are trying to do the right thing. Also consider incentives to be able to communicate better.</p><h3>James David Long — I’d have written a shorter solution but I didn’t have the time</h3><ul><li><a href="https://youtu.be/DYz5dMmtO6o?t=12655">James David Long — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*P0KjuPM8jshyqFgH.jpg" /></figure><p>By default our brains are thinking in additive ways. Subtractive thinking is hard and people don’t tend to do it, but there is great benefit in it. The whole concept of Minimum Viable Product is an exercise to trick you brain into subtractive thinking, figuring out what’s the least we can do, to make the most positive value. Another great example is, when you are facing a bug, try creating a minimum reproducible example, because removing all the noise usually leads to the answer or makes it easier for someone else to find the answer. This is a reductive exercise and it’s a critical meta skill.</p><h3>James Kirk — Data’s desire paths: shortcuts and lessons from industrial recommender systems</h3><ul><li><a href="https://youtu.be/DYz5dMmtO6o?t=3771">James Kirk — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*OeODBcC3RrwTfkYc.jpg" /></figure><p>James talks about how to frame recommender systems, because most of the time they are poorly framed (loose concepts about how it should work or using technology in search of a problem). His advice can be applied to almost all types of projects. For the right framing, make sure that the team is aligned and you have crisp requirements: clearly defined user with a use-case, a measurable definition of success and how does recommendation success translate to business success. The three different flavors of recommendation are: classic recommendation based only on context, personalization uses user data and interaction data, “omakase” — you choose, infinite feed style based on loosely formed requests. Recommender systems are similar to search, but the query is based on the user/context and can be optimized for other factors not just precision — novelty, broadness, interactivity.</p><h3>Chris Albon — Don’t do invisible work</h3><ul><li><a href="https://youtu.be/DYz5dMmtO6o?t=20041">Chris Albon — NormConf talk</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*X7FNGRFArFnFlshw.jpg" /></figure><p>Without tools, people suck at remembering. A month from now you won’t really remember all the things that you have worked on, and your manager will barely remember anything you have worked on. But performance review, promotions, bonuses are all based on work that people remember. Solution is to track your work and tell people about your work. Nobody is going to record your work for you, it is on you to keep a record. The format/tools you use don’t really matter, just start doing it (example: brag documents, daily activity log, worklog entries, blog posts). These records will become very handy for future evaluations or updating your resume.</p><p><em>Originally published at </em><a href="https://semmi88.github.io/blog_posts/normconf_summary.html"><em>https://semmi88.github.io</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9987ec6f43e0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Taming the Rubik’s Cube — or How I met Group Theory]]></title>
            <link>https://medium.com/@endre.sukosd/taming-the-rubiks-cube-or-how-i-met-group-theory-52766ab2e930?source=rss-b521b6d638f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/52766ab2e930</guid>
            <category><![CDATA[rubiks-cube]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[group-theory]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Endre Sukosd]]></dc:creator>
            <pubDate>Sun, 22 May 2022 18:23:33 GMT</pubDate>
            <atom:updated>2022-05-28T16:00:05.415Z</atom:updated>
            <content:encoded><![CDATA[<h3>Taming the Rubik’s Cube — or How I met Group Theory</h3><p>Recently I’ve read the book <a href="https://semmi88.github.io/book_reviews/cubed.html">Cubed, written by Ernő Rubik</a> (the inventor of the cube), and this book rekindled my love for the Cube. The book details the process of invention and searches for reasons to explain its popularity. The argument put forth, with which I agree, is that it is not a coincidence that the Rubik’s Cube became widely known around the world. There is something universal, almost magical about it, and it is full of contrast and contradictions: simplicity vs complexity, pleasure vs frustration.</p><p>The game itself is easy to understand, intuitive — there is no need for an instruction manual. A child and an adult can both understand the mechanics and the goal within 3 seconds of holding the cube and playing with it. Nevertheless it is a challenging puzzle, even just after a couple of rotations our minds cannot follow the patterns and we can get lost, unable to find our way back to the unscrambled state. It is frustrating, because the difficulty of the puzzle is not evident from its simple, aesthetically pleasing appearance. The cube evokes emotions, as it is not what we expect. And we, as humans, are naturally curious and drawn to these types of challenges, we want to be able to understand its mysteries and be able to tame the puzzle.</p><p>No wonder that the Rubik’s Cube became a cultural symbol, a symbol of intelligence and problem solving. It brought on a revolution in edutainment (education + entertainment) by offering fun ways to introduce mathematical concepts to kids. And in the process it made studying, thinking about problems cool again. I could even go as far as to say, that the Rubik’s Cube gave us a universal value system on which we can all agree. As somehow, deep down, we can all agree that solving a scrambled cube is a good thing, being able to understand and solve complex puzzles is a useful skill in life, and it is worth investing time to learn these skills.</p><blockquote>The Rubik’s Cube made the world a better place</blockquote><h3>Cubing Basics</h3><p>So how can you solve the cube? There are several well documented strategies, like the <a href="https://ruwix.com/the-rubiks-cube/how-to-solve-the-rubiks-cube-beginners-method/">layer-by-layer approach</a>, where you focus on completing each layer at a time by orienting and permuting the cubies. In total you need to learn about 5 algorithms, and with practice you will be able to solve the cube in around 2 minutes. That is pretty cool!</p><p>Of course there are better, more advanced solving methods, but these require you to memorize more algorithms. Speedcubers, people who compete in cube solving world championships, learn about 200 different algorithms, which they can apply to different states of the cube, and so are able to solve a scrambled cube in under 10 seconds. Now that is impressive!</p><ul><li>But where do these solving methods come from?</li><li>Why do they work, what is the trick behind them?</li><li>And how could you come up with a solving method?</li></ul><p><em>These are the questions that I will try to explore in this article</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/496/0*iMbRsjZa_t-ImqwI.jpg" /></figure><p>A first intuition about creating your own solving methods consist in the observation that every rotation can be undone. Meaning that if we know exactly the rotations that scrambled the cube, then the puzzle becomes trivial. We can just do those moves in reverse and we get back to the original state. This is a key observation, although on its own it is not very helpful (as we usually don’t know the rotations that scrambled the cube in the first place).</p><p>The difficult thing about solving the cube is that rotating any face moves a lot of pieces around, and it is hard to follow and keep up with all the changes. Ideally it would be nice to come up with algorithms that only affect a small part of the cube, only a small subset, like rotating two corners and leaving the rest of the cube unchanged. The good news is that using intuition and a bit of mathematics, we can come up with such algorithms. To be able to describe and discuss these algorithms, let’s go over some cubing basics.</p><p>The Rubik’s cube is made up of 26 tiny cubes (or cubelets), which can be grouped in three categories:</p><ul><li>6 center pieces, which have one colored face</li><li>12 edge pieces which have two different colored faces (or facelets)</li><li>8 corner pieces, which have three different colored faces (or facelets)</li></ul><p>Solving methods usually are described using the <a href="https://ruwix.com/the-rubiks-cube/notation/">Standard Cube Notation</a>, which assigns a single capital letter to face rotations.</p><ul><li>90° clockwise rotation of the 6 faces: F=Front, B=Back, R=Right, L=Left, U=Up, D=Down</li><li>90° rotation of middle layers: E=Equator (between Up-Down), M=Middle (between Left-Right), S=Standing (between Front-Back)</li><li>Counterclockwise rotations of 90° are described by adding an apostrophe: F’ is the opposite (or inverse operation) of F</li><li>Multiple rotations are described by adding a number after the letter: FFF = F3</li><li>Turning a face 4 times leaves the cube unchanged (identity operation), so: F4=1</li><li>Three turns in one direction equal a turn in the opposite direction: F3=F’ (3 x 90 clockwise = 1 x 90 counterclockwise turn)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/0*gH_w7HmC32caVjsj.jpg" /></figure><h3>Hello Group Theory</h3><p>The cube is a highly symmetric twisty puzzle. It can be studied using Group Theory, which is an abstract branch of mathematics that studies patterns and symmetries. To be more specific, the cube can be described as the mathematical structure called a permutation group.</p><p>A permutation group is an ordered list of numbers, on which we define permutation operations. These operations can rearrange the numbers, in a certain ways, and also meet the four primary properties of a group (have Identity Operation, have Inverse Operations, are Associative, exhibit Closure).</p><p>The cube has 6 different colored faces and each color is repeated exactly 9 times, so it can be considered an ordered list of 54 numbers. Rotating a face of the cube then just rearranges the ordered list in a certain way (it’s a permutation operation). Repeating and combining these permutations we can define new permutations, which rearrange the list in new ways. This way we can transform the problem of solving the cube, into studying permutations on lists of numbers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*J-Frn4UkbyAkkQbl.png" /></figure><h3>Non-commutativity makes the puzzle hard</h3><p>An important thing to notice is that the face twists (these permutation operations) are non commutative. This just means that the order of operations matters, and changing the order might give us a different result. (This is also called non-abelian, after the mathematician Niels Henrik Abel).</p><ul><li>this is different than multiplication, which is commutative, where reversing the order doesn’t change the result 10 x 2 = 2 x 10</li><li>it is more like division, where 10 / 2 ≠ 2 / 10</li></ul><p>To see this non commutative property of cube rotations in action, let’s just do the following sequence of moves — R B (right face rotation, followed by a back face rotation) - and check the end state of the cube. Let&#39;s compare this to the end state we get if we apply the operations in reverse order - B R (back face, then right face rotation). As we can see, the order matter, as we end up with different end configurations for the two cases: R B ≠ B R</p><p><strong>If you don’t own a Rubik’s cube, but want to follow along, just use this </strong><a href="https://rubiks-cube-solver.com/"><strong>neat online cube solver</strong></a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/0*j9rkzzhYtO5pduXg.png" /></figure><p>And in fact this non-commutative property is what makes the puzzle hard, because we need to apply the rotations in a careful order. If twisting the cube faces would be commutative, then solving the cube would be trivial. To see this, let’s take a simplified version of the puzzle, where we can only turn the front (F) and back (B) faces (all other rotations are not allowed). In this specific case, we have commutative operations, because the front and back faces don’t intersect (the facelets that they are permuting are independent of each other), and so the order of twists does not matter. (A fancy way of saying this in mathematics is that “disjoint permutations” commute).</p><p>No matter how much someone scrambles the cube with these two operations, the solution will be trivial. We know that making 4 turns of any face gets us back to the initial starting position. So if the front and back faces are not in the initial starting position, we just need to turn them 1,2 or 3 times (depending on the setup) and the cube is solved. So we can conclude that commutativity is boring, when it comes to cubing.</p><p>As a side note, computer solving algorithms (like the Thistlethwaite algorithm), use principles from group theory and similar subgroups (with restricted set of moves) to reduce the complexity of solving the cube and guarantee a worst case scenario of 45 moves to solve any scrambled cube.</p><h3>Commutators — a cubers best friends</h3><p>As we saw before, some operations on the cube are non-commutative (right-back turns, R B ≠ B R), while others are commutative (front-back turns F B = B F). So what determines commutativity? How can we define it or measure it? And why should we care about it?</p><p>In mathematics we measure how commutative two operations are using a commutator. The idea is to apply the two operations and their inverses one after the other and check the result. For example given X and Y operations, the commutator would be calculated as the sequence X Y X&#39; Y&#39;.</p><p>If the operations are commutative, the order can be exchanged ( X Y X&#39; Y&#39; = X X&#39; Y Y&#39;), and operations and their inverses will cancel each other out, and we get &quot;zero&quot; or Identity Operation as a result (which means that the state is left unchanged). However for non-commutative operations, the result of the commutator will be different from &quot;zero&quot; and will reflect the level commutativity. Almost commutative operations will have a &quot;simple&quot; commutator, and operations which are far from commuting will have a &quot;complex&quot; commutator. So in a way commutator shows how many elements were &quot;co-mutated&quot; by applying both operations and their inverses.</p><p>Coming back to cube solving, we want to find algorithms which modify only a few parts of the cube, and leave the rest unchanged. We can achieve this goal by finding two operations which almost commute. Applying the commutator of these operations will affect only a few cubelets, as most of the changes will be canceled out.</p><p>And how can we find operations which almost commute? As a rule of thumb we can say that permutation operations “almost commute” if they only affect a few elements in common. (This is not generally true, but a good enough assumption for our use case). To really understand all this, let’s look at two examples.</p><p><strong>And again, if you don’t own a Rubik’s cube, but want to follow along, just use this </strong><a href="https://rubiks-cube-solver.com/"><strong>neat online cube solver</strong></a><strong>, which can also execute algorithms specified with the standard cube notation</strong></p><h3>RoCo</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/0*pIXzrthzqNQB5zEk.jpg" /></figure><p>Say that we want to come up with the algorithm that rotates corners on the top layer, meaning that it will not move them, just change their orientation. Let’s call this algorithm Roco (from Rotates Corners — and in this case specifically upper-right corners). Here is the strategy that we can apply:</p><ul><li><strong>Step1</strong> We find a sequence of useful moves (let’s call it X) — twists that leave the top layer unchanged, except for the one useful change that we are interested in: a single corner cubelet rotated. This is easier than it sounds, because even though we have to be careful with the top layer, our operation can arbitrarily mess up the bottom layer. So after some tries, we could come up with the following sequence of 6 moves: R&#39; D R F D F&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/567/0*dBJFYqYYLCEU3i_z.jpg" /></figure><ul><li><strong>Step2</strong> After this we do a simple auxiliary/helper move (let’s call it Y) — which barely intersects with our sequence of useful moves (X). This could just be twisting the upper layer, so our rotated corner cubelet is replaced by another corner cubelet, and we do not touch the bottom layer. The intersection of the two moves (X and Y) then is just in the top layer, meaning that everything which is messed up in the bottom layer, will be reversed by the commutator: U</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/312/0*gJC8nKkHiCyUDG0A.jpg" /></figure><ul><li><strong>Step3</strong> Do the inverse of the useful moves in Step1 (X’) — this will undo all the mess in the bottom layer, and also rotate the new corner cubelet in the opposite direction: F D&#39; F&#39; R&#39; D&#39; R</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/603/0*XW24MTXFlXAJHf_e.jpg" /></figure><ul><li><strong>Step4</strong> Do the inverse of the auxiliary/helper move in step2 (Y’)- this just gets the flipped corners back to their initial position: U&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/337/0*KanXaz2Ooky_Ui9E.jpg" /></figure><p>If you look carefully, with these 4 steps we executed the commutator X Y X&#39; Y&#39; of two operations. And because these operations almost commute, we undo most of the changes to the cube, except the ones involving common elements of X and Y in the top layer - the rotated corners. And that is exactly what we wanted!</p><p>This formula can be applied to generate all sorts of algorithms that modify only a few parts of the cube. And it is fairly simple, the only creative part is to come up with the first sequence of operations (the useful moves), which make a slight change in the top layer.</p><h3>SwEd</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/464/0*f4ybYCVtk-mRBceV.jpg" /></figure><p>Another example would be swapping edge cubelets, moving three of the edges in the upper layer (permute them in a cycle), without changing their orientation. Let’s call this algorithm SwEd (from Swapping Edges — and in this case specifically upper layer, front-right-back edges).</p><ul><li><strong>Step1</strong> The useful moves (let’s call it X) — in this case is swapping a pair of edge cubelets in the top layer (edge1 swapped with edge2). Again, here we don’t care about messing up the bottom layer. A possible sequence would be applying the following 7 twists: M S D S&#39; D&#39; D&#39; M&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/567/0*c5dRFxcBHl9Aytbe.jpg" /></figure><ul><li><strong>Step2</strong> We apply a similar auxiliary/helper move (let’s call it Y) as before, just twisting the upper layer, so our pair of swapped edges are replaced by another pair: U</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/0*NxxCG02y-VTuu_ym.jpg" /></figure><ul><li><strong>Step3</strong> Do the inverse of the useful moves in step1 (X’) — this will undo all the mess in the bottom layer, and will also swap the new pair of edge cubelets (edge1 swapped with edge3): M D D S D&#39; S&#39; M&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/0*ia8UuGsnOB33k2XY.jpg" /></figure><ul><li><strong>Step4</strong> Do the inverse of the auxiliary/helper move in step2 (Y’)- this just gets the upper layer back to it’s initial position U&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/413/0*-4bTUIo_RXDATuaO.jpg" /></figure><p>Similarly as before, in these 4 steps, we applied the commutator X Y X&#39; Y&#39;. And because the only common elements between the operations were the swapped edges in the top layer, all other layers are left unchanged. We could go on and invent other algorithms, but will stop here for now.</p><h3>Parity — The laws of the cube</h3><p>The algorithms that we have come up with (RoCo, SwEd) work really well, but strangely they have some constraints. We cannot rotate just one corner, we always have to rotate two of them. Similarly we cannot swap only two edges, we have to swap three of them. Now why is that?</p><p>This is related to the concept of parity, which refers to whether a permutation is even or odd. An even permutation can be represented by an even number of swaps, while an odd permutation can be represented by an odd number of swaps. Now, because of the mechanics and the symmetries of the Rubik’s cube, there are certain “laws” that arise, which put constraints on possible cube states.</p><p>Whenever we twist a face of the cube, we always perform an even number of swaps. The center cubelet does not move, and each of the other 8 cubelets of a face changes location (even number of swaps). And so, no matter how many twists we make, the accumulated number of swaps will always remain even (as even + even = even). So it is impossible to swap only two cubelets of the cube using legal moves, as that would be an odd number of swaps.</p><p>If we look at corner pieces, there are three possible orientations to which we can assign numbers: correctly orientation (0), rotated clockwise (1) or rotated counterclockwise (2). Now we can prove that the sum of corner orientations always remains divisible by 3. Think of a solved cube, and define a corner as correctly oriented if the top/bottom facelets have the top/bottom center colors. Now let’s examine the 6 possible face twists and how they affect the sum. Up and Down rotations don’t change the corner orientation (so the sum stays 0). For the remaining 4 side turn (Left, Right, Front, Back) we always rotate 4 corners, two in clockwise and two in counterclockwise direction (so the sum is increased by 1+1+2+2=6). And so the sum always remains divisible by 3, no matter how many legal turns we make. Making it impossible to rotate only one corner, as that would increase the sum by 1 or 2, breaking the law.</p><h3>Conjugates — a cubers second best friends</h3><p>Once we came up with some algorithms (RoCo, SwEd), our next step would be to find ways to apply these algorithms more flexibly. For example these algorithms only work if the cubelets are all in the upper layer and in specific positions. This is where conjugates come to our help.</p><p>In group theory the conjugate of an operation X, with another operation Y is defined as the sequence of X Y X&#39;. But from the cubers point of view, the important thing to know is that if X and Y are possible operations on a group, then the conjugate X Y X&#39; also is. And this means we can combine moves that we already know in a flexible way and make new algorithms.</p><p>This is typically applied with a setup move X, then doing the main algorithm Y (usually a commutator), and finally undoing the setup move X’. This pattern offers us an easy way to reuse algorithms. For example, let’s say we want to rotate the upper layer’s front-right corner and the bottom layer’s back-right corner:</p><ul><li><strong>Step1</strong> These corner cubelets we want to rotate are not on the same layer, so we apply a setup move (X) and twist the back face to bring them onto to top layer: B</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/298/0*Fm91r26s1cPW9wgU.jpg" /></figure><ul><li><strong>Step2</strong> Now, we can just apply the RoCo algorithm to rotate the two corners in the upper layer — right hand side: R&#39; D R F D F&#39; U F D&#39; F&#39; R&#39; D&#39; R U&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/421/0*S_qvyAvTE2O00zy3.jpg" /></figure><ul><li><strong>Step3</strong> Finally, we undo the setup move, to get back to the original cube position: B&#39;</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/0*H_mQv0BQrwYzffI-.jpg" /></figure><p>Notice that in these three steps we have executed a conjugate X Y X&#39;, where the middle operation Y was in itself a series of operations, more precisely a commutator for corner rotations. Equipped with all these tools we can confidently go on and solve the Rubik&#39;s cube and many other similar twisty puzzles!</p><p><strong>References</strong></p><ul><li><a href="https://www.youtube.com/watch?v=7LTCEyrQk44">https://www.youtube.com/watch?v=7LTCEyrQk44</a></li><li><a href="https://www.youtube.com/watch?v=54SGrZbLcoE&amp;t=2161s">https://www.youtube.com/watch?v=54SGrZbLcoE&amp;t=2161s</a></li><li><a href="https://math.berkeley.edu/~hutching/rubik.pdf">https://math.berkeley.edu/~hutching/rubik.pdf</a></li><li><a href="http://www.geometer.org/rubik/group.pdf">http://www.geometer.org/rubik/group.pdf</a></li><li><a href="https://rubiks-cube-solver.com/">https://rubiks-cube-solver.com/</a></li></ul><p><em>Originally published at </em><a href="https://semmi88.github.io/blog_posts/rubiks_cube.html"><em>https://semmi88.github.io</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=52766ab2e930" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[I’ve failed my Facebook interview, but that’s okay]]></title>
            <link>https://medium.com/@endre.sukosd/ive-failed-my-facebook-interview-but-that-s-okay-d21fa509b678?source=rss-b521b6d638f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/d21fa509b678</guid>
            <category><![CDATA[failure]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[facebook]]></category>
            <category><![CDATA[mindset]]></category>
            <category><![CDATA[thoughts-and-feelings]]></category>
            <dc:creator><![CDATA[Endre Sukosd]]></dc:creator>
            <pubDate>Sun, 01 Aug 2021 20:22:18 GMT</pubDate>
            <atom:updated>2021-08-01T20:22:18.729Z</atom:updated>
            <content:encoded><![CDATA[<p>The idea for this blog post came to me after I had a hard time handling negative thoughts and emotions following my failed job interview with Facebook. I wanted to share what my thinking pattern was and how I tried to organise the thoughts in my head in order to end up with a more positive outlook. So in part, I am writing this as a form of self therapy. Also I am writing this because I can, as I am in between two jobs right now and I can share interview experiences freely, without affecting my actual work environment.</p><h3>Background</h3><p>Earlier this year a recruiter from Facebook reached out to me and asked if I would be interested in applying for a machine learning engineer position, in one of the new tech hubs about to be opened. I have to admit, I was flattered. For a software engineer interested in data and machine learning systems this seemed like a golden opportunity.</p><p>Although I’m not a huge fan of social media and Facebook had its fair share of controversy and scandals, I still wanted to get hired. Social media has a great potential to create good in society. And from an engineering perspective the technical challenges are amongst the greatest I can ask for. Being able to work on fake account identification and removal, for example, and by this fostering a healthy public discussion, seems like the kind of dream job to me.</p><p>And lastly, if I’m really honest to myself, I wanted to get hired to look cool. Getting hired by Facebook would mean that I made it. I wanted the validation and praise of others, and I was already imagining how it would feel, when people are congratulating me. Not the best kind of motivation, I realise, but at the time this was one of my main drivers.</p><h3>The interview process</h3><p>The first step was a technical screening, where I had to solve two medium difficulty coding challenges in 45 minutes. The problems were not obvious, but were not impossible either. I’ve managed to come up with a solution for both problems, however after the interview I’ve realised that I did make a couple of mistakes. After this realisation I was really angry at myself, as the mistakes were silly and very easy to spot, but I did not notice them during the interview. I was expecting to be rejected, because of my silly mistakes, but in the end neither of my solutions were correct. However, the feedback was that I passed the technical screening, as they valued the continuous communication and the way I have explained my thought process more than the correctness of the code. This was surprising and also gave me a lot of hope.</p><p>The next step was the onsite interview rounds, which was held remotely this time. This round consists of 5 interviews, each one with a duration of 45 minutes, covering various topics. There were two interviews focused on live coding, algorithms and data structures, similar to the technical screening. Then there was a behavioural interview, where they checked motivation and culture fit. Finally there were two design interviews, one focused on scalability and large systems and another specifically targeted at data and machine learning systems.</p><p>I was intimidated by this second round of interviews. They have sent me tons of materials to look through, videos, links to resources and example questions. It was overwhelming information at first. The good thing was that they gave me one month to prepare for the interviews, to have time to study and perform at my best. Studying and preparing, while having a full time job, was a bit hard, but a very rewarding experience. If you have a specific goal, like a scheduled job interview, you are way more likely to focus and have meaningful study sessions.</p><p>So then the time came for the interviews, which were scheduled during two consecutive days. I can’t really recall how they went because of the stress and focus and heightened emotions. But my general feeling was that I did well, with a weaker performance here and there, but I was feeling hopeful. A week later the rejection email came “thank you for your time and patience, but we won’t be proceeding to offer this time”.</p><h3>Initial thoughts</h3><p>As a note, the experiences that I describe here, I was not fully aware of at the moment I was experiencing them. However, thinking back later, they became more clear and I could manage to write them down and reflect on them.</p><p>My initial reaction after reading the rejection email was shock and disappointment. The little voice in my head (the monkey part of my brain, see below) started to talk and come up with an explanation of what had happened and why:</p><ul><li>I am not good enough for this job. Here is the clear evidence</li><li>What was I even thinking? I thought that I could be hired at Facebook, haha? I am not that smart</li><li>I was a fool for being hopeful, because I never even had a chance</li><li>I am not worthy</li></ul><p>Obviously this left me with a lot of negative feelings and self doubt, and I did not know how to deal with this. This was hurting my ego, so the monkey got to work again and came up with another explanation:</p><ul><li>But I am good enough, and they were wrong to reject me.</li><li>The interviews were not fair. A 45 minute interview cannot measure performance accurately</li><li>The questions were not fair. Actually they were stupid and useless, and have nothing to do with the day-to-day work</li></ul><h3>Dealing with failure</h3><p>A big help in dealing with these thoughts were the ideas that I’ve read in a book called <a href="https://www.amazon.com/Chimp-Paradox-Management-Program-Confidence/dp/039916359X">The Chimp Paradox</a>, written by a sports psychologist. This book presents a mind management strategy, based on a not so accurate, but very useful model of the brain. According to the book, the brain can be thought of as the interplay and cooperation of three systems — a computer, a monkey and a human. The computer is responsible for fastest, automatic responses. The monkey is responsible for quick emotional reactions, while the human is the one doing slow reasoning and logical thinking. The paradox comes from the fact that the monkey is a double-edged sword, quick emotional thinking can save your life and benefit you greatly, while at the same time it can make you end up in terrible situations. So in short, the good strategy is to get to know your monkey and learn to manage them. The monkey metaphor allows you not to blame yourself, but instead just accept the monkey acting out and find ways to deal with it.</p><p>As described in the book, the quick thoughts of the monkey that popped up in my head, are not necessarily true and for sure they are not helpful. I was hurt and wanted to explain away the pain. But I don’t have to blindly accept these monkey thoughts. I can choose to double check them, analyse them to see if they are actually true. Or I can try to change my mindset and expectations in order to come away with a more positive explanation.</p><h3>An unhelpful thought</h3><blockquote>A failed interview means I am not good enough</blockquote><p>Technically this is true, but it is not accurate enough. As a rejected interview means — I am not good enough — right now, at this point in my life. This does not mean that I will never be good enough. I might learn and be good enough later in life. This is essentially the fixed mindset versus the growth mindset thinking, where the growth mindset allows for the possibility to grow and improve throughout life.</p><p>Also — not good enough — is too generic. Not good at what? There are many skills and abilities a person can have and no one can excel at everything. There will inevitably be stronger and weaker areas. So let’s see what are the specific things, where I did not pass the bar. After a quick call with the recruiter, where I have asked for more detailed feedback, I found out the specifics. As it turns out the coding and behaviour interviews went great, and I had a weak performance in the design interviews, specifically in designing complex data flows. So now, I could focus on improving those areas in the future, leaving me with a better self image and more motivation.</p><h3>An untrue and destructive thought:</h3><blockquote>A failed interview means I am not worthy</blockquote><p>I was convinced that my worth is tied to obtaining that job at Facebook. If I fail the interview, that means that I have failed as a person. I have attached my value to my potential new job. This is not just unhelpful, but it is also false. If I think about it, I don’t value others based on job titles. My partner, my family, my friends are important to me because of other things, like their personalities, attitudes, common experiences and skills, not their job title. And the other way around, if I ask myself what would I like to be valued for by them? I’m pretty sure, I would not want to be valued based on my job. because that would be a sadder world to live in.</p><p>And yes, there are people who I admire also because of their job, but I don’t really know them or they are not important connections in my life, or it is not the only thing that I admire about them. And of course, it is a good thing to aspire, to dream about getting a specific job, but my self-worth should not be tied to obtaining it. I might think that I know exactly what I want from my job life, but the reality is that I cannot be sure and I’m just assuming. Job satisfaction and meaningful work is super important to me, but that does not depend on any one specific job opportunity and can be achieved in a myriad of different ways.</p><h3>An unrealistic expectation:</h3><blockquote>Interviews should be totally fair</blockquote><p>Well, interviews are not fair. Life is not fair in general, unfortunately. Expecting interviews to be 100% fair is unrealistic. The interviewer has to make a decision in a limited amount of time, with limited information. It’s hard for the candidate to transmit the right signals, and it’s subjective how these signals are received and interpreted by the interviewer. And on top of that luck will always play a role (of course, if you are better prepared, that role will be smaller). It’s far from a perfect process, but I cannot suggest an obviously better approach either.</p><p>Also, large tech companies have lots of applicants and the cost of hiring the wrong person is high. Because of this it makes sense for tech hiring to be conservative and risk averse, hire only the best performers on the interviews, even if they miss out on some potential talent.</p><p>So a more realistic expectation would be that interviews are not fair, but interviewers are doing their best, acting in a way which makes sense for their company. No matter how much I prepare I could still fail an interview, but that is okay, I can try again another time, another place. And finally, a failed interview could be a good thing, it could mean that I am not fit for the job right now, and could save me from ending up in a position where I will underperform and feel miserable.</p><h3>Conclusion</h3><p>In summary, disappointments are unavoidable in life and they can be tough to handle, however they need to be kept in perspective. The pattern I noticed in my own thinking is that after a failure the monkey in my head comes up with unhelpful explanations and applies unreasonable expectations, which lead to negative emotions. But after taking a closer look at these thoughts, and writing them down, discussing with someone, I could see that they are not necessarily true and many times they can be replaced by more realistic and helpful patterns of thinking. I can think of this whole experience as a great learning opportunity and hopefully, sharing this can help someone else, just as it helped me.</p><p><em>Originally published at </em><a href="https://semmi88.github.io/blog_posts/facebook_interview.html"><em>https://semmi88.github.io</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d21fa509b678" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Contact Tracing — a System Design Exercise]]></title>
            <link>https://medium.com/@endre.sukosd/contact-tracing-a-system-design-exercise-e8ef44136a63?source=rss-b521b6d638f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/e8ef44136a63</guid>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[exposure-notification]]></category>
            <category><![CDATA[contact-tracing]]></category>
            <category><![CDATA[software-architecture]]></category>
            <category><![CDATA[system-design-project]]></category>
            <dc:creator><![CDATA[Endre Sukosd]]></dc:creator>
            <pubDate>Tue, 05 Jan 2021 18:09:10 GMT</pubDate>
            <atom:updated>2021-01-06T08:11:55.800Z</atom:updated>
            <content:encoded><![CDATA[<h3>Contact Tracing — a System Design Exercise</h3><p>Contact tracing is one of the possible ways to control the spread of an infectious disease, by notifying the people who have been in contact with a confirmed positive case, and asking them to self-quarantine. Governments and health authorities are conducting contact tracing using various methods, some involving manual processes others using an automated system based on smartphone apps. How would you design such an automated contact tracing system? Here I want to present to you upfront a possible architecture with one use case depicted. Don’t worry about all the details now, as you go through the blog post hopefully all the pieces should fall into their place.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AGEOmLMnHH3z0FSL8CnyVw.png" /></figure><p>Also note that this is not purely a theoretical exercise, these systems already exist and are in production in some countries. At the time of writing this in January 2021, there are 8 countries from the European Union that use an official contact tracing app, inter-operating with each other, functioning beyond borders (Croatia, Denmark, Germany, Italy, Netherlands, Ireland, Latvia, Poland and Spain). Some of these systems even have open source implementations, for example the <a href="https://github.com/RadarCOVID">Spanish RadarCovid</a>.</p><p>Based on the latest data (27 December 2020) in Spain the app was downloaded by 6 million people (12% of the population), with around 25.000 positive cases declared through the app. This 25.000 only equals about 1.5% of the total positive cases reported since the initial release of the app 9th of September 2020 ( <a href="https://ourworldindata.org/coronavirus-data-explorer?zoomToSelection=true&amp;time=2020-09-09..latest&amp;country=~ESP&amp;region=World&amp;casesMetric=true&amp;interval=total&amp;hideControls=true&amp;smoothing=0&amp;pickerMetric=location&amp;pickerSort=asc">1.4 million cases</a>).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/96/0*G0_3jOtcF1eNNGgQ.png" /></figure><p>The goal of this blog post is to describe how these contact tracing systems are built and how they work, applying some simplifications to favor understandability. The approach taken is to present this as a systems design exercise, divided into the following parts:</p><ul><li>Scoping</li><li>High-Level Design</li><li>Design Trade-Offs</li><li>ENS — the basic building block</li></ul><h3>Scoping</h3><p>First, let’s talk about some facts that are given and some assumptions that we presume. To be able to detect contact between users we need a distributed system where each user carries a device, which is part of the system. Given the following assumptions it is possible and worthwhile to build such a system:</p><ul><li>enough people carry smartphones to build a contact tracing system using smartphone apps</li><li>close contact of smartphones is a good approximation of close contact of people</li><li>smartphones are not shared between different individual generally (or only in a negligible percentage of cases)</li><li>with time, enough people will use the app to make a difference or at least help out the authorities with contact tracing</li></ul><p>Other assumptions about the disease that we can make:</p><ul><li>infectious period of the disease is known or at least can be closely approximated — we can use 14 days in case of COVID-19 (as defined in the <a href="https://radarcovid.gob.es/politica-de-privacidad">Privacy Policy of a real app</a>)</li><li>for the disease to spread, individuals have to be in close physical contact — for which we can use the definition of less than 2 meters for more than 15 minutes (as in the <a href="https://radarcovid.gob.es/politica-de-privacidad">Privacy Policy of a real app</a>)</li></ul><p>This first assumption one is an important piece of information, as all data and events registered by the system can be deleted after 14 days, as they are no longer relevant. This puts limits on the storage space, network data transfer and computations needed and allows the system to scale nicely, as we don’t need to keep infinite history. The following assumption will help us when doing the calculations for close contact events and exposure detection.</p><p>Next, let’s roughly define the main use cases, and agree on the requirements of the system. These could be grouped in four separate categories.</p><p><strong>User proximity/close contact</strong></p><ul><li>detection</li><li>storage (for a limited time period) in order to check for exposure</li></ul><p><strong>Positive diagnostic cases</strong></p><ul><li>reporting — newly confirmed positive diagnosis of users can be added to the system</li><li>storage of all previously reported positive cases (for a limited time period) in order to warn of exposure</li></ul><p><strong>Exposure detection</strong></p><ul><li>check for user close contacts with a confirmed positive case in a given time period and calculate risk score</li><li>based on risk score notify user of possible exposure to the disease and clear medical instructions</li></ul><p><strong>Privacy</strong></p><p>So based on all the scoping above let’s try to come up with a simple design for such a system.</p><h3>High-Level Design</h3><p>There are some key technologies that we should be familiar with and make use of to build such a distributed system.</p><p>Firstly, for detecting proximity of mobile devices we should use a wireless data transfer technology. The natural choice is <strong>Bluetooth Low Energy (BLE)</strong>, which is a short distance, low power consumption technology, ideal for small data transfers between devices. The reduced power consumption is important for mobile devices, and our requirements do not require the transfer of large amounts of data. Other technologies are less suitable for our use case; NFC has insufficient range (only about 10cm, while the airborne infectious disease can spread further than 1 meter), while WiFi is aimed more towards high data throughput and has higher power consumptions.</p><p>Based on Bluetooth Low Energy, we need to choose some form of location-based technology. Here a good choice would be to use <strong>Bluetooth Beacon technology</strong>, which was specifically designed to broadcast information to other, nearby Bluetooth-enabled devices. This is used (by placing small hardware transmitters) in specific points of interest to distribute messages, like traffic information at a bus stop or marketing messages in stores. This kind of broadcasting only allows for 1-way data transmission, the emitter Beacon does not expect nor accept any response from the receivers, and so a Beacon cannot be used to track users against their will.</p><p>Mobile devices can act as a Bluetooth Beacons to periodically broadcast information, and can also periodically scan their surroundings to detect other Bluetooth Beacons broadcasting. The typical data packages broadcasted are a unique Beacon ID and other associated metadata like a web url.</p><p>So as a first approach, we could create a mobile app, let’s call it Virus Radar. This app would generate a random, universally unique ID (UUID) associated with the device (and the owner/user of the device), and start broadcasting that ID (with some metadata to specify that this should be used for contact tracing for a specific disease). The app would also scan and collect UUIDs from nearby devices and store them together with a timestamp and a receiver signal strength (for later calculation of exposure time and distance approximations). This takes care of the first requirement group.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/867/1*x8580yZ6K9wohXz4LDwemg.png" /></figure><p>The seconds requirement group, the handling of positive diagnostic cases, should be managed/updated centrally. This would avoid inconsistencies in the data and serve as a single source of truth. We could add a central service, which would accept requests to register a new positive diagnostic case. We could call this component the Positive Diagnosis Server or just Diagnosis Server. To simplify, we will assume that the registration of new positive cases is done voluntarily and is based on self-declaration of users after a confirmed test. (In the real implementations of the system, there is a Verification Server component, which can validate test results using associated QR codes given out by the Health Authorities).</p><p>So whenever a user is confirmed positive for the virus, there will be an option in the app to register this with the Diagnosis Server. During registration we would store the UUID that corresponds to the user/device and the registration timestamp. We could also store a time interval, during which we consider that UUID infectious. If we are overly cautious, we could use a large 28 day time-window, considering 14 days before and after the registration.</p><p>The Positive Diagnosis Server could be queried by the mobile application periodically for all newly registered positive cases in a given time period (for example in the last day). These confirmed positive UUIDs than could be downloaded to the app for exposure detection.</p><p>Once we have access to both sets of information (close contacts and positive diagnostic cases in a given time period), exposure detection calculation becomes trivial, we just need to look for matching UUIDs in both sets, during the same interval. Once a match is found, given the timestamps and the received signal strength, the app can calculate a risk score, based on which a warning can be shown to the user with clear medical instructions to follow).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/771/1*XCHPxvS41J2HeUSeTKMjUQ.png" /></figure><p>With this we have the big picture of how to build a contact tracing system. Now all that is left is to sort out the details.</p><h3>Design Trade-Offs</h3><h4>How often should the app broadcast its UUID?</h4><p>Broadcasting, being a 1-way data transmission, is cheap from a resource perspective, so we should do it often. More so, because scanning devices need to detect the broadcasted signal during their scan. If we broadcast once every minute, scanning devices need to keep scanning for a whole minute to guarantee that they will detect a nearby signal. That would be really wasteful on the scanning side. The current recommended broadcasting interval for exposure notifications is around 200 milliseconds ( <a href="https://blog.google/documents/70/Exposure_Notification_-_Bluetooth_Specification_v1.2.2.pdf">Exposure Notification — Bluetooth Specification</a>).</p><h4>How often should the app scan for nearby UUIDs?</h4><p>For scanning we face the trade-off between high frequency/precision and resource usage. Scanning can consume significant resources, since in a public place there could potentially be hundreds of broadcasters to detect and register, so we should do it rarely. Our close contact definition states that we need to detect exposures longer than 15 minutes, so we could get away with scanning only once in 7.5 minutes for example. If we detect a signal in three consecutive scans, we have detected close contact. This approach can have a maximum measurement error of 7.5 minutes, meaning we can only guarantee detection of 22.5 minute exposures. But we could go for a very frequent scanning, every minute, guaranteeing the detection of any 16 minute exposure. It all comes down to the error interval that wwe are willing to accept, that we are comfortable with. The current recommended strategy for exposure notifications is opportunistic scanning (leveraging existing wakes and scan windows) and with minimum periodic sampling every 5 minutes ( <a href="https://blog.google/documents/70/Exposure_Notification_-_Bluetooth_Specification_v1.2.2.pdf">Exposure Notification — Bluetooth Specification</a>). Also, we should scan for an interval of at least 200ms to guarantee broadcast detection.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/899/1*qyD1F6Qvf8RyfFmLsfcORA.png" /></figure><h4>How long should the UUIDs be? How many bits?</h4><p>Longer IDs have a smaller chance of collision, but take up more storage space and would require more network data transfer. In computer science using 128 bits for UUID is considered good enough (without any central coordination system the chance of ID collision/duplication is negligible). And in fact these 128 bit ids are used in real applications ( <a href="https://blog.google/documents/69/Exposure_Notification_-_Cryptography_Specification_v1.2.1.pdf">Exposure Notification — Cryptography Specification</a>).</p><p>However, it is interesting to do a thought experiment and try to argue for decreasing the number of bits used, assuming that some probability of collision is acceptable.</p><p>To help with our calculations, we should estimate also the number of potential users of our system. If we consider the country of Spain and assume that 20% of the population would use the application, then we would expect to have about 10 million users. That means that we need to generate at least 10 million UUIDs.</p><p>To estimate the collision probability, we can use the generalized form of the birthday problem. The original birthday problem is concerned with calculating how many people are needed to have a 50% probability that at least two of them are born on the same day? The surprising answer is only 23. The generalized birthday problem, stated as a collision problem, is the following: how many integers (n) can we select from an uniformly distributed interval [1,d], with a probability (p) of at least one collision. There are two methods to estimate the value mentioned on <a href="https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem">wikipedia</a>.</p><p>The first one is more like a ballpark estimation, that says that the expected number of N-bit hashes that can be generated before getting a collision is 2^(N/2). So to make our calculations easier, let’s say we want to generate 16 million UUIDs (~ 16 <em>1024</em> 1024 = 2²⁴), before getting a collision. For that we would need the double of 24, which is 48 bits. Compared to the original 128 bits, this would result in 62% (1-(48/128)) reduction in ID sizes, but comes with an increased probability of collisions. The other method lists a formula that helps us estimate the probability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/0*nOMwSZzla521dwPa.png" /></figure><p>Let’s use the above derived values of a 48 bit ID, and say that our interval ranges from 1 to 2⁴⁸ (= 2⁸ * 2⁴⁰ ~ 256 * 10¹² = d). Now if we accept a probability of 1% for collision (p=0.01) and put these values into the formula we get the resulting number of 2.2 million. This means that we can select/generate 2 million IDs, using 48 bits, with a 1% chance of collision.</p><p>If we accept a higher probability, 25% chance for collisions (p=0.25), we get a higher number 12 million. Meaning from 12 million IDs generated, using 48 bits, we have a 25% change that any two collide. Similarly, lower probabilities (0.01%, p=0.0001) will result in a lower number of IDs that can be generated without collision (~150.000=0.15 million).</p><p>So given all this, should we decrease the number of bits used for IDs, and settle on a higher acceptable level of collisions, that could lead to false positives for our contact tracing system? Probably not, and we should stick with using 128bit IDs, unless we can really trust our estimations and the ID size turns out to be a bottleneck for the system.</p><h4>How often should the app query the Diagnosis Server? Would this scale?</h4><p>This question has to be answered taking into account two perspectives. From the mobile apps point of view, querying too often would not be an efficient use of networking resources. From the server perspective serving too many clients too often might overload the service.</p><p>We also need some additional data. First we should have an estimate of potential users of the app, to be able to account for the server load when serving data to all the users. Let’s go here with the previously proposed 10 million users here as well. Second we should have an estimate of how often and how many new positive cases are detected. So let’s consider the country of Spain and a roughly one month period, when there was a surge in the number of cases, between October 15th — November 19th, 2020. In this period the confirmed cases of COIVD-19 increased by more than half million, <a href="https://ourworldindata.org/grapher/covid-19-total-confirmed-cases-vs-total-tests-conducted?tab=chart&amp;stackMode=absolute&amp;time=2020-10-15..2020-11-19&amp;country=~ESP&amp;region=World">620.000</a>. In these 35 days, there were on average 17.000 new cases daily — which is equivalent to 1 new case every 5 seconds on average (86.400 seconds in a day vs 17.000 new cases reported daily).</p><p>Given these numbers we can see that there will be an asymmetric traffic pattern, heavily skewed towards reads. If the app only queries the server once a day, then we have 10 million reads versus the daily maximum number of new cases added, which we can approximate as 20.000 writes. Also we might want to query more frequently than once a day, let’s say roughly once every hour with randomized time intervals to spread the load. This would equal on average to 2800 read requests/second versus less than 1 write request/second.</p><p>To be able to serve these types of read-heavy request patterns, the database has to be read scalable. This is usually done by replicating the database, setting up several read replicas. There will be a primary node, which will accept read and write requests, and several secondary nodes which will only accept read requests. Every write request to the primary node will be replicated to all secondary nodes. These secondary nodes or read replicas can also serve as failover nodes, in case the primary node fails. The replication can be done synchronously, if write requests to the primary node only return successfully after at least some secondary nodes are updated as well. This results in an active-active architecture, where failover can happen immediately. Replication can also be asynchronous, if the writes to the primary node are decoupled from the updates happening to secondaries. This is called active-passive or primary-standby architecture, which offer lower latency writes in exchange for slower failovers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/942/1*y95tcSS0Zr_dzxdDvsu1oA.png" /></figure><p>The ability to serve the read request also depends on our exact query and the data model. Fortunately, for our use case we can have a simple data model and a simple query. We store confirmed positive UUIDs with a registration timestamp and an infectious time period. The data can be sorted based on the registration timestamp. Queries for newly registered UUIDs would just return all records with a registration timestamp greater than a given input timestamp.</p><p>We can also estimate the size of the data needed to be transferred. If we assume 1000 new cases registered per hour (~20.000 cases per day), then every hour we need to download 1000 records containing the UUID and the timestamp. The size of one data record would be a 128 bit (UUID) plus a 64 bit (timestamp), equalling to 192/8 = 24 bytes. So a raw, uncompressed data payload of 1000 records would be around 24 KB, which seems small enough to not be a bottleneck.</p><h4>How does the system protect privacy?</h4><p>As previously mentioned Bluetooth Beacon technology is a 1-way transmission, so a beacon cannot track the receivers of its signal. However, in the case of the contact tracing app, each device acts not only as a beacon (data emitter), but also as a data receiver. And whenever we are doing a scan with the app, we receive the BeaconID and this makes it possible to track specific beacons.</p><p>To avoid this, system designers came up with the clever idea not to use fixed BeaconIDs. Every 10 minutes we could generate a new ID (a new Bluetooth Beacon Ephemeral Identifier), making the tracking of any particular ID only possible for 10 minutes. Bluetooth MAC addresses can also rotate every 10 minutes to prevent location tracking by tying together observations of a fixed MAC address. This limits greatly the possibilities to track users.</p><p>One disadvantage that comes with this solution, is the increase in the amount of data that needs to be transferred between the app and the Diagnosis Server. As an example, instead of using the same UUID, we need to create a new one every 10 minutes. This means 144 different IDs per day, 6 different IDs every hour. In case of doing hourly queries to the central server, this means that we increase the payload size with one order of magnitude. Based on the previous calculation this would result in 240 KB payloads, which still seems to be of acceptable size, without causing any issues.</p><p>While trying to protect privacy as best as we can, we should note that no matter the design and algorithms chosen, perfect privacy cannot be guaranteed. As an example let’s imagine a monk, who lives alone in a mountain top, only meeting one delivery person every two weeks, who supplies the monk with the necessary food and other things he might need. Now imagine that both the monk and the delivery guy uses the Virus Radar app, both have their bluetooth activated, and after a few days of meeting the delivery guy, the monk receives the exposure notification on his phone. He will know for sure that he got exposed to the virus through meeting the delivery guy, who has been confirmed to be infected. In this case, because of the circumstances of use, the app cannot protect the delivery guy’s privacy. Some could argue that for users like the monk, who only met one person in the previous 14 days, the app should not reveal the possible exposure and protect the privacy of the delivery guy. However, what if the monk is planning to go next week to the annual monk meetup, and if he had not been notified of the possible exposure, he would spread the disease amongst all the monks in the country. Or what if the monk interacts with other people, who don’t use the contact tracing app, and so should be notified to protect the non app users as well.</p><h3>ENS — the basic building block</h3><p>Of course building all this from scratch would require a lot of effort. Fortunately, we could build upon a basic component called ENS. Google and Apple joined forces and together developed the <a href="https://www.google.com/covid19/exposurenotifications/">Exposure Notification System (ENS)</a>, which is now available as part of the platform for the latest Android and iOS. The Exposure Notification System was created with the specific purpose to enable the creation of privacy respecting contact tracing apps on these platforms. Almost all critical parts are taken care of automatically by ENS:</p><ul><li>it manages the creation and rotation of cryptographically random keys and derived Bluetooth identifiers</li><li>it manages the Bluetooth and data transmission, Bluetooth Beacons, rotating MAC addresses and scanning for nearby devices</li><li>it protects privacy, by not allowing direct access for the apps to scanned identifiers (more on this later)</li><li>it can be integrated with a verification server, to only release IDs in case of a verified positive diagnosis</li><li>it handles the matching of close contact and positively diagnosed IDs and does the exposure calculations</li></ul><p>On Android the Exposure Notification System is accessed through Google Play Service. Based on what we have discussed so far, the following diagram should give you an idea, how do all the pieces fit together.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NWTLscze8IYUe34aACo74g.png" /></figure><p>One interesting thing to examine is how the ID generation works. This is documented in the <a href="https://blog.google/documents/69/Exposure_Notification_-_Cryptography_Specification_v1.2.1.pdf">Cryptographic specification</a>, however it is worth going into the details a bit here and separating the encryption and decryption flows.</p><p>The basic idea is generating a random key every day, then using that key to derive (through several steps) a new BeaconsIDs and bluetooth payload every 10 minutes. These BeaconIDs are used for close contact detection (transmitted and scanned). However when reporting a positive diagnostic case, we don’t send the BeaconIDs, instead we send the original random generated keys to the server. These random keys can then later be used to re-derive the BeaconIDs and detect close contact events.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W9uHXKEVHuuCwm0EtAlICQ.png" /></figure><p>The encryption flow that takes place in ENS is the following. A cryptographic random number generator (CRNG) generates a Temporary Exposure Key (TEK) every 24 hours. This Temporary Exposure Key is then used to derive another key called Rolling Proximity Identified Key (RPIK). The key derivation is done using a hash-based key derivation function (HKDF). Once we have the derived key (RPIK), we use it to generate a new identifier every 10 minutes, which is called Rolling Proximity Identifier (RPI). This Rolling Proximity Identifier will serve as the BeaconID basically. The key generation step is done through encryption, using the AES symmetric key cipher. Symmetrics means that the same key (RPIK) can be used for encryption and decryption as well. The data that we encrypt to generate the final IDs, is the timestamp corresponding to the 10 minute interval, marking the creation of the new IDs.</p><p>The same process is repeated, starting from the Temporary Exposure Key (TEK), we derive another key called Associated Encrypted Metadata Key (AEMK). Using this key we generate the final part of the bluetooth payload called the Associated Encrypted Metadata (AEM). AEM is generated using symmetric encryption, but in <a href="https://cryptobook.nakov.com/symmetric-key-ciphers/cipher-block-modes">counter mode (AES-CTR)</a>. This mode of operation requires an initialization vector (IV), which should be like a random salt (we can use RPI for this purpose). Finally the data that we encrypt contains the protocol version and the transmit power, which can be used for proximity calculation based on receiver signal strength.</p><p>Now I have to be honest, I don’t really understand the reason behind the key derivation step, as the original random key (TEK) could just be used instead of deriving a new key (RPIK). The key derivation step could serve various purposes. It could be needed to improve the random number generators output (which could be potentially biased). It could also serve to protect against analysis and attacks of the system. With every PRIK we generate 144 PRIs every day (one every 10 minutes), so in theory these IDs could be used to try to guess the original encryption key (RPIK). But knowing the derived key (RPIK) is not enough to exploit the system, as we would need access to the original Temporary Exposure Key (TEK) for that.</p><p>The important thing to note here is that the generated BeaconIDs (RPIs) never have to leave the Exposure Notification System. The mobile apps cannot access them, and they are not sent to the Diagnosis Server either. The only keys that are accessed by the app and are sent to the Diagnosis Server are the original Temporary Exposure Keys (TEK) and their creation timestamp (corresponding to a 10 minute interval number). These keys (TEKs) and their timestamp provide enough information to the Exposure Notification System to derive BeaconIDs, decrypt information and do the calculation to detect possible exposure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TRfAG4lrWPAs9enYwxAqJQ.png" /></figure><p>Let’s examine the decryption flow in more details. Once the Diagnosis Server is queried, we receive a set of Temporary Exposure Key (TEK) and corresponding timestamps. Using the key derivation function (HKDF) we can re-derive the Rolling Proximity Identifier Keys (RPIK) and Associated Encrypted Metadata Keys (AEMKs). Then for each of the PRIKs we re-create the 144 Rolling Proximity Identifiers (RPI), knowing that their broadcast time is every 10 minute interval of the day (and the day is known from the Temporary Exposure Keys timestamp). Now these recreated RPIs can be compared to the ones that were scanned and stored in the last 14 days. If there is a match of IDs with an overlap of scan time and broadcast time (using a tolerance window) we have detected a possible exposure. For each match we can calculate the exposure duration based on timestamps. Using the corresponding AEMK we can also decrypt the metadata and access the original transmit power data. This can be compared to the stored receiver signal strength to give estimations for the proximity of the contact. Based on the duration and proximity of the exposure a risk score can be calculated. The Exposure Notification System can provide daily summary of pre-calculated risk score, or surface the exposure data to the app to allow for flexible risk score calculations. Based on the risk score the users can be notified with clear medical instructions.</p><p>And that is how ENS provides all the basic building blocks to be able to create a contact tracing system.</p><p><em>Originally published at </em><a href="https://semmi88.github.io/blog_posts/contact_tracing.html"><em>https://github.com</em></a><em>.</em></p><h4>References</h4><ul><li><a href="https://github.com/RadarCOVID">https://github.com/RadarCOVID</a></li><li><a href="https://ourworldindata.org/coronavirus-data-explorer">https://ourworldindata.org/coronavirus-data-explorer</a></li><li><a href="https://radarcovid.gob.es/politica-de-privacidad">https://radarcovid.gob.es/politica-de-privacidad</a></li><li><a href="https://www.google.com/covid19/exposurenotifications/">https://www.google.com/covid19/exposurenotifications/</a></li><li><a href="https://blog.google/documents/70/Exposure_Notification_-_Bluetooth_Specification_v1.2.2.pdf">https://blog.google/documents/70/Exposure_Notification_-_Bluetooth_Specification_v1.2.2.pdf</a></li><li><a href="https://blog.google/documents/69/Exposure_Notification_-_Cryptography_Specification_v1.2.1.pdf">https://blog.google/documents/69/Exposure_Notification_-_Cryptography_Specification_v1.2.1.pdf</a></li><li><a href="https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem">https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem</a></li><li><a href="https://cryptobook.nakov.com/symmetric-key-ciphers/cipher-block-modes">https://cryptobook.nakov.com/symmetric-key-ciphers/cipher-block-modes</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e8ef44136a63" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>