Skip to content
A programming interview challenge for CancerIQ in Crystal
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
spec
src
.gitignore
.travis.yml
LICENSE
Makefile
README.md
shard.yml

README.md

This is an archive of my challenge with CancerIQ. I was allowed to use Crystal.

I didn't pass the interview. I didn't get a response until after I emailed to confirm.

Maybe I should've used Ruby & studied Big-O a little more. Maybe at a workplace censorship filters prevent googling or learning on the job.


CancerIQ Challenge

This project solves the challenge given by CancerIQ.

Usage

Compile the source and run the binary file:

  • make
  • make debug if you want a full stack trace.

You can also build it manually:

  • crystal build --release src/CancerIQ.cr -o bin/cancerIQ
  • crystal build --debug --error-trace src/CancerIQ.cr -o bin/cancerIQ

Then in order to run it:

  • bin/cancerIQ -i spec/samples/input0*.txt

Input Flags

  • -h => Print the help.
  • -b => Enable benchmarking.
  • -i => Specify input file(s).

Tests

Simply run crystal spec.

Reasoning & Benchmarks:

The Results

input00.txt  43.65k ( 22.91µs) (± 3.82%) 
---
input01.txt  21.51k ( 46.49µs) (± 8.60%) 
---
input02.txt   4.78k (209.29µs) (± 5.32%) 
---
input03.txt   2.56k (391.05µs) (± 6.97%) 
---
input04.txt   1.97k (506.34µs) (± 5.82%) 
---
input05.txt  14.69  ( 68.07ms) (± 3.79%) 
---
input_easy.txt   6.94k (144.14µs) (± 1.32%) 
---
input_hard.txt   4.17  (239.92ms) (± 1.58%) 

In the query_max function, the second pass requires finding the index of a specific node.

The original route I chose was converting NodeA's path array to a Hash, but I wondered if the conversion time could be improved.

It turns out that it's faster to iterate backwards through path until a common ancestor is found from NodeB's path.

Mapping the Array to a Hash

pathHash = {} of Int32 => Node
pathHash = path.map_with_index { |k, v| [v, k] }.to_h

index = pathHash.key(currentNode)
index = index.as(Int32)
# Reverse Array Traversal
index = 0
(path.size - 1).to(0) do |i|
  index = i
  break if currentNode.key == path[i].key
end

The benchmarks for both:

input00.txt-Hash  44.55k ( 22.45µs) (± 3.69%)  1.33× slower
input00.txt-Array  59.24k ( 16.88µs) (± 5.74%)       fastest
----------------------
input01.txt-Hash  18.18k (  55.0µs) (± 7.82%)  1.26× slower
input01.txt-Array  22.96k ( 43.55µs) (± 4.58%)       fastest
----------------------
input02.txt-Hash    3.0k ( 333.1µs) (± 6.45%)  1.60× slower
input02.txt-Array   4.81k (207.71µs) (± 2.41%)       fastest
----------------------
input03.txt-Hash   1.81k (553.33µs) (± 1.18%)  1.46× slower
input03.txt-Array   2.64k (378.93µs) (± 4.65%)       fastest
----------------------
input04.txt-Hash   1.19k (839.36µs) (± 3.71%)  1.56× slower
input04.txt-Array   1.86k (538.93µs) (± 4.00%)       fastest
----------------------
input05.txt-Hash   1.69  (591.52ms) (± 5.97%)       fastest
input05.txt-Array   1.68  (594.61ms) (± 6.16%)  1.01× slower
----------------------
input_easy.txt-Hash   3.97k (252.13µs) (± 2.76%)  1.25× slower
input_easy.txt-Array   4.97k (201.28µs) (± 5.57%)       fastest
----------------------
input_hard.txt-Hash   1.17  ( 856.0ms) (± 4.08%)  1.12× slower
input_hard.txt-Array   1.31  (762.26ms) (± 3.79%)       fastest

Big O

I'm not the best with Big O notation, so this is my reasoning and best guess.

Insertion is handled with a Hash. O(1)

The query_add function is O(N) since it iterates through its children.

The query_max function is O(Depth × 2) + O(N):

  • There are two passes (if NodeB isn't on the same subtree). Worst case each pass goes all the way to the root (1) node. O(Depth) + O(Depth)
  • In order to add the second path to the first, the index of the first common ancestor must be found by traversing the first path in reverse. O(N)

Contributors

  • azah Andrew Zah - creator, maintainer
You can’t perform that action at this time.