index.html (179591, 2018-07-28)
theme.setup (728, 2018-07-28)
# -*- org-export-use-babel: nil; after-save-hook: org-html-export-to-html; -*-
#+TITLE: Elements of Programming Interviews: Solutions
#+AUTHOR: Jonathan Jin
#+TODO: TODO(t) | WRITTEN(w) PSEUDOCODE(c) DONE(d) LOOKED-UP(l)
#+OPTIONS: tags:nil H:4
#+EXPORT_FILE_NAME: index
#+SETUPFILE: theme.setup
* Foreward
All problems presented here are from [[http://elementsofprogramminginterviews.com/][Elements of Programming Interviews]], by
Dr. Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. All credit goes to them.
All solutions presented are my own.
* Data Structures and Algorithms
** Primitive Types
*** DONE Computing the parity of a word :C0:
CLOSED: [2017-06-21 Wed 00:44]
#+BEGIN_QUOTE
The parity of a binary word is 1 if the number of 1s in the word is odd;
otherwise, it is 0. For example, the parity of 1011 is 1, and the parity of
10001000 is 0. Parity checks are used to detect single bit errors in data
storage and communication. It is fairly straightforward to write code that
computes the parity of a single ***-bit word
#+END_QUOTE
We assume that the word is provided as a ***-bit unsigned integer.
A naive implementation would be to iterate through every bit of the word,
XOR-ing a counter for every 1-bit.
#+BEGIN_SRC python :results silent :session
def parity(word):
p = 0
for shift in range(0,***):
p ^= (word>>shift)&1
return p
#+END_SRC
#+BEGIN_SRC python :results value :session
all([parity(int(w,2))==p for w,p in [
("1011", 1),
("0000", 0),
]])
#+END_SRC
#+RESULTS:
: True
This implementation is O(n), where n is the length of the input word.
We can, however, optimize this function further by precomputing the
parities of words and storing the parities in a lookup table. For
illustration's purpose, we'll define a lookup table that stores the
parities of all words of length 2:
#+BEGIN_SRC python :results none :session
PARITIES_2 = {
int(w,2): p for w,p in [
("00", 0),
("01", 1),
("10", 1),
("11", 0),
]
}
#+END_SRC
Resulting in the following implementation:
#+BEGIN_SRC python :results none :session
def memoized_parity(word):
p = 0
memo_word_length = 2
for s in range(0,***/memo_word_length):
mask = 2^memo_word_length - 1
shift = s * memo_word_length
p ^= PARITIES_2[(word >> shift) & mask]
return p
#+END_SRC
#+BEGIN_SRC python :results value :session
all([memoized_parity(int(w,2))==p for w,p in [
("1011", 1),
("0000", 0),
]])
#+END_SRC
#+RESULTS:
: True
This revised implementation is O(n/w) = O(n), where w is the word length of
the lookup key.
*** TODO Compute x^{y} :C1:
#+BEGIN_QUOTE
Compute x^{y} without using arithmetic operators, i.e. using only assignment,
bitwise operators, and equality checks.
#+END_QUOTE
** Arrays
*** TODO The Dutch national flag problem :C0:
Write a program that takes an array A and an index i into A, and rearranges
the elements such that all elements less than A[i] (the "pivot") appear
first, followed by eleents equal to the pivot followed by elements greater
than the pivot.
/Hint/: Think about the partition step in quicksort.
**** Solution
*** DONE Sample offline data :C1:
CLOSED: [2017-06-27 Tue 00:00]
Implement an algorithm that takes as input an array of distinct elements and
a size, and returns a subset of the given size of the array elements. All
subsets should be equally likely.
**** Solution
We can use reservoir sampling to achieve a linear-time implementation.
#+BEGIN_SRC python :results output :session
def sample(N, l):
from random import randint
reservoir = [N[i] for i in range(0, l)]
for i in range(l, len(N)):
_i = randint(0, i)
if _i < l:
reservoir[_i] = N[i]
return reservoir
#+END_SRC
*** DONE Sample online data
CLOSED: [2017-06-27 Tue 00:00]
Design a program that takes as input a size k, and reads packets,
continuously maintaining a uniform random subset of size k of the read
packets.
**** Solution
Analogous to solution outlined in "Sample offline data."
*** DONE Compute the spiral ordering of a 2D array :C1:
CLOSED: [2018-04-30 Mon 23:18]
#+BEGIN_SRC python
def spiral(mtx):
bounds = {
"top": -1,
"bottom": len(mtx),
"left": -1,
"right": len(mtx[0]),
}
actions = {
"left": {
"update": (lambda i,j: (i,j-1)),
"within": lambda i,j: j>bounds["left"],
"next": "up",
},
"right": {
"update": (lambda i,j: (i,j+1)),
"within": lambda i,j: j
bounds["top"],
"next": "right",
},
"down": {
"update": (lambda i,j: (i+1,j)),
"within": lambda i,j: i=. The maximum profit
that can be made with one buy and one sell is 30 -- buy at 260 and sell
at 290. Note that 260 is not the lowest price, nor 290 the highest price.
Write a program that takes an array denoting the daily stock price, and
returns the maximum profit that could be made by buying and then selling one
share of that stock.
**** Solution
Note that this problem is a simplification of the knapsack problem. A naive
solution would reduce this problem to its inspiration, giving us a O(n^{2})
solution. However, we note that the problem doesn't ask for exactly
*which* stocks to buy and sell for maximum profit -- only the profit
amount. This simplification means that we do not need the comprehensive
bookkeeping that a DP-based solution to the knapsack problem provides us.
We first note that a lower buying price always results in a higher profit
with the same selling price.
We can then implement a O(n) solution that compares the "current profit" --
defined as difference between the current sell-price under consideration
and the as-yet-seen lowest buy price, with a rolling maximum of that
value. Every time we see a value less than the as-yet-seen lowest buy
price, we update accordingly. Once we reach the end of the list, we return
the rolling max value.
#+BEGIN_SRC python :results silent :session
def max_profit(*args):
min_so_far = args[0]
profit = 0
for p in args:
profit = max(profit, p - min_so_far)
if p < min_so_far:
min_so_far = p
return profit
#+END_SRC
#+BEGIN_SRC python :results value :session
max_profit(310,315,275,295,260,270,290,230,255,250) == 30
#+END_SRC
#+RESULTS:
: True
** Strings
*** DONE Interconvert strings and integers :C0:
CLOSED: [2017-06-26 Mon 22:08]
Implement string/integer inter-conversion functions.
**** Solution
#+BEGIN_SRC python :results silent :session
def stoi(s):
i = 0
for c in s:
i = 10 * i + ord(c) - ord("0")
return i
#+END_SRC
#+BEGIN_SRC python :results value :session
all([
stoi("123") == 123,
stoi("0") == 0,
stoi("***7654321***") == ***7654321***,
])
#+END_SRC
#+RESULTS:
: True
#+BEGIN_SRC python :results silent :session
def itos(i):
import math
s = ""
while True:
s += chr(ord("0") + i % 10)
i = int(math.floor(i / 10))
if i == 0:
break
return s[::-1]
#+END_SRC
#+BEGIN_SRC python :results value :session
all([
itos(123) == "123",
itos(0) == "0",
itos(***7654321***) == "***7654321***",
])
#+END_SRC
#+RESULTS:
: True
*** TODO Base conversion :C1:
In the decimal number system, the position of a digit is used to signify the
power of 10 that digit is to be multiplied with. For example, "314" denotes
the number 3 * 100 + 1 * 10 + 4 * 1. The base b number system generalizes
the decimal number system: the string "a_{k-1}a_{k-2}...a_{1}a_{1}", where 0 \leq a_i \leq
b, denotes in base-b the integer a_0 \times b^{0} + a_1 \times b^{1} + a_2 \times
b^{2} + ... + a_{k-1} \times b^{k-1}.
Write a program that performs base conversion. The input is a string, an
integer b_1, and another integer b_2. The string represents an integer in base
b_1. The output should be the string representing the integer in base
b_2. Assume 2 \leq b_1, b_2 \leq 16. Use "A" to represent 10, "B" for 11, ..., and
"F" for 15. (For example, if the string is "615", b_1 is 7 and b_2 is 13, then
the result should be "1A7", since 6 \times 7^{2} + 1 \times 7 + 5 = 1 \times 13^{2} + 10 \times 13 + 7).
*** TODO Replace and remove :C1:
Consider the following two rules that are to be applied to an array of
characters.
- Replace each "a" by two "d"s.
- Delete each entry containing a "b".
For example, applying these rules to the array == results in
the array ==.
Write a program which takes as input an array of characters, and removes
each "b" and replaces each "a" by two "d"s. Specifically, along with the
array, you are provided an integer-valued size. Size denotes the number of
entries of the array that the operation is to be applied to. You do not
have to worry about preserving subsequent entries. For example, if the array
is == and the size is 4, then you can return ==. You
can assume there is enough space in the array to hold the final result.
*** DONE Test palindromicity :C2:
CLOSED: [2017-07-05 Wed 11:18]
For the purpose of this problem, define a palindromic string to be a string
which when all the nonalphanumeric are removed it reads the same front to
back ignoring case.
Implement a function which takes as input a string s and returns true if s
is a palindromic string.
**** Solution
Use two cursors; one that starts at start of string, and one at the end.
Each step, perform equality comparison of the chars under each, returning
early with False if equality does not hold. Continue until i_{s} > i_{e}
and return True if reach end of iteration.
Time O(n) and space O(1).
#+BEGIN_SRC python :results output :session
def is_pal(S):
i_s, i_e = 0, len(S) - 1
while i_s < i_e:
if S[i_s].lower() != S[i_e].lower():
return False
i_s += 1
i_e -= 1
while not S[i_s].isalnum() and i_s < i_e:
i_s += 1
while not S[i_e].isalnum() and i_s < i_e:
i_e -= 1
return True
#+END_SRC
#+RESULTS:
#+BEGIN_SRC python :results value :session
all([
is_pal("A man, a plan, a canal, Panama"),
not is_pal(",,a,b,,"),
])
#+END_SRC
#+RESULTS:
: True
*** DONE Compute all mnemonics for a phone number :C3:
CLOSED: [2017-07-05 Wed 11:36]
Write a program which takes as input a phone number, specified as a string
of digits, and returns all possible character sequences that correspond to
the phone nuber. The cell phone keypad is specified by a mapping that takes
a digit and returns the corresponding set of characters. The character
sequencs do not have to be legal words or phrases.
**** Solution
We maintain a static mapping from digits to sets of characters and use
recursion to generate the power set of each digits' set.
Complexity O(4^{n}), since each recursion step "fans out" at most four times
(due to keypad mapping).
#+BEGIN_SRC python :results output :session
def mnemonics(S):
MAP = {
"0": ["0"],
"1": ["1"],
"2": set("abc"),
"3": set("def"),
"4": set("ghi"),
"5": set("jkl"),
"6": set("mno"),
"7": set("pqrs"),
"8": set("tuv"),
"9": set("wxyz"),
}
if S == "":
return []
elif S[0] not in MAP:
raise Exception
return set([c+t for c in MAP[S[0]] for t in mnemonics(S[1:])])
#+END_SRC
#+BEGIN_SRC python :results value :session
all([
mnemonics("2276696") | { "ACRONYM", "ABPOMZN" },
])
#+END_SRC
#+RESULTS:
: True
** Linked Lists
*** DONE Merge two sorted lists :C0:
CLOSED: [2017-06-21 Wed 12:53]
Write a program that takes two lists, assumed to be sorted, and returns
their merge. The only field your program can change in a node is its =next=
field.
/Hint/: Two sorted arrays can be merged using two indices. For lists, take
care when one iterator reaches the end.
**** Solution
We describe a solution that completes the task in linear time and constant
space.
Call input lists =A= and =B=.
We decide on the head of the return list with respect to comparison. We
save a reference =H= to this head for final return; in the meantime, we
create an additional "work-in-progress" reference =l= that we will use to
iteratively wire up the return value.
While neither =A= nor =B= have reached their ends, we compare the head
values of each; whichever is less than or equal to the other, becomes the
new target for =l.next=. We then increment both the assignee and =l= to
their next links.
Once one of =A= or =B= have reached their end, we treat the other as the
"remainder" list. Since the two input lists are given to be sorted, we have
the invariant that every element in the remainder is greater than or equal
to the current =l=. As such, we assign =l.next = remainder=.
For this solution's purpose, we define a lightweight linked-list API as
follows:
#+BEGIN_SRC python :results silent :session
class LL():
def __init__(self, v):
self.v = v
self.next = None
def append(self, l):
self.next = l
return self
def __eq__(self,l):
me = self
while me is not None and l is not None:
if me.v != l.v:
return False
me = me.next
l = l.next
return me is None and l is None
#+END_SRC
Our solution is as follows:
#+BEGIN_SRC python :results silent :session
def merge(A,B):
if A is None:
return B
if B is None:
return A
if A.v < B.v:
head = A
A = A.next
else:
head = B
B = B.next
l = head # wip tracker
cursors = { "A": A, "B": B }
while cursors["A"] is not None and cursors["B"] is not None:
k_next = "A" if cursors["A"].v < cursors["B"].v else "B"
l.next = cursors[k_next]
l = l.next
cursors[k_next] = cursors[k_next].next
l.next = cursors["A"] if cursors["A"] is not None else cursors["B"]
return head
#+END_SRC
#+BEGIN_SRC python :results value :session
all([
# base cases
merge(None,None) == None,
merge(None, LL(1).append(LL(2))) == LL(1).append(LL(2)),
merge(LL(1).append(LL(3)), None) == LL(1).append(LL(3)),
# "normal" case
merge(
LL(1).append(LL(3).append(LL(5))),
LL(2).append(LL(4).append(LL(6))),
) == LL(1).append(LL(2).append(LL(3).append(LL(4).append(LL(5).append(LL(6)))))),
# remainder case
merge(
LL(1).append(LL(5)),
LL(2).append(LL(6).append(LL(10))),
) == LL(1).append(LL(2).append(LL(5).append(LL(6).append(LL(10))))),
])
#+END_SRC
#+RESULTS:
: True
*** DONE Reverse a singly linked list :C1:
CLOSED: [2017-06-27 Tue 13:07]
**** Solution
#+BEGIN_SRC python :results output :session
class LL():
def __init__(self, v):
self.v = v
self.next = None
def append(self, l):
self.next = l
return self
def __eq__(self,l):
me = self
while me is not None and l is not None:
if me.v != l.v:
... ...