cool.fire.ra
BAN USERDude...
stackoverflow . com/ a/ 11897490
This is to check if a player wins as the game progresses. I understand that you are given a snapshot of the grid at any given time and you need to determine who won.
- cool.fire.ra July 08, 2014N: size of array. O(N) time (amortized), O(1) space. A modification of quicksort like many others pointed out.
(semi rigorous) proof for complexity:
At any stage, T(n) = T(a n) + O(n); a<1 at subproblem size n (i.e., we are depending on a smaller problem of size a N). In reality we will have different values of
a
at every stage but lets say its the average value.
on summing up starting from problem size N, we have N + a N + a^2 N + .... + 1 and termination is upon reaching 1 or 0. so, we have: T(N) = (1-a^(N+1)/(1-a))*N.
when N-<inf, T(N) -> N.
O(1) space because it is in place.
package pracPkg;
import java.util.Arrays;
public class NGreaterThanN {
public static void main(String[] args){
int[] arr;
arr = new int[]{3,2,1,9,8,7};
//arr = new int[]{1,4,9,8,7,3,5};
System.out.println(Arrays.toString(arr));
System.out.println(nGn(arr));
}
public static int nGn(int[] arr){
return nGn(arr, 0, arr.length-1, -1);
}
private static int nGn(int[] arr, int start, int end, int bestAns){
if(end< start)
return bestAns;
if(start == end){
if(arr.length - start >= arr[start])
bestAns = arr[start];
return bestAns;
}
int ind = partition(arr, start, end);
if(arr.length - ind >= arr[ind]){
bestAns = arr[ind];
return nGn(arr,ind+1,end,bestAns);
}
else
return nGn(arr,start,ind-1,bestAns);
}
private static int partition(int[] arr, int start, int end){
int pivot = arr[start];
int i = start, j= start+1;
while(j<=end){
if(arr[j]<pivot){
int temp = arr[i+1];
arr[i+1] = arr[j];
arr[j] = temp;
i++;
}
j++;
int temp = arr[i];
arr[i] = pivot;
arr[start] = temp;
}
return i;
}
}
As someone pointed out, if you are swapping subtrees, then it is not possible to handle if one of the input nodes is root. Next, how are the nodes presented to us? Pointers to the treeNodes itself? Do treeNodes also have parent pointers set?
Assuming that we don't have parent pointers and references to treeNodes are inputs, we can do a preorder traversal (equivalent to BFS) and determine the parent nodes and then swap the children.
public class MyTree{
TreeNode root;
public boolean swapSubTrees(TreeNode n1, TreeNode n2){
if(n1 == root || n2==root)
return false;
/*search for parents*/
LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
TreeNode p1=null, p2=null, curr=root;
if(curr!=null)
Q.add(curr);
else
return false;
while(! Q.isEmpty()){
cur = Q.remove();
if(cur.left == n1 || cur.right == n1)
p1=cur;
if(cur.left == n2 || cur.right == n2)
p2=cur;
if(p1 == null || p2 == null){
if(cur.left!=null)
Q.add(cur.left);
if(cur.right!=null)
Q.add(cur.right);
}
else
break;
}
if(p1==null || p2==null)
return false;
else{
if(p1.left == n1)
p1.left = n2;
else
p1.right = n2;
if(p2.left == n2)
p2.left = n1;
else
p2.right = n1;
}
}
public class TreeNode<K,V>{
K key;
V val;
TreeNode left;
TreeNode right;
/* Assume appropriate constructors and insert fns exist*/
}
}
I think it will be N^3/2 (assuming that each row has approx sqrt(N) elements).
- cool.fire.ra May 30, 2014We can do this in O(N) where N is total number of elements.
1. Draw the smallest element from the head of each of each row.
2. Update the head to next element for the element that was last drawn.
3. write to output array.
4. repeat until all elements are read.
public class nWayMerge{
public static void main(String[] args){
int[][] a = new int[][] {{2,5,6},{1,4},{3,11}};
doNWayMerge(a);
}
public static int[] doNWayMerge(int[][] a){
int numRows = a.length;
int[] numCols = new int[numRows];
int totalLen = 0;
for (int i=0;i<numRows; i++){
numCols[i] = a[i].length;
totalLen += a[i].length;
}
int[] b = new int[totalLen];
int[] colInd = new int[numRows];
for (int i=0;i<numRows; i++){
colInd[i] = 0;
}
//actual sorting part
while(1){
int nextMin = Integer.MAX_VALUE, nextMinRow=-1;
for (int i=0; i<numRows; i++){
if(colInd[i] < numCols[i]){
if(nextMin > a[i][colInd[i]]){
nextMin = a[i][colInd[i]];
nextMinRow = i;
}
}
}
if(nextMinRow == -1){
//no more remaining elements.
break;
}
else{
b[j] = nextMin;
colInd[nextMinRow ] = colInd[nextMinRow ]+1;
}
}
return b;
}
}
I'm assuming this is the description:
- cool.fire.ra July 10, 2014From: https: //github . com/ rohitsinha54/ ArrayHopper
Problem Description
You are given an array of integers with values greater than or equal to 0, for example:
[5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
You will develop and implement an algorithm to traverse the array in the shortest number of “hops” starting at index 0, where traversal is defined as follows:
Start at the first (0th) index of the array, look at the array value there, and you can hop forward to any array index that is no farther than that value away. So in this example, you start at index 0 containing the value 5 and can now consider hopping to any of indices 1 through 5 inclusive.
If you choose to hop to index 3, it contains the value 4 and you can next hop up to 4 more spots from your current index (3)—so you now consider indices 4 through 7 as next steps in your sequence.
Once you can legally hop beyond the last array element, you have successfully traversed the array.
Your job is to compute the minimum-length sequence of hops that successfully traverses the array starting from index 0, or determine that there is no such sequence.
Your algorithm must identify a minimum-hops solution, but can choose arbitrarily among solutions with the same number of hops.