# Interview Preparation Questions

## 1. Two Sum
Link: https://leetcode.com/problems/two-sum/

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

<details>
<summary>Solution 1</summary>

const twoSum = (nums, target) => {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return [i, j]
}
}
}
};
</details>

<details>
<summary>Solution 2</summary>

const twoSum = (nums, target) => {
const indices = {};

nums.forEach((item, index) => {
indices[item] = index
});

for (let index = 0; index < nums.length; index++) {
const complement = target - nums[index];

if (indices[complement] !== undefined && indices[complement] !== index) {
return [index, indices[complement]]
}
}

</details>

What is the different between the two solutions? Which one is better?

## 2. Palindrome

Link: https://leetcode.com/problems/palindrome-number/

Given an integer x, return `true` if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

<details>
<summary>Solution 1 </summary>

const isPalindrome = (x) => {
const start = '' + x;
let left = 0;
let right = start.length - 1;
while (left < right) {
if (start[left] !== start[right]) return false;
left++;
right--;
}
return true;
};

</details>

**Follow up**: Could you solve it without converting the integer to a string?

<details>
<summary>Solution 2 </summary>

const isPalindrome =(x) => {
if (x < 0) return false;
let num = x;
let res = 0;
while (num !== 0) {
res = (res * 10) + (num % 10);
num = Math.floor(num / 10);
}
return res === x;
};

</details>

## 3. Remove Duplicates from Sorted Array
Link: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

<details>
<summary>Solution</summary>

const removeDuplicates = (nums) => {
if(nums.length == 0) return 0;

let i = 0;
for (let j = 1; j < nums.length; j ++){
if(nums[j] !== nums[i]){
i++;
nums[i] = nums[j];
}
}

return i + 1
};

</details>

## 4. Fizz Buzz
Link: https://leetcode.com/problems/fizz-buzz/

Given an integer n, return a string array answer (1-indexed) where:

- `answer[i] == "FizzBuzz"` if `i` is divisible by `3` and `5`.
- `answer[i] == "Fizz"` if `i` is divisible by `3`.
- `answer[i] == "Buzz"` if `i` is divisible by `5`.
- `answer[i] == i` (as a string) if none of the above conditions are true.

Example 1:

Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

<details>
<summary>Solution 1</summary>

const fizzBuzz = (n) => {
let output = [];
for (let i = 1; i <= n; i++) {
if (i % 3 === 0 && i % 5 === 0) {
output.push('FizzBuzz');
} else if (i % 3 === 0) {
output.push('Fizz');
} else if (i % 5 === 0) {
output.push('Buzz');
} else {
output.push(i.toString());
}
}
return output;
};

</details>

<details>
<summary>Solution 2: concatenation</summary>

const fizzBuzz = (n) => {
let output = [];
for (let i = 1; i <= n; i++) {
let newString = '';
if (i % 3 === 0) {
newString += 'Fizz';
}
if (i % 5 === 0) {
newString += 'Buzz';
}
output.push(newString.length ? newString : i.toString());
}
return output;
};

</details>

## 5. Single Number
Link: https://leetcode.com/problems/single-number/

Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

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

<details>
<summary>Solution 1</summary>

const singleNum = (nums) => {
for(let i=0;i<nums.length;i++){
let flag = true;
for(let j=i+1;i<nums.length;j++){
if(nums[i] == nums[j]){
flag = false;
}
}
if(flag == true) return nums[i];
}
return -1;
}

</details>

<details>
<summary>Solution 2</summary>

const singleNum = (nums) => {
let map = {}
for(let i=0;i<nums.length-1;i++){
if(map[nums[i]]) map[nums[i]] = false;
else map[nums[i]] = true;
}
for(let [key, value] of Object.entries(map)){
if(value) return key;
}
return -1;
}

</details>

## 6. Anagram
Link: https://leetcode.com/problems/valid-anagram/

Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

<details>
<summary>Solution 1</summary>

const isAnagram = (s, t) => {
if (s.length !== t.length) {
return false;
}
const stringS = s.split('').sort().join('');
const stringT = t.split('').sort().join('');
return stringS === stringT
}

</details>

<details>
<summary>Solution 2</summary>

const isAnagram = (s, t) => {
const lengthS = s.length;
const lengthT = t.length;
const characters = {};

if (lengthS !== lengthT) return false;

for (let i = 0; i < lengthS; i++) {
if (!characters[s[i]]) {
characters[s[i]] = 0;
}
characters[s[i]]++;
}

for (let j = 0; j < lengthT; j++) {
if (!characters[t[j]]) {
return false;
}
characters[t[j]]--;
}

return true;
};

</details>

## 7. Maximum Subarray
Link: https://leetcode.com/problems/maximum-subarray/

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

<details>
<summary>Solution</summary>

const maxSubArray = (nums) => {
const len = nums.length;
let max = Number.MIN_SAFE_INTEGER;
let before = 0;
let now = 0;

if (!len) return 0;

for (let i = 0; i < len; i++) {
now = Math.max(before + nums[i], nums[i]);
max = Math.max(now, max);
before = now;
}

return max;
};

</details>

## 8. Majority Element

Link: https://leetcode.com/problems/majority-element/

Given an array nums of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

<details>
<summary>Solution 1</summary>

const majorityElement = function(nums) {
let map = {};
let max = 0;
let majorNum = 0;
let len = nums.length;
for (let i = 0; i < len; i++) {
if (!map[nums[i]]) map[nums[i]] = 0;
map[nums[i]]++;
if (map[nums[i]] > max) {
majorNum = nums[i];
max = map[nums[i]];
}
}
return majorNum;
};

</details>

<details>
<summary>Solution 2</summary>

const majorityElement = (nums) => {
let count = 0;
let majorNum = 0;
const len = nums.length;
for (let i = 0; i < len; i++) {
if (!count) {
majorNum = nums[i];
count = 1;
} else {
count += (nums[i] === majorNum ? 1 : -1);
}
}
return majorNum;
};

</details>

## 9. Plus One

Link: https://leetcode.com/problems/plus-one/

You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

<details>
<summary>Solution</summary>

const plusOne = function(digits) { //[1,2,3,4] [9]
let i = digits.length - 1;
let val = 0;
let carry = 1;

while (i >= 0 && carry) {
val = digits[i] + carry;
carry = Math.floor(val / 10);
digits[i] = val % 10;
i--;
}

if (carry) digits.unshift(carry);
return digits;
};

</details>

## 10. Contains Duplicate
Link: https://leetcode.com/problems/contains-duplicate/

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

<details>
<summary>Solution</summary>

const containsDuplicate = (nums) => {
const map = {}
for(const num of nums) {
if(map[num]) {
return true
}
map[num] = true
}
return false
};

</details>