Are you cut out to work at facebook? group these anagrams in SPIN

tonyp12tonyp12 Posts: 1,821
edited June 2015 in Propeller 1 Vote Up0Vote Down
Don't Google the answer/the angle of attack.

During a 45minute Facebook job interview you could be requested to write a C++ from scratch that does this:
You have a list of these words
"tsar", "rat", "tar", "star", "tars", "cheese"

re-arrange them so the anagrams (words that have the same letters) are grouped together.
output order not important.
«13

Comments

  • 61 Comments sorted by Date Added Votes
  • Beau SchwabeBeau Schwabe Posts: 6,275
    edited May 2015 Vote Up0Vote Down
    I would fire the hiring manager and explain to the staff why he or she is unfit for the job. Then I would promptly leave my contact information and walk out the door.



    Beau Schwabe -- Metallurgical Machine Design and Development Engineer
    ෴My Message෴www.Kit-Start.com - bschwabe@Kit-Start.com ෴෴ www.BScircuitDesigns.com - icbeau@bscircuitdesigns.com ෴෴

    "I've said it before ... If you follow the directions for apple pie and then expect it to taste like cherry pie then your absolutely insane"
  • Duane DegnDuane Degn Posts: 10,000
    edited May 2015 Vote Up0Vote Down
    I would fire the hiring manager and explain to the staff why he or she is unfit for the job. Then I would promptly leave my contact information and walk out the door.

    I'm trying to understand how these sentences go together. If you've just fired the hiring manager, then you're their boss right? If you've the hiring manager's boss why are you leaving contact information? Are you leaving work early by walking out the door?

    Or are you placing yourself in the position of the person at the interview and showing Facebook they should hire you to be the hiring manager's boss? I'm confused, which is not uncommon after you've made a post but generally my confusion arrives from your technical presentation sailing over my head. This time I don't think my confusion is caused by my lack of understanding of the subtleties of inductors. (Don't get me wrong. I'm usually thrilled to be confused by the subtleties of inductors.)
  • SRLMSRLM Posts: 5,036
    edited May 2015 Vote Up0Vote Down
    Sort the letters for each word alphabetically and use that as a key to a map, whose value stores an array of the words.

    Did I win?
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    There are at least two ways to go about this:
    1. Sort the letters in each string alphabetically, then compare strings for equality to group them.
    2. G
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • GordonMcCombGordonMcComb Posts: 3,034
    edited May 2015 Vote Up0Vote Down
    Count the number of characters; only the four-character entries in this specific list share the same anagram; the three letter ones a separate anagram. Tsar and rat are not true anagrams. They simple share some of the same characters.

    Nothing in the challenge indicated they are wanting a universal algorithm for arbitrary words, just these -- emphasis on "these words" in the question text.

    (You don't even have to count characters if you're going after the literal interpretation of the question.)

    I agree that on the surface a test like this seems trivial and useless, but often they are looking for coders who don't overcomplicate the simple.
  • Heater.Heater. Posts: 19,354
    edited May 2015 Vote Up0Vote Down
    Phil,

    "G
  • Heater.Heater. Posts: 19,354
    edited May 2015 Vote Up0Vote Down
    Gordon,

    I noticed that the correct grouping of that list is known simply by the length as well. What ran though my mind is that given the problem description is to ask if that is the only input or is it just an example. If the answer is that it is the only input then I would have explained my solution and expected not to have to fiddle around writing code.

    If you are going to short circuit the solution like that you don't even need to compare the string lengths, just write six statements that print the strings in the right order!
  • Heater.Heater. Posts: 19,354
    edited May 2015 Vote Up0Vote Down
    Phil,
    Both methods would work in Spin, at least for short strings. (The 26th prime number is only 101.)
    How short?

    If I'm not mistaken "zzzzz" encodes as 101 to the power 5, which is 10510100501, which is greater than the maximum value of an unsigned 32 bit integer. So the G
  • abecedarianabecedarian Posts: 312
    edited May 2015 Vote Up0Vote Down
    Facebook, eh?

    First you'd need a Propeller cluster to receive data and transmit that data to a second Propeller cluster running an ad server, and a third Propeller cluster running an anagram server that relays anagram data to the second cluster. The third Propeller cluster also sends your data to a fourth Propeller cluster running a dictionary server comparing your anagrams to real words and phrases, and sends dictionary (mis)match information to the second cluster which spams others within about 50 "friends" distant to you with data related to you and your inability to create words that make anagrams and offers programs and FB add-ins that can help those "friends" do better than you....


    This was for Facebook, right?
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    Heater,

    If it ain't in the Official Scrabble Players' Dictionary, it ain't a word, and "zzzzz" ain't in there. By arranging the letters in order of frequency (e-t-a-o-i-n-s ...) and assigning those with the highest frequency the lowest primes you can accommodate the most words with G
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Mark_TMark_T Posts: 1,577
    edited May 2015 Vote Up0Vote Down
    Internally sorting the strings isn't the easiest to code correctly in a hurry, but if you take C++ to mean C++ 11,
    then sort and stable_sort are in the standard libraries...

    Building a character frequency table for each word avoids the size limit of "Godel coding". Either way
    you then have to spot equivalence classes (can again be done by sorting the encodings of the words,
    or just by N^2 search for matching entries)

    In a hurry I would be tempted to write something inefficent and recursive which is readable and hard
    to get wrong:
    bool is_anagram (char * a, char * b)
    {
      for (char letter = 'a' ; letter <= 'z' ; letter++)
        if (char_count (a, letter) != char_count (b, letter))
          return false ;
      return true ;
    }
    
    int char_count (char * a, char c)
    {
      if (a[0] == 0)
        return 0 ;
      return char_count (a+1, c) + (a[0] == c ? 1 : 0) ;
    }
    
    The top level takes a word at a time and picks out all its anagrams, outputing them and striking from the input list.
  • Heater.Heater. Posts: 19,354
    edited May 2015 Vote Up0Vote Down
    Should "cheese" be included in the output? It's not an anagram of anything else in the list.
  • tonyp12tonyp12 Posts: 1,821
    edited May 2015 Vote Up0Vote Down
    The output list should include Cheese, it's about grouping the anagrams in the new/rearranged list and not just finding them.


    Quora:

    I was recently told, after 10 minutes in an internship interview, that I'm "just not cut-out for Facebook." What (if anything) can I take away from this feedback to improve for the future?

    For some background, I'm in the top 5% of the computer engineering program at a large university, and have a year of work experience from a small software company. Admittedly, I was pretty nervous in the interview.

    •The interview was supposed to be 30 minutes, but was shortened because the interviewer started about 10 minutes late. I had arrived 15 minutes early.

    •After briefly discussing my resume, I was asked one technical question: Write a program that takes a list of words and groups together the anagrams. The program is trivial if you can see the "trick". However, I couldn't see it, and ended up trying to hack together an inefficient solution involving character by character comparisons between all the words. At no point did the interviewer suggest I consider a different strategy.

    •The actual words "not cut-out for Facebook" were used. In the interviewer’s defense, what I came up with for the anagrams problem was garbage.

    •This ended the interview a few minutes early. I felt pretty crushed by the experience. I thanked the interviewer for his honesty and he opened the door for me to leave. I was so focused on what went wrong that I cannot remember the name of the interviewer.

    •I still think Facebook is a great company, and I love watching the tech talks on the projects they are working on. I’m certainly not going to judge them based on a bad experience with one person. I do wonder if there is an elitist attitude that creeps into the top tech companies. However, Ankur’s answer indicates that the company culture is definitely against this kind of attitude.
  • Heater.Heater. Posts: 19,354
    edited May 2015 Vote Up0Vote Down
    tonyp12,

    Perhaps you are right, "cheese" should be included even though it is not an anagram of anything in that list. The question does say "re-arrange them ..." which implies list them all.

    I thought I'd find a strict definition of "anagram". Type that into google and it says "Did you mean: nag a ram" :) That is a cunning stunt.
  • tonyp12 wrote: »
    Don't Google the answer/the angle of attack.

    During a 45minute Facebook job interview you could be requested to write a C++ from scratch that does this:
    You have a list of these words
    "tsar", "rat", "tar", "star", "tars", "cheese"

    re-arrange them so the anagrams (words that have the same letters) are grouped together.
    output order not important.

    The ascii codes from each word multiplied together would tell you which words ( groups of letter ) had the same value. tsar, star and tars = 442, rat and tar = 327 and cheese = 621.

    During interviews you don't have the luxury of time when giving answers. The paradox is that someone spent quite a bit of time developing the questions.

    Sandy
    Infantryman's Axiom; Always cheat, always win.
  • tonyp12tonyp12 Posts: 1,821
    edited May 2015 Vote Up0Vote Down
    >The ascii codes from each word multiplied together
    But the program can not just be limited to these specific words, some words may be so long that it will overflow 32bits using that technic
    Some words may be using same letter more than once and may come to same total though it's not an anagram of any other word in the list.
  • tonyp12 wrote: »
    >The ascii codes from each word multiplied together
    But the program can not just be limited to these specific words, some words may be so long that it will overflow 32bits using that technic
    Some words may be using same letter more than once and may come to same total though it's not an anagram of any other word in the list.

    That's why I'll probably never work at Facebook. Must have been an interesting experience anyway. I can't imagine that many people get to the interview stage with those guys.

    I just did an interview with an organization that are building muon detectors for the Large Hadron Collider. The experience was interesting but I don't think I got the job.

    Sandy
    Infantryman's Axiom; Always cheat, always win.
  • Beau SchwabeBeau Schwabe Posts: 6,275
    edited May 2015 Vote Up0Vote Down
    @Duane Degn -

    The latter of the two is what I was thinking ... "...Or are you placing yourself in the position of the person at the interview and showing Facebook they should hire you to be the hiring manager's boss?"


    In almost ALL cases, a question like this at an interview is to see if you know the lingo. Thinking outside of the box is always to your advantage unless you have little to no ambition and are happy answering tech phone calls all day long. Personally not my cup of tea.


    So the task proposed ... "re-arrange them so the anagrams (words that have the same letters) are grouped together.
    output order not important."

    You have to ask yourself, how this would be applied in a practical way? ... Predictive typing and spell checking is immediately what comes to my mind.

    So given the words, (assuming they are all words), what must be done here is to create an algorithm that builds a histogram based on the letters in each of the words.

    i.e.

    take the first word "tsar"

    rat - is a 75% letter match
    tar - is a 75% letter match
    star - is a 100% letter match
    tars - is a 100% letter match
    cheese - is a 25% letter match

    So the FIRST alphabetized grouping would be...
    100%
    star
    tars
    tsar
    75%
    rat
    tar
    25%
    cheese


    For the second group, take the word "rat"

    tsar - is a 75% letter match
    tar - is a 100% letter match
    star - is a 75% letter match
    tars - is a 75% letter match
    cheese - is a 0% letter match

    So the SECOND alphabetized grouping would be...
    100%
    rat
    tar
    75%
    star
    tars
    tsar
    0%
    cheese

    ... and so on for each "word" .... the coding for this is trivial, since it is simple string manipulation. If you are having problems there then perhaps you need to re-evaluate your application in the first place.

    However for the remaining words the results for "tar" and "rat" would be the same as well as the same results for "star", "tars", and "tsar" ... and "cheese" is always on his own, just to make sure that a bad apple is detected although the "s" in cheese would give a trace percent for some of the words

    ... hint, just look at the 100% grouping for the words you have already done, there is no need to re-hash the algorithm each and every time.



    Beau Schwabe -- Metallurgical Machine Design and Development Engineer
    ෴My Message෴www.Kit-Start.com - bschwabe@Kit-Start.com ෴෴ www.BScircuitDesigns.com - icbeau@bscircuitdesigns.com ෴෴

    "I've said it before ... If you follow the directions for apple pie and then expect it to taste like cherry pie then your absolutely insane"
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    The ascii codes from each word multiplied together would tell you which words ( groups of letter ) had the same value. tsar, star and tars = 442, rat and tar = 327 and cheese = 621.
    That won't work. The numbers have to be distinct primes (i.e. G
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • base2designbase2design Posts: 78
    edited May 2015 Vote Up0Vote Down
    Ok, so I'm cheating a little by using Lua for the answer, but aside from not having to malloc() anything, nothing I'm doing here is too hard in straight C:
    t = { "tsar", "rat", "tar", "star", "tars", "cheese", }
    function id(s)
        local n=0
        for i=1,#s do
            n = n + s:byte(i,i)
        end
        return n
    end
    u = {}
    p = {}
    for i=1,#t do
        p[#p+1] = 0
        u[#u+1] = id(t[i])
    end
    for i=1,#u do
        if p[i] == 0 then
            p[i] = 1
            print("===")
            print(t[i])
            for j=1,#u do
                if p[j] == 0 and u[i] == u[j] then
                    p[j] = 1
                    print(t[j])
                end
            end
        end
    end
    

    output is:
    ===
    tsar
    star
    tars
    ===
    rat
    tar
    ===
    cheese
    
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    So you're adding up the ASCII values of the characters to give the anagram a unique identify? In that scheme MOW == LOX.

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    A technique that might lend itself to Spin is to create a 26-character string for each word, initialized to all 1s. For each letter in each word, add one to its position in the word's 26-character string. Then just compare the 26-character strings to do the grouping.

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • base2designbase2design Posts: 78
    edited May 2015 Vote Up0Vote Down
    So you're adding up the ASCII values of the characters to give the anagram a unique identify? In that scheme MOW == LOX.

    -Phil

    Yeah, I threw the "id" function together quickly and it accidentally worked for this case. ;)
  • GordonMcCombGordonMcComb Posts: 3,034
    edited May 2015 Vote Up0Vote Down
    Heater. wrote: »
    I noticed that the correct grouping of that list is known simply by the length as well. What ran though my mind is that given the problem description is to ask if that is the only input or is it just an example. If the answer is that it is the only input then I would have explained my solution and expected not to have to fiddle around writing code.

    If you are going to short circuit the solution like that you don't even need to compare the string lengths, just write six statements that print the strings in the right order!

    There's a story that's decades old, and perhaps apocryphal, about a company (variously IBM or some other large firm) "testing" its college grad applicants by giving them a written test. After a short instructional paragraph at the top, it said, "Do not take this test. Put your name on it, leave all questions blank, and sit quietly at your desk." The story goes about 80% of the applicants didn't read the instructions, and filled out the test. They didn't get to the second interview.

    The thing is this: Tony's initial description doesn't warrant anything but writing a C++ program where you've manually re-arranged the elements of the array. If that's not demanding enough, you could use a bit of Occam's Razor to come up with the least obtuse result given only the stated instructions. So it's really not short-circuiting, but following directions.

    Assuming this Facebook story isn't apocryphal too (and I believe it is), the real instructions are likely more involved. But who knows. Shouldn't a programmer's first job, when faced with uncertain requirements, is to get clarification? Perhaps the correct answer is, "What do you mean exactly?. Please be more specific what the example program is intended to do."
  • base2designbase2design Posts: 78
    edited May 2015 Vote Up0Vote Down
    Here's an updated version inspired by PhiPi's comments (once again in Lua... I probably should be posting Spin here ;) ):
    t = { "tsar", "rat", "tar", "star", "tars", "cheese", "mow", "lox"}
    
    function id(s)
    	local t = {}
    	for i=1,26 do t[i] = 0 end
    	for i=1,#s do
    		local c = string.lower(s:sub(i,i))
    		if c >= "a" and c <= "z" then
    			local h = string.byte(c) - ("a"):byte() + 1
    			if h > 0 then t[h] = t[h] + 1 end
    		end
    	end
    	local r = ""
    	for i=1,26 do
    		if t[i] > 0 then
    			r = r .. string.char(("a"):byte() + i - 1)
    		end
    		if t[i] > 1 then
    			r = r .. t[i]
    		end
    	end
    	return r
    end
    p = {} u = {}
    print("* word -> id *")
    for i=1,#t do
    	p[i] = 0
    	u[i] = id(t[i])
    	print(t[i], u[i])
    end
    for i=1,#u do
    	if p[i] == 0 then
    		p[i] = 1
    		print("===")
    		print(t[i])
    		for j=i+1,#u do
    			if p[j] == 0 and u[i] == u[j] then
    				p[j] = 1
    				print(t[j])
    			end
    		end
    	end
    end
    

    Here's the output (I also show the string to id table)
    * word -> id *
    tsar    arst
    rat     art
    tar     art
    star    arst
    tars    arst
    cheese  ce3hs
    ===
    tsar
    star
    tars
    ===
    rat
    tar
    ===
    cheese
    
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    ... once again in Lua... I probably should be posting Spin here ...
    No, I appreciate the exposure to Lua. I need to grok it better, since the fastest and most comprensive CHDK scripts are written in it.

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • mindrobotsmindrobots Posts: 6,488
    edited May 2015 Vote Up0Vote Down
    I have little faith in the interview process or the people conducting the interviews

    Many moons ago, I interviewed for a position at the customer I had been providing onsite vendor support for over the prior 2 years. I was told I wasn't "right" for the position....I don't recall her actual reasons for not considering me as a good candidate. I went back to the customer's site and told my future manger HR's reaction. Within a couple hours, the HR person had received calls from a rather disappointed manager, director and executive director (oh, and her director) that maybe she reconsider her perspective on my interview. She called back and confirmed I could start on the previously agreed upon date. Twenty seven years later, so much for HR and interview process.

    As for the Facebook question, sprinkle some random advertising in your output and suggest how they can send the collected user data to one of their "big data" lakes and monetize it and I'm sure they'll love you!! (Maybe I feel the same about Facebook as I do about HR interviews!)
    MOV OUTA, PEACE <div>Rick </div><div>"I've stopped using programming languages with Garbage Collection, they keep deleting my source code!!"</div>
  • tonyp12tonyp12 Posts: 1,821
    edited May 2015 Vote Up0Vote Down
    I have not seen the question, maybe it's even just given verbally.
    Here is some more info:
    http://sahandsaba.com/interview-question-facebook-anagrams.html

    Depending what language you get to use, it would be pretty hard to write one in 10minutes if you are not pro in string sorting.
    In SPIN it's very hard as there is no run time allocating of new arrays and strcomp and strsize are the two only string commands available, everything else has to be done byte by byte.

    SPIN rules: All words are in lower case already, random words, length and amount (could even be external file with no visual idea how many there are)
    The list is just a zero delimited byte array ending with 13 or use the address of listend as match
    use "Parallax Serial Terminal.spin" to output the words, you are allowed to trash the workspace once you have output that word.
    A workspace buffer that is up to 4 times the size of list.
    DAT
    list byte "tsar",0,"rat",0,"tar",0,"star",0,"tars",0,"cheese",0
    listend byte 13
    workspace byte 0[120]
    
  • ercoerco Posts: 18,185
    edited May 2015 Vote Up0Vote Down
    I have my first job interview in 30 years on Wednesday. Can't wait to see if they fire some of these bizzare left-field, "where did THAT come from" questions at me, which seem to be all the rage for many companies these days.

    http://humanresources.about.com/od/interviewing/a/interview_odd.htm
    "When you make a thing, a thing that is new, it is so complicated making it that it is bound to be ugly. But those that make it after you, they don’t have to worry about making it. And they can make it pretty, and so everybody can like it when others make it after you."

    - Pablo Picasso
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,044
    edited May 2015 Vote Up0Vote Down
    Good luck with the interview, erco! Hopefully, they'll throw you what they think will be a curve ball about flame throwers, which you will deftly swat out of the park!

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
Sign In or Register to comment.