I can't stand developer interviews with algorithms (Or, why I'm learning APL)

=> home

I've been contacted by several HR people who are looking for a software engineer. It's good. I'm always looking for new challenges. What I can't stand is a large portion of the company decides that they should test the candidate's algorithm skill. Sorry, what? You just said you want to hire a senior GPU developer. Instead of interviewing with actual related domain knowledge and writing code that runs on the GPU. You decided if I want the potision, I should spend time on LeetCode and write algorithm questions. You are waisting my time. And so I'll have my revenge.

Before that, let me have my quick rant about interviews I don't get why so many companies think it's a good idea to interview with algorithms. I've seen web devs, backend, App, even some system programer occupations's test for algorithm skill. I undestand that you need to keep the code clean and fast. Algorithms (especially the big-O notation) is a super important knowledge. But I've also seen company (ex G**gle) that treats cache and SIMD optmization as a bad thing in their interview. And take my attempt at improving memory access pattern as goofing around. These companies should be looking for top talent engineers. But their interview is a joke that a CS graduate, with some sturbness can pass.

Furthermore, I think it's more ideal to just test them with actuall problems you might face in works. Heck if that's too hard, just ask them to read some code in realted field and tell you what is it doing. And even potential ways to optimize it. Reading is 10x faster than writing. And the participant don't need to spend percious interview time on debugging some stupid mistyped index. If thay can't understand the code, they probably isn't fit for the job anyways.

The industry seriously need a new process to actually hire good devs.

Entering APL

For the companies that's wasting my time. In the future, i.e. if I encounter any company that uses algorithms as interview questions, I won't turn down the interview. Instead I'll do the entire interview in APL. So wasting your time too (and I've fun messing around).

APL is a (arguably) failed attempt at creating a daily and concise language. It was create way back in 1962 when people are using room sized mainframes and coding with teletype. So APL is desgiend to be very dense so not to take up much time printing on a teletype. And be efficiently transfered in very low bandwidth. But that also caused APL to earn it's rightful place in the Esoteric Programming Language Wiki[1].

=> [1]: EsoLang Wiki's APL entry

For some first impression. I'll be solving LeetCode #1342[2] in both C++ and APL. The problem is simple, given the number n. How many times the following rule has to be applied to get the number 0? And the rule is. a) if n is even, n is divided by 2. b) if n is odd, n is decremented by 1. The solution in C++ is quite stright forward.

auto solve(int n, int depth=0) -> int {
    if(n == 0) return depth;
    if(n % 2 == 0) return solve(n / 2, depth + 1);
    return solve(n - 1, depth + 1);
}
print("solve(14) = %d\n", solve(14));
// > solve(14) = 6

The APL version is much more cryptic. I won't go into detail of how it works. But you see all the non-ASCII characters. Yes, those are APL operators. They are a part of the language itself.

    solve2 ← {(2|⍵)=0 : ⍺+1 solve ⍵÷2 ⋄ 1 : ⍺+1 solve ⍵-1}
    solve ← {⍵=0 : ⍺ ⋄ 1 : ⍺ solve2 ⍵}
    solution ← {0 solve ⍵}
    solution 14

6

=> LeetCode 1342[2] - Number of Steps to Reduce a Number to Zero

Or the classic FizzBuzz

    n ← 15
    {(⍵ 'Fizz' 'Buzz' 'FizzBuzz')[1+((3|⍵)=0)+(2×(5|⍵)=0)]}¨⍳n

1 2   Fizz   4   Buzz    Fizz   7 8   Fizz    Buzz   11   Fizz   13 14   FizzBuzz 

Sudoku in APL

Ok, solving FizzBuzz isn't going to land me any job. Let's solve a hard problem shall we.. How about LeetCode #37 - Sudoku Solver[3]? I ain't good enough at APL yet to come up with a complete solution. I ended understanding the algorithm by Dyalog[4].

=> [3]: Dyalog's Sudoku Solver | [4]: LeetCode 37 - Sudoku Solver

    skgrid ← {⍵⌿ ⍵/ ⍵ ⍵ ⍴⍳⍵*2}
    idxs ← {(⍳ ⍵), ¨skgrid ⊃⍵*÷2}
    relation ← {⊂[⍳⍴⍴⍵]1 ∊¨ ⍵ ∘.= ⍵}
    possibe ← {(⍳⊃⍴⍵) ~ ⍵ × ⊃⍺ ⌷ relation idxs ⍴⍵}
    at ← {⍵+(⍴⍵) ↑ (-⍺⍺)↑⍺}
    replace ← {(⍺ possibe ⍵) (⍺ at)¨ ⊂⍵}
    pvex ← {⊃, /⍺∘replace¨⍵}
    emt ← {(,⍵=0)/ ,⍳⍴⍵}
    solve ← {⊃pvex/(emt ⍵), ⊂⊂⍵}

The algorithm is stright forward to understand. It generates a set of indices for each Sudoku cell, which row, column and block. Then generate a relations map for each cell, which denotes the area that can't share the same number. Then generate possible numbers for each empty cell. Apply possible numbers and DFS until a solution is found. We can dump LeetCode's example data into it

      s99 ← 9 9 ⍴ 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9
      solve s99

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

I don't know how to end this post. Well, bye and f all the companies wasting my time.