Yajana Rao

BlogsNotesAbout

Interview Preparation

This is a collection of notes on Interview Preparation. This is a work in progress and will be updated regularly.

Two Pointer Pattern

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

Constraints:

  • 2 <= nums.length <= 104

  • -109 <= nums[i] <= 109

  • -109 <= target <= 109

  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Intuition

The problem is to find two numbers in the array that add up to a given target. A straightforward way would be to use two loops and check every combination of two numbers. However, this would be inefficient.

Sorting the array increases time complexity.

A more efficient way would be to use a hashmap (or in JavaScript, a Map) to store the numbers we've seen so far and their indices. As we iterate through the array, for each number, we can check if the difference between the target and that number exists in the map. If it does, we've found our two numbers.

Approach

Using HashMap and Javascript Object

  1. Initialize an empty Map.
  2. Iterate through the array.
  3. For each number, calculate the difference between the target and that number.
  4. Check if this difference exists in the Map.
  5. If it does, return the index of the difference from the Map and the current index.
  6. If not, add the current number and its index to the Map.

Complexity

  • Time complexity:

The time complexity is (O(n)) because we iterate through the array once, and operations with the Map (both get and set) are on average (O(1)).

  • Space complexity:

The space complexity is (O(n)) because in the worst case, we might store all numbers in the Map.

Code

HashMap

function twoSum(nums: number[], target: number): number[] {
    const numToIndex = new Map()
    for(let i:number =0; i<nums.length; i++) {
        const complement = target - nums[i]
        if(numToIndex.has(complement)) return [numToIndex.get(complement), i];
        numToIndex.set(nums[i], i);
    }
};
  • Map is more memory-intensive because of its advanced functionality and robust key handling.
  • The implementation uses a single pass through the array, storing each number's index in a Map.
  • Time complexity: O(n) - We traverse the list containing n elements only once.
  • Space complexity: O(n) - The extra space required depends on the number of items stored in the hash map, which stores at most n elements.

Object

function twoSum(nums: number[], target: number): number[] {
	const numToIndex = {};
	for (let i:number = 0; i < nums.length; i++) {
		const complement =  target - nums[i];
		if(numToIndex[complement] !== undefined) return [numToIndex[complement], i];
		numToIndex[nums[i]] = i;
	}
}
  • Plain objects use slightly less space due to lower overhead.
  • The implementation uses a single pass through the array, storing each number's index in an object.
  • Time complexity: O(n) - We traverse the list containing n elements only once.
  • Space complexity: O(n) - The extra space required depends on the number of items stored in the object, which stores at most n elements.

Javascript Questions

Question 1

Given an integer array nums, return the length of the longest increasing subsequence.

Example:

> increasingSubsequence([10, 9, 2, 3, 7, 101, 18])
> 4
> increasingSubsequence([4, 4, 4, 4, 3])
> 1
> increasingSubsequence([0, 1, 0, 3, 2, 3])
> 4
> increasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18])
> 4

Subsequence: A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Increasing Subsequence: A subsequence where each element is greater than the previous one.

Non-Contiguous: The elements of the subsequence do not have to be contiguous in the original array.

Solution

Attempt 1

This was done without understanding the problem statement properly.

 
function increasingSubsequence(nums) {
  let maxSeries = [];
  let max = 1;
  for (let i = 1; i < nums.length; i++) {
    if(nums[i] > nums[i - 1]) {
      max++;
    } else if(i == nums.length -1) {
      maxSeries.push(max);
    } else {
      maxSeries.push(max);
      max = 1;
    }
  }
  return Math.max(...maxSeries);
}

  • function finds the longest consecutive increasing subsequence, not the longest increasing subsequence in general. It only compares adjacent elements.

  • solution has a time complexity of O(n) and space complexity of O(n)

  • It will miss non-consecutive increasing subsequences.

Attempt 2

With the help of chatgpt

function increasingSubsequence(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    const n = nums.length;
    const dp = new Array(n).fill(1);
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp);
}

This JavaScript implementation follows the same logic as the Python version:

  1. We first check if the input array is empty. If so, we return 0.

  2. We create a dp array of the same length as the input array, initialized with all 1s.

  3. We use nested loops to compare each element with all previous elements.

  4. If we find a smaller previous element, we update the current dp value if necessary.

  5. Finally, we return the maximum value in the dp array, which represents the length of the longest increasing subsequence.

The time and space complexities remain the same: O(n^2) time and O(n) space, where n is the length of the input array.

Question 2

Define a FruitStand class that allows you to add different types of fruits with their quantities and prices, update them, and calculate the total value of all the fruits in the stand.

Implement the following methods:

  • addFruit(name, quantity, price)
  • updateQuantity(name, quantity)
  • totalValue()

Example usage:

// Create a new fruit stand
let stand = FruitStand()
 
// Add fruits to the stand
stand.addFruit("apple", 10, 0.5)
stand.addFruit("banana", 5, 0.2)
stand.addFruit("cherry", 20, 0.1)
 
// Update the quantity of an existing fruit
stand.updateQuantity("banana", 10)
 
// Calculate the total value of all fruits in the stand
console.log(stand.totalValue())
Solution
 
class FruitStand {
  fruits = {};
  addFruit(name, quantity, price){
    this.fruits[name] = {quantity, price};
  }
  updateQuantity(name, quantity){
    this.fruits[name].quantity = quantity;
  }
  totalValue(){
    return Object.values(this.fruits).reduce((total, fruit) => total + fruit.quantity * fruit.price, 0);
  }
}

Question 3

Write a function that takes an array of integers representing the number of flowers planted in a line, and an integer k representing the number of additional flowers you want to plant. Return whether it's possible to plant all k flowers without planting any two flowers adjacent to each other.

Example:

> canPlantFlowers([1, 0, 0, 0, 1], 1)
> true // you can plant 1 flower between the others
 
> canPlantFlowers([1, 0, 0, 0, 1], 2)
> false
 
> canPlantFlowers([0, 0, 0, 0, 0], 3)
> true
 
> canPlantFlowers([1, 0, 1, 0, 1], 1)
> false
Solution
function canPlantFlowers(flowers, k) {
    let count = 0;
 
    for(i = 0; i < flowers.length; i++) {
        if(flowers[i] == 0) {
            prevEmpty = (i === 0) || (flowers[i-1] === 0)
            nextEmpty = (i === flowers.length-1) || (flowers[i+1] === 0)
            if(prevEmpty && nextEmpty) {
                flowers[i] = 1;
                count++;
            }
            if(count >= k) return true
        } 
    }
    return count >= k;
}

Question 4

Write a function that takes a list of names and returns the names sorted by the number of vowels in each name in descending order. If two names have the same number of vowels, sort them alphabetically.

Example:

> sortNames(["Goku", "Vegeta", "Piccolo", "Gohan"])
> ["Piccolo", "Vegeta", "Gohan", "Goku"]
 
> sortNames(["Edward", "Alphonse", "Roy", "Winry"])
> ["Alphonse", "Edward", "Winry", "Roy"]
Solution
function sortNames(names) {
  const vowels = ['a', 'e', 'i', 'o', 'u'];
  const countGroup = {}
  for (let i = 0; i < names.length; i++) {
    const vowelsCount = names[i].split('').filter(a => vowels.includes(a)).length
   
    const peers =  countGroup[vowelsCount] || []
    countGroup[vowelsCount] = [...peers, names[i]]
  }
  
  
  const result = []
  Object.keys(countGroup).sort((a, b) => b - a).map(i => {
      const sort = countGroup[i].sort().forEach(word => result.push(word))
  })
  return result
}

Question 5

Write a function that takes an array of integers and a target sum, and returns all unique quadruplets [a, b, c, d] in the array such that a + b + c + d = target. If it's impossible, return an empty array.

Example:

> fourSum([1, 0, -1, 0, -2, 2], 0)
> [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
 
> fourSum([], 0)
> []
 
> fourSum([1, -2, -5, -4, -3, 3, 3, 5], -11)
> [[-5, -4, -3, 1]]
Solution

Attempt 1

function fourSum(data, targetSum) {
    const result = []
    for(let i=0; i < data.length; i++) {
        for (let j=0; j< i;j++) {
            for(let k =0; k < j; k++) {
                for(let l=0; l< k; l++) {
                    let sum = data[i]+ data[j] + data[k] + data[l]
                    if(targetSum == sum) {
                        result.push([data[i], data[j], data[k], data[l]])
                    }
                }
            }
        }
    }
    return result
}

Pros:

  • Straightforward: The logic is simple and easy to understand.

Cons:

  • Time Complexity: The time complexity of this solution is 𝑂(𝑛^4), where 𝑛 is the length of the input array. This is inefficient for larger arrays.

  • Handling Duplicates: This solution does not handle duplicates, so it may return the same quadruplet multiple times if the input array contains duplicate elements.

  • Space Complexity: The space complexity is 𝑂(1) for the algorithm itself, but the result array can grow significantly if there are many matching quadruplets.

Attemp 2

function fourSum(nums, target) {
    nums.sort((a, b) => a - b); // Sort the array
    const result = [];
    const n = nums.length;
 
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // Skip duplicates for the first element
 
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue; // Skip duplicates for the second element
 
            let left = j + 1;
            let right = n - 1;
 
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
 
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
 
                    // Skip duplicates for the third and fourth elements
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    while (left < right && nums[right] === nums[right - 1]) right--;
 
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
 
    return result;
}

Question 6

Write a function that takes an array of integers and returns a new array containing only the even numbers, and sorted.

Example:

> onlyEvens([1, 2, 3, 4, 5, 2])
> [2, 2, 4]
 
> onlyEvens([7, 8, 1, 0, 2, 5])
> [0, 2, 8]
 
> onlyEvens([11, 13, 15])
> []
Solution

Attempt 1

const onlyEvens = (nums) =>  nums.filter(n => !(n % 2)).sort()

The solution is concise and leverages JavaScript's higher-order functions filter and sort. However, there is a minor issue with the sort method. By default, the sort method sorts elements as strings, which can lead to incorrect orderings for numerical arrays.

Attempt 2

const onlyEvens = (nums) => nums.filter(n => !(n % 2)).sort((a, b) => a - b);

Complexity:

  • Time Complexity:

    Filtering: 𝑂(𝑛), where 𝑛 is the length of the input array. Sorting: 𝑂(π‘šlogπ‘š), where π‘š is the number of even numbers. Overall: 𝑂(𝑛+π‘šlogβ‘π‘š).

  • Space Complexity: 𝑂(π‘š), where π‘š is the number of even numbers, as a new array is created to store the even numbers

Question 7

Write a program that implements the DelayedTaskExecutor interface defined below. Think about how it would work if you ran the exec function multiple times in a row, before the task is run!

Interfaces:

interface Task {
    // a blocking run
    void run();
 
    // when the task should be executed
    long timeStamp(); 
}
 
interface DelayedTaskExecutor {
   // executes task.run() at the given timestamp
   void exec(Task task);
}
 
// usage
executor.exec(new Task(10:00am));
executor.exec(new Task(10:10am));
executor.exec(new Task(10:05am));

Question 8

Write a function that converts between metric and imperial units. Break up the units into millimeters, centimeters, and meters for metric, and into inches and feet for imperial, up to 2 decimal places.

Example:

> convertUnits(7, "ft")
> "2m 13cm 3.6mm"
 
> convertUnits(44, "cm")
> "1ft 5.32in"
Solution
 
const cmPerInch = 2.54;
 
function convertUnits(value, unit) {
	const metricUnits = ["km", "m", "cm"]
	const imperialUnits = ["in", "ft"]
	if(metricUnits.includes(unit)) {
		let centimeters = value
		if(unit === "km") {
		  centimeters = value * 100000
		}
		if(unit === "m") {
		  centimeters = value * 100  
		}
		let totalInches = centimeters / cmPerInch;
		let feet = Math.floor(totalInches / 12)
		let inches = totalInches % 12
		return (feet && `${feet}ft `) + `${inches.toFixed(2)}in`
	} else if(imperialUnits.includes(unit)) {
	  let totalInches = value
	  if(unit === "ft") {
	    totalInches = value * 12
	  }
	  let totalCm = totalInches * cmPerInch;
	  let meters = Math.floor(totalCm / 100)
    totalCm -= meters * 100
	  let cm = Math.floor(totalCm)
	  let mm = Math.floor(totalCm - cm) * 10
	  return `${meters}m ${cm}cm ${mm.toFixed(1)}mm`
	}
}

Question 9

The Spanish language uses inverted punctuation marks (ΒΏ and Β‘) in interrogative and exclamatory sentences. Write a function that takes in a string str, and adds ΒΏ and Β‘ if they're needed. You can ignore exclamations in the middle of a sentence for this problem.

Example:

> fixInvertedPunc("Feliz cumpleaΓ±os!")
> "Β‘Feliz cumpleaΓ±os!"
 
> fixInvertedPunc("Ella ya se graduΓ³ de la universidad? Β‘No!")
> "ΒΏElla ya se graduΓ³ de la universidad? Β‘No!"
Solution

My version

function fixInvertedPunc(str) {
  const puncs = ["?", "!"]
  const invertedPuncMap = {
    '?': 'ΒΏ',
    '!': 'Β‘'
  }
  for (let punc of puncs) {
    if(str.includes(punc)) {
      const subStrings = str.split(punc)
      str = subStrings.map((subStr, index) => index < subStrings.length -1 ? (subStr.includes(invertedPuncMap[punc]) ? `${subStr}${punc}` : `${invertedPuncMap[punc]}${subStr}${punc}`) : subStr).join('')
    }
  }
  return str
}

ChatGPT version

function fixInvertedPunc(str) {
  const invertedPuncMap = {
    '?': 'ΒΏ',
    '!': 'Β‘'
  };
 
  // Helper function to add inverted punctuation if needed
  function addInvertedPunc(subStr, punc) {
    if (!subStr.startsWith(invertedPuncMap[punc])) {
      return `${invertedPuncMap[punc]}${subStr}`;
    }
    return subStr;
  }
 
  // Split the string into an array of words and punctuations
  const tokens = str.split(/([?!])/); // This regex captures the punctuation marks
 
  let result = '';
 
  // Iterate over the tokens and add inverted punctuation where necessary
  for (let i = 0; i < tokens.length; i++) {
    if (tokens[i] === '?' || tokens[i] === '!') {
      // Add inverted punctuation to the preceding substring
      tokens[i - 1] = addInvertedPunc(tokens[i - 1], tokens[i]);
    }
    result += tokens[i]; // Build the result string
  }
 
  return result;
}

Regular Expression: /([?!])/

Breakdown:

  • / and /: These are the delimiters for the regular expression in JavaScript.

  • [ and ]: This denotes a character class. A character class matches any one of the characters inside the square brackets.

  • ?!: Inside the character class, this matches either a ? or a !. This means any occurrence of ? or ! will be a match.

  • (): Parentheses denote a capturing group. This means whatever matches inside the parentheses will be captured and included in the result of the split.

Question 10

Write a function that takes in a list (of length >= 3) of numbers, and returns the maximum product that can be obtained by multiplying any three integers from the list.

Example:

> maxProduct([2, 4, 1, 3, -5, 6])
> 72 // 4*3*6
Solution

Attempt 1

function maxProduct(data) {
  let sorted = data.sort((a, b) => b-a)
  return sorted[0] *  sorted[1] * sorted[2]
}

Attempt 2

 
function maxProduct(data) {
  const sorted = data.sort((a, b) => b-a)
  const product1 = sorted[0] *  sorted[1] * sorted[2]
  const product2 = sorted[0] * sorted[data.length - 1] * sorted[data.length - 2]
  return Math.max(product2, product1)
}

Question 11

Create a function that should take one argument n, which is a positive integer. The function should return the sum of all squared positive integers between 1 and n, inclusive.

Example:

> squares(5)
> 55
> squares(10)
> 385
> squares(25)
> 5525
> squares(100)
> 338350
Solution

Attempt 1

function squares(num) {
  let sum = 0
  for(let i=1;i <= num; i++) {
    sum = sum + i * i
  }
  return sum
}

Attempt 2

function squares(n) {
  return Array.from({length: n}, (_, i) => i + 1).reduce((acc, num) => acc + num * num, 0)
}

Question 12

Write a "word wrapping" function that takes in a string and the maximum width of a line of text, and return the text "wrapped" to that line length. Include dashes for broken words (which is included in the length of that line), and don't let a line start with a non-alphanumeric character.

Example:

let string = "Hello, world! I am hungry."
let length = 10
 
> wrap(string, length)
`Hello, wo-
 rld! I am
 hungry.`
Solution

Attempt 1

function wrap(string, length) {
  let text = ""
  let cursor = 0
  while(cursor < string.length) {
    if(cursor + 10 < string.length) text = text + ${string.slice(cursor, cursor+ 9)}-\n
    else text = text + string.slice(cursor, cursor+ 9)
    cursor = cursor + 10
  }
  return text
}

Problems:

  • It always adds a hyphen before the newline character, even if the break happens at a space or a punctuation mark, which is not ideal.
  • It doesn't handle breaking words correctly to avoid lines starting with non-alphanumeric characters.
  • It hardcodes the line length to 10 instead of using the length parameter.

Question 13

Imagine the users on your app are all typing slightly incorrectly, in that they shifted their hands one key to the right. Write a function that translates what they mean to say. The examples below assume an ANSI keyboard layout, you can choose how you want to do that!

Example:

> translateRightShift(';p; epeor')
"lol wowie"
 
> translateRightShift('ejp s, o')
"who am i"
Solution
function translateRightShift(str) {
  const keyboard = "1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./".split('')
  return str.toLowercase().split('').map(char => char === ' ' ? char : keyboard[keyboard.indexOf(char) - 1]).join('')
}

Handling Edge Cases:

  • The current implementation works well for most cases but might fail for characters at the very start of the keyboard string (e.g., 1 or q), as keyboard.indexOf(char) - 1 would access an out-of-bounds index.
  • To avoid this, you could add a condition to check if keyboard.indexOf(char) - 1 is less than 0 and handle it appropriately.

Uppercase Letters:

  • The function currently doesn’t handle uppercase letters. To support them, you could either extend the keyboard string with uppercase characters or convert the input string to lowercase before processing.

Question 14

Given a direction and a number, write a function that outputs an arrow of asterisks with the height of that number! See the pattern below.

Example:

$ printArrow('right', 3)
*
 *
  *
 *
*
 
$ printArrow('left', 5)
    *
   *
  *
 *
*
 *
  *
   *
    *
 
$ printArrow('up', 2)
  *
 * *
Solution
 
function printArrow(direction, len) {
  let arrow = ''
  let num = len - 1
  if(direction === "right") {
      for(let i=0; i<num; i++) {
          for(let j=0; j<i;j++) {
            arrow = arrow + ' '
          }
         arrow = arrow + '*\n'
      }
      for(let i=num; i>=0; i--) {
          for(let j=0; j<i;j++) {
            arrow = arrow + ' '
          }
         arrow = arrow + '*\n'
      }
  }
  if(direction === "left") {
      for(let i=num; i>0; i--) {
          for(let j=0; j<i;j++) {
            arrow = arrow + ' '
          }
         arrow = arrow + '*\n'
      }
      for(let i=0; i<=num; i++) {
          for(let j=0; j<i;j++) {
            arrow = arrow + ' '
          }
         arrow = arrow + '*\n'
      }
  }
  if(direction === "top") {
      for(let i=num; i>0; i--) {
         arrow = arrow + ' '.repeat(i)
         arrow = arrow + '*'
         
      }
    arrow = arrow + '\n'
  }
  return arrow
}

Question 15

Given an array of logs and variable assignments, return a list of all unused variables.

Examples:

> findUnused(["a = 1", "b = a", "c = 2", "log(b)"]);
> ["c"]
 
> findUnused(["a = 1", "b = a", "c = 2", "log(c)"]);
> ["a", "b"]
Solution

Attempt 1

 function findUnused(data) {
   let stack = {}
   for (const item of data) {
     if(item.includes('=')) {
       const values = item.split('=')
       const variable = values[0].trim()
       const value = values[1].trim()
       if(!parseInt(value)) {
         if(Object.keys(stack).includes(variable)) {
           stack[variable]['ref'] = value
         } else {
           stack = {
             ...stack,
             [variable]: {
               'ref': value
             }
           }
         }
       } else {
         stack[variable] = value
       }
       
     } else  if(item.includes('log')) {
        let refKey = item.slice(4, -1)
        while(refKey) {
          newRefKey = stack[refKey]?.ref
          delete stack[refKey]
          refKey = newRefKey
        }
      }
   } 
   return Object.keys(stack)
 }

Improvements

  • Use of Destructuring: Utilize destructuring to make the code cleaner when splitting the string by =.
  • Simplified Conditionals: Simplify the logic for updating the stack by directly assigning values and avoiding unnecessary checks.
  • Avoid Repeated Lookups: Remove the need for repeatedly checking the existence of a variable in the stack.
  • Consistent Variable Naming: Use meaningful and consistent variable names to make the code easier to follow.
  • Remove Redundant Code: Simplify the logic to remove unnecessary checks or operations.
function findUnused(data) {
  const stack = {};
 
  for (const item of data) {
    if (item.includes('=')) {
      const [variable, value] = item.split('=').map(s => s.trim());
 
      if (isNaN(value)) {
        // Value is a reference, not a number
        stack[variable] = { ref: value };
      } else {
        // Value is a number
        stack[variable] = value;
      }
    } else if (item.includes('log')) {
      let refKey = item.slice(4, -1);
      // Follow the reference chain and remove used variables
      while (refKey && stack[refKey]) {
        const newRefKey = stack[refKey].ref;
        delete stack[refKey];
        refKey = newRefKey;
      }
    }
  }
 
  return Object.keys(stack);
}

CSS Questions

Solution
<div class="container">
<div class='half'>
<div class="box top-left"><div class='round with-border'></div></div>
<div class="box bottom-left"><div class='round'></div></div>
</div>
<div class='half secound'>
<div class="box top-right"><div class='round'></div></div>
<div class="box bottom-right"><div class='round with-border'></div></div>
</div></div>
<style>
*{background: #FADE8B}
.round{border-radius: 50%;background: #FADE8B;height: 100%;width: 100%}
.with-border {height: 60px;width: 60px;background: #D86F45;border: 20px solid #FADE8B}
.container {display: flex; height: 100%}
.box {background: #D86F45;width: 100px;height: 100px}
.half {flex: 1;flex-direction: column;justify-content: center;align-items: flex-end;display: flex}
.secound {align-items: flex-start}
.top-right {border-radius: 50% 50% 50% 0%}
.top-left {border-radius: 50% 50% 0% 50%}
.bottom-right {border-radius: 0% 50% 50% 50%}
.bottom-left {border-radius: 50% 0% 50% 50%}
</style>