q***0
发帖数: 43 | 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. | a*******d
发帖数: 85 | 2 for the first question, I would use a multilevel map in C++. | A**u
发帖数: 2458 | 3 求详解
【在 a*******d 的大作中提到】
: for the first question, I would use a multilevel map in C++.
| q****x
发帖数: 7404 | 4 第一个排序为何不行？
【在 q***0 的大作中提到】
: 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:
| q***0
发帖数: 43 | 5
Cannot print
California, Palo Alto, Alice
California, Palo Alto, Bob
Need to print different levels and print the names of people in the same
city together.
California
Palo Alto
Alice, Bob
【在 q****x 的大作中提到】
: 第一个排序为何不行？
| D***h
发帖数: 183 | 6 肯定可以。
先sort。
keep the current state, city, name set.
对每一行，如果state ！=current state,就输出之前的city， name set，然后update
current state, city, 清空name set, 并且打印新的state;
如果city ！=current city，就打印name set里面的所有name，打印新的city, 并且
update current city，把name set清空；否则把name加入到name set里面。
Cannot print
California, Palo Alto, Alice
California, Palo Alto, Bob
Need to print different levels and print the names of people in the same
city together.
California
Palo Alto
Alice, Bob
【在 q***0 的大作中提到】
:
: Cannot print
: California, Palo Alto, Alice
: California, Palo Alto, Bob
: Need to print different levels and print the names of people in the same
: city together.
: California
: Palo Alto
: Alice, Bob
| s******n
发帖数: 3946 | 7 why not create a tree then first-order visit tree? | q***0
发帖数: 43 | 8
Don't understand, please explain?
【在 s******n 的大作中提到】
: why not create a tree then first-order visit tree?
| f*******t
发帖数: 7549 | 9 我觉得第一题除了用vector存并sort，还可以用类似于radix tree的数据结构 | q***0
发帖数: 43 | 10
How do you sort a m*n array using one column? Do you have to write your own
function or does Java/STL provide it?
【在 f*******t 的大作中提到】
: 我觉得第一题除了用vector存并sort，还可以用类似于radix tree的数据结构
| A**u
发帖数: 2458 | 11 第一题目，建立这么个结构行不
root
/
/
California -- Arizona --Washington
/ / /
/ Phoenix Seattle
/ / /
/ bob bar
Palo Alto--San Francisco--San Diego
/ / /
/ Eve peter
Alice--Foo
这东西好做不 |
|
