Puzzle #13 – A Google Interview Question

The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment – until then I am sure the headline will generate some traffic .

The original question as it was given to me was:
Given an array with 2n+1 integer elements, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.

Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness – the rest of the 2^N – (2n+1) are all zeroes). n elements appear twice – in different places in the SRAM, while a single value appears only once.

Design a circuit with the minimum amount of hardware to find the value which appears only once.

Polymorphic Circuits

Here is a neat and not so new idea that I came across last year – “Polymorphic Circuits”. The basic concept is logic gates which under specific operating conditions behave in a certain way while under different operating conditions behave in another way. For example a circuit when operated with a 2 volt supply might act as an OR gate but when supplied with 1 volt will become an AND gate, or another example might be a circuit which in room temperature behaves as an XOR gate while at 120 degrees, the very same circuit operates as a NAND gate.

This concept just screams for new application (I guess mainly in security) but I was not able to think of something specific so far. Feel free to shoot ideas around in the comments section of this post.

In the meantime more details can be found on this paper (just skip to the images at the end of the paper to get the idea), or this paper.

Predictive Synchronizers

As we discussed many times before, synchronization of signals involves also latency issues. Sometimes these latency issues are quite a mess. This post will go over the principle of operation of predictive synchronizers, which offer a specific solution for a very specific case.

Let’s start by describing the conditions for this specific case. For the sake of explanation let us assume we have two clock domains with different clock periods. On top we have a certain limited or capped jitter component defined by our spec.
Taking the conservative approach, we would always use a full two flip flop synchronizer. However, a closer look at a typical waveform reveals something interesting.

The figure above shows both clocks. The limited jitter as defined by our spec, is shown in gray. Notice how only during specific periods a full synchronizer needs to be used. For the upper clock each 5th cycle is a “dangerous” one, while for the lower clock each 4th is problematic. The time window in which these danger zones occur is predictable.

In general we could count the clock cycles, and then, when the next clock edge occurs in the “danger zone” we could switch and use a full synchronizer circuit, otherwise a single flop is enough.

A circuit which implements this idea can be seen below. The potentially metastable node is blocked by the FSM during the “danger time” and the synchronizer output is taken, otherwise the normal, first flop’s output, is taken. The logic at the output is basically that of a MUX.