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

tonyp12

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.

Beau Schwabe

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.

Duane Degn

Beau Schwabe wrote: »

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.)

SRLM

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)

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

GordonMcComb

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.

Phil,

"G

Heater.

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.

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

abecedarian

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)

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

Mark_T

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.

Should "cheese" be included in the output? It's not an anagram of anything else in the list.

tonyp12

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.

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.

Alexander (Sandy) Hapgood

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

tonyp12

>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.

Alexander (Sandy) Hapgood

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

Beau Schwabe

@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.

Phil Pilgrim (PhiPi)

Alexander (Sandy) Hopgood wrote:

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

base2design

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)

So you're adding up the ASCII values of the characters to give the anagram a unique identify? In that scheme MOW == LOX.

-Phil

Phil Pilgrim (PhiPi)

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

base2design

Phil Pilgrim (PhiPi) wrote: »

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.

GordonMcComb

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."

base2design

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)

base2design wrote:

... 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

mindrobots

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!)

tonyp12

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]

erco

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

Phil Pilgrim (PhiPi)

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