## Elements of Programming Interviews

This is an index to the problems from THE book being solved in haskell (and counting). Some of the trivial ones will only be attempted on demand!

## Chapter 5 – Primitive Types

EPI 5.1: Find the number of bits set in a number (and Parity)

EPI 5.4: Closest integers with the same weight

EPI 5.5 – Generating Power Sets

EPI 5.6 String to Integer inter conversion functions

EPI 5.7 – Generalised conversion between bases

EPI 5.8 – Spreadsheet Column Encoding

EPI 5.9 – Elias encoding and decoding

EPI 5.10 – Greatest Common Divisor

## Chapter 6 – Strings and Arrays

EPI 6.1 Dutch Flag Partition

EPI 6.3 – Max Difference

EPI 6.4 – Generalized Max Difference

EPI 6.5 – Subset summing to 0 mod n

EPI 6.6 – Longest contiguous increasing subarray

EPI 6.13 – Rotating an array

EPI 6.15 – Printing a 2D array in spiral order

EPI 6.18 – Run-Length Encoding

EPI 6.19 – Reversing words in a string

## EPI 6.18 – Run-length Encoding

Problem:

Implement functions to run length encode a string and decode the RLE value of an encoded string.

For example “aaaabcccaa” should be encoded to “4a1b3c2a”, while “3e4f2e” would be decoded to “eeeffffee”.

Solution:

Encoding is straight forward:

```run_length_encode :: [Char] -> [Char]
run_length_encode xs = run_length_encode' 0 '|' xs
where
run_length_encode' 0 _ [] = []
run_length_encode' 0 _ (x:xs) = run_length_encode' 1 x xs
run_length_encode' count curr_ch [] = (show count) ++ [curr_ch]
run_length_encode' count curr_ch (x:xs)
| curr_ch == x = run_length_encode' (count + 1) curr_ch xs
| otherwise = (show count) ++ [curr_ch] ++ run_length_encode' 1 x xs
```

Decoding is also fairly straightforward, except we just need to accumulate the “count” before that many characters can be output:

```run_length_decode :: [Char] -> [Char]
run_length_decode xs = run_length_decode' 0 xs
where
run_length_decode' _ [] = []
run_length_decode' count (x:xs)
| isDigit x = run_length_decode' ((count * 10) + (digitToInt x)) xs
| otherwise = (replicate count x) ++ run_length_decode' 0 xs
```

## EPI 6.15 – Printing a 2D array in spiral order

Problem:

Given an nxm 2D array of integers, print it in spiral order.

Eg for a 3×3 matrix (with the following implicit values):

 1 2 3 4 5 6 7 8 9

Would be printed as “1 2 3 6 9 8 7 4 5″

Solution:

The straight forward solution is to have 4 iterations, and in each iteration to print one of the two directions (horizontal and vertical) alternatively.

However a more intuitive solution is to use vectors to create a tour starting from the index (0,0) and incrementing the next point based on the current direction and position.

First we create the concept of directions along with a couple of helper functions:

```data Direction = North | East | South | West
-- Return the clockwise direction of a given direction
clockwise_of North = East
clockwise_of East = South
clockwise_of South = West
clockwise_of West = North

-- Returns the vector representing the direction
vector_of North = (0, -1)
vector_of South = (0, 1)
vector_of East = (1, 0)
vector_of West = (-1, 0)

-- The primary coordinate that will be updated when traversing in a particular direction
primary_coord North = 1
primary_coord South = 1
primary_coord East = 0
primary_coord West = 0

-- Given a direction and point, returns the next and previous points in the direction.
next_pt dir (x,y) = ((x + fst (vector_of dir)),(y + snd (vector_of dir)))
prev_pt dir (x,y) = ((x - fst (vector_of dir)),(y - snd (vector_of dir)))

```

Now we simply use the above helpers to start and iterate through a tour:

```print_spirally width height = print_spirally' East (0,0) 0 [width, height]
where
print_spirally' dir (x,y) t [w,h]
| w == 0 || h == 0 = []
| t < [w,h] !! curr_coord = (y * width + x + 1) : print_spirally' dir (next_pt dir (x,y)) (t+1) [w,h]
| otherwise = print_spirally' next_dir (next_pt next_dir (prev_pt dir (x,y))) 0 [next_w,next_h]
where
curr_coord = primary_coord dir
dir_vector = vector_of dir
next_dir = clockwise_of dir
next_dir_vector = vector_of next_dir
next_w = w - (abs (fst next_dir_vector))
next_h = h - (abs (snd next_dir_vector))
```

Couple of things to note:

* w,h represent the “remaining” width and height in the spiral as each time there is a change in direction, the available coordinate size reduces by one (height if beginning vertically, width if beginning horizontally).
* t is the number of values printed in a given direction (when this value reaches “w” or “h” depending on the direction, direction is rotated and t is reset to 0).
* When the direction needs to change (in the otherwise) the “current” point is one beyond the last point in the direction. For this reason the next point is evaluted from the previous direction in the previous point.

## EPI 6.13 – Rotate an array

Problem:

Given an Array of n elements, design an algorithm for rotating an Array right by i positions. Only O(1) additional storage is allowed.

Solution:

The natural solution is to start from position the value at index k to k + i, repeatedly n times. This will work well if GCD(n,i) is != 1. However a general solution is to perform m jumps of size i, l times, but each time starting from the next index.

The first helper function is to perform m jumps of “size” each starting from a given index, wrapping around if necessary. For example if A = [1,2,3,4,5,6,7,8,9,10],

`m_rotations A 0 3 3`

would cause the following jumps: 1 -> 4 -> 7, with A resulting in:

```[1, 2, 3, 1, 5, 6, 4, 8, 9, 10]
```
```m_rotations xs index size m = elems (m_rotations' (arrayFromList xs 0) index (xs!!index) size m)
where
len = length xs
m_rotations' arr curr_index curr_value size numleft
| curr_index < 0 || size <= 0 || numleft <= 0 = arr
| otherwise = m_rotations' (arr // [(next_index, curr_value)]) next_index next_value size (numleft - 1)
where
next_index = mod (curr_index + size) len
next_value = arr!next_index
```

Now we create the actual rotator method that calls m_rotations k times, where k = gcd(|A|, j).

This is:

```rotate_array xs j = rotate_array' xs 0
where
lxs = length xs
j' = mod j lxs
gcd_lxs_j = greatest_common_divisor lxs j'
numtimes = div lxs gcd_lxs_j
rotate_array' xs start_index
| start_index >= gcd_lxs_j = xs
| otherwise = m_rotations ys (j' - (start_index + 1)) j' numtimes
where
ys = rotate_array' xs (start_index + 1)
```

A simpler algorithm to perform this is very similar to reversing words in a sentence:

```rotate_array_simple xs j = reverse (take j rxs) ++ reverse (drop j rxs)
where rxs = reverse xs
```

## EPI 5.10 – Greatest Common Divisor

Problem:

Design an algorithm for computing the GCD of two numbers without using multiplication, division or the modulus operator.

Solution:
The GCD of two numbers can be computed by recursively subtracting the smaller number from the larger until one of the numbers is 0, at which point the non-zero value is the GCD.

However this can be improved by “quickly” eliminating factors of two (by inspecting the least significant bits) and doubling and halving values (via left and right shifting by 1 respectively).

```greatest_common_divisor x 0 = x
greatest_common_divisor 0 y = y
greatest_common_divisor x y
| x_is_even && y_is_even = 2 * greatest_common_divisor (x `shiftR` 1) (y `shiftR` 1)
| x_is_odd && y_is_even = greatest_common_divisor x (y `shiftR` 1)
| x_is_even && y_is_odd = greatest_common_divisor (x `shiftR` 1) y
| x  y = greatest_common_divisor (x - y) x
| otherwise = x
where
x_is_even = (x .&. 1) == 0
y_is_even = (y .&. 1) == 0
x_is_odd = not x_is_even
y_is_odd = not y_is_even
```

## EPI 6.6 – Longest contiguous increasing subarray

Problem

An array is increasing if each element is less than its succeeding element except for the last element.

Given an array A of n elements return the beginning and ending indices of a longest increasing subarray of A.

Solution

Let S[i] be the longest increasing subarray between the indexes (0,i – 1).
Then

S[i] = a,b if A[i] > A[i – 1],
i,i otherwise
where a,b = S[i – 1]

```longest_contig_inc_subarray :: (Ord a) => [a] -> (Int, Int)
longest_contig_inc_subarray [] = (-1, -1)
longest_contig_inc_subarray (x:xs) = longest_contig_inc_subarray' (0, x, 0, x) xs
where
longest_contig_inc_subarray' (i,ai,j,aj) [] = (i,j)
longest_contig_inc_subarray' (i,ai,j,aj) (x:xs)
| x >= aj = longest_contig_inc_subarray' (i,ai,j + 1,x) xs
| otherwise = longest_contig_inc_subarray' (j + 1,x,j + 1,x) xs
```

A heuristic to improve the best case complexity (but does nothing in the worst case) is to realise that if the length of the longest subarray till i is L (and A[i + 1] < A[i] – indicating an end of the longest subarray), then a larger increasing subarray must contain *atleast* L elements. So we only need to start with L items in front and check backwards.

The code for this is (here the start index and the length of the subarray are returned instead):

```

-- Returns the size of the largest increasing "prefix" in an array
largest_inc_prefix [] = 0
largest_inc_prefix (x:[]) = 1
largest_inc_prefix (x:y:xs)
| x = y = 1 + largest_dec_prefix (y:xs)
| otherwise = 1

-- Returns the size of the largest decreasing "prefix" in an array
largest_dec_prefix [] = 0
largest_dec_prefix (x:[]) = 1
largest_dec_prefix (x:y:xs)
| x >= y = 1 + largest_dec_prefix (y:xs)
| otherwise = 1

lcisa :: (Ord a) => [a] -> (Int, Int)
lcisa [] = (-1,-1)
lcisa xs = lcisa' (0,1) 0 xs
where
lcisa' (start,maxlen) i [] = (start,maxlen)
lcisa' (start,maxlen) i xs
| nextlen > maxlen = lcisa' nextbest
(i + maxlen + inc_prefix)
(drop inc_prefix rest)
| otherwise = lcisa' (start,maxlen) (i + maxlen) rest
where
first_l = take maxlen xs
rest = drop maxlen xs
dec_prefix = largest_dec_prefix (reverse first_l)
inc_prefix = largest_inc_prefix rest
nextlen = inc_prefix + dec_prefix
nextbest = (i + maxlen - dec_prefix, nextlen)
```

## EPI 6.19 – Reversing words in a sentence

Problem

Reverse the words in a sentence.

Solution

We can define a word as any substring separated by one or more spaces. To do this on constant space, simply reverse the entire sentence, and then reverse each word within.

In haskell, the recursive solution would be:

```reverse_words :: [Char] -> [Char]
reverse_words [] = []
reverse_words xs = initial_spaces ++ (reverse after_spaces) ++ reverse_words remaining
where
initial_spaces = takeWhile isSpace xs
spaces_dropped = dropWhile isSpace xs
after_spaces = takeWhile (\x -> not (isSpace x)) spaces_dropped
remaining = drop (length after_spaces) spaces_dropped
```

This is clearly not O(1) in space usage. The constant space solution would require maintaining array structures and swapping entries within the array.