Skip to content

If Google would be looking to hire F# programmers – part 2

April 27, 2013

Problem #2 from the book reads: “write an efficient algorithm that searches for a given element in a 2D array, which elements are sorted by rows and columns, i.e. for each pair of indices i and j elem[i,j] <= elem[i+1,j] and elem[i,j] <= elem[i,j+1]".
This problem is known as saddleback search. It has received a lot of attention in the literature. I am not going to dig too dip and will provide a “good enough” solution that allows for further improvement.

My solution would be similarly to Nuts and Bolts problem based upon “divide and conquer” approach.

Let’s begin the search from the lower left corner having the whole 2D array aa of n columns and m rows as the search space. Compare element aa.[0,m – 1] with the pattern x. If they are equal, our mission is accomplished (we will disregard here that multiple occurences of the pattern may have place). If not and aa.[0,m – 1] > x, then we should exclude the last row from search space as elements there just grow towards right side, and move new comparison element one row up. This effectively makes the search space narrower by one row. For the scenario aa.[0,m – 1] < x the similar considerations exclude from search space leftmost column moving comparison one element to the right to aa.[1,m – 1]. Repeating these actions on the shrinking search space eventually either brings the matched element, or the conclusion that the match does not exist.

F# implementation below is quite literal reproduction of this search strategy description:

let saddlebackSearch (aa: 'a[,]) n m x =
    let up (h, v) =
        match v with
        | 0 -> None
        | _ -> Some((h, v - 1))
    let right (h, v) =
        match m - 1 - h with
        | 0 -> None
        | _ -> Some((h + 1, v))
    let rec searcher = function
    | None -> None
    | Some(h, v) -> match (Operators.compare aa.[h,v] x) with
                    | 0 -> Some(h, v)
                    | -1 -> searcher (right(h, v))
                    | _ -> searcher (up(h, v))
    searcher (Some((0, m - 1)))

Talking of the effectiveness of the code above is should be clear that it delivers conclusion by time O(n+m) in the worst case scenario. Exercising the implementation with the code below

let aa = Array2D.init  10 10 (fun i j -> 3*i + 27*j + j*j)
saddlebackSearch aa 10 10 22
saddlebackSearch aa 10 10 175

delivers the following results:

val aa : int [,] = [[0; 28; 58; 90; 124; 160; 198; 238; 280; 324]
                    [3; 31; 61; 93; 127; 163; 201; 241; 283; 327]
                    [6; 34; 64; 96; 130; 166; 204; 244; 286; 330]
                    [9; 37; 67; 99; 133; 169; 207; 247; 289; 333]
                    [12; 40; 70; 102; 136; 172; 210; 250; 292; 336]
                    [15; 43; 73; 105; 139; 175; 213; 253; 295; 339]
                    [18; 46; 76; 108; 142; 178; 216; 256; 298; 342]
                    [21; 49; 79; 111; 145; 181; 219; 259; 301; 345]
                    [24; 52; 82; 114; 148; 184; 222; 262; 304; 348]
                    [27; 55; 85; 117; 151; 187; 225; 265; 307; 351]]

val it : (int * int) option = None
 
val it : (int * int) option = Some (5, 5)

To be continued…

Advertisements

From → F#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: