#
Algorithms

### Two Sum and Its Variants

2022-01-25

Problem Statement Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

### Random Linked List Node

2022-01-25

Problem Statement Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Implement the Solution class:
Solution(ListNode head): Initializes the object with the integer array nums. int getRandom(): Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen. Constraints:
The number of nodes in the linked list will be in the range [1, 10^4].

### Single Number

2022-01-25

Single Number Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums = [1] Output: 1 Using a HashSet (linear space complexity) We can iterate nums and for each number n do the following:
If this is the first time we’ve seen n, then we add n to a hashset If the hashset contains n, then n gets removed from the hashset: 1 2 3 4 5 6 7 8 def get_single_number(nums: List[int]) -> int: uniques = set() for n in nums: if n not in uniques: uniques.

### Prime Factorization of a Number

2022-01-25

Problem Statement How do we find all the prime factors of a given number?
For example, when n = 12, the output should be [2, 3]. Notice that 1, 4, 6, 12 are also factors of 12 but they aren’t prime and therefore should be excluded from the output.
Solution The following solution is straightforward:
1 2 3 4 5 6 7 8 9 10 def get_prime_factors(n: int) -> List[int]: prime_factors = [] prime = 2 while n > 1: while n % prime == 0: if not prime_factors or prime !

### Find all prime numbers up to a given number

2022-01-25

Problem Statement How do we find all the prime numbers up to a given number?
For example, when n = 10, the output should be 4 since there are 4 prime numbers less than 10, namely 2, 3, 5, 7.
Naive Approach A naive approach would be to iterate from 2 to n and count the number of primes along the way:
1 2 3 4 5 def count_primes_less_than(n: int) -> int: return sum(is_prime(i) for i in range(2, n)) def is_prime(num: int) -> bool: return all(num % i !

### How to prepare for Google coding challenge

2022-01-25

Coding challenges are technological developments designed to test your knowledge of algorithms and data structures.
The company invites developers to participate in these events, solves coding problems, and wins top competition awards. Google runs three coding challenges each year.
Preparing for a coding challenge can prepare you for interviews at large technology firms, as FAANG and tier-1 Technical interviews also revolve around troubleshooting algorithms and data structures.
See also:
FAANG Software Engineering Interview How to pass the googlyness interview So, how to prepare for a coding challenge (at Google interview)?