Interview Question I Got# JobHunting - 待字闺中
q*0
1 楼
C++ or Java:
Given table passed in as a 3*N array of strings
California, Palo Alto, Alice
Arizona, Phoenix, Bob
California, Palo Alto, Foo
California, San Francisco, Eve
California, San Diego, Peter
Washington, Seattle, Bar
Print State, City, Name hierarchically, order does not matter:
E.g. the following is valid:
California
Palo Alto
Alice, Foo
San Francisco
Eve
San Diego
Peter
Arizona
Phoenix
Bob
Washington
Seattle
Bar
My solution
1. Sort array by state column, then within each state sort by city
column,
this gives the new array below.
Arizona, Phoenix, Bob
California, Palo Alto, Alice
California, Palo Alto, Foo
California, San Diego, Peter
California, San Francisco, Eve
Washington, Seattle, Bar
We print this. I was asked to write code for this, but didn't know how
to
sort a 2d array using 1 column as the pivot.
2. Create a HashTable>
Top level hashtable uses states as key, and value is another
hashtable. This
other hashtable uses city name (e.g. Palo Alto) as key and returns a
list,
this list is the list of people living in that state in that city.
So then I get iterators for the top hashtable, then iterate over the
hashtables contained in it and print out the name list.
Interviewer said this is okay, but there are other ways. I think he
mentioned composite hashing or combine hashing or something, but I
don't
remember. Is there a non-standard hashing method that will solve this
problem more efficiently? Thanks.
Given table passed in as a 3*N array of strings
California, Palo Alto, Alice
Arizona, Phoenix, Bob
California, Palo Alto, Foo
California, San Francisco, Eve
California, San Diego, Peter
Washington, Seattle, Bar
Print State, City, Name hierarchically, order does not matter:
E.g. the following is valid:
California
Palo Alto
Alice, Foo
San Francisco
Eve
San Diego
Peter
Arizona
Phoenix
Bob
Washington
Seattle
Bar
My solution
1. Sort array by state column, then within each state sort by city
column,
this gives the new array below.
Arizona, Phoenix, Bob
California, Palo Alto, Alice
California, Palo Alto, Foo
California, San Diego, Peter
California, San Francisco, Eve
Washington, Seattle, Bar
We print this. I was asked to write code for this, but didn't know how
to
sort a 2d array using 1 column as the pivot.
2. Create a HashTable
Top level hashtable uses states as key, and value is another
hashtable. This
other hashtable uses city name (e.g. Palo Alto) as key and returns a
list,
this list is the list of people living in that state in that city.
So then I get iterators for the top hashtable, then iterate over the
hashtables contained in it and print out the name list.
Interviewer said this is okay, but there are other ways. I think he
mentioned composite hashing or combine hashing or something, but I
don't
remember. Is there a non-standard hashing method that will solve this
problem more efficiently? Thanks.
