Skip to content

Instantly share code, notes, and snippets.

@bmershon
Last active June 16, 2017 05:58
Show Gist options
  • Save bmershon/b51d7a52967424c3defcc0199e68383f to your computer and use it in GitHub Desktop.
Save bmershon/b51d7a52967424c3defcc0199e68383f to your computer and use it in GitHub Desktop.
How to be Annoying During a Coding Interview

Problem 1

You are given a string of the form 101?01?110?0001 where the "?" characters are unknown digits in a string representing a binary number. For example, the string 101 represents the number 5 and the string 11101 represents the number 29. You are instructed to print out all the possible numbers that this special string with "?" characters might represent. Each "?" is either a 0 or 1 digit. The string 1?1 would require you to print both 5 and 7, as either of those numbers could be represented by 1?1.

Choose a programming language you are comfortable using.

...

"Hmm, is it okay if I use Scheme? I mean it's basically just Lisp. How much do you use Scheme here?"

...

"Do you mind if I omit some parentheses on the whiteboard?"

...

"Actually, would it be ok to use a macro? Maybe I could make an expander with two provided functions that..."

...

"You said 15 minutes, right?"

...

"Sorry okay wait, yeah, those parenths match with these and that one matches with..."

#lang racket

; Prints all numbers that could be represented by strings of the form:
; 1001?01?11 where the ? characters indicate unknown binary digits.
(define combinations
  (lambda (x)
    (print "" x)))

;; Print all combinations, using prefix and suffix
;; arguments to process the string with unknown digits.
(define print
  (lambda (prefix suffix)
    (cond
      ((zero? (string-length suffix)) (displayln (binary->decimal prefix)))
      ((equal? (substring suffix 0 1) "?")
       (begin
         (print (string-append prefix "0") (substring suffix 1))
         (print (string-append prefix "1") (substring suffix 1))))
       (else (print (string-append prefix (substring suffix 0 1)) (substring suffix 1))))))

; Returns the number represented by the binary number
; in the given string of 1's and 0's.
(define binary->decimal
  (lambda (b)
    (cond
      ((zero? (string-length b)) 0)
      ((equal? (substring b 0 1) "1")
       (+ (/ (expt 2 (string-length b)) 2) (binary->decimal (substring b 1))))
      (else (binary->decimal (substring b 1))))))

; Test binary to decimal.
(binary->decimal "100101") ;; 37
(binary->decimal "101") ;; 5
                
; Test printing combinations
(combinations "10?01?001?11")
;; 2191
;; 2251
;; 2255
;; 2699
;; 2703
;; 2763
;; 2767
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment