Anthony Mays
BAN USER 1 Answer Bit Manipulation Exercise
How might you solve this? Write a method that return the number corresponding to a pattern of bits of length n consisting of consecutive 1s of p length and consecutive 0s of q length. The sample input of p=3, q=3,and n=18 should produce the result "000111000111000111" whereas an input of p=4, q=2, and n=15 would produce the result "111001111001111".
 Anthony Mays July 26, 2013 Flag  PURGE
The following is a solution in Java. Assumes that sorted integers are unique. We start by looking at position k since we're guaranteed that the value won't be in a position greater than k. Once we've checked k, we can then do a binary search on the range 0..k1. This solution is O(log k).
public static int findPosition(String[] input, int k) {
if (input == null  input.length == 0  input[0] == "$")
return 1;
if (input[k] == Integer.toString(k))
return k;
return binarySearch(input, k, 0, k1);
}
public static int binarySearch(String[] input, int k, int start, int end) {
if (end < start)
return 1;
int mid = (start + end) / 2;
// Convert string array value to int, if possible
int midValue = 1;
if (input[mid] != "$")
midValue = Integer.parseInt(input[mid]);
// Check mid point
if (midValue == k)
return mid;
// Search low if mid value is greater than k
// or if it is "$"
if (midValue > k  input[mid] == "$")
return binarySearch(input, k, start, mid  1);
// If mid point isn't "$", then search the upper range
else if (input[mid] != "$")
return binarySearch(input, k, mid + 1, end);
return 1;
}

Anthony Mays
July 28, 2013 I'm not sure that your solution is O(log n) in the worst case, and it is not guaranteed to return the right index. The example case would be {1, 99, $, $, $, $, $, $, .....}, where n = 2 and the first n cells contains integers in sorted order.
 Anthony Mays July 28, 2013Here's a brute force implementation in Java. The basic algorithm involves placing the first student in matrix[0][0]. For each successive student, evaluate the shortest distance to the next closest student for each cell position and place the student in the cell with the max shortest distance. I'm convinced a Dynamic Programming solution is probably the best option for this kind of a problem.
public static int[][] placeStudents(int width, int height, int numOfStudents) {
int[][] result = new int[width][height];
Cell c = new Cell();
c.x = 0; c.y = 0;
for (int k = 0; k < numOfStudents; ++k) {
// When k = 0, position will 0,0 in the matrix
result[c.x][c.y] = k + 1;
if ((k + 1) < numOfStudents)
c = evaluateCells(result);
}
return result;
}
public static Cell evaluateCells(int[][] positions) {
double maxCost = 1.0; Cell result = new Cell();
// For each matrix cell
for (int i = 0; i < positions.length; ++i) {
for (int j = 0; j < positions[i].length; ++j) {
if (positions[i][j] > 0) continue;
// Get the distance to the next closest cell
double cost = getCost(i, j, positions);
// If its the max distance, then remember the cell position
if (cost >= maxCost) {
maxCost = cost;
result.x = i;
result.y = j;
}
}
}
return result;
}
public static double getCost(int a, int b, int[][] positions) {
double minDistance = Integer.MAX_VALUE;
for (int i = 0; i < positions.length; ++i) {
for (int j = 0; j < positions[i].length; ++j) {
if (positions[i][j] > 0) {
// Using the Pythagorean theorem to calculate distance between
// coordinates in matrix
double cost = Math.sqrt(Math.pow(Math.abs(a  i), 2) + Math.pow(Math.abs(b  j), 2));
if (cost < minDistance)
minDistance = cost;
}
}
}
return minDistance;
}

Anthony Mays
July 27, 2013 @vgeek
Thanks for your reply! I thought I posted a comment in response so I apologize if it appears twice. The short of it is that I'm having trouble following your logic. Your solution assumes that the input will be unique that that you only need evaluate unique couples. My understanding of the problem assumes that the input can contain all of the same elements such that the number of couples I should report is n(n1)/2 with a difference of 0.
Sticking to your example where arr = {1,2,3,4,5,6,7,8,9}, there are two couples with difference 7, three couples with difference 6, so forth and so on. A correct algorithm should produce the values 2,3,4,5,6,7, and 8.
I pasted your code into codepad.org (paste bTSskmXA) and changed the input to match your example . The output was not what I was expecting. Please let me know if I'm not using your code correctly.
I think you're on to something, but the implementation needs a little work. Thanks!
Here's a C# example. I've tested this against a single element array, an array containing all of the same elements, and against the sample posted above.
public int[] GetMaxInterval(int[] input) {
// Jagged array will store a pair of values for the difference between the two values
int[][] differences = null;
Array.Sort(input);
int maxDiff = input[input.Length1]  input[0];
differences = new int[maxDiff+1][];
for (int i = 0; i < input.Length  1; ++i) {
int j;
for (j = i + 1; j < input.Length; ++j) {
if((j  i) == (input[j]  input[i])) {
continue;
} else {
differences[j  i  1] = new int[] {input[i], input[j  1]};
i = j  1;
break;
}
}
// Check the edge case where the last element of the array is included in the max range.
if(j == input.Length) {
differences[j  i  1] = new int[] {input[i], input[j  1]};
}
}
// Iterated through the jagged array backwards to find the max difference.
for (int i = differences.Length  1; i >= 0; i) {
if (differences[i] != null)
return differences[i];
}
return null;
}

Anthony Mays
July 13, 2013 It's not clear to me how you can achieve O(n lg n) performance for arr = {1, 2, 4, 8, 16, 32, 64}. Doesn't every element have to be compared against another in order to calculate a difference? I do think we can do better than O(n(n1)/2) in the average case by leveraging the fact that the array is sorted. For instance, if arr[arr.length]  arr[0] = 0, then the result is automatically arr.length * (array.length  1) / 2. Of course, I'm only talking about arrays of length greater than 2.
 Anthony Mays July 13, 2013
RepI am randy, 29 year old and I am doing a job. I am doing a job as a plant ...
Repmarkglove17, Associate at Arista Networks
Hi, I am Mark from North Edwards, CA .I am just crazy about dance.I am not professionally trained, but ...
RepShayneLJohnson, Scientific Officer at Cerberus Capital
I'm Shayne and I have a history of sensitivities that range from dietary issues to skin care and other ...
Repjuliaaperez05, Cloud Support Associate at ABC TECH SUPPORT
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
Repcarmenrhargis, Associate at Achieve Internet
Hi, I am Gladys, I live in Florida, USA, I am working as a project manager in a Life’s ...
Repverarfurman, Problem Setter at Cerberus Capital
I am Vera from Bullard USA, I am working as a Violin repairer in a Handyman company. My interest in ...
Repdavisjerryh, Backend Developer at Abs india pvt. ltd.
For the last two years, I am Effectively managing the team’s performance, conducting regular performance reviews and appraisals, and ...
Repangelwilley8, xyz at Asiatic Solutions
I am Angel J. Willey from Gurnee. I am working as a truck driver in Asiatic Solutions company. I also ...
Repkevinlmoses, Animator at Accenture
I am Experienced Building Manager who is an expert in public and industrial safety with a preventative mindset against fire ...
RepI believe in magic, power, aliens, parallel universe, god. I always dream about the powers and out of the world ...
Reppathfisher, Animator at Rack N Sack
I am Pat working in Rack N Sack where I use sequential images to produce the illusion of movement and ...
Repjohnlevans657, Principal Software Engineer at Ask.com
Hi, I am John, from Taxes USA, I am a dedicated, extremely organized, and highly competent Administrative Specialist seeking a ...
Open Chat in New Window
Ah, I see where you're going, I misinterpreted the number ranges. Clever solution, you got my vote.
 Anthony Mays July 29, 2013