SWE Interview preparation

https://leetcode.com/problems/counting-bits/ Given a non negative integer number  num . For every numbers  i  in the range  0 ≤ i ≤ num  calculate the number of 1's in their binary representation and return them as an array. Example 1: Input: 2 Output: [0,1,1] Example 2: Input: 5 Output: [0,1,1,2,1,2] Follow up: It is very easy to come up with a solution with run time  O(n*sizeof(integer)) . But can you do it in linear time  O(n)  /possibly in a single pass? Space complexity should be  O(n) . Can you do it like a boss? Do it without using any builtin function like  __builtin_popcount  in c++ or in any other language. --- --

https://leetcode.com/problems/complement-of-base-10-integer/ Every non-negative integer  N  has a binary representation.  For example,  5  can be represented as  "101"  in binary,  11  as  "1011"  in binary, and so on.  Note that except for  N = 0 , there are no leading zeroes in any binary representation. The  complement  of a binary representation is the number in binary you get when changing every  1  to a  0  and  0  to a  1 .  For example, the complement of  "101"  in binary is  "010"  in binary. For a given number  N  in base-10, return the complement of it's binary representation as a base-10 integer. Example 1: Input: 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10. Example 2: Input: 7 Output: 0 Explanation: 7 is "111" in binary, with complement ...

https://leetcode.com/problems/divide-two-integers/ Given two integers  dividend  and  divisor , divide two integers without using multiplication, division and mod operator. Return the quotient after dividing  dividend  by  divisor . The integer division should truncate toward zero, which means losing its fractional part. For example,  truncate(8.345) = 8  and  truncate(-2.7335) = -2 . Example 1: Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = truncate(3.33333..) = 3. Example 2: Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = truncate(-2.33333..) = -2. Note: Both dividend and divisor will be 32-bit signed integers. The divisor will never be 0. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2 31 ,  2 31  − 1]. For the purpose of this problem, assume that your function  returns 2 31  − 1 when the divi...

https://leetcode.com/problems/number-of-1-bits/ Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the  Hamming weight ). Example 1: Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011  has a total of three '1' bits. Example 2: Input: 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000  has a total of one '1' bit. Example 3: Input: 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits. Note: Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed ...

https://leetcode.com/problems/single-number-ii/ Given a  non-empty  array of integers, every element appears  three  times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,3,2] Output: 3 Example 2: Input: [0,1,0,1,0,1,99] Output: 99 --- Related problems 136-single-number ---

https://leetcode.com/problems/1-bit-and-2-bit-characters/ We have two special characters. The first character can be represented by one bit  0 . The second character can be represented by two bits ( 10  or  11 ). Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero. Example 1: Input: bits = [1, 0, 0] Output: True Explanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character. Example 2: Input: bits = [1, 1, 1, 0] Output: False Explanation: The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character. Note: 1 <= len(bits) <= 1000 . bits[i]  is always  0  or  1 . ---

https://leetcode.com/problems/hamming-distance/ The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Given two integers  x  and  y , calculate the Hamming distance. Note: 0 ≤  x ,  y  < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. ---

https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/ Given  head  which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number. Return the  decimal value  of the number in the linked list. Example 1: Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10 Example 2: Input: head = [0] Output: 0 Example 3: Input: head = [1] Output: 1 Example 4: Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880 Example 5: Input: head = [0,0] Output: 0 Constraints: The Linked List is not empty. Number of nodes will not exceed  30 . Each node's value is either  0  or  1 . ---

https://leetcode.com/problems/single-number/ 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? Example 1: Input: [2,2,1] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4 --- Intuition XOR of number with itself is zero XOR of number with 0 is itself XOR all array elements, all duplicates with result in 0, and XOR with unique number will be unique answer --- Related problems 137-single-number-ii ---

https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/ Given an integer array  arr . You have to sort the integers in the array in ascending order by the number of  1's  in their binary representation and in case of two or more integers have the same number of  1's  you have to sort them in ascending order. Return  the sorted array . Example 1: Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits is [0,1,2,4,8,3,5,6,7] Example 2: Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order. Example 3: Input: arr = [10000,10000] Output: [10000,10000] Example 4: Input: arr = [2,3,5,7,11,13,17,19] Output: [2,3,5,17,7,11,13,19] ...