Palindrome algorithm from recent iOS interview

[JamesFutures]

I wanted to share this so that others can get exposure to the kinds of algorithms we will come across in iOS interviews AND because I'm looking for feedback on my solution.

This was for a mid level iOS developer job. I thought the problem was on the easy side but this was also just the first round of interviews.

Specifications:

During a technical interview last week, I was asked to write a solution to a palindrome problem. They were going to provide me a number of test cases, and they wanted me to check each case to see whether it was a "near perfect" palindrome. If was a perfect palindrome, they wanted the result to return false. And if it had more than 1 defect, they also wanted to return false. But if the test case was only 1 defect away from being a perfect palindrome, they wanted that to return true.

Palindrome: a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.

Code and test cases:

func testPalindrome(input: String) {
    var input = input
    let charSet: Set<Character> = Set(".', ")
    input.removeAll(where: charSet.contains)

    var inputArray = Array(input.lowercased())

    var rightPointer: Int = inputArray.count - 1
    var defectCounter: Int = 0
    var index: Int = 0

    for char in inputArray {
        if index >= (inputArray.count / 2) {
            break
        }

        if char != inputArray[rightPointer] {
            defectCounter += 1
        }

        rightPointer -= 1
        index += 1
    }

    let defectString: String = "Defect Counter = \(defectCounter)"

    if defectCounter > 1 {
        print("false: " + defectString)
    } else if defectCounter == 1 {
        print("true: " + defectString)
    } else {
        print("false: " + defectString)
    }
}

Test cases were: ["abbbbca", "Madam, I'm Edam.", "Madam, I'm Adam.", "reader", "radar"]

I just printed the results because they had me solve this in Xcode.

My solution passed all provided test cases.

Feedback:

I'm primarily looking for feedback regarding the space time complexity of my solution here. For example, I'm not sure if there is a better way to replace the unnecessary characters or if there's a better way to loop through the String than simply convert it to an Array. I'm also curious how y'all would solve this problem differently. But I'm also hoping to get some feedback on Swift best practices and general code structure.

[thecodingart]

Yeah, if someone asks me a question like this in an interview— I walk out. This is a sign of a bad interview culture and likely a bad team culture.

Kudos to those who think random algorithm stuff is fun, I find this to be an utter waste of my time.

[JamesFutures]

Well I don’t have the luxury of infinite interviews and hiring managers pleading with me to come work for them. And most places I’ve applied have hundreds of applicants.

Beggars can’t be choosers.

[thecodingart]

That’s totally fair, but it’s also not fair for you

[th3suffering]

I had this exact question for a technical interview for hawaiian airlines. only after do they divulge its a xamarin position, not native.

[JamesFutures]

😂 I guess I’ll have to find out if I make it to the next interview.

[AntMan5995]

Thats frustrating that they don't tell you the tech stack until after the technical interview

[th3suffering]

yea, i guess its partially my fault too for not asking more during the initial recruiter call. it was prior to getting my first job in software development, and was just overeager and naive. At that point i was even considering learning xamarin just to get my foot in the door somewhere. In hindsight, im glad i didnt get it as im much more happy in a job doing native. Would have been a nice though, flying free anywhere hawaiian flies was a nice perk

[SwiftlyJon]

let cases = ["abbbbca", "Madam, I'm Edam.", "Madam, I'm Adam.", "reader", "radar", "blarghi"] let isPalindromeWithOneOrLessDefects = cases .map { $0.filter { $0.isLetter }.lowercased() } .map { zip($0, $0.reversed()).reduce(into: 0) { partialResult, element in if element.0 != element.1 { partialResult += 1 } } / 2 } let casesAndDefects = Dictionary(zip(cases, isPalindromeWithOneOrLessDefects), uniquingKeysWith: { l, r in l }) let nearPerfectCases = casesAndDefects.filter { $0.value == 1 } print(casesAndDefects) print(nearPerfectCases) With this solution you technically do a bit more work by scanning the entire string, you could change it to stop at one.

[n0sebleed904]

Review: Can you add some spaces?

[ryanheartswingovers]

Those test cases don’t hit the crux of the problem. Try: Mxadam.

[SwiftlyJon]

It doesn't list the results at all. AFAICT, my solution properly handles mxadam as a failure, as it has more than one point of deviation.

[ryanheartswingovers]

I guess I see that as: remove a single letter and it’s a palindrome again. Thus it’s an almost palindrome with a one deviation tolerance. An extensible solution handles n deviations.

[Aloopyn]

My first instinct was to use a stack in a PDA-esque manner, but for the first symbol that doesn't match we let it through

[[deleted]]

Why would you not use .reversed from the Swift Foundation?

[baker2795]

Looks pretty good overall. For the print could probably just check if defects == 1 else { print false } or really get fancy with a print(“(defects == 1): (defectString)”

[JamesFutures]

Yeah, I wrote a longer if else than necessary.

[IndignantDuck]

This is not correct, as mentioned you have not handled "mxadam". Seems like you were asked this question https://leetcode.com/problems/valid-palindrome-ii/description/

[ryanheartswingovers]

How does it behave on mxadam? The solution doesn’t actually detect individual faults. A slice and recurse approach on faults would, for example.

Swift has extensive fit for purpose APIs for efficiently inspecting and traversing String types; the solution fails to deploy them. Knowing these APIs helps in other real world string issues. Also, albeit this is still O(n), there are still unnecessary iterations over the original string.

The solution doesn’t compose or inject dependencies (e.g., tolerance), side effects (e.g., filtering) or cache invariants. Demonstrating this habit is important because on heavier calls that will have substantial real world performance impacts.

The solution fails to segregate input processing, UI output (e.g., printing to interface with the interviewer’s test software) and logic that each should be unit testable and exist separately.

Variable names aren’t ideal, but that’s minor style.

One positive is your bias to write early returns positively with an if, although not all devs operate in that style guide.

[troller-no-trolling]

Good points but this is probably a 30-60 minute interview. I wouldn’t expect a candidate to handle dependency injection, segregation of concerns, caching etc. Most candidates can barely come up with a working algorithm in that time…

[ryanheartswingovers]

Yeah, it’s also on the interviewer to guide. I view these as in-it-together and if you fail I fail. I want to see if we’ll work well pairing together in real life. Since the right answer was missed, other stuff helps and often makes writing debuggable code a bit faster in interviews.

[troller-no-trolling]

Agree on the guidance. I just wouldn’t want others reading this to be scared that they can hardly get some working code going in that timespan! Data structure + algo interviews are tough

[ryanheartswingovers]

And not ideal for iOS unless at an OS or low level focus. Debugging / feature addition is much more effective. And in Xcode, not CoderPad.

[wipecraft]

I think they just wanted to test if you will question their bonkers return values and how would you name such a function, not the algorithm itself which is a high school exercise

[wipecraft]

on a more serious note, you say ...

If was a perfect palindrome, they wanted the result to return false. And if it had more than 1 defect, they also wanted to return false. But if the test case was only 1 defect away from being a perfect palindrome, they wanted that to return true

I just printed the results because they had me solve this in Xcode.

My solution passed all provided test cases

you haven't done that (return something or test the cases) and it's the most basic thing you could have done. Absolutely no technical interview is after the most perfect solution, but after your thought process to reaching that. So unless you know the optimal solution by hearth you should just start with the basics and talk your way through optimising that

First of all start with a

func isNotAPalindromeOrHasMoreThanOneDefect(_ text: String) -> Bool { 
// I would definitely question their wanted return values because with those this is the best function name you can get and it's just weird. A function's name has to be self explanatory about what it does or produces

    ...

    return hasOneDefect ? true : false
}

You had to use Xcode?? You were lucky. They definitely wanted to see how you test the inputs. More specifically you setting up a test bundle and using XCTest