benny.chaucc
BAN USERI spent an hour, still haven't find a better solution (O(n) time and O(1) space).
I can only optimize your 2nd approach by storing a boolean instead of count for smaller storage.
Why would this even work?
for
int[] a = { 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4 };
The output from this code would be 3.
- benny.chaucc August 27, 2014Nice, but map.containsValue might not be constant, is it? If it's not, then it's not O(n), it might be linear, so it would be O(n^2).
containsKey is constant.
My solution is using a separate HashSet:
String findStartValue(List<Step> steps)
{
HashSet<String> hsStart = new HashSet<String>();
for(Step step : steps)
{
if(hsStart.contains(step.start))
hsStart.remove(step.start);
else
hsStart.add(step.start);
if(hsStart.contains(step.finish))
hsStart.remove(step.finish);
}
return (String) hsStart.toArray()[0];
}
Then it's O(n).
- benny.chaucc August 13, 2014Many people A always win, this is not the case. It depends on the randomness of the gold distribution, we can only maximize.
Here is a test run with 100 pots each time, and run 10000 times.
B consistently wins around 35% of the time, I did 10 different runs, so that's 100,000 times.
The actual % depends many variables, including, number of integers, and the random range of each integer.
Here is a prove: 1 3 1, A loses no matter what.
Here is the full code you can run it yourself, have fun.
static int count = 0;
public static void main(String[] args)
{
for (int j = 0; j < 10000; j++)
{
List<Integer> a = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0; i < 100; i++)
{
int temp = r.nextInt(5) + 1;
a.add(temp);
System.out.print(temp);
}
System.out.println();
game(new LinkedList<Integer>(a), 0, 0);
}
System.out.println("b wins " + count / 10000d * 100 + "%");
}
public static void game(LinkedList<Integer> ll, int a, int b)
{
if (ll == null)
return;
if (ll.size() == 0)
printResult(a, b);
else if (ll.size() == 1)
printResult(a + ll.poll(), b);
else if (ll.size() == 2)
{
int head = ll.poll();
int tail = ll.poll();
if (head >= tail)
printResult(a + head, b + tail);
else
printResult(a + tail, b + head);
} else
{
a = optimalPick(ll, a);
b = optimalPick(ll, b);
game(ll, a, b);
}
}
public static int optimalPick(LinkedList<Integer> ll, int playerGold)
{
int gain1 = ll.peekFirst() - (Math.max(ll.peekLast(), ll.get(1)));
int gain2 = ll.peekLast() - (Math.max(ll.peekFirst(), ll.get(ll.size() - 2)));
if (gain1 > gain2)
return playerGold + ll.pollFirst();
else
return playerGold + ll.pollLast();
}
public static void printResult(int a, int b)
{
System.out.println("A has " + a);
System.out.println("B has " + b);
if(b > a)
count++;
}
public static void main(String[] args)
{
Integer [] input = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};
findEvenOccur(input);
}
public static void findEvenOccur(Integer [] input){
if(input == null || input.length == 0)
return;
HashMap<Integer, Boolean> countingMap = new HashMap<Integer, Boolean>();
for(Integer i : input)
{
Boolean isOdd = countingMap.get(i);
if(isOdd == null)
isOdd = false;
countingMap.put(i, isOdd ^ true); //even occurence will have false, odd will have true.
}
for(Integer i : countingMap.keySet())
{
if(!countingMap.get(i))
System.out.println(i);
}
}
O(n) time
O(k) for the hashmap where k = the range of the numbers, and it's k <= n -3. Assume large n and small k, then it's constant.
Your answer failed 5) e getMostRecent() since you moved the elements in the list in the delete.
You should put null object into the list for delete instead of replacing with end object. The list will keep growing forever, but there is no requirement for space. Only O(1) time complexity
First of all, we should take k1, k2, k3 as unrelated keys, because that's the usual case for database.
Second, any data structure with hashtable woudn't be efficient because it's super slow for iteration, eg mysql doesn't use hashtable for index.
Here is my take.
1. Since this is related to database, we should use b+ tree for k1 with leaves pointing to pages (disk page size) where array of k1-sorted items are stored.
// Make use of locality of reference with O(log n) -> super fast for all operation even iteration.
2. For k2 and k3, we should use b+ tree as well, but the leaves are pointing at pages where array of k2/k3 sorted references are stored. These references points to the page id and array index of the item from (1).
// Slower than k1 for iteration, but still make use of locality of reference on all nodes except leaves. The references are still on pages, which is fast, but access item data will be random access. Searching is same as k1.
If speed is the main concern for k2 and k3 iteration, then you can store k2 and k3 data as k1, but 3 times the data.
static int[][] cache;
//find biggest value in cache
static int max = -1;
static int max_i = -1;
static int max_j = -1;
public static void main(String[] args)
{
int array[][] = {{1, 5, 9},
{2, 3, 8},
{4, 6, 7}};
solve(array);
System.out.println();
}
static void solve(int[][] mat)
{
cache = new int[mat.length][mat.length];
for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
cache[i][j] = -1;
}
}
for (int i = 0; i < mat.length; i++)
{
for (int j = 0; j < mat.length; j++)
{
findSeqLength(mat, i, j);
}
}
int start = mat[max_i][max_j];
//walk the result.
for (int i = 0; i <= max + 1; i++)
{
System.out.print(start + i);
}
}
static void findSeqLength(int[][] mat, int i, int j)
{
//out of bound
if (i < 0 || i > mat.length - 1 || j < 0 || j > mat.length - 1)
{
return;
}
//checked
if (cache[i][j] != -1)
{
return;
}
//check
peek(mat, i, j, i, j + 1);
peek(mat, i, j, i + 1, j);
peek(mat, i, j, i - 1, j);
peek(mat, i, j, i, j - 1);
}
static void peek(int[][] mat, int i, int j, int target_i, int target_j)
{
if (target_i < 0 || target_i > mat.length - 1 || target_j < 0 || target_j > mat.length - 1)
{
return;
}
if (mat[target_i][target_j] - 1 == mat[i][j])
{
int temp = cache[target_i][target_j];
if (temp == -1)
{
findSeqLength(mat, target_i, target_j);
}
temp = cache[target_i][target_j];
if (cache[i][j] <= temp)
{
cache[i][j] = temp + 1;
if (cache[i][j] > max)
{
max = cache[i][j];
max_i = i;
max_j = j;
}
}
}
}
Fully testable code
- benny.chaucc August 12, 2014
Actually, this is O(n) time and O(1) space.
- benny.chaucc August 27, 2014The space needed is the range of Integer which is a constant. Max range is Integer.MAX_VALUE - Integer.MIN_VALUE + 1.
You need O(n+k) time and O(k) space.
If n is large, then it's O(n) time and O(1) space.