I had a technical test for an entry-level job 2 days ago. It went well apart from the last assessment. I will go over the assessment with the CTO tomorrow and was hoping I could get help to get my head around this one, so I do not sound clueless. It was something like this:

Given string as an argument, give us palindrome method that would check if a palindrome of a minimum 3 characters can be created by removing 1 or 2 characters. The string has no special characters, numbers or whitespace basically only letters (eg: str = "abecbea") If true, print letters removed, if false print "not possible"

"remove 1 or 2 characters" and "print letters removed" is giving me a headache legit

I have tried a lot of different things but for the last 2 days but i am completely stuck! [EDIT]

Ideas i started with below

def is_palindrome(s)
  s == s.reverse && s.length >= 3
end

def possible_palin_by_removing_one_char(s)
  array_chars = s.chars
  first_char = array_chars[0]
  last_char = array_chars[-1]

  while first_char < last_char 
    if first_char != last_char
      first_char  = 1
      last_char -= 1
    else
      if is_palindrome
        puts ????
      else
        puts "not possible"
      end
    end
  end
end

or

def palindrome?(string)
  deleted_chars = []
  candidates = 0.upto(string.length-1).map do |index|
    array_chars = string.chars 
    deleted_chars << array_chars.delete_at(index)
    array_chars
  end

  if candidates.any? { |c| c.reverse == c } && string.length >= 3
    puts "It is a palindrome with letters '#{deleted_chars.join(",")}' removed !"
    # puts deleted_chars
  else
    if string.length <= 3
      puts "String '#{string}' is too short"
    else  
      puts "This is not possible to create palindrome with string '#{string}'"
    end
  end
end

palindrome?("abcecbae")

I would love someone to help me solve this one Thanks heaps for your help

CodePudding user response：

• Put all chars in an Array (ar = str.chars)
• Try all combinations which are 2 less than the size of the array (so 5 in the example "abcecbae")(ar.combination(5))
• Select all combinations which happen to be equal to their reverse
• Map the result(s) back from arrays to strings
• Similar for 1 removed char.

CodePudding user response：

This task might be a little bit trickier without Ruby's rich standard library support.

Here is how I'd solve this task in the 1st iteration:

1. Check if the original string is a palindrome, return immediately if it is
2. Build a list of possible combinations of indices to remove
3. Iterate over this list, check if removing the chars at given indices makes our input string a palindrome

The trickiest part here is (2), but Enumerable#permutation almost does the job.

So, something like

def palindrome?(s)
  s == s.reverse
end

def indices_to_remove(string)
  ary = (0..string.size-1).to_a
  # Permutations like [0,1] and [1,0] means the same in our context, so we need to remove this duplication.
  (ary.map { |x| [x] }   ary.permutation(2).map(&:sort)).uniq
end

def remove_chars(str, *indices)
  str.dup.tap do |s|
    indices.sort.reverse_each { |i| s[i] = '' }
  end
end

def find_palindrome(str)
  return if palindrome?(str)

  indices_to_remove(str).each do |indices|
    new_str = remove_chars(str, *indices)
    return "Letters removed: #{indices.inspect}; palindrome: '#{new_str}'" if palindrome?(new_str)
  end
end

That's it. Let's see if i works:

pry(main)> find_palindrome("abecbea")
=> "Letters removed: [1, 3]; palindrome: 'aebea'"

It does. Adjust the filtering logic (check palindroms' size as needed) and output if necessary.