libertythecoder
BAN USERI push the children nodes from right to left, so each level is printed from left to right:
public void printTree(Node root){
Queue<Node> nodes = new Queue<>();
if(root != null)
nodes.add(root);
Stack<Integer> result = new Stack<>();
while(!nodes.isEmpty()){
Node node = nodes.pop();
result.add(node.val);
if(node.right != null)
nodes.add(node.right);
if(node.left != null)
nodes.add(node.left);
}
while(!result.isEmpty())
System.out.print(result.pop() + “ “);
}
Uncompleted, but you get the idea. Maybe, as the matrix is sparse, we can save some space by doing DFS/BFS as it indicates the problem.
public Coordinate biggestCross(boolean[][] matrix){
int n = matrix.length;
if(n == 0)
return null;
int m = matrix[0].length;
if(m == 0)
return null;
Edge[][] edges = new Edge[n][m];
//Here we count 1s to the left
//We must do the same for top, right and bottom (I did not code it)
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = 0; j < n; j++){
edges[i][j] = new Edge();
edge.left = sum;
if(matrix[i][j])
sum++;
else
sum = 0;
}
}
//Then it is just a matter of selecting the biggest one
//...
}
public int[] getRandomPermutation(int n){
int[] result = new int[n];
for(int i = 0; i < n; i++){
result[i] = i;
}
for(int i = 0; i < n; i++){
int index = i + (int)(getRandom() * (n - i));
int aux = result[i];
result[i] = result[index];
result[index] = aux;
}
return result;
}
I think we can also do memorization to avoid repeating tons of operations. I didn't check the code but you get the idea:
private Set<Integer> sums;
private int[] coinValues, quantity;
private int size;
private HashSet<Integer>[] memorization;
public Set<Integer> getPossibleSums(int[] coinValues, int[] quantity){
this.coinValues = coinValues;
this.quantity = quantity;
this.size = coinValues.length;
sums = new HashSet<Integer>();
memorization = new HashSet<Integer>[size];
possibleSums(0, 0);
return sums;
}
public void possibleSums(int n, int sum){
if(n != size){
if(memorization[n] == null || !memorization[n].contains(sum)){
int coinValue = coinValues[n];
for(int i = 0; i <= quantity[n]; i++){
int nextSum = sum + i * coinValue;
possibleSums(n + 1, nextSum);
if(memorization[n + 1] == null)
memorization[n + 1] = new HashSet<Integer>();
memorization[n + 1].add(nextSum);
}
}
}else{
sums.add(sum);
memorization
}
}
private int maxHeight = 0;
public int height(Node root){
height(root, 0);
return maxHeight;
}
private void height(Node node, int height){
if(node != null){
for(Node child : node.children)
height(child, height + 1);
}else{
if(height > maxHeight)
maxHeight = height;
}
}
SELECT gpa, count(gpa)
FROM student
WHERE gpa = 3 OR gpa = 4
GROUP BY gpa
The trick here is to know that the different characters size (256, for Java) is a constant value, so we can use an array containing the different characters without breaking the problem rules:
public char firstNonRepeated(String str){
Integer[] indexes = new int[256];
char[] chars = str.toCharArray();
for(int i = 0; i < str.length(); i++){
int index = Character.getNumericValue(chars[i]);
if(count[index] == null)
count[index] = i;
else
count[index] = -1;
}
char first = ‘’;
int firstIndex = Integer.MAX_VALUE;
for(i = 0; i < 256; i++){
if(count[i] != null && count[i] != -1 && count[i] < firstIndex){
first = (char) i;
firstIndex = count[i];
}
}
return first;
}
Easy and adaptable solution:
private final static HashMap<Char, Char> parenthesis = new HashMap<>();
static{
parenthesis.add(“(“, “)”);
parenthesis.add(“<“, “>”);
parenthesis.add(“{“, “}”);
parenthesis.add(“[“, “]”);
}
public boolean isBalanced(String str){
Stack<Character> stack = new Stack<>();
for(Char c : str.toCharArray()){
if(parenthesis.contains(c)){
stack.push(c);
}else{
if(parenthesis.(stack.pop()) != c)
return false;
}
}
if(stack.isEmpty())
return true;
return false;
}
Supposing the two integer values are not repeated:
private int num1, num2;
private Integer ancestor;
public int leastCommonAncestor(Node root, int num1, int num2){
this.num1 = num1;
this.num2 = num2;
leastCommonAncestor(root);
return ancestor;
}
private Integer leastCommonAncestor(Node node){
if(node == null)
return null;
//Check if the ancestor is behind this node
Integer left = leastCommonAncestor(node.left);
if(ancestor != null)
return null;
Integer right = leastCommonAncestor(node.left);
if(ancestor != null)
return null;
//Chech if the ancestor is this node
if(left != null && right != null){
ancestor = node.val;
return null;
}
//Check if the ancestor is this node, being also one of the numbers
boolean isNum = (node.val == num1) || (node.val == num2);
if((left != null || right != null) && isNum))
ancestor = node.val;
return null;
}
//Return the num
if(left != null)
return left;
if(right != null)
return right;
if(isNum)
return node.val;
return null;
}
Juste a simple DFS solution, saving the path in a list:
private List<Integer> path;
private List<String> result;
public List<String> nodeToLeafPaths(TreeNode root){
path = new LinkedList<>();
result = new LinkedList<>();
leafPath(root);
return result;
}
public void leafPath(TreeNode node){
if(node != null){
path.add(node.val);
if(node.left == null && node.right == null){
StringBuilder sb = new StringBuilder();
int i = 0;
for(Integer n : path){
sb.append(n);
if(i++ != path.size() - 1)
sb.append(“->”);
}
result.add(sb.toString());
}
leafPath(node.left);
leafPath(node.right);
path.remove(path.size() - 1);
}
}
This solution takes O(nlog(k)) time and O(k) space. I think it is the simplest coding solution, at least for Java:
public int largestValue(int[] array, int k){
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int i = 0; i < array.length; i++){
heap.add(array[i]);
if(heap.size() > k)
heap.poll();
}
return heap.peek();
}
BFS solution starting at the guards. O(n^2) time and space:
class Square{
int x, y, distance;
Square(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}
}
static int[][] DIRECTIONS = new int[]{{0, 1}, {0, -1}, {1, 0}, {-1,0}};
public int[][] getDistances(char[][] museum){
int n = museum.length;
int m = museum[0].length;
if(n == 0 || m == 0)
return null;
boolean[][] visited = new boolean[n][m];
int[][] result = new int[n][m];
Queue<Square> squares = new Queue<Square>();
//BFS starting at the guards
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(museum[i][j] == ‘G’){
squares.add(new Square(i, j, 0));
visited[i][j] = true;
}else{
if(museum[i][j] == ‘W’){
visited[i][j] = true;
}
//By default no way to reach a guard
result[i][j] = -1;
}
}
}
while(!squares.isEmpty()){
Square square = squares.pop();
result[square.x][square.y] = square.distance;
for(int[] direction : directions]){
int x = square.x + direction[0];
int y = square.y + direction[1];
if(x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]){
squares.add(new Square(x, y, square.distance + 1);
visited[x][y] = true;
}
}
}
}
Take care of boundary cases, for example for arrays of 0 length:
public boolean existsContigous(int[] array, int x){
int size = array.length;
if(size == 0)
if(x == 0)
return true;
else
return false;
int left = 0;
int right = 0;
int sum = 0;
while(right < size){
if(sum == x)
return true;
if(sum < x){
sum += array[right];
right++;
}else{
sum -= array[left];
left++;
}
}
return false;
}
Really simple algorithm, as we are not allowed to do other operations:
public void sort(int[] array){
int size = array.length;
for(int i = 0; i < size; i++){
int minimum = i;
for(int j = i; j < size; j++){
if(array[j] < array[minimum]){
minimum =j;
}
}
moveToFront(minimum);
}
}
Recursive:
public void flatten(Node head){
if(head != null){
System.out.println(head.a);
flatten(head.down);
flatten(head.right);
}
}
Iterative:
public void flatten(Node head){
Stack<Node> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
head = stack.pop();
while(head != null){
System.out.println(head.a);
if(head.right != null)
stack.push(head.right);
head = head.down;
}
}
}
O(n) solution:
public String format(String str, int k){
int size = str.length();
char[] chars = str.toCharArray();
StringBuilder sb = new StringBuilder();
for(int i = size - 1; i >= 0; i++){
sb.append(chars[i]);
if((i + 1) % k == 0)
sb.append(“-”);
}
return sb.reverse().toString();
}
I think the problem here is with the cache. If we cache the list of fraud cards then a fraud card can exists in the original fraud cards list but not in our cache. So the problem is, when do we update our cache? I suppose that usually most of the cards of the users are not fraud cards, so updating each time a card is not in our fraud cards list could be computationally expensive.
Probably there are more specifications that you can ask to the amazon's interviewer. For example you can maybe query the external service to know if there were any changes in the list.
I made a solution for each problem in Java. Although I didn't test the code you can get the idea.
First problem:
public class Subsets{
private int size;
private int[] array;
private List<List<Integer>> results = new ArrayList<>();
public List<List<Integer>> subsets(int[] array, int target){
size = array.length;
this.array = array;
List<Integer> numbers = new LinkedList<>();
subsets(0, target, numbers);
return results;
}
public void subsets(int index, int target, List<Integer> numbers){
if(target == 0){
results.add(numbers);
}else{
if(index < size){
subsets(index + 1, target - array[index], numbers;
subsets(index + 1, target, new LinkedList<>();
}
}
}
}
Second one:
public class Subsets{
private int size;
private WorkItem[] array;
private int maximum;
private List<WorkItem> maximumList;
private List<WorkItem> workItems;
public List<WorkItem> subsets(WorkItem[] array, int money){
size = array.length;
this.array = array;
workItems = new LinkedList<>();
subsets(0, money, 0);
return results;
}
public void subsets(int index, int money, int utility){
if(index < size){
subsets(index + 1, money, utility);
WorkItem workItem = array[index];
//We suppose that there are no negative costs
if(money >= workItem.money){
workItems.add(workItem);
subsets(index + 1, money - workItem.money, utility + workItem.utility);
workItems.remove(workItems.size() - 1);
}
}else{
if(utility > maximum){
maximum = utility;
maximumList = new LinkedList<>();
for(WorkItem workItem : workItems)
maximumList.add(workItem);
}
}
}
}
Third one (I assume that WorkItem has a field "with", which contains the name and the utility of the related item:
public class Subsets{
private int size;
private WorkItem[] array;
private int maximum;
private List<WorkItem> maximumList;
private HashMap<String, WorkItem> workItems;
public List<WorkItem> subsets(WorkItem[] array, int money){
size = array.length;
this.array = array;
workItems = new HashMap<>();
subsets(0, money);
return results;
}
public void subsets(int index, int money){
if(index < size){
subsets(index + 1, money);
WorkItem workItem = array[index];
//We suppose that there are no negative costs
if(money >= workItem.money){
workItems.put(workItem.name, workItem);
subsets(index + 1, money - workItem.money);
workItems.remove(workItem.name);
}
}else{
int utility = 0;
for(WorkItem workItem : workItems.values()){
if(workItem.with != null && workItems.containsKey(workItem.with.name))
utility += workItem.with.utility;
else
utility += workItem.utility;
}
if(utility > maximum){
maximum = utility;
maximumList = new LinkedList<>();
for(WorkItem workItem : workItems.values())
maximumList.add(workItem);
}
}
}
}
This solutions takes O(1) time for query, O(Lamps) time for initializing and O(n) space, being n the size nxn of the grid. It just stores which columns, rows and diagonals are iluminated.
public class Lamps{
private boolean[] columns, rows, diagonalsLeft, diagonalsRight;
public Lamps(int size, int[][] lamps){
this.columns = new boolean[size];
this.rows = new boolean[size];
this.diagonalsLeft = new int[(size - 1) * 2 + 1];
this.diagonalsRight = new int[(size - 1) * 2 + 1];
for(int[] lampcoor : lamps){
int x = lampcoor[0];
int y = lampcoor[1];
this.columns[x] = true;
this.rows[y] = true;
this.diagonalsLeft[x + y] = true;
this.diagonalsRight[x - y] = true;
}
}
public boolean query(int x, int y){
if(columns[x] || rows[y] || diagonalsLeft[x + y] || this.diagonalsRight[x - y])
return true;
}
}
How is the graph represented?
- libertythecoder October 14, 2016I did not remember that it was SPARSE, but in any case you can get the idea. The time complexity is O(rows) or O(columns):.
public class NotSparseMatrix{
private int[][] matrix;
private int[][] columnSum;
private int rows, columns;
public SparseMatrix(int rows, int columns){
this.columns = columns;
this.rows = rows;
this.matrix = new int[columns][rows];
this.columnSum = new int[columns][rows];
}
public void set(int row, int col, int val){
if(row < rows && col < columns){
int difference = val - matrix[col][row];
for(int i = row; i < rows; i++){
columnSum[col][i] += difference;
}
}
}
public int sum(int row, int col){
int result = 0;
if(row < rows && col < columns){
for(int i = 0; i <= col; i++){
result += columnSum[i][row];
}
}
return result;
}
}
Easy and clean code:
public boolean existsPair(int[] array1, int[] array2){
Hashset<Integer> set = new Hashset<>();
for(int num : array1)
set.add(num);
for(int num : array2)
if(set.contains(-num))
return true;
return false;
}
The best way to optimize space and avoid problems with cycles is having a reference to the nodes of the new graph. It can also be done using a data structure like a Hashmap but it wastes more memory.
public Node copyGraph(Node root){
Node next = root;
int size = 0;
while(next != null && next.copy == null){
next.copy = new Node();
next = next.next;
size++;
}
next = root;
Node copyNext = root.copy;
while(size > 0){
if(next.next != null)
copyNext.next = next.next.copy;
next = next.next;
copyNext = copyNext.next;
size--;
}
next = root;
while(next.copy != null){
next.copy = null;
next = next.next;
}
}
This solution takes O(n) time.
int careercup(int[] array, int max){
if(max <= 0)
return 0;
int size = array.length;
int left = 0;
int sum = 0;
int count = 0;
int maxCount= 0;
for(int i = 0; i < size; i++){
int word = array[i];
if(sum + word <= max){
sum += word;
count++;
}else{
if(count > maxCount)
maxCount = count;
sum += word;
while(left <= i && sum > max){
sum -= array[left];
left++;
count--;
}
}
}
if(count > maxCount)
maxCount = count;
return maxCount;
}
Easy recursive solution. I use the variable "currentStack" in order to avoid repeated states (for example poping from the first stack and then the second one is the same as poping from the second one and then from the first one).
- libertythecoder November 28, 2016