Getting a job in software development: A Reddit discussion round-up

Re:Getting a job in software development: A Reddit discussio... by itmag on Sunday December 11, 2011 @08:38AM (#3340023)

So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next smallest value. For example, if the tree contains 1, 2, 3, and 5, and I ask for 4, then return 3.

Out of curiosity, what is the solution?

I would imagine something like keeping a variable of the highest found value under 4 and if you don't find 4 then you use this variable.

[ Parent | on HN ]

Re:Getting a job in software development: A Reddit discussio... by kd5bjo on Sunday December 11, 2011 @10:31AM (#3340215)

Start at the root of the tree; at each node:

  - If the node value matches, return it
  - If the node value is too low:
    - If possible, step right and repeat
    - Otherwise, return this node value
  - If the node value is too high:
    - If possible, step left and repeat
    - Otherwise, return the value of this node's predecessor:
      - Walk up until you traverse a right link
      - Return the node's value
      - If you hit the root, the requested value is less than any value in the tree

[ Parent | on HN ]

Re:Getting a job in software development: A Reddit discussio... by 3pt14159 on Sunday December 11, 2011 @11:23AM (#3340303)

I wrote it out in python for you: http://pastebin.com/5hX9ZMvB

and the solution written out in words below, also in python (I like this one better)

http://pastebin.com/PapfMhfU

[ Parent | on HN ]