BigFrontEnd Category 17 String Implementation Questions

Introduction

This blog post summarizes the String implementation related questions found on BigFrontEnd.Dev.

1.convert HEX color to RGBA
2.convert snake_case to camelCase
3.decode message
4.longest substring with unique characters
5.implement String.prototype.trim()
6.compress a string
7.validate an IP address
8.validate string of parentheses
9.find the first duplicate character in a string
10.Count palindromic substrings
11.remove duplicate characters in a string
12.the angle between hour hand and minute hand of a clock
13.roman numerals to integer
14.integer to roman numerals
15.implement btoa()
16.implement atob()
17.most frequently occurring character
18.semver compare
19.remove characters
20.validate number string
21.uncompress string
22.interpolation
23.uglify CSS class names

1.convert HEX color to RGBA

78.https://bigfrontend.dev/problem/convert-HEX-color-to-RGBA

Suppose you write some CSS code, you need to set colors. You can choose hexadecimal notation #fff or Functional notation rgba(255,255,255,1).

Can you write a function to convert hexadecimal notation to functional notation?

hexToRgb('#fff')
// 'rgba(255,255,255,1)'

Alpha channel should have maximum 2 digits after decimal point, round up if needed.
Don't forget to do input validation

Solution:

/**
 * @param {string} hex
 * @return {string}
 */
function hexToRgba(hex) {
  // Helper function to validate the hex color input
  function isValidHex(hex) {
    return /^#([0-9A-Fa-f]{3,4}|[0-9A-Fa-f]{6,8})$/.test(hex)
  }

  // Helper function to expand shorthand hex notation to full form
  function expandShorthand(hex) {
    if (hex.length === 4) {
      return '#' + hex[1] + hex[1] + hex[2] + hex[2] + hex[3] + hex[3]
    }
    if (hex.length === 5) {
      return '#' + hex[1] + hex[1] + hex[2] + hex[2] + hex[3] + hex[3] + hex[4] + hex[4]
    }
    return hex
  }

  // Validate input
  if (!isValidHex(hex)) {
    throw new Error('Invalid hexadecimal color format')
  }

  // Expand shorthand notation if necessary
  hex = expandShorthand(hex)

  // Extract the red, green, blue, and alpha components
  let r = parseInt(hex.slice(1, 3), 16)
  let g = parseInt(hex.slice(3, 5), 16)
  let b = parseInt(hex.slice(5, 7), 16)
  let a = 1

  if (hex.length === 9) {
    a = parseInt(hex.slice(7, 9), 16) / 255
    a = Math.round(a * 100) / 100 // Round to two decimal places
  }

  return `rgba(${r},${g},${b},${a})`
}
// Example usage:
console.log(hexToRgb('#fff')) // 'rgba(255,255,255,1)'
console.log(hexToRgb('#ffffff')) // 'rgba(255,255,255,1)'
console.log(hexToRgb('#ff00ff80')) // 'rgba(255,0,255,0.5)'
console.log(hexToRgb('#123')) // 'rgba(17,34,51,1)'
console.log(hexToRgb('#1234')) // 'rgba(17,34,51,0.27)'

2.convert snake_case to camelCase

79.https://bigfrontend.dev/problem/convert-snake_case-to-camelCase

Do you prefer snake_case or camelCase ?

Anyway, please create a function to convert snake_case to camcelCase.

snakeToCamel('snake_case')
// 'snakeCase'
snakeToCamel('is_flag_on')
// 'isFlagOn'
snakeToCamel('is_IOS_or_Android')
// 'isIOSOrAndroid'
snakeToCamel('_first_underscore')
// '_firstUnderscore'
snakeToCamel('last_underscore_')
// 'lastUnderscore_'
snakeToCamel('_double__underscore_')
// '_double__underscore_'

contiguous underscore __, leading underscore _a, and trailing underscors a_ should be kept untouched.

Sliding window: x_x => xX;

Solution:

/**
 * @param {string} str
 * @return {string}
 */
function snakeToCamel(str) {
  const n = str.length
  // n - 3, n - 2, n -1
  if (n === 0) {
    return str
  }
  const ans = [str[0]]
  let i = 0
  while (i < n - 2) {
    // conside i, i + 1, i + 2
    if (str[i] !== '_' && str[i + 1] === '_' && str[i + 2] !== '_') {
      ans.push(str[i + 2].toUpperCase())
      i += 2
    } else {
      ans.push(str[i + 1])
      i += 1
    }
  }
  ans.push(str[n - 1])
  return ans.join('')
}

3.decode message

9.https://bigfrontend.dev/problem/decode-message

Your are given a 2-D array of characters. There is a hidden message in it.

I B C A L K A
D R F C A E A
G H O E L A D

The way to collect the message is as follows

start at top left
move diagonally down right
when cannot move any more, try to switch to diagonally up right
when cannot move any more, try switch to diagonally down right, repeat 3
stop when cannot neither move down right or up right. the character on the path is the message
for the input above, IROCLED should be returned.

notes

if no characters could be collected, return empty string

State change function.

Solution:

/**
 * @param {string[][]} message
 * @return {string}
 */
function decode(message) {
  const result = []
  let x = 0
  let y = 0
  let dir = 'down'

  const nextState = (x, y, dir) => {
    if (dir === 'down') {
      x++
    } else {
      x--
    }

    if (x === 0) {
      dir = 'down'
    } else if (x === message.length - 1) {
      dir = 'up'
    }

    y++
    return [x, y, dir]
  }
  const isValidState = (x, y, dir) => message[x] && message[x][y]
  while (isValidState(x, y, dir)) {
    result.push(message[x][y])
    ;[x, y, dir] = nextState(x, y, dir)
  }

  return result.join('')
}

4.longest substring with unique characters

87.https://bigfrontend.dev/problem/longest-substring-with-unique-characters

Given a string, please find the longest substring that has no repeated characters.

If there are multiple result, any one substring is fine.

longestUniqueSubstr('aaaaa')
// 'a'
longestUniqueSubstr('abcabc')
// 'abc', or 'bca', or 'cab'
longestUniqueSubstr('a12#2')
// 'a12#'

Follow-up

What is the time & space cost of your solution ? Could you do it better?

Solution:

/**
 * @param {string} str
 * @return {string}
 */
function longestUniqueSubstr(s) {
  const n = s.length
  let i = 0
  let j = 0
  let ans = ''
  const freq = {}
  const meetCondition = (freq) => Math.max(...Object.values(freq)) < 2
  while (i < n) {
    // Move the right index as far as possible until the condition is not met.
    while (i < n && meetCondition(freq)) {
      freq[s[i]] = (freq[s[i]] || 0) + 1
      i += 1
    }
    // [j, i - 2] is the range which meets the condtion.
    // freq contains the data from [j, i - 1]
    if (meetCondition(freq)) {
      // [j, i - 1] (freq) meet the condition
      if (ans.length < i - 1 - j + 1) {
        ans = s.substring(j, i)
      }
      break
    } else {
      // [j, i - 2] meet the condition
      if (ans.length < i - 2 - j + 1) {
        ans = s.substring(j, i - 2 + 1)
      }
    }
    // move the left index as far as possible until the condition is met.
    while (!meetCondition(freq)) {
      freq[s[j]] -= 1
      j += 1
    }
  }
  return ans
}

5.implement String.prototype.trim()

95.https://bigfrontend.dev/problem/implement-String-prototype-trim

String.prototype.trim() is commonly used when processing strings.

It is very easy, can you implement your own one?

There are many ways to do it, can you think of different approaches?

Solution:

\u3000 and are the spaces.

/**
 * @param {string} str
 * @return {string}
 */
function trim(str) {
  const n = str.length
  const isWhiteSpace = (char) => char === ' ' || char === '\u3000'
  let i = 0
  while (i < n && isWhiteSpace(str[i])) {
    i += 1
  }
  // i is the first non-empty character.
  let j = n - 1
  while (j >= 0 && isWhiteSpace(str[j])) {
    j -= 1
  }
  // j is the last non-empty character.
  return str.slice(i, j + 1)
}

/**
 * @param {string} str
 * @return {string}
 */
function trim(str) {
  return str.replace(/^[\s\u3000]+|[\s\u3000]+$/g, '')
}

6.compress a string

97.https://bigfrontend.dev/problem/compress-a-string

Given a string, compress the repeating letters with count number

compress('a') // 'a'
compress('aa') // 'a2'
compress('aaa') // 'a3'
compress('aaab') // 'a3b'
compress('aaabb') // 'a3b2'
compress('aaabba') // 'a3b2a'

Solution:

Fixed size sliding window.

function compress(str) {
  const n = str.length
  if (n <= 1) return str
  let count = 1
  let ans = []
  for (let i = 0; i < n - 1; i++) {
    // window i, i + 1
    if (str[i] === str[i + 1]) {
      count += 1
    } else {
      // str[i] ends and str[i + 1] start
      ans.push(str[i])
      if (count > 1) {
        ans.push(String(count))
      }
      count = 1
    }
  }
  ans.push(str[n - 1])
  if (count > 1) {
    ans.push(String(count))
  }
  return ans.join('')
}

/**
 * @param {string} str
 * @return {string}
 */
function compress(str) {
  let ans = ''
  let pre = ''
  let count = 0
  for (const char of str) {
    if (pre === '') {
      pre = char
      count = 1
    } else if (pre === char) {
      count += 1
    } else {
      if (count === 1) {
        ans += pre
      } else {
        ans += `${pre}${count}`
      }
      pre = char
      count = 1
    }
  }
  if (count === 1) {
    ans += pre
  } else {
    ans += `${pre}${count}`
  }
  return ans
}

7.validate an IP address

98.https://bigfrontend.dev/problem/validate-an-ip-address

IPv4

An IPv4 Address is represented in dot-decimal notation, consisting of 4 numbers( called 'octet'), each ranging from 0 to 255, like 1.22.33.255. It has 32 bit, so there are maximum 2^32 = 4,294,967,296 IPv4 addresses.

Leading zeroes are not allowed in IPv4, like 01.01.01.01 is invalid.

IPv6

An IPv6 Address have 128 bits (which is a lot), separated by 8 groups (called 'hexadectet', or 'hextet', not fixed yet). Each group has 16 bits, so could be represented by a hexadecimal string at 4 digits, such as 2001:0db8:85a3:0000:0000:8a2e:0370:7334.

Notice that leading zeroes are allowed in IPv6.

There are other valid format of IPv6 addresses, like Zero compression, but it is beyond the scope here, you can ignore them.

Task

You are given some random string, please write a function if it is valid IPv4 or IPv6 address.

Follow-up

Can you solve it with regular expressions ?

Solution:

/**
 * @param {string} str
 * @return {boolean}
 */
function isValidIPv4(ip) {
  const ipv4Pattern =
    /^(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)){3}$/
  return ipv4Pattern.test(ip)
}

function isValidIPv6(ip) {
  const ipv6Pattern = /^([0-9a-fA-F]{1,4})(:[0-9a-fA-F]{1,4}){7}$/
  return ipv6Pattern.test(ip)
}

function isValidIP(ip) {
  return isValidIPv4(ip) || isValidIPv6(ip)
}

8.validate string of parentheses

102.https://bigfrontend.dev/problem/validate-parenthesis

Given a string containing only following characters:

parentheses : ( or ) brackets: [ or ] braces: { or } write a function to determine if they are valid.

By 'valid', it means all should be rightly paired, and with the valid order.

validate('{}[]()')
// true
validate('{[()]}')
// true
validate('{[}]')
// false, they are not in the right order
validate('{}}')
// false, last `}` is not paired with `{`

Follow-up

What is time & space complexity of your approach ? Can you do it better?

Solution:

/**
 * @param {string} str
 * @return {boolean}
 */
function validate(str) {
  const stack = []
  for (let i = 0; i < str.length; i++) {
    const ch = str[i]
    if (['{', '[', '('].includes(ch)) {
      stack.push(ch)
    } else {
      if (stack.length === 0) {
        return false
      }
      const matched = `${stack.pop()}${ch}`
      if (!['()', '[]', '{}'].includes(matched)) {
        return false
      }
    }
  }
  return stack.length === 0
}

9.find the first duplicate character in a string

105.https://bigfrontend.dev/problem/find-the-first-duplicate-character-in-a-string

Given a string which might have duplicate letters, write a function to find the first duplicate.

firstDuplicate('abca')
// 'a'
firstDuplicate('abcdefe')
// 'e'
firstDuplicate('abcdef')
// null

What is the time & space cost of your approach ? Can you do better?

Solution:

/**
 * @param {string} str
 * @return {string | null}
 */
function firstDuplicate(str) {
  const seen = new Set()
  for (const char of str) {
    if (seen.has(char)) {
      return char
    }
    seen.add(char)
  }
  return null
}

10.Count palindromic substrings

111.https://bigfrontend.dev/problem/Count-palindromic-substrings

A palindromic string reads the same backward as forward, such as 'madam'.

Now given a string, count how many substrings it has?

Like 'madam', it has following palindromic strings:

'm'
'a'
'd'
'a'
'm'
'ada'
'madam'

What is the time and space cost of your solution ? Could you improve it ?

Solution:

/**
 * @param {string} str
 * @return {number}
 */
function countPalindromicSubstr(str) {
  const n = str.length
  if (n === 0) return 0
  const memo = new Map()
  let count = 0
  for (let i = 0; i < n; i++) {
    memo.set(`${i},${i}`, true)
    count += 1
  }
  for (let i = 0; i < n - 1; i++) {
    memo.set(`${i},${i + 1}`, str[i] === str[i + 1])
    if (str[i] === str[i + 1]) {
      count += 1
    }
  }
  const helper = (i, j) => {
    const key = `${i},${j}`
    if (memo.has(key)) {
      return memo.get(key)
    }
    const ans = str[i] === str[j] && helper(i + 1, j - 1)
    memo.set(key, ans)
    if (ans) {
      count += 1
    }
    return ans
  }
  for (let i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      helper(i, j)
    }
  }
  return count
}

function countPalindromicSubstr(s) {
  const n = s.length
  let count = 0
  const dp = Array(n).fill(Array(n).fill(false))
  // const dp = Array.from({ length: n }, () => Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    dp[i][i] = true
    count++
  }

  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1
      if (s[i] === s[j]) {
        if (length == 2 || dp[i + 1][j - 1]) {
          dp[i][j] = true
          count++
        }
      }
    }
  }

  return count
}

11.remove duplicate characters in a string

112.https://bigfrontend.dev/problem/remove-duplicate-letters-in-a-string

Given a string, write a function to remove the duplicate characters to make sure that each character only occurs once.

For example

'xyzabcxyzabc'

Each character appears twice, we could make it unique as follows

'xyzabc'
'xyabcz'
'xabcyz'
'abcxyz'
'abxyzc'
.....

Above all substrings subsequences (*) contains unique characters, but you need to return the smallest one in lexicographical order( 'a' -> 'z'), which is 'abcxyz'.

All input only contains valid lowercase alphabets only.

Solution:

function removeDuplicateLetters(s) {
  const charFrequency = {}
  const includedInResult = new Set()
  const result = []

  // Count the frequency of each character in the string
  for (const char of s) {
    if (charFrequency[char]) {
      charFrequency[char]++
    } else {
      charFrequency[char] = 1
    }
  }

  for (const char of s) {
    // Decrease the frequency count for the current character
    charFrequency[char]--

    // If the character is already included in the result, skip it
    if (includedInResult.has(char)) {
      continue
    }

    // Remove characters from the result if the current character is smaller
    // than the last character in the result and the last character can still appear later
    while (
      result.length > 0 &&
      char < result[result.length - 1] &&
      charFrequency[result[result.length - 1]] > 0
    ) {
      includedInResult.delete(result.pop())
    }

    // Add the current character to the result and mark it as included
    result.push(char)
    includedInResult.add(char)
  }

  // Join the result array to form the final string
  return result.join('')
}

const input = 'xyzabcxyzabc'
console.log(removeDuplicateLetters(input)) // Output: 'abcxyz'

12.the angle between hour hand and minute hand of a clock

132.https://bigfrontend.dev/problem/the-angle-between-hour-hand-and-minute-hand-of-a-clock

Given a time string in format HH:mm, please return the angle between hour hand and minute hand.

You should return rounded integer representing the smaller angle in degrees.

angle('12:00')
// 0
angle('23:30')
// 165

Solution:

/**
 * @param {string} time
 * @returns {number}
 */
function angle(time) {
  const [hours, minutes] = time.split(':').map(Number)
  const hoursDegree = ((hours >= 12 ? hours - 12 : hours) / 12) * 360 + (minutes / 60) * 30
  const mintuesDegree = (minutes / 60) * 360
  console.log(`${hoursDegree}-${mintuesDegree}`)
  const angle = Math.abs(hoursDegree - mintuesDegree)
  return Math.round(Math.min(angle, 360 - angle))
}
console.log(angle('12:15'))

13.roman numerals to integer

133.https://bigfrontend.dev/problem/roman-numerals-to-integer

Roman numerals are represented by combinations of following seven symbols, each with a fixed integer value.

Symbol	I	V	X	L	C	D	M
Value	1	5	10	50	100	500	1000

For Standard form, subtractive notation is used, meaning 4 is IV rather than IIII, 9 is IX rather than VIIII. Same rule applies to 40(XL) and 900(CM) .etc.

Simply speaking, the roman numerals in standard form follow these rules.

symbols are listed from highest to lowest, from left to right
from left to right, if the next symbol value is bigger than current one, it means subtracting, otherwise adding.

Please implement romanToInteger(). The input are all valid strings.

romanToInteger('CXXIII')
// 123
romanToInteger('MCMXCIX')
// 1999
romanToInteger('MMMCDXX')
// 3420

Solution:

/**
 * @param {string} str - roman numeral string
 * @returns {number} integer
 */
function romanToInteger(roman) {
  const romanToIntMap = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  }

  let result = 0
  for (let i = 0; i < roman.length; i++) {
    const currentVal = romanToIntMap[roman[i]]
    const nextVal = romanToIntMap[roman[i + 1]]

    if (nextVal > currentVal) {
      result -= currentVal
    } else {
      result += currentVal
    }
  }

  return result
}

14.integer to roman numerals

163.https://bigfrontend.dev/problem/integer-to-roman

Roman numerals are represented by combinations of following seven symbols, each with a fixed integer value.

Symbol	I	V	X	L	C	D	M
Value	1	5	10	50	100	500	1000

For Standard form, subtractive notation is used, meaning 4 is IV rather than IIII, 9 is IX rather than VIIII. Same rule applies to 40(XL) and 900(CM) .etc.

Simply speaking, the roman numerals in standard form follow these rules.

symbols are listed from highest to lowest, from left to right
from left to right, if the next symbol value is bigger than current one, it means subtracting, otherwise adding. Please implement integerToRoman(). The input are all integers within valid range.

integerToRoman(123)
// 'CXXIII'
integerToRoman(1999)
// 'MCMXCIX'
integerToRoman(3420)
// 'MMMCDXX'

Solution:

/**
 * @param {number} integer
 * @returns {string} str - roman numeral string
 */
function integerToRoman(num) {
  // Define a list of tuples with Roman numeral symbols and their corresponding values.
  const romanSymbols = [
    { value: 1000, symbol: 'M' },
    { value: 900, symbol: 'CM' },
    { value: 500, symbol: 'D' },
    { value: 400, symbol: 'CD' },
    { value: 100, symbol: 'C' },
    { value: 90, symbol: 'XC' },
    { value: 50, symbol: 'L' },
    { value: 40, symbol: 'XL' },
    { value: 10, symbol: 'X' },
    { value: 9, symbol: 'IX' },
    { value: 5, symbol: 'V' },
    { value: 4, symbol: 'IV' },
    { value: 1, symbol: 'I' },
  ]

  let result = ''

  // Iterate over the romanSymbols array
  for (let i = 0; i < romanSymbols.length; i++) {
    const { value, symbol } = romanSymbols[i]
    // Subtract the value from num and append the symbol to result until num < value
    while (num >= value) {
      num -= value
      result += symbol
    }
  }

  return result
}

15.implement `btoa()`

141.https://bigfrontend.dev/problem/implement-btoa

btoa() accepts a binary string and returns a Base64-encoded ASCII string from it. Characters in a binary string are the ASCII character for each byte of the binary data.

Please read Base64 wiki and implement your own btoa().

myBtoa('BFE')
// 'QkZF'
myBtoa('BFE.dev')
// 'QkZFLmRldg=='

note

Please don't use window.btoa() in your code.
The binary string passed to your function are all valid ASCII characters, there will be another problem on the general Base64 encoding/decoding.

Solution:

convert the string to binary format.
Pad 0 behind to make sure the length can be divided by 6.
split the string to 6 bits and convert it to the index and lookup for the base64 chars.
Add "=" to make sure the length of result can be divided by 4.

/**
 * @param {string} str - binary string
 * @returns {string}
 */
function myBtoa(binaryString) {
  const base64Chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

  let binary = [...binaryString]
    .map((char) => char.charCodeAt(0).toString(2).padStart(8, '0'))
    .join('')
  // Pad zeros to make sure the length can be divided by 6
  if (binary.length % 6 !== 0) {
    binary += '0'.repeat(6 - (binary.length % 6))
  }
  const n = binary.length
  let base64 = Array(Math.floor(n / 6))
    .fill(0)
    .map((_, index) => binary.slice(index * 6, index * 6 + 6))
    .map((chunk) => base64Chars[parseInt(chunk, 2)])
    .join('')

  // Ensure input length is a multiple of 4
  const padding = base64.length % 4
  if (padding > 0) {
    base64 += '===='.slice(padding)
  }
  return base64
}

16.implement `atob()`

160.https://bigfrontend.dev/problem/implement-atob

atob() decodes a string of data which has been encoded using Base64 encoding.

Please implement your own myAtob()

myAtob('QkZFLmRldg==') // 'BFE.dev'
myAtob('Q') // Error

Please don't use atob() directly in your code.

Solution:

atob() decodes a string of data which has been encoded using Base64 encoding.

/**
 * @param {string} encoded
 * @return {string}
 */
function myAtob(input) {
  const createBase64Lookup = () => {
    // Base64 characters
    const base64Chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    // 26 + 26 + 10 + 2 = 64
    const base64Lookup = Object.fromEntries(
      base64Chars.split('').map((char, index) => [char, index])
    )
    return base64Lookup
  }
  // Ensure input length is a multiple of 4
  if (input.length % 4 !== 0) {
    throw new Error('Invalid base64 string')
  }

  // Remove padding characters
  input = input.replace(/=+$/, '')

  const base64Lookup = createBase64Lookup()
  // Convert each character to its 6-bit binary representation
  const binaryString = [...input]
    .map((char) => base64Lookup[char].toString(2).padStart(6, '0'))
    .join('')

  if (binaryString.length > 0 && binaryString.length < 8) {
    throw new Error()
  }

  // Split the binary string into 8-bit chunks and convert to ASCII characters
  const n = binaryString.length
  return Array(Math.floor(n / 8))
    .fill(0)
    .map((_, index) => binaryString.substring(8 * index, 8 * index + 8))
    .map((byte) => String.fromCharCode(parseInt(byte, 2)))
    .join('')
}

17.most frequently occurring character

145.https://bigfrontend.dev/problem/most-frequently-occurring-character

Given a non-empty string, return the most frequently ocurring character.

If there are multiple characters with same occurrance, return an array of them.

count('abbccc')
// 'c'
count('abbcccddd')

Follow-up: What is the time & space complexity of your approach?

Solution:

/**
 * @param {string} str
 * @returns {string | string[]}
 */
function count(str) {
  const calFreq = (str) => {
    const freq = {}
    for (const char of str) {
      const val = freq[char] || 0
      freq[char] = val + 1
    }
    return freq
  }
  const freq = calFreq(str)
  const maxFreq = Math.max(...Object.values(freq))
  const ans = Object.keys(freq).filter((key) => freq[key] === maxFreq)
  return ans.length === 1 ? ans[0] : ans
}

18.semver compare

157.https://bigfrontend.dev/problem/semver-compare

Please implement a function to compare 2 semver strings.

compare('12.1.0', '12.0.9')
// 1, meaning first one is greater
compare('12.1.0', '12.1.2')
// -1, meaning latter one is greater
compare('5.0.1', '5.0.1')
// 0, meaning they are equal.

Solution:

/**
 * @param {string} v1
 * @param {string} v2
 * @returns 0 | 1 | -1
 */
function compare(v1, v2) {
  const items1 = v1.split('.').map(Number)
  const items2 = v2.split('.').map(Number)
  if (items1.length !== 3 || items2.length !== 3) {
    throw new Error('input is not correct.')
  }
  for (let i = 0; i < 3; i++) {
    if (items1[i] !== items2[i]) {
      return items1[i] < items2[i] ? -1 : 1
    }
  }
  return 0
}

19.remove characters

165.https://bigfrontend.dev/problem/remove-characters

Given a string contaning only a, b and c, remove all b and ac.

removeChars('ab') // 'a'
removeChars('abc') // ''
removeChars('cabbaabcca') // 'caa'

What is the time and space complexity of your approach?

Solution:

/**
 * @param {string} input
 * @returns string
 */
function removeChars(input) {
  let ans = input
  let reducedSize = input.length
  while (reducedSize > 0) {
    const size = ans.length
    ans = ans.replaceAll('b', '').replaceAll('ac', '')
    reducedSize = size - ans.length
  }
  return ans
}

20.validate number string

166.https://bigfrontend.dev/problem/validate-number-string-1

Give a number string, check if it is valid number.

By "valid", we mean if it validates as one of below formats:

integer, such as '0', '-1'
decimal number like '1.0', '-2.335'
exponential notation -12.3e45

Formats such as BigInt, Infinity, NaN, octal and hexadecimal .etc are out of scope, you can treat them as invalid.

Pay attention to the sign + -.

Note

The test cases are not covering all the possible cases, since this is not a problem to test your knowledge against JavaScript language spec.

You should confirm with your interviewer about the scope and those edge cases.

isNaN() seems to be a nice trick, but could you solve without it?

Solution:

function validateNumberString(str) {
  // Define the regular expression pattern for valid numbers
  // const pattern = /^[\+\-]?(\d+)?(\.)?(\d+)?(e[\+\-]?\d+)?$/i;
  const pattern = /^[\+\-]?(\d+(\.\d*)?|\.\d+)(e[\+\-]?\d+)?$/i
  // Test the input string against the pattern
  // [\+\-]?
  // (\d+(\.\d*)?|\.\d+) => \d+(\.\d*)? or \.\d+
  // (e[\+\-]?\d+)? => e, [\+\-]?, \d+
  return pattern.test(str)
}

21.uncompress string

173.https://bigfrontend.dev/problem/uncompress-string

Given a compressed string, return its original form.

For example.

uncompress('3(ab)') // 'ababab'
uncompress('3(ab2(c))') // 'abccabccabcc'

a number k followed by a pair of parenthesis, meaning to repeat the substring inside the parenthesis by k times, k is positive integer.
inputs are guaranteed to be valid input like above example, there is no numerical digit in original form.

Solution:

The basic structure is a structure like ab2(c). The first part is letters part: ab. The second part is a numbers part: 2. The last part is wrapped with () and contains the similar structure.

When a ( is met, we need to push ab and 2 to the stack. and reset curStr and curNum. When a ) is met, we need pop out, curStr and curNum and calculate the result.

/**
 * @param {string} str
 * @returns {string}
 */
function uncompress(s) {
  let stack = []
  let currNum = 0
  let currStr = '' // Track the current string between ( and )

  for (let char of s) {
    if (char === '(') {
      stack.push([currStr, currNum])
      currStr = ''
      currNum = 0
    } else if (char === ')') {
      const [prevStr, num] = stack.pop()
      currStr = prevStr + currStr.repeat(num)
    } else if (Number.isNaN(parseInt(char))) {
      currStr += char
    } else {
      currNum = currNum * 10 + parseInt(char)
    }
  }

  return currStr
}

22.interpolation

149.https://bigfrontend.dev/problem/interpolation

Have you ever added i18n support to your projects?

Take i18next as an example, generally the keys and translations are kept separately, like this JSON below.

{
  "evaluation": "BFE.dev is {{evaluation}}"
}

At places where this key is used, we can then interpolate the string by passing a data object.

t('evaluation', { evaluation: 'fantastic' })
// "BFE.dev is fantastic"

Now, please create a similar t() function which accepts the translation directly.

it supports {{ and }} as delimiters Let's make it clearer and simpler, when a new pair {{ is met, characters until the following }} are treated as the property name.

For all the other cases, they should not be treated as delimiters.

t('BFE.dev is {{{evaluation}', { evaluation: 'fantastic' })
// "BFE.dev is {{{evaluation}"
t('BFE.dev is {{{evaluation}}}', { '{evaluation': 'fantastic' })
// "BFE.dev is fantastic}"
t('BFE.dev is {{evalu ation}}', { 'evalu ation': 'fantastic' })
// "BFE.dev is fantastic"

if no data is passed or no property exists, just leave it empty

t('BFE.dev is {{evaluation}}')
// "BFE.dev is "

Solution:

We can use findIndex to locate the positions of {{ and }}, then extract and translate the key.

/**
 * @param {string} translation
 * @param {any} data
 * @returns {string}
 */
function t(translation, data) {
  let chars = [...translation];
  const n = translation.length;
  const index1 = chars.findIndex((val, index) => val === "{" && index < n - 1 && chars[index + 1] === "{");
  if (index1 === -1) return translation;
  const slicedChars = chars.slice(index1, n);
  const index2 = slicedChars.findIndex((val, index) => val === "}" && index < n - 1 && slicedChars[index + 1] === "}");
  if (index2 === -1) return translation;
  let str1 = translation.slice(0, index1);
  const key = translation.slice(index1 + 2, index1 + index2);
  let str2 = t(translation.slice(index1 + index2 + 2), data);
  if (!data || !data[key]) return `${str1}${str2}`;
  return `${str1}${data[key]}${str2}`;
}

23.uglify CSS class names

153.https://bigfrontend.dev/problem/unique-class-name

If you use css-loader in your webpack project, localIdentName could be used to transform class names, like below:

localIdentName: "[path][name]__[local]--[hash:base64:5]", Or you can create your own function to generate class names by setting getLocalIdent.

Now please create a function to generate unique class names following rules below.

only use alphabets: a to z , A to Z return one unique class name each time function is called the class name sequence should first be in order of length, then in Alphabetical order(lowercase in front). should provide a function to reset the sequence

getUniqueClassName()
// 'a'
getUniqueClassName()
// 'b'
getUniqueClassName()
// 'c'
// skip cases till 'Y'
getUniqueClassName()
// 'Z'
getUniqueClassName()
// 'aa'
getUniqueClassName()
// 'ab'
getUniqueClassName()
// 'ac'
// skip more cases
getUniqueClassName()
// 'ZZ'
getUniqueClassName()
// 'aaa'
getUniqueClassName()
// 'aab'

getUniqueClassName()
// 'aac'
getUniqueClassName.reset()
getUniqueClassName()
// 'a'

Solution:

We can extract the character codes and simulate the process of adding 1.

let cur = 'a';
/**
 * @returns {string}
 */
function getUniqueClassName() {
  const chars = [];
  const ans = cur;

  const n = cur.length;
  let carry = 0;
  for (let i = n - 1; i >= 0; i--) {
    const charCode = cur.charCodeAt(i);
    let newCharCode = charCode + carry;
    if (i === n - 1) {
      newCharCode += 1;
    }
    if (newCharCode - 1 === 'z'.charCodeAt(0)) {
      newCharCode = 'A'.charCodeAt(0);
      carry = 0;
    } else if (newCharCode - 2 === 'z'.charCodeAt(0)) {
      newCharCode = 'B'.charCodeAt(0);
      carry = 0;
    } else if (newCharCode - 1 === 'Z'.charCodeAt(0)) {
      newCharCode = 'a'.charCodeAt(0);
      carry = 1;
    } else if (newCharCode - 2 === 'Z'.charCodeAt(0)) {
      newCharCode = 'b'.charCodeAt(0);
      carry = 1;
    } else {
      carry = 0;
    }
    chars.unshift(String.fromCharCode(newCharCode));
  }
  if (carry === 1) {
    chars.unshift("a");
  }
  cur = chars.join("");
  return ans;
}

getUniqueClassName.reset = function() {
  cur = 'a';
}

Introduction

1.convert HEX color to RGBA

2.convert snake_case to camelCase

3.decode message

4.longest substring with unique characters

5.implement String.prototype.trim()

6.compress a string

7.validate an IP address

8.validate string of parentheses

9.find the first duplicate character in a string

10.Count palindromic substrings

11.remove duplicate characters in a string

12.the angle between hour hand and minute hand of a clock

13.roman numerals to integer

14.integer to roman numerals

15.implement btoa()

16.implement atob()

17.most frequently occurring character

18.semver compare

19.remove characters

20.validate number string

21.uncompress string

22.interpolation

23.uglify CSS class names

15.implement `btoa()`

16.implement `atob()`