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/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/find-the-difference/ Given two strings  s  and  t  which consist of only lowercase letters. String  t  is generated by random shuffling string  s  and then add one more letter at a random position. Find the letter that was added in  t . Example: Input: s = "abcd" t = "abcde" Output: e Explanation: 'e' is the letter that was added. ---

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] ...