thelineofcode
BAN USER@Anonymous, fixed.
- thelineofcode February 02, 2014@kesar you're right I provided the fix.
- thelineofcode February 02, 2014There are to cases which we have to handle:
1) If array is sorted in ascending order then
we have to find the first point at which left side of the array is smaller then right side.
2) If array is sorted in descending order then
we have to find the first point at which right side of the array is smaller then left side.
Choose the min value from 1 and 2
Code:
public static void main(String[] args) {
// int[] arr = { 4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3 };
int[] arr = { 3, 2, 1, 6, 5, 4 };
int l = 0;
int r = arr.length - 1;
while (arr[l] > arr[r]) {
int m = l + (r - l) / 2;
if (arr[m] > arr[r]) {
l = m + 1;
} else {
r = m;
}
}
int minAcs = arr[l];
l = 0;
r = arr.length - 1;
while (arr[r] > arr[l]) {
int m = (l + (r - l) / 2) + 1;
if (arr[m] > arr[l]) {
r = m - 1;
} else {
l = m;
}
}
System.out.println("value: " + Math.min(minAcs, arr[r]));
}
O(log n)
- thelineofcode February 02, 20141) Iterate over the array (n - k) times.
2) In each iteration find the pair of elements for which abs(a[j] - a[i]) is minimal.
3) Merge a[i] and a[j] and add total += abs(a[j] - a[i]);
Code:
public static void main(String[] args) {
int n = 4;
int k = 2;
Integer arr[] = { 1, 2, 5, 7 };
int numberOfRelocations = n - k;
int totalDiff = 0;
int toMerge = 0;
for (int i = 0; i < numberOfRelocations; i++) {
int minDiff = Integer.MAX_VALUE;
for (int j = 0; j < arr.length - 1; j++) {
if (arr[i] == null)
continue;
for (int l = j + 1; l < arr.length; l++) {
if (arr[j] == null)
continue;
if (minDiff > Math.abs(arr[l] - arr[j])) {
toMerge = arr[l] > arr[j] ? j : l;
minDiff = Math.abs(arr[l] - arr[j]);
}
}
}
totalDiff += minDiff;
arr[toMerge] = null;
}
System.out.println(totalDiff);
}
O((n-k)*n^2)
- thelineofcode February 01, 2014Yup, I'm wondering whether this question with such memory constraints was really asked by google or it is just the invention of the author.
- thelineofcode February 01, 2014Its O(n^2) solution.
- thelineofcode February 01, 2014The array is sorted so the better approach is to use binary search.
- thelineofcode February 01, 2014I doesn't say that we can't flip coins either. If it mentioned flipping then it would suggest the solution. I believe it is not the intention of the interviewer to give tips in the question.
- thelineofcode January 31, 2014Split coins on two groups.
G1 = 10 coins; G2 = 90 coins
Coins can be distributed among the groups as follows
G1 G2
10H 90T
9H 1T 89T 1H
8H 2T 88T 2H
.
.
.
1H 9T 81T 9H
10T 80T 10H
So flip either group and then number heads should be equal.
- thelineofcode January 31, 2014@chriscow in your explanation you have to change the part
* ( 1 - Prob(box i+1 is NOT picked at step i+1) )
into
* ( 1 - Prob(box i+1 is picked at step i+1) )
since
1 - Prob(box i+1 is picked at step i+1) = Prob(box i+1 is NOT picked at step i+1)
Java:
public static int findDistance(String s, String word1, String word2) {
String[] words = s.split(" ");
int p = -1;
int dist = s.length();
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p = i;
} else if (words[i].equals(word2)) {
if (p != -1 && i - p < dist) {
dist = i - p;
}
p = -1;
}
}
return dist == s.length() ? -1 : dist;
}
For this input we just have to keep a set of unique numbers different then 1.
These are nodes which are connected neither to tail nor any 'good' node.
The size of the set is the number of nodes which have to be changed.
For the examples given in question:
a) 5 5 5 5 5 5 - set is {5} - change one element the remaining elements are pointing to it.
b)1 2 3 4 5 - set is {2 3 4 5} - None of the nodes is connected to the 'good' node so all of them have to be changed.
I don't see any reason to construct a graph while we are able to determine the connections based on the node's values.
Isn't just about rotating the list about k positions so as to put number on its correct position?
1) Convert the list to the array to quickly access random elements.
2) Rotate array about k positions.
3) Reconstruct the list from the rotated array
Check wiki/Verbal_arithmetic
- thelineofcode January 27, 2014KMP is one of the easiest algorithms to write on the board. Reasonably prepared candidate should do this in no more then 10 min.
- thelineofcode January 27, 2014Java:
public static void main(String[] args) {
int[] arr = { 3, 1, 2, 0 };
for (int i = 0; i < arr.length; i++) {
int index = i;
Set<Integer> set = new HashSet<Integer>();
while (!set.contains(arr[index])) {
set.add(arr[index]);
index = arr[i];
}
System.out.println(set);
}
}
@Novice, there was a bug in choosing root I provided the fix. Thx for pointing it out
- thelineofcode January 25, 20141) Map each input like Map<Integer, List<Integer>>; key - parentId, value children's list.
2) Recursively reconstruct the tree.
Code:
public static void main(String[] args) {
int[][] nodes = { { 2, 4 }, { 1, 2 }, { 3, 6 }, { 1, 3 }, { 2, 5 } };
Map<Integer,List<Integer>> treeMap = new HashMap<Integer,List<Integer>>();
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
int rootCandidate = nodes[0][0];
for (int i = 0; i < nodes.length; i++) {
List<Integer> children = null;
if (treeMap.containsKey(nodes[i][0])) {
children = treeMap.get(nodes[i][0]);
} else {
children = new ArrayList<Integer>();
treeMap.put(nodes[i][0], children);
}
children.add(nodes[i][1]);
childParentMap.put(nodes[i][1], nodes[i][0]);
}
while(childParentMap.containsKey(rootCandidate)) {
rootCandidate = childParentMap.get(rootCandidate);
}
System.out.println(reconstructTree(treeMap, rootCandidate));
}
public static Node reconstructTree(Map<Integer, List<Integer>> treeMap, int v) {
Node root = new Node(v);
if (treeMap.get(v) == null || treeMap.get(v).isEmpty()) {
return root;
}
root.left = reconstructTree(treeMap, treeMap.get(v).get(0));
if (treeMap.get(v).size() == 2) {
root.right = reconstructTree(treeMap, treeMap.get(v).get(1));
}
return root;
}
Use KMP algo.
- thelineofcode January 25, 2014I doesn't make sense. If you remove all L2's elements from L1 in first operation then
L2.removeAll(L1)
does nothing. To make it work you have to store original L1 in additional variable which I believe is bad solution considering memory constraints and objects size.
- thelineofcode January 24, 2014Because lists contain large amount of data and we are probably almost out of memory creating additional objects like HashMap to count occurrence of each element is not good solution. So I would suggest sorting both lists and keeping two pointers iterate over both lists choosing not repeated elements.
- thelineofcode January 24, 2014Do we know how many offices is reserved for developers and testers?
- thelineofcode January 24, 2014You can always check your previous question id=5664748918013952 :)
- thelineofcode January 24, 2014Can s3 contain common characters for s1 and s2? E.g s1=abc, s2, =abc, s3 = abcd
What is the correct output true or false?
1) Count two cumulative sums from left to right and from right to left. Store the results in corresponding arrays.
2) Iterate over the left -> right array and check if at any position leftRight[i] == rightLeft[i+1] if yes current position is a breaking point.
Code:
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 2, 5, 4, 4 };
int[] leftRightSum = new int[arr.length];
int[] rightLeftSum = new int[arr.length];
leftRightSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
leftRightSum[i] = arr[i] + leftRightSum[i - 1];
}
rightLeftSum[arr.length - 1] = arr[arr.length - 1];
for (int i = arr.length - 2; i >= 0; i--) {
rightLeftSum[i] = arr[i] + rightLeftSum[i + 1];
}
for (int i = 0; i < arr.length - 1; i++) {
if (leftRightSum[i] == rightLeftSum[i + 1]) {
System.out.println("Breaking point is at " + i);
}
}
}
Note you can skip one array and keep only running counter. However I kept it for better demonstration.
- thelineofcode January 23, 2014Use double ended queue containing data from the last 60s.
When new data were sent remove old ones (which exceed 60s) from the end of the queue and add new data on the beginning of the queue.
First scan array to find appropriate row, column ad depth and then do the replacement.
Code:
public static void setZeros(int[][][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
int[] depth = new int[matrix[0][0].length];
// Store the row, column and depth index with value <= 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
for (int k = 0; k < matrix[0][0].length; k++) {
if (matrix[i][j][k] <= 0) {
row[i] = 1;
column[j] = 1;
depth[k] = 1;
}
}
}
}
// Set matrix[i][j][k] to 0 if either row i, column j or depth k is <= 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
for (int k = 0; k < matrix[0][0].length; k++) {
if (row[i] == 1 || column[j] == 1 || depth[k] == 1) {
matrix[i][j][k] = 0;
}
}
}
}
}
Check leetcode - longest-palindromic-substring-part-ii. There is explained O(n) solution using Manacher’s Algorithm.
- thelineofcode January 22, 2014Just google for 'Vending Machine DP' problem.
- thelineofcode January 22, 2014You have already asked the same question id=5131269318901760, haven't you?
- thelineofcode January 21, 2014We can solve it using stacks. Search each node in the tree and construct stacks which contain paths from root to given node. E.g
stack 1 | stack 2 ... stack k
root root
parent 1 parent 1
parent 2 parent 2
parent 3 parent 3
parent 4 node 2
node 1
Till some point stacks will contain the same parents for all nodes. The latest common parent for all nodes is the answer.
- thelineofcode January 19, 2014Well I think we should do post order traversal so that we start searching from the bottom of the tree. Every time we find 0 which any of the children is different from 0 do the following relocation:
1) Swap not 0 child with the 0 parent
2)Repeat 1 point till both children of 0 parent are also equal 0 or 0 parent is leaf node.
id=4834282094723072
- thelineofcode January 18, 2014Did you test it?
For "1234", "111" returns 4432.
You should add digits from the end not from the beginning.
You can represent numbers as a List where each digit is the node in the list and then
perform add operation like on the paper.
Use to stacks and print them interchangeably.
public static void zigzag(BinaryTreeNode node) {
Stack<BinaryTreeNode> currentStack = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> nextStack = new Stack<BinaryTreeNode>();
currentStack.add(node);
zigzag(currentStack, nextStack, true);
}
private static void zigzag(Stack<BinaryTreeNode> currentStack, Stack<BinaryTreeNode> nextStack, boolean reverse) {
while (!currentStack.isEmpty()) {
BinaryTreeNode pop = currentStack.pop();
System.out.println(pop);
if (reverse) {
if (pop.left != null)
nextStack.push(pop.left);
if (pop.right != null)
nextStack.push(pop.right);
} else {
if (pop.right != null)
nextStack.push(pop.right);
if (pop.left != null)
nextStack.push(pop.left);
}
zigzag(nextStack, currentStack, !reverse);
}
}
What is the structure of the log file? Is it just a sequence of the page names e.g. 'page1, page2, page3' or there are some additional attributes like user name -> page?
- thelineofcode January 16, 2014So what is the output for {12, -3, 12, 12, 8} ?
Note -3 + 8 = 1 + 4
Wow, someone down voted this answer without the explanation. I'm wondering what is wrong with this solution. :D
- thelineofcode January 14, 2014@krylloff, as you have already noticed you didn't understand the algo. I gave a step by step example for better understanding. You don't swap 5 with 1 but with 'the smallest bigger digit from 5' which is 6. So you swap 5 and 6. The output is 261234557 which is correct answer.
- thelineofcode January 14, 2014It looks like the service is down. I updated my post with a new link which contains the same description as the previous one.
- thelineofcode January 13, 2014Algo:
1) Starting from the end of the number keep checking each digit and store max value till the following condition is met:
if(next digit > max)
Once you found max value which is bigger then next digit break.
2) Lets say first smaller digit n which is < max is located on position i.
3) Find the smallest digit which is bigger then n between number which has already been processed (i+1 - length of number) (max value doesn't have to be the smallest bigger digit).
4) Swap n[i] and the number found in 3
5) Sort number located after after i-th position in a ascending order
In your example 2576
1) Starting from the end 6 < 7, 7 > 5 - max is 7 - break;
2 - 3) Find the smallest bigger digit from 5 between 6-7 which is 6.
4) Swap 6 and 5 - 2675
5) Sort number located after 6 in ascending order 2657
This problem is known as telephone words and can be solved using simple recursion.
- thelineofcode January 13, 2014Create Map<String, List<String>>.
- Key is a sorted string.
- Values is a List of strings which after sorting are equal to the key and the original key itself.
Code:
public static void findAnagrams(String[] arr) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String s : arr) {
char[] temp = s.toCharArray();
Arrays.sort(temp);
String sortedString = new String(temp);
List<String> anagrams = null;
if (map.containsKey(sortedString)) {
anagrams = map.get(sortedString);
} else {
anagrams = new ArrayList<String>();
map.put(sortedString, anagrams);
}
anagrams.add(s);
}
for (String key: map.keySet()) {
System.out.println(map.get(key));
}
}
It's not so simple. Consider the matrix
0 0 0
0 0 0
1 1 1
Output should be 3 but this algo will return 1 since all 1's are located on the edge.
Here is good solution id=15420704.
The other one is here.
belbesy.wordpress.com/2011/03/11/uva-108-maximum-sum/
@DS the algorithm you provided is for finding largest square whereas the question states that it may be rectangle as well
- thelineofcode January 13, 2014We can use stack to solve this problem.
Keep adding elements on the stack till the top of the stack is different then the currently added element. If they are the same remove the top and increment counter. For your example.
1) Add Y, R, G to the stack, next element is G so remove G and increment counter = 1;
2) Stack is Y,R - next is also R so remove the top, counter = 2;
3) Stack is Y, - next is R so add it.
5) Stack is Y R - add G
6) Stack is Y R G - next is also G so remove G, counter = 3
7) Stack is Y R - next is also R so remove the top, counter = 4
8) Stack is Y - the last element is Y, counter = 5
9) Stack is empty.
This algorithm returns k closest pairs. However, the distance between each pair might be very large like ((2,1)(2,2)), ((10,11)(10,12)) and in the end it won't be closest points.
- thelineofcode January 13, 2014
Again binary search does the job
Code
- thelineofcode February 02, 2014