• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need some help with an algorithm  RSS feed

 
Janeice DelVecchio
Bartender
Posts: 1812
12
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, so I'm sure I'm not thinking of something simple here, but here goes...

The assignment was to take some input file and read it (which I have done, presumably correctly)... the file contains lists of people. The people can be sorted into two categories.

Each person is followed by a secondary list of people which are in the "opposite" category as the first person. This is done with some looping and a scanner and stuff... all that isn't totally important.

Here's my issue. I have an algorithm as follows:



This seems like a good plan to me, but I'm afraid I think I wasn't expecting some issues. Before the sets get fully populated (say in the first 2 or 3 rounds), I've found there is a high probability that the names could end up in the wrong set. I've also found, in some test cases, that the total of names in both sets can end up to be more than the amount of names I started with... meaning there are duplicates. Each person should be in one and only one category.

There is also a performance issue, too... I need to keep things as lean as possible as there are large data files that need to be processed.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
not sure I understand so i'm gonna ask dumb questions...

So you get a file something like

fred susan melanie ethel
mary joe tom peter


every name after the first goes in the 'other group'.

you want to read the first name, and based on the other names determine where to put it. Are you guaranteed to be able to tell? For example:

fred bob peter john
henry george phil tom

I don't think you can tell from this list who goes where. Sure you know fred is in group A, bob-peter-john all go in B. but there is no way to tell if henry goes in A or B, just from this list.

is your data going to be 'good enough' to determine this?
 
Janeice DelVecchio
Bartender
Posts: 1812
12
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the help, fred

All the clarification things are right on....

Here's the link to the problem.... this is something where I could get in trouble for "posting real code," but I think asking for tips and hints won't get me in trouble.... I have submitted to the bot several times and when I finally found some test cases, I realized there's something wrong with my logic.

http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=20

And I read in their discussions that the problem is solveable with an algorithm that supposedly many people learn in a typical undergrad program... I'm just missing something.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
interesting problem...and more subtle than I thought...sadly I don't have much help for you...but it IS interesting.

There has to be some kind of data structure that would make this easy, but I can't think of what it is...

I'll let it percolate and see if anything bubbles up.

 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok...been thinking about this one...

everyone on a truth teller list will be liars

everyone on a liars list will be a truth teller.

if that's the case, then you know that a single list is coherent. I.e.


and then


So the trick is to build all these lists, then connect them all together. You have to expect, given what the problem states, that eventually you will start finding links...


So once you get this, you can figure that F,G,H,J, and K are all in the same group, as are E and I.

does this make any sense? Does it help at all?

or do you already have the solution?
 
Janeice DelVecchio
Bartender
Posts: 1812
12
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fred, this makes sense, and I went back and forth when creating my current implementation between using Sets or a Map.
This seems like I should create more than one map?

A map with a string as a key and a list as a value?

I guess this makes sense, but how to incorporate it into one list is still the mystery.

Thanks so much for the pointers!
 
Janeice DelVecchio
Bartender
Posts: 1812
12
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suppose I need to decide how many times I need to read through the data to get 2 solid lists. It looks like once won't be enough.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!