Daily Interview Problem / Former Pinterest COO accuses the company of Gender Bias!

August 12, 2020

Hey,

Hope you’re having a good day! Here’s your interview problem and industry news for the day!

Daily Interview Problem

Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.

Input - [6, 1, 3, 3, 3, 6, 6]

Output - 1

Input - [13, 19, 13, 13]

Output - 19

Do this in O(N) time and O(1) space.

The solution is at the bottom of this email!

Industry News

  • Former Pinterest COO accuses the company of gender bias - Francoise Brougher, Pinterest’s former COO said she was fired after speaking up about mistreatment. She makes claims of backstabbing, factions and misogyny at Pinterest. You can read her full complaint here.

  • Major Blow to Uber and Lyft in California - Uber and Lyft and have been ordered by a California judge to classify their drivers as employees instead of independent-contractors. This puts major strain on the business model powering the gig economy. Read More.

  • TikTok tracked User Data using MAC addresses, bypassing Android Restrictions - Android locked down MAC addresses in 2015 over concerns of violating user privacy. TikTok bypassed those restrictions on Android by using a widely-known security hole. Read More.

Daily Interview Problem Solution

We can find the unique number in an array of two duplicates by XORing all the numbers in the array. This will cancel all the bits that have an even number of 1s, leaving the unique (odd) bits out. But how do we use this for three duplicates?

Well, instead of cancelling out all the bits with an even number of bits, we want to cancel out those that have a number of bits that are a multiple of three.

Let's assume all integers fit in 32 bits. Then let's create a list that is 32 zeroes long, and when iterating over each number in our array, we can add up all the bits to its proper spot in the array. Finally, we'll go over each bit in the array and make it equal to itself modulo 3. This means that any bit that has been set some multiple of 3 times will effectively be cleared, leaving only the bit from the unique number.

You can check the code out (and run it!) using this REPL.

The time complexity is linear and the space complexity is constant.