IMMENSE.LY

IT’S THAT BIG

  • Is Rotation

    I’m not certain how practical this next problem is, but it seems to be a staple of interviewing questions. The problem is to write a function to check to see if one string is a rotation of another string. By rotation, they’re asking if the string is offset by some amount of characters, and then has excess characters prepended to the beginning of the string. For example, “erwat” is a rotation of the string “water”. I ended up solving this two different ways, the first was to just brute force the problem by writing a function which would rotate one of the strings until it matched the other string. Here’s the code: def isRotation1(s1, s2): if len(s1) != len(s2): return False def rotateStr(mystr, count): return mystr[count:] + mystr[0:count] for n in range(len(s1)): if s2 == rotateStr(s1, n): return True return False This is pretty ineffecient. The string copy is super expensive, so the runtime of this is O(N2) which is pretty ugly. A smarter way of solving this problem is to concatenate one of the strings against itself and then searching for the other string inside of the larger string. With our “erwater” example, we end up with a larger string which is “erwaterwat” and then we just search in that string for “water”.

    Read more…
  • Set Matrix Zeros

    Much like the Rotation Matrix, the “Set Matrix Zeros” problem involves being careful about not destroying the existing matrix which is being operated on. The idea is that given a cell in the matrix which is set to zero, set all of the other cells in the same row or column to zero. I tackled this in two ways which are almost identical. First up was just making a copy of the initial matrix and working on that instead. Here’s the code: import copy def zeroMatrix1(mtrx): newMtrx = copy.deepcopy(mtrx) def zeroRowCol(r, c): for n in range(len(mtrx)): newMtrx[n][c] = 0 for n in range(len(mtrx[0])): newMtrx[r][n] = 0 for r in range(len(mtrx)): for c in range(len(mtrx[0])): if not mtrx[r][c]: zeroRowCol(r, c) return newMtrx The deepcopy is important here otherwise you end up with a copy of the original matrix and you’ll be operating on that instead. There’s not really a “trick” here per se, but the key is if we hadn’t made the copy and zeroRowCol() operated on the original matrix, it would fill in everything with lots of zeros. Since making a copy of the matrix is expensive, there is a way of doing this by just keeping track of any cells we found that had a zero, and calling zeroRowCol() later.

    Read more…
  • Rotation Matrix

    Next up is “Rotate Matrix” which, unsurprisingly, rotates an X by X matrix by 90 degrees. There are two ways of tackling this problem, the first which is creating a new matrix and copying over each of the cells, and the second is to be able to swap elements in place. The second is harder because it means you have to iterate around the matrix with each of the values because you don’t have a separate space to put them. Let’s go over the solution which copies elements to a new matrix: def rotateMatrix(mtrx): N = len(mtrx) newMtrx = [[0 for x in range(N)] for y in range(N)] for r in range(N): for c in range(N): newMtrx[r][c] = mtrx[N-1-c][r] return newMtrx and let’s say we have a 4x4 matrix which looks like: [['A','B','C','D'], ['E','F','G','H'], ['I','J','K','L'], ['M','N','O','P']] We want to rotate that matrix so that it looks like: [['M','I','E','A'], ['N','J','F','B'], ['O','K','G','C'], ['P','L','H','D']] In rotateMatrix() we create a new blank 4x4 matrix initially filled with zeros. We then walk through each of the cells of the matrix and take each cell in each column from the bottom up. The runtime here is O(N) even though we have the two for loops because we’re only ever touching each cell once.

    Read more…
  • Run Length Encoding

    I was actually somewhat surprised that Run Length Encoding (they call it “String Compression”) was included in Cracking the Coding Interview, because it’s not particularly a difficult algorithm to write. I would have thought that writing Huffman Encoding would have been more interesting in interviews given the entire chapter on graphs and trees in the book. The key to RLE is to remember the last character as you’re iterating through the string. If the next character is different, write out the current character and append a count of the number of times you have seen it. Here’s the code: def runlength(s): counter = 0 lastChar = '' newStr = "" for currChar in s: if currChar == lastChar: counter += 1 else: if lastChar != '': newStr += lastChar + str(counter) counter = 1 lastChar = currChar newStr += lastChar + str(counter) return newStr I didn’t bother with the check for whether the returned string is shorter than the string which was passed in, however, it’s easy enough to do. But, there is a slight problem here, and I’m guessing that they’re expecting interviewers to play this up. The runtime complexity for iterating through the string is going to be O(N), but the string copy, in theory, is going to be O(N2) every time we concatenate the new string.

    Read more…
  • Happy Halloween!

    Happy Halloween everyone! To celebrate, I’ve released a new Docker Doodle! $ docker run -it --rm docker/doodle:halloween2019 A fun fact: I made the ASCII moon follow the actual phases of the moon, so in theory it should change to a “first quarter” moon on November 4th. Halloween this year gets a waxing crescent moon.

  • One Way Changes

    Next up is writing a program which can compare two strings to see if they’ve been changed by having had one character removed, one extra character inserted, or one character replaced with a different character. I tackled this by breaking it into three separate problems. I think the point of this question is to see whether you can decompose a problem into smaller steps and then see how you can glue them back together again. First up is writing the function which can remove a character from one string and see if it matches the other string. def removeChar(s1, s2): for n in range(len(s1)): if s2 == s1[:n] + s1[n+1:] return True return False This is just walking through each character of the string and then using slicing techniques to construct new possible strings. If we match our second string, return True, otherwise just return False. Next we need to check if a character was inserted into the first string. We could write a routine which adds each letter of the alphabet into each position of our first string, but that is needlessly fussy and would take a lot of time and complexity when there is a far better option.

    Read more…
  • Palindrome Permutations

    This was kind of a weird problem, but the solution was kind of fun to write. Given a string, determine if it’s a palindrome and then write out all the possible permutations of palindromes that string potentially would have. Here’s my solution: import collections import itertools def palinpermute(s): s = s.replace(" ", "") c = collections.Counter(s) pivot = '' for k, v in c.iteritems(): if v % 2 != 0: if not pivot: pivot = k else: return (False, []) newStr = "" for k, v in c.iteritems(): if k != pivot: newStr += k*(v/2) palins = list() for c in itertools.permutations(newStr): palins.append("".join(c) + pivot + "".join(reversed(c))) return (True, palins) Like a lot of the other solutions to string problems, we’re back to using the Counter again. In this case we use it to make certain that for each character, there has to be a matching one. If there isn’t a matching one, choose that character as a pivot point for our palindrome. Once we’ve selected a pivot point, there can’t be another one, so just return False and an empty list if we find one. This next part is probably not obvious: newStr = "" for k, v in c.

    Read more…
  • String Permutations

    Up next is checking whether one string is a permutation of another string. When I originally wrote my solution I was thinking the question was asking to find a permutation which is also a substring of the other string. My solution for that problem looks like: from collections import Counter def isPermutation(s1, s2): c = Counter(s1) for n in s2: c[n] -= 1 for v in c.itervalues(): if v < 0: return False return True This again makes use of a Counter from collections. I think the only real takeaway here is you should definitely clarify with the interviewer up front what’s expected by the question. In this case it would have been better to have just written: def isPermutation(s1, s2): c1 = Counter(s1) c2 = Counter(s2) return c1 == c2 Which is really just an exercise in comparing two dictionaries. Behind the scenes python is going to take O(n) to construct the two counters, but it’s unclear to me exactly how it will compare them against each other. My suspicion would be that it would compare the keys of the two dictionaries in alphabetical order, which would mean n*log(n) for runtime complexity, but you could have constructed the counter as an array of 26 or so integers for all of the lowercase characters in the string, and then compared the two arrays.

    Read more…
  • Unique Strings

    I’ve been perusing Cracking the Coding Interview lately, and thought I’d share some of my solutions to a few of the problems. If you’re planning on doing a coding interview, I’d definitely recommend attemping to come up with your own solutions, but I figured these might be useful as I wrote them in Python and the book is pretty heavy on Java. I’m actually not a huge Java fan for doing interviews. Most of the Java programmers that I’ve interviewed over the years tended to get caught up in syntax or fighting the compiler on CoderPad and things have a habit of not turning out well. I think this is exacerbated by a lot of engineers being used to writing in an IDE and then struggling with an unfamiliar interface. When I’m conducting interviews, I actually don’t really care what language a person is using, although I give the interviewee that caveat that if I don’t know the language I’m probably going to ask a lot more questions. Anyway, first up is the Unique Strings problem, which I guess is kind of like FizzBuzz. I think the point is really to just get you to warmed up to move on to more difficult problems.

    Read more…
  • Switching to Hugo

    Ever since I first created this blog I’ve had reservations about using Wordpress. It’s not that I have anything particularly against Wordpress, it’s just that as someone who is more comfortable on the command line than in a browser, I always felt a little out of my element. It also felt a bit like overkill running a small, fairly static blog with a backend database to hold all of the content, even if that database was just a tiny MariaDB instance. It was running in a docker container, but I’d neglected it for almost two years because, honestly, who really has time to pay attention to that stuff for a tiny blog with about 0.3 viewers? Plus, even that “tiny” database image was weighing in at over 400MB (side note, newer versions are down to around 100ish MBs compressed, so I guess that’s good?). All of this had been weighing on my psyche for quite some time. I’d been thinking about using Hugo for a while, but I knew converting everything over was going to be a huge pain in the neck. It got to the point where I had stopped writing blog posts because I didn’t want to use the clunky Wordpress interface and knew I’d just be compounding my misery when I finally did switch everything over.

    Read more…