Two Sigma OA

原帖地址:一亩三分地

OA 5 minutes ago.Still
http://www.1point3acres.com/bbs/ … adio%26sortid%3D311

All tests passed

static int friendCircles(String[] friends) {

if ( null == friends || 0 == friends.length ) return 0;

int n = friends.length;

//queue and visited flag for BFS
Queue queue = new LinkedList();
boolean[] visited = new boolean[n];
//min-heap holds the next friend to process at top
PriorityQueue remaining = new PriorityQueue();

for (int i = 0; i < n; ++i) { visited = false; remaining.offer(i); } //enqueue 0, the first friend enqueue(0, queue, visited, remaining); int circles = 0; while (true) { int cur = queue.poll(); char[] friendsOfCur = friends[cur].toCharArray(); for (int i = 0; i < n; ++i) { if ('Y' == friendsOfCur i != cur !visited) { enqueue(i, queue, visited, remaining); } } //Either all done or move to next circle if (queue.isEmpty()) { circles++; //all done, exit the loop if( remaining.isEmpty() ) break; //otherwise pick up the smallest friend that has not been processed enqueue(remaining.peek(), queue, visited, remaining); } } return circles; } static private void enqueue(int idx, Queue q, boolean[] visited, PriorityQueue remaining ){
q.offer(idx);
visited[idx] = true;
remaining.remove(idx);
}

============================================

static int longest_chain(String[] w) {

if (null == w || w.length == 0) return 0;

//Index words by length. Key: length, value: set of words with given length
//Use TreeMap so that the keys are sorted
TreeMap> wordsByLength = new TreeMap>();

for (int i = 0; i < w.length; ++i) { int wordLen = w.length(); Set wordsOfLen = wordsByLength.get(wordLen);
if (null == wordsOfLen) {
wordsOfLen = new HashSet();
wordsByLength.put(wordLen, wordsOfLen);
}
wordsOfLen.add(w);
}

int longest = 1;

//process the longest word first (using descendingMap)
for (Map.Entry> entry : wordsByLength.descendingMap().entrySet()) {
Set wordsOfLen = entry.getValue();
for (String word : wordsOfLen) {
int chainLenOfTheWord = getChainLenOfTheWord(word, wordsByLength);
longest = Math.max(longest, chainLenOfTheWord);
}
}

return longest;
}

//Make recursive calls.Remove visited (shorter) words for performance
static private int getChainLenOfTheWord(String word, Map> wordsByLength) {

if (1 == word.length()) return 1;//base case

int chainLenOfTheWord = 1;
for (int i = 0; i < word.length(); ++i) { StringBuilder sb = new StringBuilder(word); sb.deleteCharAt(i);//delete char at i String shorter = sb.toString(); Set wordsOfLen = wordsByLength.get(shorter.length());
if (null != wordsOfLen) {
if (wordsOfLen.remove(shorter)) { // remove it, no need to visit it again
int chainLenOfTheShorter = getChainLenOfTheWord(shorter, wordsByLength);
chainLenOfTheWord = Math.max(chainLenOfTheWord, chainLenOfTheShorter + 1);
}
}
}

return chainLenOfTheWord;
}