还没看你的codes,不过感觉set不好,因为最后的输出是要求顺序的。
我想的与lanti一样,用list与map结合。for each string, convert to small case
and bucket sort, use the converted string as key in map, value is the index
in arraylist, maintain/update the list by using this index.
the result is the arraylist.
IMHO, HashSet+ArrayList+从后往前扫描 is the best solution. Time complexity
is log(n+m), n is num of words, m is num of anagrams. The space complexity
is log(m).
Set set = new HashSet();
List list = new ArrayList();
for( int i = words.size()-1; i >= 0; i-- ) {
String sortedWord = sort( words.get( i ).toLowerCase() );
if ( !set.contains( sortedWord ) ) {
set.add( sortedWord );
list.add( word );
}
}
Collections.reverse( list );
return list;
我觉得你没有理解人家的思路。这里是我的Java实现,仅供参考。
//- 5.2.3 Generation with minimal changes
package mylib;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Perm implements Iterable>, Iterator> {
final int n;
final int pos[];
final Integer perm[];
final boolean dir[];
final T[] data;
int cnt;
public Perm(List data) {
this.n = data.size();
pos = new int[n];
perm = new Integer[n];
dir = new boo... 阅读全帖
顺着楼上的思路解一题:
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
public class DeepIteratorImpl2 {
private int cursor;
private List elements;
// Constructor
public DeepIteratorImpl2(Collection> c) {
if (c == null) {
throw new IllegalArgumentException("Invalid input
Collection of Data");
}
this.cursor = 0;
this.elements = new ArrayList(... 阅读全帖
综合楼上的解答,我试着写了一个。
/**
* find all the prime up to n(including n)
*/
public static List findPrimes(int n){
List res = new ArrayList();
if (n <= 1) return res;
// create a boolean array to track whether a number
// is a prime or not
boolean[] primeTrack = new boolean[n+1];
for (int i = 2; i <= n; i++){
primeTrack[i] = true;
}
int upper = (int)Math.sqrt(n);
for (int i = 2; i <= upper; i++){
for (int j = i * i; j <= n; j +=... 阅读全帖
The Python is super, but if you do not know it, try to refer java below:
public List BinaryOutput(String input) {
if (input == null || input.empty())
return null;
List output = new ArrayList();
List temp = new ArrayList("");
for (int i = 0; i < input.length(); i++) {
output.clear();
for (String s : temp) {
if (input.charAt(i) == '?') {
output.add(s + '0');
output.add(s + '1');
}
else {
outpu... 阅读全帖
我把重复的位置记下来,从第7个开始,整体的string就是6部分的string合起来。
但是每次都是
Output Limit Exceeded
不知道为什么。。。
题目是:
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
--------------------------------------------------------------
public String count... 阅读全帖
一老印,电面迟到15分钟,打过来也不花两分钟介绍一下team之类的,直接上题。。
1) Can you explain dependency injection with an example, in java.
我一下子懵了,听都没听说过这个东西,什么也扯不出来,只好老实承认没听说过。。
事后google了一下,好像是Spring framework里面的一个概念。。
2) Can you create memory leak with a sample program.
也是完全没准备过,想了两分钟想不出什么来,老印直接开始问下题
3) What do you think is the output of this sample program
public class MyThread implements Runnable {
String myString = "Yes ";
public void run() {
this.myString = "No ";
}
public static void main(String[] args) {
MyThread t ... 阅读全帖
差不多
它们说的是类似这种的做法
List list = new ArrayList();
但是问题在于,我不能确定里面的element一定是String
完全可以是其它的东西
有挨滴用了1.7的简写方式
List list = new ArrayList<>();
然后在纽约阿妈总的某个人物,举出了guava的类和方法
which是第三方google提供的类库
但是我不认为对于没有经验的人来说是必需掌握的
描述得看不懂啊。写了个感觉比较简明的,就是对所有不可再分的区间进行计数。
排序O(nlogn)+查找O(2*nlogn)+计数O(n*m),其中m是平均区间分割数。
List mostOverlapped(Interval[] ints) {
Set set = new HashSet();
for (Interval itv : ints) {
set.add(itv.start);
set.add(itv.end);
}
// all candidate intervals;
List ends = new ArrayList(set);
Collections.sort(ends);
int max = 0;
// count overlapped times of each candidates
int[] counts = new int[ends.size()];
for (i... 阅读全帖
没签NDA神马的,攒人品了~
电面:
1. 给一个矩阵如下:
a b c d
e f g h
i j k l
m n o p
要求按如下方式打印:
a f k p
b g l
c h
d
e j o
i n
m
2. 设计题:
如果要给每个Pin加上一个price tag,怎么去evaluate这是否work?
(1) A/B testing -> 可以有好几种,讨论优劣性
(2) metrics to monitor -> click rate, impression, return user ratio, etc
上门:
1. 假设Pinterest的更新系统只能显示3条更新,怎么设计?更新可以是:用户评论、
加新的pin,repin等等,一共可能有一千多种。讨论各种方法的优劣性
回答:a ranking problem...
2. 给如下的数据格式:
比如有一组数据:
1, 3, 100
2, 4, 200
5, 6, 300
。。。
这些数据时间点可能有重合。在时间段2~3之间,value的和是100+200 = 30... 阅读全帖
public void printPrimeNum(int num) {
List list = new ArrayList();
//1
int sqrt = (int) Math.round(Math.sqrt(num));
//2
for (int i = 2; i <= sqrt; i++) {
boolean isPrime = true;
for (int j : list) {
if (i % j == 0) isPrime = false;
}
if (isPrime) list.add(i);
}
//3
List temp = new ArrayList();
for (int i = sqrt + 1; i <= nu... 阅读全帖
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator myIterator;
private final Class eleType;
private final Iterator empty = new ArrayList().iterator();
Given an array (assume numbers, no duplicate),
print all its combinations.
My code clearly generates duplicates. :-(
public static void combination(ArrayList data)
{
combination(data, 0);
}
private static void combination(ArrayList data, int index)
{
if (index >= data.size())
return;
printArrayUpToIndex(data, index);
for (int i=index; i
{
swap(data, index, i);
combi... 阅读全帖
你的code似乎有个bug: while(true)没有条件退出,进入死循环.
我觉得你flip bit的那段code有些问题,它并没有正确地flip, list.get(i)是?的index
,用它来跟0/1比较应该是不正确的.
我把它改成这样,用shift bit来做,不知有没有更好的方法.
public static List genMatchers(String str) {
List results = new ArrayList();
if (str != null && str.length() != 0) {
List questionMarkPositions = new ArrayList();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c... 阅读全帖