djmclaugh
BAN USERNote that a * b = (2 * a) * (b / 2).
So we'll use the recursive formula multiply(a, b) = multiply(2 * a, b / 2) with base case b equal to 0. (We also have to be a bit careful when b is not a multiple of two, in that case we use a * b = a + (2 * a) * ((b  1) / 2)).
This will use O(log(b)) operations. We can optimize a bit and make sure b is the smallest of the two numbers and then we get O(log(min(a, b))).
Here is the code in Java:
int multiply(int a, int b) {
if (Math.abs(a) >= Math.abs(b)) {
return multiplyHelper(a, b);
}
return multiplyHelper(b, a);
}
int multiplyHelper(int largerNumber, smallerNumber) {
if (smallerNumber == 0) {
return 0;
}
if (smallerNumber % 2 == 0) {
return multiplyHelper(largerNumber * 2, smallerNumber / 2);
}
if (smallerNumber > 0) {
retrurn largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
}
retrurn largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
}

djmclaugh
September 07, 2014 I'm assuming that there is a Booking class with an interface like
public class Booking {
//Returns how many days in the season the guest arrives.
public int getArrivalDate();
//Returns how many days in the season the guest leaves.
public int getDepartureDate();
}
I'm also assuming that the departure date must be later than the arrival date.
Here is an O(nlog(n)) solution:
boolean doIHaveEnoughRooms(int numberOfRooms, Collection<Booking> bookings) {
return numberOfRooms >= numberOfRoomsNeeded(bookings);
}
int numberOfRoomsNeeded(Collection<Booking> bookings) {
int n = bookings.size();
int[] arrivals = new int[n];
int[] departures = new int[n];
int i = 0;
for (int d : bookings) {
arrivals[i] = d.getArrivalDate();
departures[i] = d.getDepartureDate();
++i;
}
Arrays.sort(arrivals); // Built in O(nlog(n)) sorting.
Arrays.sort(departures); // Built in O(nlog(n)) sorting.
int aIndex = 0;
int dIndex = 0;
int current = 0; // Current number of guests.
int max = 0; // Max number of guests
while (aIndex < n) {
// You need <= instead of < if you can't use a room the same day the guest leaves.
if (arrivals[aIndex] < departures[dIndex]) {
++aIndex;
++current; // Someone needs a room.
max = Math.max(max, current);
} else {
++dIndex;
current; // Someone vacates a room.
}
}
return max;
}
Note that the bottleneck is the sorting, everything else is simply O(n). So if you use a linear sorting algorithm instead (counting sort seems like a reasonable choice, especially if the season doesn't have too many days and you expect many people to arrive/leave on the same day), you get an O(n) algorithm.
 djmclaugh September 02, 2014Here is a linear solution.
1. Have three variables. "start", "mid", and "end".
2. initialize "start" at 0. initialize "mid" at the index of the first "0" in the string (if the string has no '0's just return the size of the string), and initialize 'end' at the index of second '0' (or the size of the string if there is no second '0').
3. If you flip the '0' at "mid", you get a block of (end  start) '1's.
4. Now start becomes mid + 1, mid becomes end, and end becomes the index of the next '0'.
5. Keep doing thing while keeping track of the max block size until you run out of '0's.
Here is the algorithm in Java:
// I'm assuming that the input string only contains '0's and '1's.
int maxConsecutiveOnesAfterAtMostOneFlip(String s) {
int maxBlockSize = 0;
int start = 0; // The first character of the block.
int mid = s.indexOf('0'); // The first '0' of the block.
if (mid == 1) { // if the string is all '1's.
return s.length();
}
int end = s.indexOf('0', mid + 1); // The first '0' after the block.
while (end != 1) {
maxBlockSize = Math.max(maxBlockSize, end  start);
start = mid + 1;
mid = end;
end = s.indexOf('0', mid + 1);
}
maxBlockSize = Math.max(maxBlockSize, s.length()  start);
return maxBlockSize;
}

djmclaugh
August 28, 2014 You could push the values in a stack while going through the list in order and then print the values as you remove them from the stack: O(n) time and O(n) memory.
You could also keep track of the index of the last printed element and start from the beginning and traverse the list one less than that index until you print the first element: O(n^2) time and O(1) memory. I feel this is not a good solution though.
If you are allowed to alter the linked list as long as you restore it by the end of the algorithm, you can reverse the list (O(n) time O(1) memory), print it in order (O(n) time O(1) memory), and reverse it again (O(n) time O(1) memory) for a total of O(n) time and O(1) memory.
If you must use recursion, then you want something like this:
void printListInReverse(Node* head) {
if (head != NULL) {
printListInReverse(head>next);
cout << head>data;
}
}
Which is basically the first solution but using the stack frame for the function calls instead of a stack for the node values.
 djmclaugh August 26, 2014Brute force BFS solution in Java:
int minNumberOfMoves(String initialPosition) {
if (isSolved(initialPosition)) {
return 0;
}
List<boolean[]> actions = new LinkedList<boolean[]>();
actions.add(new boolean[] { true, true, false, false, false, false, false, false});
actions.add(new boolean[] { true, true, true, false, false, false, false, false});
actions.add(new boolean[] {false, true, false, false, true, true, true, false});
actions.add(new boolean[] {false, false, true, false, false, true, false, false});
actions.add(new boolean[] {false, false, false, true, false, true, false, false});
actions.add(new boolean[] {false, false, false, true, false, false, false, true});
actions.add(new boolean[] {false, false, false, false, false, true, false, true});
actions.add(new boolean[] {false, false, false, false, false, false, true, true});
Set<String> seenPositions = new HashSet<String>();
Set<String> currentPositions = new HashSet<String>();
Set<String> nextPositions = new HashSet<String>();
seenPositions.add(initialPosition);
currentPositions.add(initialPosition);
for (int moveCounter = 1; currentPositions.size() > 0; ++moveCounter) {
for (String current : currentPositions) {
for (boolean[] action : actions) {
String next = performAction(current, action);
if (!seenPositions.contains(next)) {
if (isSolved(next)) {
return counter;
}
seenPositions.add(next);
nextPositions.add(next);
}
}
}
currentPositions = nextPositions;
nextPositions = new HashSet<String>();
}
return 1;
}
String performAction(String position, boolean[] action) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < position.length(); ++i) {
if (action[i]) {
switch (position.charAt(i)) {
case 'N':
result.append('E');
break;
case 'E':
result.append('S');
break;
case 'S':
result.append('W');
break;
case 'W':
result.append('N');
break;
}
} else {
result.append(position.charAt(i));
}
}
return result.toString();
}
boolean isSolved(String s) {
for (int i = 1; i < s.length(); ++i) {
if (s.charAt(0) != s.charAt(i)) {
return false;
}
}
return true;
}

djmclaugh
August 25, 2014 What about "19191919"? Clearly, every 1 can be seen alone or as part of 19, so there is 2^4 = 16 ways to decode the string which is more than 8, the fibonacci number you would get using your algorithm.
What you have to do is find the correct fibonnaci number for consecutive blocks of 1s and 2s and then multiply those numbers. Also, when you encounter a 2, make sure the digit after is 6 or less ("27" can only be decoded one way).
This idea in Java:
public void printDifference(String[] a, String[] b) {
TrieSet setA = new TrieSet(a);
TrieSet setB = new TrieSet(b);
for (String s : a) {
if (!setB.contains(s)) {
System.out.println(s);
setB.add(s); // To avoid printing the same word twice if "a" contains duplicates.
}
}
for (String s : b) {
if (!setA.contains(s)) {
System.out.println(s);
setA.add(s); // To avoid printing the same word twice if "b" contains duplicates.
}
}
}
Here is one possible implementation of the TrieSet class (a "real" implementation would also have methods to remove words from the set and to iterate through the elements, but adding and checking is sufficient for this question):
public class TrieNode {
private Map<Character, TrieNode> children;
private boolean isTerminal;
public TrieNode() {
children = new TreeMap<Character, TrieNode>();
isTerminal = false;
}
public TrieNode getChild(char c) {
return children.getOrDefault(c, null);
}
public TrieNode getOrCreateChild(char c) {
TrieNode child = getChild(c);
if (child != null) {
return child;
}
return addChild(c);
}
private TrieNode addChild(char c) {
TrieNode child = new TrieNode();
children.put(c, child);
return child;
}
public boolean isTerminalNode() {
return isTerminal;
}
public void markAsTerminalNode() {
isTerminal = true;
}
}
public class TrieSet {
TrieNode root = new TrieNode();
public TrieSet() {}
public TrieSet(String[] words) {
for (String s in words) {
add(s);
}
}
public void add(String s) {
TrieNode current = root;
for (int i = 0; i < s.length(); ++i) {
current = current.getOrCreateChild(s.charAt(i));
}
current.markAsTerminalNode();
}
public boolean contains(String s) {
TrieNode current = root;
for (int i = 0; i < s.length(); ++i) {
current = current.getChild(s.charAt(i));
if (current == null) {
return false;
}
}
return current.isTerminalNode();
}
}
The above algorithm with the above data structure has average and worstcase time complexity of "total number of characters" * log("size of the alphabet") (which is simply O(n) if the alphabet is fixed and you are guaranteed that all words are under a certain length). Using a HashSet instead of a TrieSet is also possible and reduces the expected runtime to O(n) no matter what, but increases the worst case to O(n^2).
 djmclaugh August 24, 2014Use the fact that if n is not prime, then n has at least one factor less or equal to the square root of n.
Keep a list of primes so you don't have to check if composite numbers factor n. Expand it as needed.
An implementation in Java:
List<Integer> firstFivePrimesWithTenDigits() {
List<Integer> knownPrimes = new ArrayList<Integer>();
knownPrimes.add(2);
knownPrimes.add(3);
List<Integer> bigPrimes = new ArrayList<Integer>();
for (int i = 1000000001; bigPrimes.size() < 5; i += 2) {
if (isPrime(i, knownPrimes)) {
bigPrimes.add(i);
}
}
return bigPrimes;
}
// Assumes "knownPrimes" is a list of the first k primes from some k >= 2
boolean isPrime(int n, List<Integer> knownPrimes) {
int squareRoot = (int) Math.sqrt(n);
while (knownPrimes.get(knownPrimes.size()  1) < squareRoot) {
addNextPrime(knownPrimes);
}
for (int i = 0; i < knownPrimes.size(); ++i) {
int prime = knownPrimes.get(i);
if (prime >= squareRoot) {
break;
}
if (n % prime == 0) {
return false;
}
}
return true;
}
// Takes in a list of the first k primes for some k >= 2 and makes it a list of the first k+1 primes.
void addNextPrime(List<Integer> knownPrimes) {
for (int i = knownPrimes.get(knownPrimes.size() 1) + 2; true; i += 2) {
if (isPrime(i, knownPrimes)) {
knownPrimes.add(i);
return;
}
}
}
This is a simple approach. More sophisticated solutions can be found by looking up "primality test" online.
 djmclaugh July 23, 2014First, the question tells us to assume that we have all numbers from 1 to n*n EXACTLY once, so your situation cannot happen.
Also, if you're not guaranteed distinct integers, the algorithm does not make any sense. What do you store in arr[5] if one of the 6s is adjacent to 7 but the other one isn't?
I hope that clears up some confusion.
1. In an array, store the position of every integer from 1 to n^2 by simply reading every entry of the matrix.
2. Iterate through the array. At every step, check if the next position is adjacent to the current position. If so, your current sequence's size increases by 1. If not, your current sequence is over. Every time a sequence terminates, if its length is greater than the longest sequence seen so far, remember its length and where it ends.
3. Knowing the size of the longest sequence and on which number it ends, you can easily print the sequence by printing the numbers from "end  length + 1" to "end".
Running the algorithm on the given example looks like this:
input
1 5 9
2 3 8
4 6 7
1. Produce the following array:
[(0,0), (0,1), (1,1), (0,2), (1,0), (1,2), (2,2), (2,1), (2,0)]
2.
Set length counter to 1.
(0,0) is adjacent to (0,1): +1;
(0,1) is adjacent to (1,1): +1;
(1,1) is not adjacent to (0,2): sequence length is 3, our current best, so lets remember the length and that it ended on the 3rd entry. Reset length counter to 1.
(0,2) is not adjacent to (1, 0): sequence length is 1, not our best. Simply reset counter to 1.
(1,0) is not adjacent to (1, 2): sequence length is 1, not our best. Simply reset counter to 1.
(1,2) is adjacent to (2,2): +1;
(2,2) is adjacent to (2,1): +1;
(2,1) is adjacent to (2,0): +1;
(2,0) is the end of the array, so the sequence ends: sequence length is 4, our current best, so lets remember the length and that it ended on the 9th entry.
3.
Our longest sequence has length 4 and ends at 9. So it starts at 9  4 + 1 = 6. So we output 6 7 8 9.
This algorithm has O(n^2) time and space complexity. O(n^2) is optimal for time complexity because you have to at least look at all of the entries, but O(n^2) is not optimal for space complexity. I can't seem to reduce the space complexity without increasing the time complexity however...
In Java:
void printLongestSnake(int[][] matrix) {
int n = matrix.length;
int nSquared = n * n;
Coordinate[] positions = new Coordinate[nSquared];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
positions[matrix[i][j]  1] = new Coordinate(i, j);
}
}
int maxLength = 1;
int maxEnd = 1;
int currentLength = 1;
for (int i = 1; i < nSquared; ++i) {
if (positions[i].isAdjacent(positions[i  1])) {
++currentLength;
} else {
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = i;
}
currentLength = 1;
}
}
if (currentLength > maxLength) {
maxLength = currentLength;
maxEnd = nSquared;
}
for (int i = maxEnd  maxLength + 1; i < maxEnd; ++i) {
System.out.print(i + " ");
}
System.out.println(maxEnd);
}
where Coordinate is the following simple class (you could just use an array of size 2 instead of making a class if you want to be more efficient, but then, you shouldn't be using Java lol)
class Coordinate {
private int x;
private int y;
public Coodinate(int x, int y) {
this.x = x;
this.y = y;
}
public boolean isAdjacent(Coordinate c) {
if (x == c.x && (y == c.y  1  y == c.y + 1) {
return true;
}
if (y == c.y && (x == c.x  1  x == c.x + 1) {
return true;
}
return false;
}
}
I assumed that you want to print the *longest* sequence of of consecutive numbers that are adjacent in the array. If not could you please clarify your question please, thanks.
 djmclaugh July 14, 2014Just read the number from right to left.
In Java:
int longestSequenceOfOnes(int input) {
int max = 0;
int current = 0;
for (i = input; i > 0; i = i >> 1) {
if (i % 2 == 1) {
++current;
} else {
max = Math.max(max, current);
current = 0;
}
}
return Math.max(max, current);
}

djmclaugh
July 11, 2014 vgeeks's 3rd algorithm in java:
boolean twoSum(int[] input) {
int sum = getSum(input);
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
Set<Integer> seen = new HashSet<Integer>();
for (int i = 0; i < input.length; ++i) {
if (seen.contains(target  input[i])) {
return true;
}
seen.add(input[i]);
}
return false;
}
int getSum(int[] input) {
int sum = 0;
for (int i = 0; i < input.length; ++i) {
sum += input[i];
}
return sum;
}
akkaiah.j's solution (assuming nonnegative integers):
(I'm not checking if the two largest integers are greater or equal to the target sum as it isn't necessary and doesn't improve the asymptotic run time)
boolean nonNegativeTwoSum(int[] input) {
sum = getSum(input);
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
int[] candidates = new int[4];
int candidatesFound = 0;
int halfTarget = (target + 1) / 2; // Adding 1 to target in case it is odd. I want it to round up. Needed to guarantee at most 4 candidates (if we round down, [1,1,1,1,1,1] will give us 6 candidates...).
for (int i = 0; i < input.length; ++i) {
if (input[i] >= halfTarget) {
candidates[candidatesFound++] = i;
}
}
for (int i = 0; i < input.length; ++i) {
for (int j = 0; j < candidatesFound; ++j) {
if (input[i] + input[candidates[j]] == target && i != candidates[j]) {
return true;
}
}
}
return false;
}

djmclaugh
July 11, 2014 In java:
String removeDuplicates(String input) {
Set<Character> seen = new HashSet<Character>();
StringBuilder result = new StringBuilder();
for (int i = 0; i < input.length(); ++i) {
char c = input.charAt(i);
if (seen.add(c)) {
result.append(c);
}
}
return result.toString();
}

djmclaugh
July 11, 2014
Repannehbell8, Quality Assurance Engineer at Globaltech Research
Build and maintain relationships with convention vendors. Resolve issues throughout meeting event timelines.Plan room layouts and event programs, schedule ...
Open Chat in New Window
Here is a solution with O(N*log(N)) time and O(N) space. I think the trick to this question is to make an appropriate data structure to represent the medal distribution. I used a hashmap to remember where and by how much the medal count per officer varies.
Ex:
If the medal count is:
My data structure remembers:
Here is my solution in Java:
 djmclaugh September 07, 2014