Support NeoGAF

[Soybean]

I've been looking for a new job. Interviewed at a really cool company. My first interview was 6 hours of oral interviewing (lots of puzzles) followed by a programming test, which I didn't do too great on. I was called in for a second programming test.

I had to do this problem, and I took forever trying to come up with the solution (didn't help that my Standard Template Library was rusty), which I never actually did. I did come up with a wrong solution that was close, but I had to present it and got comments like, "What took you so long?" and "Quite frankly, I'm not impressed" and "This was your second chance" (implying the results of the second chance were not good). So yeah, I suck.

I will now share the final interview problem. Feel free to tell me how fucking easy this is:

Let's say you've got lots of data like this in a file:

School      State   Region      Type      Size      Renowned Major 
---------------------------------------------------------------------------------- 
Rutgers      NJ   Northeast   Public      Large      Social 
Princeton    NJ   Northeast   Private     Large      PoliSci 
Seton Hall   NJ   Northeast   Private     Small      Whatever 
Faketown     TX   Midwest     Private     Medium     Whatever 
Superfake    MA   Northeast   Private     Large      Blah

Imagine hundreds of these, for lots of states, regions, sizes small medium and large, and all kinds of majors.

You had to write a function that given two schools would determine the set of attributes (they called these "predicates" in the problem) of those two schools that makes that pair unique. This conjnction of predicates should be the minimum necessary to make the pair of schools unique.

For example, in the case above (let's assume the NJ schools you see are the only NJ schools in the entire list), if you were given Princeton and Seton Hall, you could determine that those two schools are the only Private Schools in NJ. So the "State" and "Type" predicates differentiate that pair. You could also say that Princeton and Seton Hall are the only two private, Northeast schools in NJ, but the "Northeast" part is unecessary. Again you want the minimum # of predicates.

If the pair given is not distinct at all (there are other schools with the same values as the values in common between the pair), return NULL.



What I did (which was wrong and didn't satisfy the minimum size requirement) was have an array of 5 hash maps (5 for the 5 predicate categories), each map using the predicate value as the key (like State map has keys like "NJ", "MA", etc.), and a vector as the value. The vector holds the schools that are associated with that key (so the State hash map might have a [key,value] pair of [NJ, Princeton;Rutgers;Seton Hall]).

So my function, when given two schools, sees which values are in common (since for the conjunction to occur, the two schools need to have at least some data in common). Let's say their State (PA), Size (Large) and Region (Northeast) match up. I do an intersection amongst the State->PA vector, Size->Large vector and Region->Northeast vector. The final intersection should only contain 2 schools. If not, that conjunction isn't valid and you return NULL.

The problem of course, is that just taking the intersection doesn't give you the minimum set. With the Princeton/Seton Hall example, my algorithm DOES list "Region" as one of the predicates (Region should never be listed really, as it's a superset of state).

What you could do is try every combination of intersections for a brute force solution (say 4 predicates match; try intersections among all combinations of 3 of those predicates, then all combinations of 2, etc.), but brute force is not good enough.



I spent 20 hours interviewing at this company for nothing! The worst part is that I feel really fucking incompetent. But it also sucks that I missed out on a great salary there.

I will post questions from the first interview later if anyone cares.

 

[Foreign Jackass]

I'm a software engineer and I wouldn't know how to answer this one quickly enough. However, I'm currently considering changing careers, and one of the reasons I want to is that I'm just not interested enough by this bullshit to really care about if I'm able or not to solve it.

 

[Soybean]

This was the first programming test:

Part A
Write a function that determines how many "perfect shuffles" must be performed (at least one; you can't say zero) so a deck of cards is restored to its original order.

long shuffles(nCards, iCut);

A "perfect shuffle" in this problem is where you have a deck of nCards unique cards and you cut the deck iCut cards down. Take the bottom card of the top deck and put it down. Take the bottom card of the bottom deck and put it down. Repeat until one of the cut portions is depleted. Then take the remainder of cards and just plop it on top of your pile.

So with nCards = 5, iCut =2:

1   3 1 3 1 3 1
2   4 5 2 4 5 2
-   - - - - - -
3   1 3 1 3 1 3
4   5 2 4 5 2 4
5   2 4 5 2 4 5

6 shuffles

Make it efficient!!!!!!! It should run quickly.

Run it on (1101, 101) (or something like that; don't remember exactly)

Part B
Write a server that implements this function:

(nCards, iCut) --> (shuffles(nCards, iCut), time)

where time is the amount of time the server took to execute the function.

Write a client that connects to the server, executes 10000 random queries and writes each response to a file.

On the back was an implementation for a function that finds the least common multiple of two numbers.

When someone told me what the solution was and how obvious it is, I wanted to bash my head against the wall.

 

[cubicle47b]

Your explanations of the problems are confusing.

If given a list of schools with attributes and asked to hand back the attributes that were unique to the two schools I'd check the value of each hash individually, check the count to see if it equaled two, and if it did check the two schools to see if they were the two I was looking for uniqueness on. If they were, I add the attribute to the attribute return list and move on to the next hash until I'm done.

This works if my understanding of the problem is correct.


I'm still trying to make sense of the second problem.

 

[cubicle47b]

return leastcommondenominator(nCards-iCut, iCut)

 

[Soybean]

Sorry. I'm not very good at explaining these things.

If I understand your solution correctly, it doesn't work. In my example data set, Princeton and NJ are the only Private NJ schools. The "Private" vector will have a list of ALL private schools in all states. The "NJ" vector will have all NJ schools. You can't simply do a count within one attribute because it's the conjunction of those two attributes that makes the pair unique.

 

[Soybean]

return leastcommondenominator(nCards-iCut, iCut)

Not quite. You do have to perform a number of shuffles to get some data about the behavior of the shuffle.

 

[cubicle47b]

I was still working out the second one (it was a guess based on a quick test). You have to figure out the number of times it takes for each number to repeat and find the least common denominator for all of them. So you have to run cycles until each number has repeated and then run the lcd function recursively.

Yeah, I don't really understand what you have to do in the first. Find what makes them unique within their state?

edit: Oh, you're just trying to use the least amount of data you can give to get those two results?

 

[Soybean]

I was still working out the second one (it was a guess based on a quick test). You have to figure out the number of times it takes for each number to repeat and find the least common denominator for all of them. So you have to run cycles until each number has repeated and then run the lcd function recursively.

Yup (although I don't understand the recursive part; once you figure out the cycles required for numbers to return to their original positions you can just take the LCD of those cycles; no recursion I think)! Thanks for making me feel even stupider! Am I the only one who couldn't get this?

Oh, you're just trying to use the least amount of data you can give to get those two results?

Yes! But there are cases where you can find multiple ways to get a minimal set. In that case, just choose one and return it.

 

[RiZ III]

What were you given in for data? Meaning was/were the function param(s) and what was the return type? Were you given this data in an stl:air or map or list or something else?

 

[cubicle47b]

Yup (although I don't understand the recursive part; once you figure out the cycles required for numbers to return to their original positions you can just take the LCD of those cycles; no recursion I think)! Thanks for making me feel even stupider! Am I the only one who couldn't get this?

They gave you a big hint with the lcd function. I wouldn't call anyone stupid for not figuring it out, though. I said recursive in case there were more than 2 patterns within larger datasets. I'm guessing there aren't by your reply.

I'm looking at the first one again.

 

[Soybean]

It was given to me in a text file, tab-separated values. I put it into std::map and vectors, but clearly there was a better way to organize the data than what I did.

There was no function signature, so I could do whatever I wanted. This was actually just part 1, so you'd want to make it fit into the second part.

Part 2 was creating a simple interface. You'd type in the name of a school, hit ENTER and the program would randomly pick another school and show you the relationship between the two: "Did you know that University of Blah and FooBar U. are the only two Public schools that specialize in video game development?". Hit ENTER again and the program will pick another random school, etc. (if no relationship is found, try another school).

 

[cubicle47b]

I don't know how you can get around brute forcing the last one, at least a little. I'd order my matching hashes from smallest hash count to largest hash count and compare 2 hash lists at a time (if the count is two return) at first, then 3 and so on. If there are always more than 2, return the null.

edit: When you do list comparisons don't bother counting after you hit 3, just move onto the next two lists. I would have made a key lookup table (int, school name) too.

so:

there are 4 matching hashes - A (3 items hash to A), B (5), C (13), D (57)

compare A&B, A&C, A&D, B&C, B&D, C&D, A&B&C, etc. until you get two results or you never find uniqueness.


I'd like to hear some other solutions. I spent a *lot* of time working out a system of only keeping the matching list of the hash lists before deciding it was stupid.