Forgot your password?
Close
typodupeerror
User Journal

Journal Saige's Journal: Brain Teasers and Algorithms - Straight from my Interview 21

Journal by Saige

As I had a request to give information on the types of brain teasers and algorithms I was asked at my interview, I thought I'd share everything I could remember with those interested. However - there are no answers here, as getting the correct answer wasn't the point here, but going through the problem solving process.

Brain Teasers:

- You have a list of n numbers, in random order, from 1 to n+1 - except there is one missing. Find the missing number.

- There are four cities, located at what would be the corner points of a square with an edge length of 1 mile. You need to build roads to connect all the cities, though they don't all have to be directly connected. What is the smallest amount of road you need to build?

And a bonus one, not one I was asked, but one I saw while preparing, and couldn't get out of my head until I had solved it:

- There are 4 women on one side of a bridge. It is night out, and thus dark. While they have a single flashlight, the bridge is still dangerous, so they can only cross one or two at a time, and only while one of them is carring the flashlight - and they have to walk the flashlight across, they can't toss it. Each woman walks at a different speed - woman A crosses in 1 minute, woman B crosses in 2 minutes, C in 5 minutes, and D in 10 minutes. When two women are walking together, they walk at the speed of the slowest woman.

How do they cross in 17 minutes? And what is the other way?

Algorithms/Functions:

- Given a string containing a full URL, return the string with the directory structure simplified. By simplified, I mean that if "http://www.website.com/this/website/really/sucks/../../is/great/index.html" is passed in, you'd return "http://www.website.com/this/website/is/great/index.html"

- You are given two arrays that contain sorted lists of integers. The arrays are not full - empty space remains in both, and at least one array has room for all the elements in both lists. Merge them together into an array with room, in sorted order.

- Give an algorithm to find all the words in a string of arbitrary length, and the number of times each word appears.

- Given two strings of less than ten characters, how do you determine if the two are anagrams? Now, how do you do it for strings of thousands of characters?

- Give an algorithm for solving the n queens problem. If you are not familiar with it, the problem is - how do you fit n queens on a n by n chessboard so that none of them could capture any other?

- You are given a list of n numbers, from 1 to n, in random order. Using only a call to the function "flip(list, size_of_list, flip_position)", sort the list. When you pass the list into flip(), all the items from 1 to flip_position are reversed (ie 3 1 5 6 7 flipped at 4 becomes 6 5 1 3 7). Find the most efficient solution.

This discussion has been archived. No new comments can be posted.

Brain Teasers and Algorithms - Straight from my Interview More

Brain Teasers and Algorithms - Straight from my Interview

Comments Filter:
  • Too bad they didn't ask you to demonstrate that you could do the job...by doing the job in the interview (unless you interviewed to be a brain-teaser test answer person) :)

    The bridge thing is an oldie but a goodie, commonly called the "U2 Bridge problem."

    1. 1 + 2 cross, 1 returns (3 min elapsed)
    2. 10 + 5 cross, 2 returns (15 min elapsed)
    3. 1 + 2 cross (17 min elapsed)
    • Too bad they didn't ask you to demonstrate that you could do the job

      I think they did. The point isn't that you answer the questions correctly it is how you go about answering them, that is what direclty reflects your abilities at a job.

      Would you rather:

      Person (A) who gets 80% of the questions right without thinking about them but gives up on the others.

      OR

      Person (B) who during your 2 hour interview only got 50% of them right but was on the right track for the other 50% and, like our little /.'er here

      • Re:Wow (Score:2)

        by ces ( 119879 )
        While there is some validity to the infamious "MS interview questions" in that if used properly they can give you some insight into how someone thinks and their approach to solving problems. There is also the problem of selecting for people who are good at doing brain teasers or puzzles under pressure.

        There are some good well-thought-out rants against the "MS style" interview on the net (sorry no link at the moment). Most of them seem to advocate asking canidates to solve job related problems and to disscu

        • Re:Wow (Score:1)

          by Saige ( 53303 )
          There are some good well-thought-out rants against the "MS style" interview on the net (sorry no link at the moment). Most of them seem to advocate asking canidates to solve job related problems and to disscus problems they solved or design approches used at past jobs.

          5+ hours worth of interviews is a lot of time, and a lot of opportunities to ask the algorithm/brain teaser questions, along with asking questions to better get a feel for the personality, along with details of past jobs and solving more job

          • Re:Wow (Score:2)

            by ces ( 119879 )
            5+ hours worth of interviews is a lot of time, and a lot of opportunities to ask the algorithm/brain teaser questions, along with asking questions to better get a feel for the personality, along with details of past jobs and solving more job-related problems. I know because I did all of that - I created a quick DB schema, along with writing some statements to do various queries, as an example of my DB skills. I discussed various past job assignments and problems. And so on - I didn't just get stuck with the
      • I pick Person (c) who demonstrates that s/he can tackle a live, real-life problem that the staff is grappling with now, and make an intelligent stab at it.

        No test, quiz, hypothetical situation, or 1001 Interview Questions (from the Big Book Of Interview Questions) is better at judging how well a person does at the job than actually making them do the job. We also get to see how they do the job (widget-construction style, neatness, attention to detail, etc.).

        ---

        Question for candidate 1:
        Here is a flat-file. H

        • Well, if you were interviewing me I'd first run in fear of XML, but that's just me.

          As far as the right candidate I'd have to ponder if this is just a contractor like thing where I need to get this one job done as best as possible or if I'm looking to hire someone who in a few years will move up the food chain with me =)

          There was a supervisor at IBM I worked with who said he'd never have anyone work under him who could ever replace him. Didn't seem to be thinking about ever moving up the foodchain to me,

    • Re:Wow (Score:1)

      by Saige ( 53303 )
      A lot of the algorithm questions also served for further questions. After I came up with logic for the solution, they had me describe what I would do to test the function. Considering I'm applying to be a developer in test, the algorithms and test plans are quite relevant. After all, showing I can put together the logic to solve a problem is a lot more valuable than just churning out code onto a whiteboard - because I can look up syntax or translate from pseudo-code into code easily. I'm glad they didn't
    • Ok, thank you, I knew there was a damn answer to it, but I couldn't think of it quickly.

      Buffer's brain is currently on shore leave.
  • Perhaps I'm looking too deeply or looking too hard for hidden riddles, but:

    "You have a list of n numbers, in random order, from 1 to n+1 - except there is one missing. Find the missing number."

    Sure implies to me that you are merely given 2 to n+1 and the O(1) solution is that the number one is absent. It could just be how the problem is stated.

    The rest are pretty darn straighforward things I'd expect my students to be able to do... hmm, perhaps there are some good test questions in the lot.
    • OK, yes, you are looking too hard. :) The missing number could be one, but there's no way to know beforehand.

      There is also an almost identical problem where there are 1 to n numbers, and a list of size n+1, with one of the elements duplicated, and you need to find which number is present twice. The answer is practically identical.
  • The first one is basically an algorithm question, unless you know the value of n. I have a half-formed way of solving it well by doing a sort just looking at it. Sort the array in numerical order(start by placing 1, then 2, then 3, etc.[There's another name for it, but I'm BFAA tired]), if you reach the end of the array before finding the number, you've found the missing number. You could also do a better sort(like a quick sort) then go through the array from 1 - n+1 looking for the number, but this wo
    • Interesting answer for the first, but just about any sort you're going to do here is going to be greater than O(n) time - and there is a O(n) solution available. Someone has already posted an answer elsewhere, but don't let that stop you from looking at it more.

      The bonus - well, I'm assuming you mean you think it can only be done in 19 minutes - A with B (2), A back (3), A with C (8), A back (9), A with D (19). That's the best I could see for a while, also. But the problem is that you are optimizing eac
      • Actually, what I was thinking of was basically a linear(AKA sequential) sort, which is O(n)(I know there has to be a better way, it's floating just outside the scope of my vision). I just described my implementation badly. I'm still tired, but I remember a little of my college days. :-)

        Yup, I tend to be myopic with my answers. It causes me as many problems as it solves(I'm gradually learning to grow through my mental myopia, but it's a hard process). I read the answer, and now I don't understand how I

      • TMTOWTDI. It's easy, because you know only one numbers is missing. There are a couple of O(n) calculations you can do that will reveal the missing number immediately.

    • The bonus, ack aye.

      this is easy if you realize you need C&D to cross together. There are two ways to make this happen, and they both yield 17 minutes.

      Hmmmmm - if little, widely known problems like this makes MS think they are getting really clever people, it explains a lot.

  • Moo (Score:2)

    by Chacham ( 981 ) *
    You have a list of n numbers, in random order, from 1 to n+1 - except there is one missing. Find the missing number.

    n+1(n+2)/2 - (all the numbers added together).

    • Typo (Score:2)

      by Cujo ( 19106 ) *

      You left out parens on the n+1.

      • Oops, thanx. :)

        The reason is....... the answer originally was n(n+1)/2--the normal formula--until i realized that he already described n as being one less than the number. So, i added one to each n, completely forgetting about the parens. Thanx!
  • A variant of almost each one of those is on my list of questions to ask when I get to be the nice interviewer -- not do the technical grilling.

    For my last job I got asked 5 or 6 of them, and since I ask them myself, I did pretty well ;)

    (I did admit to them that I'd heard almost all of them before)

Slashdot Top Deals

"Floggings will continue until morale improves." -- anonymous flyer being distributed at Exxon USA

Close