Posts Tagged ‘interview’

Programming Praxis – First Unrepeated Character In A String

April 30, 2013

In today’s Programming Praxis exercise, our goal is to find the find the first unrepeated character in a string, along with its index. Let’s get started, shall we?

import Data.Maybe
import Data.List

We traverse the list from right to left, keeping a list of characters we’ve already encountered and a list of possible options. When we check a character, we first check if it’s in the list of duplicate characters. If not, we then check the list of options. If the letter in question is there already, we remove it from the list of options and add it to the list of duplicates. Otherwise, we add the current character to the list of options. At the end, we return the first unique element (if any).

unrepeated :: String -> Maybe (Integer, Char)
unrepeated = listToMaybe . snd . foldr f ([], []) . zip [0..] where
    f (i,c) (ds,us) = if elem c ds then (ds, us) else
        maybe (ds, (i,c):us) (\(fi,fc) -> (fc:ds, delete (fi,fc) us)) $
        find ((== c) . snd) us

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ unrepeated "aaabc"       == Just (3, 'b')
          print $ unrepeated "aaabbbcddd"  == Just (6, 'c')
          print $ unrepeated "aaaebbbcddd" == Just (3, 'e')
          print $ unrepeated "aabbcc"      == Nothing
          print $ unrepeated "aba"         == Just (1, 'b')

Programming Praxis – Amazon Interview Question

November 27, 2012

In today’s Programming Praxis exercise, our goal is to find the 100 points closest to (0, 0) out of a list of 1000000 random points in O(n). Let’s get started, shall we?

Some imports:

import Control.Applicative
import qualified Data.IntMap as I
import System.Random

The obvious solution is to simply sort the list and take the first 100 elements. Sorting, however, usually takes O(n log n), which is not allowed. Fortunately, by using the square of the distance rather than the distance we not only save a million square root operations, but it also makes the value we’re sorting by an integer, which allows us to use an IntMap that has O(1) insertion and thus O(n) sorting.

closest :: Int -> [(Int, Int)] -> [(Int, Int)]
closest n = take n . concat . I.elems . I.fromListWith (flip (++)) .
            map (\(x,y) -> (x*x+y*y, [(x,y)]))

To test, we need a million random points.

points :: IO [(Int, Int)]
points = take 1000000 <$> liftA2 zip (randomRs (-1000, 1000) <$> newStdGen)
                                     (randomRs (-1000, 1000) <$> newStdGen)

Finally we run the algorithm.

main :: IO ()
main = print . closest 100 =<< points

To see whether our algorithm is truly linear, let’s look at some timings:

1 million: 2.9 s
2 million: 5.7 s
4 million: 11.6 s
8 million: 23.8 s

Looks fairly linear to me.

Programming Praxis – Reverse Words

March 8, 2011

In today’s Programming Praxis exercise, we’re revisiting the well-known interviewing problem of reversing the words in a string. This time, we have to do the reversal in place and without using any library functions for determining the words. Let’s get started, shall we?

Haskell doesn’t do much in the way of in-place modifications by default. Attempting to modify a string (or indeed the majority of all data structures) will create a copy of it (though part of the new one may refer to same memory occupied by the original). I figured the closest thing to modifying the string in place would be to turn it into a mutable array. It’s not entirely in-place since we still have to convert to and from the array, but it’s the closest we’re going to get.

import Data.Array.IO

We start with a function to switch to characters in a string.

switch :: (MArray a e m, Ix i) => i -> i -> a i e -> m ()
switch i j a = do x <- readArray a i
                  writeArray a i =<< readArray a j
                  writeArray a j x

Next, we make a function to reverse part of a string.

revRange :: Int -> Int -> IOArray Int a -> IO (IOArray Int a)
revRange i j a = mapM_ (\n -> switch n (j+i-n) a) [i..div (i+j) 2] >> return a

The algorithm for reversing the words in a string is the same as in the Scheme version: reverse the entire string, then reverse the individual words.

reverseWords :: String -> IO String
reverseWords xs = do a <- newListArray (0, length xs - 1) xs
                     (s,e) <- getBounds a
                     f 0 e =<< revRange s e a where
    f i e a = if i > e then getElems a else nextSpace i e a >>=
                 \s -> f (s+1) e =<< revRange i (s-1) a
    nextSpace i e a = if i > e then return i else readArray a i >>= \c ->
                      if c == ' ' then return i else nextSpace (i+1) e a

Let’s see if everything is working properly:

main :: IO ()
main = do let a =? b = print . (== b) =<< reverseWords a
          "" =? ""
          " " =? " "
          "  " =? "  "
          "hello" =? "hello"
          "hello " =? " hello"
          " hello" =? "hello "
          "the quick brown fox" =? "fox brown quick the"
          "the quick  brown fox" =? "fox brown  quick the"
          "the quick  brown 42 fox!" =? "fox! 42 brown  quick the"

Yup. Having to do things in place does make the code a lot longer than the original solution though.

Programming Praxis – String Subsets

November 23, 2010

In today’s Programming Praxis exercise,we have to write functions to determine if one string is a subset of another as if we were in an interview. Let’s get started, shall we?

First, some imports.

import Data.List
import qualified Data.Map as M
import qualified Data.IntMap as I

My first attempt doesn’t actually work, since the intersect function only checks whether an element is a member of the second list. It doesn’t keep track of duplicates.

subsetOf1 :: Eq a => [a] -> [a] -> Bool
subsetOf1 xs ys = intersect xs ys == xs

Since a call to a library function won’t suffice, we’ll have to whip up something ourselves. The obvious way is to get a count of all the characters in both strings and check if the second string has an equal or higher count for all the characters in the first string. Of course this method is O(n * m), so it’s not very efficient.

subsetOf2 :: Ord a => [a] -> [a] -> Bool
subsetOf2 xs ys = all (\(c, n) -> maybe False (n <=) .
                       lookup c $ count ys) $ count xs
    where count = map (\x -> (head x, length x)) . group . sort

To improve the big O complexity, we’re going to switch to a data type that has a faster lookup. Like the previous version, counting the frequency of each letter is O(n log n), but using Maps the comparison can now be done in O(m + n), meaning the overall complexity remains at O(n log n).

subsetOf3 :: Ord a => [a] -> [a] -> Bool
subsetOf3 xs ys = M.null $ M.differenceWith
    (\x y -> if x <= y then Nothing else Just x) (f xs) (f ys)
    where f = M.fromListWith (+) . map (flip (,) 1)

Since the keys of the map are characters, there’s a further optimization we can make. By converting the characters to integers we can use an IntMap instead of a plain Map. An IntMap has a lookup of O(min(n,W)), with W being the amount of bits in an Int. For any non-trivial n, this results in O(1) lookup. Counting all the letters can now be done in O(n). Since the comparison still takes O(m + n), the resulting complexity is O(m + n). This is the minimum we can achieve, as we need to fully evaluate both strings to produce an answer, which is an O(m + n) operation.

subsetOf4 :: Enum a => [a] -> [a] -> Bool
subsetOf4 xs ys = I.null $ I.differenceWith
    (\x y -> if x <= y then Nothing else Just x) (f xs) (f ys)
    where f = I.fromListWith (+) . map (flip (,) 1 . fromEnum)

A quick test shows that the first function indeed fails, but the other ones succeed.

main :: IO ()
main = do let test f = print (f "da" "abcd", not $ f "dad" "abcd")
          test subsetOf1
          test subsetOf2
          test subsetOf3
          test subsetOf4

I must say I hope that I have internet access during the interview, though. If not, I would have had to come up with an alternative for differenceWith and I might not have remembered the existence of IntMap. In that case I’d probably have gone with something along the lines of the array-based solution from number 4 of the Scheme solutions.