I was never a big fan of classical interview-tasks. Like, find the minimal size sub-array multiplied elements of which give a number sum of digits of which is a palindrome.
But these tasks for better or for worse are part of interviewing culture. And if I ever want to work in a big company (and currently not only big companies are using "smart" problems for an interview process) I probably will need to learn how to solve them. Or at least don't freak out I see them.
So I decided to participate in the Leetcode marathon. The marathon started on the 1st of April with compatibly easy tasks and during the month they suppose to be more complicated.
I'm a Python developer so all the tasks I'm going to implement in Python.
The first task was to find the first day was the following:
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
A straightforward solution would be to go through the list and create a second structure one where we'll have numbers from the list and number of their appearances. With Python dictionary might be a good structure for it because we can search quite fast.
But authors of the problem definitely wanted something else. I was thinking about some mathematical expression, to multiply every number on something and take a sum or something. But I didn't come up with a nice mathematical formula, but I remembered about the XOR function. This binary function is only 1 when values are different. For integers comparison representations of values bit by bit. It means that for equal numbers we will have always 0 as a result.
It means that full function will look like:
class Solution(object):
def singleNumber(self, nums):
res = nums.pop(0)
for i in nums:
res = res ^ i
return res
Top comments (0)