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..k-1. 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, k-1);
}
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;
}
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;
}
@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(n-1)/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.Length-1] - 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;
}
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(n-1)/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
RepDustinSeals, Accountant at 247quickbookshelp
I am Dustin . Speech-language pathologist in Standard Brands Paint Company. I diagnose and swallow problems. I work with both children ...
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 ...
Repsherykasper, Accountant at A9
Bonjour, je travaille dans une entreprise en tant que caissier. J'habite à Maysville mais je suis en fait d ...
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 ...
Repselindareese, Animator at Agilent Technologies
I am Selinda a Music teacher and composer with 6+ years of experience with an in depth knowledge of music ...
Repfanniepaisley, Computer Scientist at ABC TECH SUPPORT
Fannie Parsley, and I'm working as a Cartographer. And nowadays I am doing a new experiment on best tantrik ...
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 ...
Replisapyara, abc at 247quickbookshelp
I am motivated and organized professional with proven years of experience in mail services and industry having vast experience as ...
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 ...
Replonnacribbs, DIGITAL MARKETING at Athena Health
I am a Market Research Manager responsible for selecting the appropriate research methodology and supporting techniques to meet a defined ...
Repivaharvie, Production Engineer at BMO Harris Bank
Je suis Iva, professeur de musique et compositeur avec plus de 6 ans d'expérience avec une connaissance approfondie de ...
Repjenniferdray9, Accountant at ABC TECH SUPPORT
Hi I am Jennifer D. Ray from san Diego.Currently i am working as a parts salesperson in Rite solution ...
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 ...
RepMariaBJiles, Accountant at A9
I am working as a team leader in a development software company. I am creative in learning how to crochet ...
RepJennifer Crystal, Accountant at US
As I am an artist at Silverstone Spark have a creative mind and am a seasoned professional artist who focuses ...
Repkylecfarrell, Personnel at Bocada
Property custodian with a reputed organization and help in keeping accurate check over the supplies and inventory of materials and ...
Repriyanahobett, Sales Development Representative at Capgemini
I am Riyana , driven market researcher with over years of experience at Awthentikz , analyzing information in order to construct profiles ...
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 ...
RepLuciaLuci, Animator at Barclays Capital
I am Lucia, a Neuropsychologist in Philadelphia USA . aiming to understand how behavior and cognition are influenced by brain function ...
RepHey, I am Margaret Salas, and I am working as a Web Developer Manager. And nowadays I am doing a ...
Repamayalopez800, Accountant at A9
I am Amaya ,working in the field of training and development coordinator for three years, focusing on teaching English as ...
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 ...
Ah, I see where you're going, I misinterpreted the number ranges. Clever solution, you got my vote.
- Anthony Mays July 29, 2013