nk
BAN USERYou dont need any stack or any memory for this, its merely a linked list pointers play. This runs in O(1) memory and O(N) time which modifies the linked list in place
public class Solution {
public Node reverseLinkedListWord(Node n) {
Node curr = n, prev = null, next = null;
while(curr != null) {
if(curr.value == ' ') {
prev = curr;
curr = curr.next;
continue;
}
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return curr;
}
}
Couple of assumptions before we begin:
1) Will the string always have equal number of ( and )? If not then should we add extra missing braces to balance them? Thats the approach code below takes and runs in O(N) memory and O(N) time
public class Solution {
public String balance(String str) {
if(str == null || str.isEmpty() || (str.indexOf('(') < 0 && str.indexOf(')') < 0)) {
return str;
}
StringBuilder sb = new StringBuilder();
int rightCount = leftCount = remRight = remLeft = 0;
for(Character c : str.toCharArray()) {
if(c != '(' && c != ')') {
sb.append(c);
continue;
}
if(c == '(') {
leftCount++;
}
else {
if(leftCount > rightCount) {
rightCount++;
}
else {
remRight++;
continue;
}
}
sb.append(c);
}
// In case our input had unequal number of ( and )
while(leftCount > rightCount) {
sb.append(')');
rightCount++;
remRight--;
}
if(remRight > 0) {
for(int i = 1; i <= remRight; i++) {
sb.append('()');
}
}
return sb.toString();
}
}
there was a bug in the code above so fixing it, but idea is same recursively figure out if substrings are lottery number as well with less count:
public class Solution {
public boolean isLotteryNumber(String numberStr, int count) {
if(numberStr == null || numberStr.isEmpty() || count < 1) {
return false;
}
Map<Node, Boolean> countMap = new HashMap<>();
return this.isLotteryNumber(numberStr.toCharArray(), 0, count, countMap);
}
private boolean isLotteryNumber(Char[] array, int index, int count, Map<Node, Boolean> countMap) {
Node n = new Node();
n.index = index; n.count = count;
if(countMap.hasKey(n)) {
return countMap.get(n);
}
else if(index >= array.length || (array.length - index) < count || (array.length - index) > count*2) {
return false;
}
StringBuilder sb = new StringBuilder();
sb.append(array[index]);
boolean isValidLottery = false;
for(int i = index + 1; i < array.length; i++) {
if(!this.isValidNumber(sb.toString())) {
break;
}
isValidLottery = this.isLotteryNumber(array, i, count - 1, countMap);
if(isValidLottery) {
break;
}
sb.append(array[i]);
}
countMap.put(n, isValidLottery);
return isValidLottery;
}
private boolean isValidNumber(String s) {
if(s == null || s.isEmpty()) {
return false;
}
try {
int v = Integer.parseInt(s);
return v >= 1 && v <= 59;
}
catch(NumberFormatException e) {
return false;
}
}
private class Node {
public int index;
public int count;
// Remember to override equals and hash method, skipping here for brevity
}
}
This can be achieved with dynamic programming as to find if 1234567 is a valid lottery number of 7 count then we can say it is if 234567 is a valid lottery number with 6 count when considering 1 OR 34567 is a valid lottery number with 6 count when considering 12.
Basically when you combined the digits together the remaining string has to be a lottery number as well with a different count
public class Solution {
public boolean isLotteryNumber(String numberStr, int count) {
if(numberStr == null || numberStr.isEmpty() || count < 1) {
return false;
}
Map<Node, Boolean> countMap = new HashMap<>();
return this.isLotteryNumber(numberStr.toCharArray(), 0, count, countMap);
}
private boolean isLotteryNumber(Char[] array, int index, int count, Map<Node, Boolean> countMap) {
Node n = new Node();
n.index = index; n.count = count;
if(countMap.hasKey(n)) {
return countMap.get(n);
}
else if(index >= array.length || (array.length - index) < count || (array.length - index) > count*2) {
return false;
}
StringBuilder sb = new StringBuilder();
sb.append(array[index]);
boolean isValidLottery = false;
for(int i = index + 1; i < array.length; i++) {
if(!this.isValidNumber(sb.toString())) {
break;
}
isValidLottery = isValidLottery || this.isLotteryNumber(array, i, count - 1, countMap);
if(isValidLottery && index == 0) {
// There is atleast one valid lottery so returning true and stopping the code flow
// we arent interesting in all combinations but just to find if a valid combination exists
return true;
}
sb.append(array[i]);
}
countMap.put(n, isValidLottery);
return isValidLottery;
}
private boolean isValidNumber(String s) {
if(s == null || s.isEmpty()) {
return false;
}
try {
int v = Integer.parseInt(s);
return v >= 1 && v <= 59;
}
catch(NumberFormatException e) {
return false;
}
}
private class Node {
public int index;
public int count;
// Remember to override equals and hash method, skipping here for brevity
}
}
Its not possible to use Union Find for directed graph because Union Find works on Disjointed Sets only and relies heavily on set properties like contains/find and join. Sets by definition dont have any order i.e. if set contains vertices A, B then there will be no way to differentiate if a-> b or b -> a thus we can only use set to to have undirected edges. In other words a direction in a edge denotes and order and sets bu definition are orderless
- nk June 27, 2017There was a slight bug in my code above so fixing it:
public class Solution {
public int findNumber(Interator<Integer> itr, double percent) {
if(percent <= 0) {
throw new IllegalArgumentException("percent has to be positive");
}
int size = 0;
Node root;
while(itr.hasNext()) {
if(root == null) {
root = new Node();
root.value = itr.next();
}
else {
root.add(itr.next());
}
size++;
if(size * percent >= 1 && root != null) {
root = root.removeMin();
size--;
}
}
return root != null ? root.getMin().value : Integer.MIN_VALUE;
}
private static class Node {
public int value;
public Node leftChild;
public Node rightChild;
public Node getMin() {
Node n = this;
while(n.leftChild != null) {
n = n.leftChild;
}
return n;
}
public void add(int v) {
if(this.value >= v) {
if(this.leftChild == null) {
Node n = new Node();
n.value = v;
this.leftChild = n;
}
else this.leftChild.add(v);
}
else {
if(this.rightChild == null) {
Node n = new Node();
n.value = v;
this.rightChild = n;
}
else this.rightChild.add(v);
}
}
public Node void removeMin() {
if(this.leftChild == null) {
return this.rightChild;
}
else {
Node n = this;
while(n.leftChild != null && n.leftChild.leftChild != null) {
n = n.leftChild;
}
n.leftChild = n.leftChild.rightChild;
return this;
}
}
}
}
Before we go to code, few things to note:
1) We dont know the size hence a naive approach would be to store all elements in BST and then return the element at proper position
2) Or we can still use a BST but remove the elements from the tree which we know are before the position desired for eg: if the position is 50% then our tree will never be more than size of n/2 Or n * .5 since every time we add two elements we know the position will shift by one hence we can get rid of older elements at that point since we dont care about them.
In other words p(n, d) <= p(N+1, d) .. your index of desired position will only increase as size increases.
The below solution returns the desired number by using BST in O(log(N)) in best case and O(N) in worst case with memory of O(n*percent/100)
public class Solution {
public int findNumber(Interator<Integer> itr, double percent) {
if(percent <= 0) {
throw new IllegalArgumentException("percent has to be positive");
}
int size = 0;
Node root;
while(itr.hasNext()) {
if(root == null) {
root = new Node();
root.value = itr.next();
}
else {
root.add(itr.next());
}
size++;
if(size * percent >= 1 && root != null) {
root = root.removeMin();
size--;
}
}
return root != null ? root.removeMin().value : Integer.MIN_VALUE;
}
private static class Node {
public int value;
public Node leftChild;
public Node rightChild;
public void add(int v) {
if(this.value >= v) {
if(this.leftChild == null) {
Node n = new Node();
n.value = v;
this.leftChild = n;
}
else this.leftChild.add(v);
}
else {
if(this.rightChild == null) {
Node n = new Node();
n.value = v;
this.rightChild = n;
}
else this.rightChild.add(v);
}
}
public Node void removeMin() {
if(this.leftChild == null) {
return this.rightChild;
}
else {
Node n = this;
while(n.leftChild != null && n.leftChild.leftChild != null) {
n = n.leftChild;
}
n.leftChild = n.leftChild.rightChild;
return this;
}
}
}
}
You can precompute the number of ones at every position in a way that:
NumOfOnes(i, j) = NumberOfOnes(0-i, 0-j).... in other words at any index you should be able to tell the number of ones until that index from 0,0.
This precomputation will take O(n^2) time & O(n^2) memory but we will have to do so only once. Once you have that then finding number of ones is in subset is simply O(1) irrespective the size of grid.
public class Solution {
private final Integr[][] cachedSum;
private final Integer[][] matrix;
public Solution(Integer[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
throw new IllegalArgumentException("Pass in valid matrix");
}
this.matrix = matrix;
Map<Point, Integer> cache = new HashMap<>();
this.cachedSum = this.getPreCalculatedSum(matrix, matrix.length - 1, matrix[0].length - 1, cache);
}
// This is the api that will be called everytime and returns in O(1)
public int getSum(int row1, int col1, int row2, int col2) {
if(row1 < 0 || col1 < 0 || row1 > row2 || col1 > col2 || row2 >= matrix.length || col2 >= matrix[0].length) {
throw new IllegalArgumentException("Please pass in valid cordiates");
}
int topDiagonalSum = row1 - 1 >= 0 && col1 - 1 >= 0 ? this.cachedSum[row1 - 1][col1 - 1] : 0;
int topSectionSum = row1 - 1 >= 0 ? this.cachedSum[row1 - 1][col2] : 0;
int leftSectionSum = col1 - 1 >= 0 ? this.cachedSum[row2][col1 - 1];
return this.cachedSum[row2][col2] - leftSectionSum - topSectionSum + topDiagonalSum;
}
private int fillPreCalculatedSum(Integer[][] matrix, Integer[][] result, int row, int col, Map<Point, Integer> cache) {
Point p = new Point();
p.row = row; p.col = col;
if(cache.contains(p)) {
return cache.get(p);
}
else if(row < 0 || col < 0) {
return 0;
}
int leftSum = col - 1 >= 0 ? this.getPreCalculatedSum(matrix, result row, col - 1, cache) : 0;
int topSum = row - 1 >= 0 ? this.getPreCalculatedSum(matrix, result, row - 1, col, cache) : 0;
int diagonalTopSum = row -1 >= 0 && col - 1 >= 0 ? this.getPreCalculatedSum(matrix, result, row - 1, col - 1, cache) : 0;
int sum = matrix[row][col] + leftSum + topSum - diagonalTopSum;
result[row][col] = sum;
cache.put(p, sum);
return sum;
}
private static class Point {
public int row;
public int col;
}
}
The key to this problem is finding all the prime numbers until n and then dividing n by all the prime numbers one by one"
public class Solution {
public String getPrimeFactors(int n) {
if(n <= 3) {
return Integer.toString(n);
}
Boolean[] primes = this.getPrimes(n);
int number = n;
StringBuilder sb = new StringBuilder();
for(int i = 2; i < primes.length; i++) {
if(!primes[i] || number % i != 0) {
continue;
}
while(number % i == 0) {
sb.append(i);
sb.append(" * ");
number = number / i;
}
if(number == 1) {
break;
}
}
sb.delete(sb.length() - 3, sb.length());
return sb.toString();
}
private Boolean[] getPrimes(int n) {
if(n < 2) {
throw new IllegalArgumentException("n has to be bigger than 1");
}
Boolean result = new Boolean[n + 1];
this.initArray(result);
int prime = 2;
while(prime <= Math.sqrt(n)) {
this.checkOffNonPrimes(prime, result);
prime = this.getNextPrime(prime, result);
}
return result;
}
private void checkOffNonPrimes(int index, Boolean[] result) {
for(int i = index*index; i < result.length; i = i + index) {
result[i] = false;
}
}
private void getNextPrime(int index, Boolean[] result) {
int i = index + 1;
while(i < result.length && !result[i]) {
i++;
}
return i;
}
private void initArray(Boolean[] array) {
if(n < 2) {
throw new IllegalArgumentException("n has to be bigger than 1");
}
Arrays.fill(result, true);
array[0] = false;
array[1] = false;
}
}
1) Just iterate through numbers and ignore number with digit 9 in them like the solutions above which takes nLogN time
2) We can make the above logic fast by not considering any number to the right of 9 for eg if we are at 19876 then o point going to 19877 as 9 is at position 3 so instead jump directly to 20000 or in case of 1888 jump to 2000, this will be faster but still nlogn
3) We can do this in linear time O(N) in best case scenario by:
Lets say countOccurenceOf9(n) returns number of times 9 appears until n then n th number = n + countOccurenceOf9(n) but there must be numbers contains 9 between n and n + countOccurenceOf9(n) so then we find find how many times 9 appeared between n and n + countOccurenceOf9(n) and skip by that amount and repeat
public class Solution {
public int getNthNumber(int number, int digit) {
if(digit < 0 || digit > 9) {
return -1;
}
DigitOccurence digitOccurence = new DigitOccurence();
int n = number;
int numOfDigits = digitOccurence.getOccurence(n, digit);
int numToSkip = numOfDigits;
while(numToSkip != 0) {
int newN = n + numToSkip; // but there might be digits between n and n+numOfDigits so we need to skip them too
int t = digitOccurence.getOccurence(newN, digit);
numToSkip = t - numOfDigits;
numOfDigits = t;
n = newN;
}
return this.getNumberAfterRemovinDigit(n, digit);
}
private int getNumberAfterRemovinDigit(int n, int digit) {
if(result == -1) {
return n;
}
int numberWithDigitsWipedOutAfterPosition = n / Math.pow(10, result);
numberWithDigitsWipedOutAfterPosition = n * Math.pow(10, result); // Change 19899 into 19000
return numberWithDigitsWipedOutAfterPosition + Math.pow(10, result); // 19000 + 1000 = 20000 as we need to remove 9 from number
}
private int getMostSygnificantDigitPosition(int n, int digit) {
int position = 0;
int result = -1;
while(n > 0) {
if(n % 10 == digit) {
result = position;
}
position++;
n = n / 10;
}
return result;
}
/********************************** Code below is to find number of occurences of digit d until number n****/
public class DigitOccurence {
public int getOccurence(int number, int digit) {
number = Math.abs(number);
if(digit < 0 || digit > 9) {
return 0;
}
Map<Integer, Integer> cache = new HashMap<>();
return this.getOccurence(number, digit, cache);
}
private int getOccurence(int number, int digit, Map<Integer, Integer> cache) {
// Every digit appears once from 0 - 9
if(number < 10) {
return 1;
}
// Every digit appears 19 (conting 22 as one occurence in this case) times from 0 - 99 except 0 which appears 10 times
else if(number < 100) {
return digit == 0 ? 10 : 19;
}
else if(cache.hasKey(number)) {
return cache.get(number);
}
int numDigits = this.getNumDigits(number);
int msd = this.getMostSygnificantDigit(number);
int numButMsd = number - msd * Math.pow(10, numDigits - 1); // get 98 out of 898
/**
Here is the magic:
=> C(898, digit) = C(0-799, digit) + C(800-898, digit) // msd is 8, numButMsd is 98
=> C(799, digit) = C(99, digit) * 8 + (digit < 8) ? 100 : 0
=> C(800-898, digit) = C(98, digit) + (digit == 8) ? 99 : 0;
=> C(898, digit) = (C(799, digit) = C(99, digit) * 8 + (digit <= 6) ? 100 : 0)
+ (C(98, digit) + (digit == 8) ? 99 : 0);
*/
int occurence = (msd * this.getOccurence(Math.pow(10, numDigits - 1) - 1, digit, cache) + (digit < msd) ? Math.pow(10, msd - 1) : 0)
+ (this.getOccurence(numButMsd, digit, cache) + digit == msd ? numButMsd + 1 : 0);
cache.put(number, occurence);
return occurence;
}
private int getNumDigits(int number) {
int count = 0;
while(number > 0) {
count++;
number = number / 10;
}
return count;
}
private int getMostSygnificantDigit(int number) {
if(number == 0) {
return 0;
}
int numDigits = this.getNumDigits(number);
return number / Math.pow(10, number - 1);
}
}
}
Lets start with a bit of math before coding,Imagine the number 897 and digit 6:
1) From 0 - 9 every digit comes once
2) From 0 - 99 every digit comes 20 times except 0 which comes 10 times
3) Now count(897, 6) = count(0-799, 6) + count(800-897, 6)
count(0-799, 6) = count(99, digit) * 8 + 100 since 6 <= 7 otherwise 0
count(800-897) = count(97, 6) + 6 == 8 ? 98 : 0
Once you get the formulae right its very simple dynamic programming with memorization:
public class DigitOccurence {
public int getOccurence(int number, int digit) {
number = Math.abs(number);
if(digit < 0 || digit > 9) {
return 0;
}
Map<Integer, Integer> cache = new HashMap<>();
return this.getOccurence(number, digit, cache);
}
private int getOccurence(int number, int digit, Map<Integer, Integer> cache) {
// Every digit appears once from 0 - 9
if(number < 10) {
return 1;
}
// Every digit appears 20 times from 0 - 99 except 0 which appears 10 times
else if(number < 100) {
return digit == 0 ? 10 : 20;
}
else if(cache.hasKey(number)) {
return cache.get(number);
}
int numDigits = this.getNumDigits(number);
int msd = this.getMostSygnificantDigit(number);
int numButMsd = number - msd * Math.pow(10, numDigits - 1); // get 98 out of 898
/**
Here is the magic:
=> C(898, digit) = C(0-799, digit) + C(800-898, digit) // msd is 8, numButMsd is 98
=> C(799, digit) = C(99, digit) * 8 + (digit < 8) ? 100 : 0
=> C(800-898, digit) = C(98, digit) + (digit == 8) ? 99 : 0;
=> C(898, digit) = (C(799, digit) = C(99, digit) * 8 + (digit <= 6) ? 100 : 0)
+ (C(98, digit) + (digit == 8) ? 99 : 0);
*/
int occurence = (msd * this.getOccurence(Math.pow(10, numDigits - 1) - 1, digit, cache) + (digit < msd) ? Math.pow(10, msd - 1) : 0)
+ (this.getOccurence(numButMsd, digit, cache) + digit == msd ? numButMsd + 1 : 0);
cache.put(number, occurence);
return occurence;
}
private int getNumDigits(int number) {
int count = 0;
while(number > 0) {
count++;
number = number / 10;
}
return count;
}
private int getMostSygnificantDigit(int number) {
if(number == 0) {
return 0;
}
int numDigits = this.getNumDigits(number);
return number / Math.pow(10, number - 1);
}
}
After googling few helpful links;
1) https://stackoverflow.com/questions/32442837/minimum-number-of-steps-to-sort-3x3-matrix-in-a-specific-way
2) https://en.wikipedia.org/wiki/A*_search_algorithm
3) https://en.wikipedia.org/wiki/15_puzzle
Basically it is a modification of Dijkstra algorithm, every move of empty box at every stage will give at max 4 new states -- consider these states as neighbours. Thus every state has max 4 neighbours and we can then do a BFS on them to find the state which is sorted and combined with Dijkstra logic will give us minimum steps.
public class Solution {
public List<Point> getPathToSort(Integer[][] matrix) {
Point p = new Point();
p.row = matrix.length - 1;
p.col = matrix[0].length - 1;
Board initialBoard = new Board(matrix, null, p);
Set<Board> closedSet = new HashSet<>();
// it must be a min priority queue since the board with minimum cost should be first
PriorityQueue<Board> minQueue = new PriorityQueue<>(new BoardComparator());
minQueue.add(initialBoard);
// most important part of the program as this has the main logic, very similar to BFS
while(!minQueue.isEmpty()) {
Board b = minQueue.dequeue();
closedSet.add(b);
List<Board> neighbours = this.getAllAdjacentBoards(b);
// Iterate throught all the neighbours and add them to the queue or replace the existing board with new minimum
// cost board.
for(Board neighbour : neighbours) {
if(neighbour.isSolved()) {
return neighbour.getPath();
}
else if(closedSet.contains(neighbour)) {
continue;
}
else if(!minQueue.contains(neighbour)) {
minQueue.add(neighbour);
continue;
}
// This means we have seen this board before thus find if this neighbour has less cost or existingItem and
// replace if neccessary
int newCost = neighbour.getBoardCost();
Board existingItem = minQueue.remove(neighbour);
int existingCost = existingItem.getBoardCost();
minQueue.add(existingCost < newCost ? existingItem : neighbour);
}
}
return null;
}
private List<Board> getAllAdjacentBoards(Board b) {
List<Board> result = new ArrayList<>();
Board b = this.getBoardAfterMove("left", b);
if(b != null) {
result.add(b);
}
b = this.getBoardAfterMove("top", b);
if(b != null) {
result.add(b);
}
b = this.getBoardAfterMove("right", b);
if(b != null) {
result.add(b);
}
b = this.getBoardAfterMove("bottom", b);
if(b != null) {
result.add(b);
}
return result;
}
private Board getBoardAfterMove(String direction, Board b) {
Point newEmptyBoxPoint = b.emptyBoxPosition.getAdjacentPoint(direction, b.matrix);
if(newEmptyBoxPoint == null) {
return null;
}
Integer[][] newState = this.swapPositions(b.matrix, b.emptyBoxPosition, newEmptyBoxPoint);
Board b = new Board(newState, b, newEmptyBoxPoint);
return b;
}
private Integer[][] swapPositions(Integer[][] matrix, Point p1, Point p2) {
Integer[][] newState = new Integer[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(i == p1.row && j == p1.col) {
newState[i][j] = matrix[p2.row][p2.col];
}
else if(i == p2.row && j == p2.col) {
newState[i][j] = matrix[p1.row][p1.col];
}
else {
newState[i][j] = matrix[i][j];
}
}
}
return newState;
}
////////////////////////////////////////////////////////////////////////////////////////
public static class Board {
public Board previousBoard;
public Integer[][] matrix;
public Point emptyBoxPosition;
public int stepsTakenSoFar;
public Board(Integer[][] newState, Board oldBoard, Point emptyBoxPosition) {
this.previousBoard = oldBoard;
this.matrix = newState;
this.stepsTakenSoFar = oldBoard == null ? 0 : this.previousBoard.stepsTakenSoFar + 1;
this.emptyBoxPosition = emptyBoxPosition;
}
public List<Point> getPath() {
List<Point> path = new ArrayList<>();
while(previousBoard != null) {
path.addAll(previousBoard.getPath());
}
path.add(emptyBoxPosition);
return path;
}
public boolean equals(Object o) {
if(o == null || !(o instanceof Board)) {
return false;
}
Board b = (Board)o;
for(int i= 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] != b.matrix[i][j]) {
return false;
}
}
}
return true;
}
public int hash() {
return this.matrix.hash();
}
public boolean isSolved() {
return this.getNumbersOfBlockInWrongPosition() == 0;
}
public int getNumbersOfBlockInWrongPosition() {
for(int i= 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] != i*j + j) {
count++;
}
}
}
return count;
}
public int getBoardCost() {
return this.getNumbersOfBlockInWrongPosition() + this.stepsTakenSoFar;
}
}
////////////////////////////////////////////////////////
public static class Point {
public int row;
public int col;
public Point getAdjacentPoint(String direction, Integer[][] matrix) {
Point p = new Point();
p.row = this.row;
p.col = this.col;
switch(direction) {
case "top":
if(p.row >= 1) {
p.row--;
return p;
}
break;
case "right":
if(p.col <= matrix[0].length - 2) {
p.col++;
return p;
}
break;
case "bottom":
if(p.row <= matrix.length - 2) {
p.row++;
return p;
}
break;
case "left":
if(p.col >= 1) {
p.col--;
return p;
}
break;
default: return null;
}
return null;
}
}
//////////////////////////////////////////////////////
public static class BoardComparator implements Comparator<Board> {
public int compare(Board b1, Board b2) {
return b1.getBoardCost() - b2.getBoardCost();
}
}
}
public class Solution {
public String getRepetitivePattern(int dividend, int divisor) {
if(divisor == 0 || dividend % divisor = 0) {
return null; // There is no pattern
}
dividend = Math.Abs(dividend);
divisor = Math.Abs(divisor);
dividend = (dividend % divisor) * 10;
StringBuilder sb = new StringBuilder();
// Map of dividend to starting index of pattern
Map<Integer, Integer> cache = new HashMap<>();
int newDividend = dividend, quotient = 0;
// Return null in case we can never find a pattern
while(cache.size() < Integer.MAX_VALUE) {
quotient = (int)(dividend / divisor);
if(cache.contains(newDividend)) {
return sb.substring(cache.get(newDividend));
}
if (!cache.contains(newDividend)) {
cache.put(newDividend, substring.length());
substring.append(quotient);
}
newDividend = (dividend % divisor) * 10;
}
return null;
}
}
Wow interesting question, okay so lets start with a bit of math before coding,Imagine the number 897 and digit 6:
1) From 0 - 9 every digit comes once
2) From 0 - 99 every digit comes 20 times except 0 which comes 10 times
3) Now count(897, 6) = count(0-799, 6) + count(800-897, 6)
count(0-799, 6) = count(99, digit) * 8 + 100 since 6 <= 7 otherwise 0
count(800-897) = count(97, 6) + 6 == 8 ? 98 : 0
Once you get the formulae right its very simple dynamic programming with memorization:
public class DigitOccurence {
public int getOccurence(int number, int digit) {
number = Math.abs(number);
if(digit < 0 || digit > 9) {
return 0;
}
Map<Integer, Integer> cache = new HashMap<>();
return this.getOccurence(number, digit, cache);
}
private int getOccurence(int number, int digit, Map<Integer, Integer> cache) {
// Every digit appears once from 0 - 9
if(number < 10) {
return 1;
}
// Every digit appears 20 times from 0 - 99 except 0 which appears 10 times
else if(number < 100) {
return digit == 0 ? 10 : 20;
}
else if(cache.hasKey(number)) {
return cache.get(number);
}
int numDigits = this.getNumDigits(number);
int msd = this.getMostSygnificantDigit(number);
int numButMsd = number - msd * Math.pow(10, numDigits - 1); // get 98 out of 898
/**
Here is the magic:
=> C(898, digit) = C(0-799, digit) + C(800-898, digit) // msd is 8, numButMsd is 98
=> C(799, digit) = C(99, digit) * 8 + (digit < 8) ? 100 : 0
=> C(800-898, digit) = C(98, digit) + (digit == 8) ? 99 : 0;
=> C(898, digit) = (C(799, digit) = C(99, digit) * 8 + (digit <= 6) ? 100 : 0)
+ (C(98, digit) + (digit == 8) ? 99 : 0);
*/
int occurence = (msd * this.getOccurence(Math.pow(10, numDigits - 1) - 1, digit, cache) + (digit < msd) ? Math.pow(10, msd - 1) : 0)
+ (this.getOccurence(numButMsd, digit, cache) + digit == msd ? numButMsd + 1 : 0);
cache.put(number, occurence);
return occurence;
}
private int getNumDigits(int number) {
int count = 0;
while(number > 0) {
count++;
number = number / 10;
}
return count;
}
private int getMostSygnificantDigit(int number) {
if(number == 0) {
return 0;
}
int numDigits = this.getNumDigits(number);
return number / Math.pow(10, number - 1);
}
}
Let me start by saying thanks to ChrisK as this solution is based on his however his solution doesnt take care of circular linked list. Here is the solution that will take care of that.
THis solution runs in O(N) time and O(N) memory.
public class DoublyLinkedListHelper {
public int getNumLinkedLists(List<Pointer> pointers) {
if(pointers == null || pointers.size() == 0) {
return 0;
}
// This set will contain the individual nodes belonging to one/same linkedlist
Set<Set<Node>> setOfLinkedListNodes = new HashSet<>();
for(Pointer p : pointers) {
Iterator<Set<Node>> itr = setOfLinkedListNodes.iterator();
boolean addNewSet = true;
Set<Nodes> matchedSet = null;
while(itr.hasNext) {
Set<Node> nodes = itr.next();
// Means we found an existing linked list node set where we can add the unadded nodes
// There is a reason we havent overriden equals method as we want matching based on actual object reference
if(nodes.contain(p.from) || nodes.contain(p.to)) {
// This means that we had already found a matching list thus there is no need to keep this list
// since it will end up joining the original list
if(!addNewSet) {
// Since two linked list are joining here we need to copy the elements from one to another before we remove it;
matchedSet.addAll(nodes);
itr.remove();
// We will never have a case where a pointer is part of more than 2 sets as they must have been joined otherwise.
break;
}
else {
// Add the missing node
nodes.add(nodes.contain(p.from) ? p.to : p.from);
addNewSet = false;
matchedSet = nodes;
}
}
}
if(addNewSet) {
Set<Node> nodes = new HashSet<>();
nodes.add(p.from);
nodes.add(p.to);
setOfLinkedListNodes.add(nodes);
}
}
return setOfLinkedListNodes.size();
}
public static class Pointer {
public Node from;
public Node to;
}
public static class Node {
public int value;
public Node prev;
public Node next;
}
}
Interesting question:
1) simplest approach any bst when walked in order returns the element in sorted order so simply sort them. Takes NlogN time and logn memory depending on sorting algo
2) Recursively find the next element by going left, root and right and following BST properties by keeping a track of min and max element at any node. Takes n memory and n time.
public class PreOrderToInOrderConverter {
// simplest solution
public int[] printInorder(int[] nums) {
if(nums == null|| nums.length <= 1) {
return nums;
}
return Arrays.sort(nums);
}
// N time and n memory
public int[] printInorder_better(int[] nums) {
if(nums == null|| nums.length <= 1) {
return nums;
}
LinkedList<Integer> result = new LinkedList<>();
int minValue = Integer.MIN_VALUE;
int maxValue = Integer.MAX_VALUE;
this.getInOrderTraversal(nums, 0, minValue, maxValue, result);
return result.toArray(); // just to return the array otherwise we could have returned the list itself
}
private int getInOrderTraversal(int[] nums, int index, int minValue, int maxValue, LinkedList<Integer> result) {
if(index == nums.length) {
return index;
}
int root = nums[index];
// Left child is possible
if(index + 1 < nums.length && root >= nums[index + 1] && nums[index + 1] > minValue) {
index = getInOrderTraversal(nums, index + 1, minValue, root, result);
}
// add the root
result.add(root);
// right child is possible
if(index + 1 < nums.length && root < nums[index + 1] && nums[index + 1] <= maxValue) {
index = getInOrderTraversal(nums, index + 1, root, maxValue, result);
}
return index + 1;
}
}
Thing to keep in mind .. for a string to be balanced the number of ) should never exceed number of ( going left to right. Here is an O(n) solution with O(1) memory as it changes the string in place:
public class Solution {
public String balance(String str) {
if(str == null || str.isEmpty() || !isValid(str)) {
return "";
}
// Now we know the string can be balanced
int rightBraceOverCount;
Char array = str.charArray();
for(int i = 0; i < array.length; i++) {
Char c = array[i];
// AT NOT POINT in time should # of ) exceed number of ( if the string needs to be balanced
if(c == ')') {
rightBraceOverCount++;
// If after increment the right brace count became grater than 0 that means we need to change it to (
if(rightBraceOverCount > 0) {
array[i] = '(';
}
}
else {
// If the rightBraceOverCount was > 0 and we encountered a left brace then change it to ) as we must have replaced
// a prev ) with (
if(rightBraceOverCount > 0) {
array[i] = ')';
}
rightBraceOverCount--;
}
}
return str;
}
private boolean isValid(String str) {
Char[] array = str.charArray();
int leftBrace = 0, rightBrace = 0;
for(Char c : array) {
if(!(c == '(' || c == ')')) {
return false;
}
if(c == '(') {
leftBrace++;
}
else rightBrace++;
}
return leftBrace == rightBrace;
}
}
Here is the gist:
1) Forget longitude and latitude, its just a weighted graph
2) Run any shortest path algo like Dijkstra algorithm to find shortest path of all node from the node in question
3) return the top 5 least paths
public class Solution {
public List<Node> getClosestNode(Node n, int closest) {
if(n == null || n.children() == null || n.children().size == 0 || closest <= 0) {
return new ArrayList<Node>();
}
Set<Node> settledNodes = new HashSet<Node>();
Map<Node, Node> predecessors = new HashMap<>();
PriorityQueue unsettledNodes = new PriorityQueue(new Comparator<Node>(){
@Override
public int compare(Node n1, Node n2) {
return n1.getDistance() - n2.getDistance();
}
});
unsettledNodes.add(n);
Map<Integer, List<Node>> distance = new TreeMap<>();
distance.put(0, new ArrayList<>());
distance.get(0).add(n);
while(!unsettledNodes.isEmpty()) {
Node source = unsettledNodes.poll();
settledNodes.add(source);
List<Node> neighbours = source.neighbours();
for(Node neighbour : neighbours) {
if(settledNodes.contains(neighbour )) {
continue;
}
int newDistance = this.getDistance(source) + n.getDistance();
if(this.getDistance(distance, neighbour ) > newDistance) {
if(!distance.hasKey(newDistance)) {
distance.put(newDistance, new ArrayList());
}
distance.get(newDistance).add(neighbour );
unsettledNodes.add(neighbour );
predecessors.put(source, neighbour );
}
}
}
return this.getClosestNode(distance, closest);
}
public List<Location> getClosestLocations(Map<Integer, List<Node>> map, int closest) {
List<Location> locations = new ArrayList<Location>();
for(EntrySet<Integer, List<Node>> entry : distance) {
for(Node n : entry.value()) {
if(locations.size() == closest) {
break;
}
locations.add(n.getLocation());
}
}
return locations;
}
public int getDistance(Map<Node, Integer> distance, Node to) {
return distance.hasKey(to) ? distance.get(to) : Integer.MAX_VALUE;
}
}
public class Node {
private List<Node> neighbours.....
private Location location;
private int distance;
}
public class Solution {
private int getIndexDividingEqualSum(int[] array) {
if(array == null || array.length <= 0) {
return -1;
}
int index = 0, lastIndex = array.length - 1, indexSum = Integer.MAX_VALUE, lastIndexSum = Integer.MAX_VALUE;
while(index < lastIndex) {
indexSum = (indexSum == Integer.MAX_VALUE ? 0 : indexSum) + array[index];
lastIndexSum = (lastIndexSum == Integer.MAX_VALUE ? 0 : lastIndexSum) + array[lastIndex];
if(indexSum <= lastIndexSum) {
index++;
}
else {
lastIndex--;
}
}
return indexSum == lastIndexSum ? index - 1 : -1;
}
}
public clas Solution {
public List<Integer> getLeaves(int[] array) {
List<Integer> leaves = new ArrayList<>();
if(array == null || array.length == 0) {
return leaves;
}
getLeaves(array, Integer.MIN_VALUE, Integer.MAX_VALUE, leaves);
return leaves;
}
private int getLeaves(int[] array, int index, int minValue, int maxValue, List<Integer> leaves) {
if(index == array.length - 1) {
leaves.add(array[index]);
return index + 1;
}
// if the next value doesnt fall in the bucket then this node is the leaf as the next noad falls outside
// the allowable range
int childIndex = index + 1;
if(array[childIndex] >= maxValue || array[childIndex] < minValue) {
leaves.add(array[index]);
return childIndex;
}
// This means that this node is not a leaf hence keep on traversing
if(array[childIndex] <= array[index]) {
childIndex = getLeaves(array, childIndex, minValue, array[index], leaves);
}
if(childIndex >= array.length || array[childIndex] >= maxValue || array[childIndex] < minValue) {
// If we are reaching this point then it means that the current node had atleast one child so simply return
// as this node is no longer a leaf but parent with one child
return childIndex;
}
// This means that we have a right child so traverse on the right child to see if thats a leaf
if(array[childIndex] > array[index]) {
childIndex = getLeaves(array, childIndex, array[index], maxValue, leaves);
}
return index;
}
}
public class Solution {
public int getNumValidCombinations(String number) {
Map<String, Integer> cache = new Map<>();
if(number == null || number.isEmpty()) {
return 0;
}
return this.getNumValidCombinations(number, 0, cache);
}
private int getNumValidCombinations(String number, int index, Map<String, Integer> cache) {
if(index >= number.length) {
return 1;
}
else if(Integer.parse(number.charAt(index)) <= 0 || Integer.parse(number.charAt(index)) >= 10) {
throw new IllegalArgumentException("Param is not valid");
}
else if(cache.hasKey(number.substring(index, number.length))) {
return cache.get(number.substring(index, number.length));
}
int numWays = 0;
for(int i = index; i < number.length; i++) {
if(!isValid(number, index, i)) {
break;
}
numWays += this.getNumValidCombinations(number, i + 1, cache);
}
cache.put(number.substring(index, number.length), numWays);
return numWays;
}
/**
Returns true if we should consider the next character in the same iteration otherwise return false
*/
private boolean isValid(String number, int indexFrom, int indexTo) {
if( indexFrom - indexTo >= 2 || indexFrom >= number.length || indexTo >= number.length || indexFrom < indexTo ||
number.charAt(indexFrom) < 1 || number.charAt(indexFrom) > 2 || number.getCharAt(indexTo) >= 7 ||
number.getCharAt(indexTo) <= 0) {
return false;
}
return true;
}
}
public class Solution {
// Takes O(N) time and minimum writes to the array
public void moveNonZeroElementsLeft(int[] array) {
int lastNonZeroElement = this.getLastNonZeroElement(array.length);
if(lastNonZeroElement < 0) {
return array.length;
}
for(int i = 0; i < array.length; i++) {
if(i >= lastNonZeroElement) {
break;
}
else if(array[i] == 0) {
array[i] = array[lastNonZeroElement];
lastNonZeroElement = this.getLastNonZeroElement(lastNonZeroElement);
}
}
return i + 1;
}
private int getLastNonZeroElement(int[] array, int index) {
int i = index - 1;
while(i >= 0) {
if(array[i] != 0) {
return i;
}
i--;
}
return i;
}
}
#1) Recursively call on linked list and when recursive operation returns print the current character - recursive also takes O(n) memory as n recursive calls
#2) Iterate over the linked list and add the characters to arraylist and then print them or string reverse after adding them to a string
public class Solution {
// Question 3
public void printCharBackward(Node node) {
if(node == null) {
return;
}
int length = getLinkedListLength(node);
for(int i = length - 1; i >= 0; i++) {
int index = 0;
Node tmp = node;
while(index != i) {
tmp = tmp.next;
index++;
}
System.out.printLn(tmp.data);
}
}
private int getLinkedListLength(Node node) {
int length = 0;
Node tmp = node;
while(tmp != null) {
length++;
tmp = tmp.next;
}
return length;
}
///////////////// Question 4
public void printCharacterIterative(Node node) {
Node prev = null;
Node tmp = node;
// Reverse the list in (N)
while(tmp != null) {
Node next = tmp.next;
tmp.next = prev;
prev = tmp;
tmp = next;
}
// Print it O(N)
tmp = prev;
while(tmp != null) {
System.out.printLn(tmp.data);
tmp = tmp.next;
}
}
}
This problem looks like a modification of partition problem which is a NP-complete problem i.e. exponential time. Like any NPC problem this can also be done in exponential however since we are worried about reducing the time we can probably do this as below in polynomial time.
The solution below runs in O(NLogN) + O(n*k):
public class TasksAndWorkers {
public int getMini(int[] tasks, int k) {
if(tasks == null || tasks.length == 0 || k <= 0) {
return 0; // error condition
}
int[] workers = new int[k];
// NlogN time
Arrays.sort(tasks);
// Takes n*k time, we are going in desc order so we know the i task will always take less than i+1 task
for(int i = tasks.length - 1; i >= 0 ; i--) {
int index = getCurrentMinWorker(workers);
workers[index] += tasks[i];
}
int minWorker = getCurrentMinWorker(workers);
return workers[minWorker];
}
public int getCurrentMinWorker(int[] workers) {
int index = 0;
for(int i = 0; i <= workers.length - 1; i++) {
if(workers[index] <= workers[i]) {
index = i;
}
}
return index;
}
}
I could have removed the sorting time by not sorting the array and that would have given me the same max time needed by the most time consuming worker but other workers may not ave been ideally utilitized i.e. it could result in:
W1- 300
W2 - 15+2+1
W3- 7
Sorting helps us use all workers to max capacity
Reptargienaron, Public relations coordinator at Total Quality
I am a public relations coordinator . Planning publicity strategies and campaigns. writing and producing presentations and press releases. I explore ...
RepJaninaGilden, Java Experienced at Boeing
I am Janina , a Registered Nurse with 3 years experience providing healthcare to a variety of patients in different institutions ...
You dont need any stack or any memory for this, its merely a linked list pointers play. This runs in O(1) memory and O(N) time which modifies the linked list in place
P.S I hate it that we cant edit our posts as there was a typo in my post earlier..
- nk July 11, 2017