Mark
BAN USERMSB : the result of the final. If a team from the left bracket wins, put 0 in MSB. Otherwise, 1.
MSB-1 : the result of the semi-final of the left bracket.
MSB-2 : the result of the semi-final of the right bracket.
the next four bits are the results of quarter finals.
In this way, make an integer value S for scores, P for predictions.
~(S^P) shows how many predictions were correct. Just the count the 1 in ~(S^P) and that's the number of correct predictions.
If the problem means {1, 2, 3, 4, 5} --> {1, 3, 5, 2, 4},
my code is as follows:
(By the way, you were asked this many questions in one day interview??)
import java.util.Arrays;
public class JE5 {
public static void main(String[] args) {
int[] input1 = {2, 4, 1, 3, 6, 5};
int[] input2 = {2, 1, 3, 5, 7, 9};
int[] input3 = {0};
int[] input4 = {1, 2, 3, 3, 6, 6};
sortByEvenOdd(input1);
sortByEvenOdd(input2);
sortByEvenOdd(input3);
sortByEvenOdd(input4);
System.out.println(Arrays.toString(input1));
System.out.println(Arrays.toString(input2));
System.out.println(Arrays.toString(input3));
System.out.println(Arrays.toString(input4));
}
public static void sortByEvenOdd(int[] input) {
int ptr = 0;
int even = 0;
while(ptr < input.length) {
if(input[ptr]%2 == 0)
even++;
else
swapDownward(input, ptr, even);
ptr++;
}
}
public static void swapDownward(int[] input, int ptr, int num) {
for(int i=0; i<num; i++)
swap(input, ptr-i, ptr-i-1);
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
In this problem, we don't have to care about higher digits over the lowest 0, 1 sequence when adding 1 (or smaller numbers) to the number. For example,
11010100 --> 1101 0100 (the lowest 0,1 sequence happens in LSB+3 digit)
all we have to do is to find the next highest integer of 0100, and add 1101 on top of it.
It is because 01xx pattern can be increased to 10xx pattern and it is guaranteed that we can find 10xx pattern which has the same number of 1's as that of 01xx pattern.
(In other words, if we add too big number so that 1101 part is changed, it shouldn't be the next highest number)
For example, 0110 --> 1001, 0101 --> 1001.
Notice that we cannot use 01abcd --> 10abcd, as shown in the case 0110 --> 1001.
It is because that if we push a sequence of 1s to LSB side, we can get lower number.
For example, 011100 --> 101100 (but is this the lowest? No. push 11 to LSB) --> 100011 (now it is the lowest among all 6 digit number starting with 10 and having 3 1s)
Getting the next lowest number is similar. Just 1 and 0 exchanged.
My code is as follows:
public class JE2 {
public static void main(String[] args) {
int[] input = {0x23, // 0100 0011
0x84, // 0111 0100
0x5A, // 0101 1010
0x01, // 0000 0001
0x7FFFFFFE // 0111 1111 1111 1111 1111 1111 1111 110
};
for(int i : input) {
int low = getNextLowest(i);
int high = getNextHighest(i);
System.out.println((low != -1 ? Integer.toBinaryString(getNextLowest(i)) : "Not available")
+ " --> " + Integer.toBinaryString(i)
+ " --> " + (high != -1 ? Integer.toBinaryString(getNextHighest(i)) : "Not available"));
}
}
public static int getNextHighest(int n) {
if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
// read from LSB, ignore first 0 sequence, pass through 1's until finding 0.
int count0 = 0, count1 = 0;
while(n%2 == 0) {
n >>= 1;
count0++;
}
while(n%2 == 1) {
n >>= 1;
count1++;
}
if(count0 + count1 == 31) // assuming 32 bit integer, ignoring the sign bit
return -1;
n += 1; // change 0 to 1
n <<= 1 + count0; // append 1 + count0 0s
for(int i=0; i<count1-1; i++) { // append (count1 - 1) 1s
n <<= 1;
n += 1;
}
return n;
}
public static int getNextLowest(int n) {
if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
// read from LSB, ignore first 1 sequence, pass through 0's until finding 1.
int count0 = 0, count1 = 0;
while(n%2 == 1) {
n >>= 1;
count1++;
}
if(n == 0) return -1; // if there is no 1 any more, can't find the next lowest number with the same number of 1's
while(n%2 == 0) {
n >>= 1;
count0++;
}
n -= 1; // change 1 to 0
for(int i=0; i<count1+1; i++) { // append (count1 + 1) 1s
n <<= 1;
n += 1;
}
n <<= count0 - 1; // append count0 - 1 0s
return n;
}
}
Output is
11100 --> 100011 --> 100101
10000010 --> 10000100 --> 10001000
1011001 --> 1011010 --> 1011100
Not available --> 1 --> 10
1111111111111111111111111111101 --> 1111111111111111111111111111110 --> Not available
I just assume
- the method should return all possible sets of intervals which overlap
- [0, 3] [3, 6] are regarded as overlapped
For the follow up question, I would need the definition of "maximum"
Is it for the length of overlap or the count of intervals which overlap?
In either case, I can get it easily from the returned sets.
import java.util.*;
public class JE19 {
// Given a set of intervals (time in seconds) find the set of intervals that overlap.
// Follow-up: what if we were to find the interval with maximum overlap
// input : array of class Interval
// output : array of array of class Interval (overlap)
// interval is inclusive. [1, 3] [3, 6] --> overlapped
public static void main(String[] args) {
ArrayList<Interval> input = new ArrayList<>();
input.add(new Interval(0, 3));
input.add(new Interval(4, 6));
input.add(new Interval(2, 5));
//input.add(new Interval(3, 8));
ArrayList<ArrayList<Interval>> res = findSetOfIntervalsOverlapped(input);
for(ArrayList<Interval> outer : res) {
for(Interval inter : outer) {
System.out.print(inter);
}
System.out.println();
}
}
static class Interval {
int min, max;
Interval(int min, int max) {
this.min = min;
this.max = max;
}
public String toString() {
return "[" + min + ", " + max + "]";
}
}
public static ArrayList<ArrayList<Interval>> findSetOfIntervalsOverlapped(ArrayList<Interval> list) {
int n = list.size();
ArrayList<ArrayList<Interval>> res = new ArrayList<>();
for(int i=0; i<n; i++) {
int size = res.size();
for(int j=0; j<size; j++) {
if(isOverlapped(list.get(i), res.get(j))) {
if(res.get(j).size() == 1) {
ArrayList<Interval> newitem = new ArrayList<>();
newitem.add(res.get(j).get(0));
newitem.add(list.get(i));
res.add(newitem);
}
else {
res.get(j).add(list.get(i));
}
}
}
ArrayList<Interval> newitem = new ArrayList<>();
newitem.add(list.get(i));
res.add(newitem);
}
int m = res.size();
for(int i=0; i<m; i++) {
if(res.get(i).size() == 1) {
res.remove(i);
i--;
m--;
}
}
return res;
}
public static boolean isOverlapped(Interval inter, ArrayList<Interval> list) {
boolean bOverlapped = true;
for(Interval i : list)
if(inter.min > i.max || inter.max < i.min) {
bOverlapped = false;
break;
}
return bOverlapped;
}
}
I created an array of ArrayList of each alphabet's position.
To find a word, first locate the position of the word's first alphabet and start to explore 8 directions from it.
O(n) to create the array + 8*O(length of the word to find) to search the matrix.
public class JE16 {
public static void main(String[] args) {
// find a word in 2D array
char[][] matrix = {{'p', 'b', 's', 'd'},
{'o', 'o', 'p', 't'},
{'l', 'b', 'a', 'd'},
{'e', 'r', 'l', 'd'}};
char[] word1 = {'r', 'a', 't'};
char[] word2 = {'p', 'o', 'l', 'e'};
char[] word3 = {'d', 'a', 'b'};
char[] word4 = {'l', 'o', 's'};
char[] word5 = {'l', 'a', 'p', 's'};
char[] word6 = {'b', 'o', 'b'};
char[] word7 = {'a', 'b', 'c'};
System.out.println(Arrays.toString(word1) + " : " + (findWord(matrix, word1) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word2) + " : " + (findWord(matrix, word2) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word3) + " : " + (findWord(matrix, word3) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word4) + " : " + (findWord(matrix, word4) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word5) + " : " + (findWord(matrix, word5) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word6) + " : " + (findWord(matrix, word6) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word7) + " : " + (findWord(matrix, word7) ? "Found" : "Not Found") );
}
static boolean findWord(char[][] matrix, char[] word) {
int m = matrix.length, n = matrix[0].length; // m rows, n cols
ArrayList<Coord>[] matrixdata = new ArrayList[26];
for(int i=0; i<26; i++)
matrixdata[i] = new ArrayList<Coord>();
// Create ArrayList
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) {
matrixdata[matrix[i][j] - 'a'].add(new Coord(j, i));
}
// Find the word
Coord[] unitvector = {new Coord(-1, 0), new Coord(-1, 1), new Coord(0, 1), new Coord(1, 1),
new Coord(1, 0), new Coord(1, -1), new Coord(0, -1), new Coord(-1, -1) };
for(int i=0; i<matrixdata[word[0]-'a'].size(); i++) {
int startx = matrixdata[word[0]-'a'].get(i).x;
int starty = matrixdata[word[0]-'a'].get(i).y;
// explore 8 different directions
for(int j=0; j<8; j++) {
if(boundCheck(unitvector[j], startx, starty, n, m, word.length)) {
boolean bFound = true;
for(int k=1; k<word.length; k++) {
if(matrix[starty+k*unitvector[j].y][startx+k*unitvector[j].x] == word[k])
continue;
else {
bFound = false;
break;
}
}
if(bFound) {
System.out.println("start : (" + startx + "," + starty + ") direction : (" + unitvector[j].x + "," + unitvector[j].y + ")");
return true;
}
}
}
}
return false;
}
public static boolean boundCheck(Coord unitvector, int startx, int starty, int MaxX, int MaxY, int length) {
if(unitvector.x > 0 && MaxX-startx < length || unitvector.x < 0 && startx+1 < length)
return false;
if(unitvector.y > 0 && MaxY-starty < length || unitvector.y < 0 && starty+1 < length)
return false;
return true;
}
}
I think sorting and find consecutive numbers would be the best way.
public class JE15 {
public static void main(String[] args) {
// Find the longest consecutive numbers from input array
int[] input = {4, 5, 13, 33, 32, 10, 11, 34, 12, 31, 14};
int[] res = findLongestConsecNum(input);
System.out.println(Arrays.toString(res));
}
static int[] findLongestConsecNum(int[] input) {
// sorting and find the longest consecutive num : O(nlogn) + O(n)
// scan all numbers if a number belongs to certain consecutive chain : 1+2+3+...+n-1 = O(n^2)
Arrays.sort(input);
int[] temp = new int[input.length];
int[] res = new int[input.length];
temp[0] = input[0];
int count=1, maxcount = -1;
for(int i=1; i<input.length; i++) {
if(input[i]-input[i-1] != 1) {
if(count > maxcount) {
maxcount = count;
for(int j=0; j<temp.length; j++) {
res[j] = temp[j];
}
}
count = 0;
}
temp[count++] = input[i];
}
return Arrays.copyOf(res, maxcount);
}
}
I just do depth-first search from the difference matrix (barcode bit difference)
public class JE13 {
public static void main(String[] args) {
//
int numBox = 5;
int bcLength = 6;
int barcode[][] = { {1,1,1,1,1,1},
{0,1,1,0,1,0},
{1,1,0,0,0,1},
{1,1,1,1,0,0},
{1,0,0,0,0,0} };
int dist[][] = calcDist(barcode);
for(int i=0; i<dist.length; i++) {
for(int j=0; j<dist[0].length; j++) {
System.out.print(dist[i][j] + " ");
}
System.out.println("");
}
// find box groups
int boxgroup[] = new int[numBox];
for(int i=0; i<numBox; i++)
boxgroup[i] = -1;
int groupnum=0;
for(int i=0; i<numBox; i++) {
if(boxgroup[i] < 0) {
boxgroup[i] = groupnum;
SearchGroup(dist, boxgroup, i, groupnum);
groupnum++;
}
}
System.out.println("Group number is " + groupnum);
for(int i=0; i<numBox; i++)
System.out.println("Box " + i + " : " + boxgroup[i]);
}
static int[][] calcDist(int[][] barcode) {
int[][] dist = new int[barcode.length][barcode.length];
for(int i=0; i<barcode.length; i++) {
for(int j=i; j<barcode.length; j++) {
int d=0;
for(int k=0; k<barcode[0].length; k++) {
if(barcode[i][k] != barcode[j][k])
d++;
}
dist[i][j] = dist[j][i] = d;
}
}
return dist;
}
static void SearchGroup(int[][] dist, int[] boxgroup, int n, int groupnum) {
for(int i=0; i<dist[n].length; i++) {
if(i!=n && dist[n][i] <= 2 && boxgroup[i]<0) {
boxgroup[i] = groupnum;
SearchGroup(dist, boxgroup, i, groupnum);
}
}
}
}
public class JE8 {
public static void main(String[] args) {
int input[][] = { { 0,0,0,1,1,1,1,1,1,0,0,0,1,1 },
{ 1,1,1,0,0,0,1,0,1,1,1,1,1,0 },
{ 1,1,0,0,0,1,1,1,1,1,1,1,0,0 },
{ 0,0,1,1,1,1,0,0,0,0,1,1,1,1 },
{ 0,0,1,1,0,0,0,0,1,1,0,0,0,0 },
{ 1,1,0,0,0,1,0,0,0,0,0,1,1,0 } };
// find the maximum rectangular area covered by 0
int MaxX = input[0].length;
int MaxY = input.length;
int maxM = -1, maxN = -1, maxArea = -1;
for(int i=0; i<MaxY; i++) {
for(int j=0; j<MaxX; j++) {
int lx, rx, uy, dy;
if(input[i][j] == 0) {
// grow horizontally first
lx=j-1;
rx=j+1;
while(lx>=0 && input[i][lx]==0) lx--;
lx++;
while(rx<MaxX && input[i][rx]==0) rx++;
rx--;
// check vertically
uy=i-1;
dy=i+1;
// Go upward, see if horizontally covered with 0
while(uy>=0 && input[uy][j]==0) {
int minx2=j-1, maxx2=j+1;
while(minx2>=0 && minx2>=lx && input[uy][minx2]==0) minx2--;
minx2++;
while(maxx2<MaxX && maxx2<=rx && input[uy][maxx2]==0) maxx2++;
maxx2--;
if(minx2>lx) lx = minx2;
if(maxx2<rx) rx = maxx2;
uy--;
}
uy++;
// Go downward, see if horizontally covered with 0
while(dy<MaxY && input[dy][j]==0) {
int minx2=j-1, maxx2=j+1;
while(minx2>=0 && minx2>=lx && input[dy][minx2]==0) minx2--;
minx2++;
while(maxx2<MaxX && maxx2<=rx && input[dy][maxx2]==0) maxx2++;
maxx2--;
if(minx2>lx) lx = minx2;
if(maxx2<rx) rx = maxx2;
dy++;
}
dy--;
int areax = rx-lx+1;
int areay = dy-uy+1;
int area = areax*areay;
System.out.println("("+j+","+i+") area : (" + areax + "," + areay + ")");
if(area>maxArea) {
maxArea = area;
maxM = areax;
maxN = areay;
}
}
}
}
System.out.println("Max area : (" + maxM + "," + maxN + ")");
}
}
From all zeros, start to grow rectangular region.
If I can tell a zero covered region is convex or concave, I would be able to save more time as I can start only one 0 in a convex region; that is, if I get an area from one 0 of a convex region, starting from all other zero will yield the same result.
public class JE2 {
public static void main(String[] args) {
// A - B
// A and B are an array of digits.
int A[] = {1, 0, 0, 3, 7, 5, 2};
int B[] = { 4, 2, 1, 0};
int C[];
C = LongSubtraction(A, B);
for(int i=0; i<C.length; i++)
System.out.print(C[i]+" ");
System.out.println("");
}
static int[] LongSubtraction(int[] a, int[] b) {
int[] c;
c = new int[a.length];
int borrow = 0;
for(int i=0; i<a.length; i++) {
int sub = a[a.length-1-i]-borrow - (i>=b.length? 0 : b[b.length-1-i]);
borrow = 0;
if(sub < 0) {
sub += 10;
borrow = 1;
}
c[c.length-1-i] = sub;
}
return c;
}
}
RepLooking for the best child development center in Charlotte? Pal A Roos provide summer camp for children Charlotte. Our experienced ...
My algorithm is as follows:
First of all, I assume the integers in the array and K are nonnegative numbers.
I use a hash table to store numbers as a key and the count of that number as a value.
PseudoCode
From the two loops, I think the complexity is O(n * K).
- Mark February 06, 2014