thelineofcode
BAN USER@Nasser Ghazali reread the question with understanding and count to two.
BBB is not duplicated character but triplet. If you reduce the duplicated character the answer is AB. How do you want to reduce AB? Your logic is incorrect .
@puneet.sohi because the array my be very large say 10 000 elements and the range may be almost equal to the number of elements in the array. E.g {1,2...x10 000, 3} - there are 10 000 twos. If you start walking linearly you will not get log(n) time but O(n).
- thelineofcode April 11, 2014Agree, it can be done in O(logn) using binary search but not O(1)
- thelineofcode April 09, 2014Java code:
public static int findFirst(int[] a, int n) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == n) {
if (m == 0 || a[m - 1] != n) {
return m;
} else {
r = m;
}
} else if (a[m] > n) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
public static int findLast(int[] a, int n) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == n) {
if (m == a.length - 1 || a[m + 1] != n) {
return m;
} else {
l = m;
}
} else if (a[m] > n) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
Since the array is sorted use binary search to find first and last occurrence of the number.
- thelineofcode April 09, 2014This is backtracking problem.
Start from the second from last character and compare it with the last character.
If they are the same remove both characters. And recursively repeat the process every time comparing chars[i] with chars[i+1].
Code:
public static String removeDups(String s) {
return removeDups(new StringBuilder(s), 0).toString();
}
public static StringBuilder removeDups(StringBuilder sb, int pos) {
if(pos == sb.length()-1) {
return sb;
}
sb = removeDups(sb, pos+1);
if(sb.charAt(pos) == sb.charAt(pos+1)) {
sb.deleteCharAt(pos+1);
sb.deleteCharAt(pos);
}
return sb.length() == 0 ? new StringBuilder("-1") : sb;
}
Just make modified version of BFS. Instead of using single list create two: List<Node> currentLevel and List<Node> nextLevel:
- currentLevel - stores elements for the level which is being precessed.
- nextLevel - stores the children of the current level
In this way you can control the level which you are processing without mixing it with its children.
For the current level count the number of negative numbers. And choose the one which has max number of neg numbers.
Code:
public static void findLevelWithMaxNeg(Node root) {
List<Node> currentLevel = new ArrayList<Node>();
List<Node> nextLevel = new ArrayList<Node>();
currentLevel.add(root);
int levelWithMaxNeg = -1;
int maxNeg = 0;
int currentNeg = 0;
int levelNo = 0;
int i = 0;
while (i < currentLevel.size()) {
i++;
Node node = currentLevel.get(i);
if (node.value < 0) {
currentNeg++;
}
if (node.left != null) {
nextLevel.add(node.left);
}
if (node.right != null) {
nextLevel.add(node.right);
}
if (i == currentLevel.size()) {
if (currentNeg > maxNeg) {
maxNeg = currentNeg;
levelWithMaxNeg = levelNo;
}
levelNo++;
currentNeg = 0;
currentLevel.clear();
currentLevel.addAll(nextLevel);
nextLevel.clear();
i = 0;
}
}
System.out.println("Level with the most num of negetive number: " + levelWithMaxNeg);
}
Just quick implementation:
public static boolean isPerfectSq(int n) {
int l = 0;
int r = n;
while (l <= r) {
int mid = l + (r - l) / 2;
int sq = mid * mid;
if (sq == n) {
System.out.println(mid);
return true;
} else if (sq > n) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
Since you want to find k smallest elements max heap is more relevant (every time you have to remove max element in O(1) time). If current el is smaller then max remove max and insert a new element.
- thelineofcode April 07, 2014If you want the output to be ordered print combinations from the shortest to the longest:
public static void main(String[] args) {
int[] a = { 1, 2, 3 };
for (int i = 1; i <= a.length; i++) {
printCombo(a, new int[i], 0, 0, i);
}
}
public static void printCombo(int[] a, int[] result, int pos, int start, int comboLength) {
if (pos == comboLength) {
System.out.println(Arrays.toString(result));
return;
}
for (int i = start; i < a.length; i++) {
result[pos] = a[i];
printCombo(a, result, pos + 1, i + 1, comboLength);
}
}
Based on your example the output can not contain duplicates like [3,3,3].
Here is simple recursion in Java.
public static void main(String[] args) {
int[] a = { 1, 2, 3 };
printCombo(a, new StringBuilder(), 0, 0);
}
public static void printCombo(int[] a, StringBuilder result, int pos, int start) {
if (result.length() == a.length) {
return;
}
for (int i = start; i < a.length; i++) {
result.append(a[i]);
System.out.println(result);
printCombo(a, result, pos + 1, i + 1);
result.setLength(result.length() - 1);
}
}
@PKT if you want to change the question create a new one instead of editing old one. Now the answer is irrelevant.
- thelineofcode April 06, 2014My first impression is that the 'file' is only in the scope of try{} not in 'finally'.
- thelineofcode April 06, 2014I believe that Dijkstra's algorithm would be better the BFS.
- thelineofcode April 03, 2014Expand each interval and use "quick select" algo to find ith smallest number.
Space O(n), time O(n).
I would use graph to solve this problem.
The dictionary of valid words is given.
1) Construct the graph where each node represents a word from the dictionary. Connect a words which differ only by one letter.
2) Find the shortest path between str1 and str2. If path not exists print error msg.
1) Use XOR operator - xor each element in the array then duplicated elements will reduce each other ; time O(n), space O(1)
2) Use Set - add elements to the Set. If the set already contains given element then remove from the set. At the end set will contain only not duplicated element; time O(n), space O(n)
3) Sort array and use running counter to find not duplicated element; time O(nlogn), space O(1)
You can construct Trie. Each node which represent the last letter for the name may have List<String> which stores numbers for given name.
Additional benefits for this solution are:
1) Sorting of phone book is very easy by only pre-order traversal of the trie
2) Finding names which matches given prefix
It can be done in O(n) time.
1) You have to compute the product from the whole array
2) Then the result can be computed in the following way
output[i] = product / input[i]
3) You just have to take care of the corner cases which is zero elements
a) If the array has more then one zero elements then the output will contain only zeros
b) If the array has one zero then the output for the input[i] == 0 is equal product from the remaining elements and the remaining elements are equal 0.
You can check my implementation for better understanding though it was down-voted by someone who misunderstand that solution.
Formatted version:
public static void main(String[] args) {
int prod = 1;
int noOfZeros = 0;
int[] arr = { 3, 0, 0, 2 };
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
prod *= arr[i];
} else {
noOfZeros++;
if (noOfZeros > 1) {
break;
}
}
}
if (noOfZeros > 1) {
Arrays.fill(arr, 0);
} else {
for (int i = 0; i < arr.length; i++) {
if (noOfZeros == 1) {
if (arr[i] == 0) {
arr[i] = prod;
} else {
arr[i] = 0;
}
} else {
arr[i] = prod / arr[i];
}
}
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
int prod = 1;
int noOfZeros = 0;
int[] arr = { 3, 0, 0, 2 };
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
prod *= arr[i];
} else {
noOfZeros++;
if (noOfZeros > 1) {
break;
}
}
}
if (noOfZeros > 1) {
Arrays.fill(arr, 0);
} else {
for (int i = 0; i < arr.length; i++) {
if (noOfZeros == 1) {
if (arr[i] == 0) {
arr[i] = prod;
} else {
arr[i] = 0;
}
} else {
arr[i] = prod / arr[i];
}
}
}
System.out.println(Arrays.toString(arr));
}
Does the array contain also negative numbers?
- thelineofcode March 21, 2014For what input?
- thelineofcode March 18, 2014This is known as dutch flag problem. To partition the table correctly you only need isLow() and isHigh() functions.
public static void dutchFlag(int[] a) {
int i = 0;
int p = 0;
int r = a.length - 1;
while (i <= r) {
if (isLow(a[i])) {
swap(a, i++, p++);
} else if (isHigh(a[i])) {
swap(a, i, r--);
} else {
i++;
}
}
System.out.println(Arrays.toString(a));
}
public static boolean isLow(int input) {
if (input < 0)
return true;
return false;
}
public static boolean isHigh(int input) {
if (input > 100)
return true;
return false;
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
You can do this using one array and save some space:
public static void products2(int[] a) {
int n = a.length;
int[] products = new int[n];
int p = 1;
for (int i = 0; i < n; ++i) {
products[i] = p;
p *= a[i];
}
p = 1;
for (int i = n - 1; i >= 0; --i) {
products[i] = p * products[i];
p *= a[i];
}
System.out.println(Arrays.toString(products));
}
To make things even more interesting we can do this recursively:
public static int recursive(int[] a, int[] products, int index, int p) {
if (index == a.length) {
return 1;
}
products[index] = p;
int result = recursive(a, products, index + 1, p * a[index]);
products[index] = products[index] * result;
return result * a[index];
}
If there is only one number which appears odd number of times you can XOR all numbers and at the end you will get the 'odd' number. In you example there are multiple 'odd' numbers 11,0,-2 so you have to count them. To do that you can use HashMap or to save some space sort numbers and keep running counter.
- thelineofcode February 27, 2014question?id=5349248069533696
- thelineofcode February 26, 2014Swapping alternate elements solves the problem
private static void arrangeList(int A[]) {
for (int i = 1; i < A.length; i++) {
if (i % 2 == 1 && A[i] < A[i - 1])
swap(A, i, i - 1);
if (i % 2 == 0 && A[i] > A[i - 1])
swap(A, i, i - 1);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
It's not correct answer. You are assuming that the threes have the same structure whereas the threes can have different structure and the same in order traversal.
E.g
3
/ \
2 4
and
2
\
3
\
4
Just keep the product of 'n' running elements and every time compare it with the max product which has been found so far.
Java:
public static void findProduct(int[] arr, int n) {
int product = 1;
int maxProd = Integer.MIN_VALUE;
int startIndex = -1;
int endIndex = -1;
for (int i = 0; i < arr.length; i++) {
product *= arr[i];
if (i >= n - 1) {
if (i == n - 1) {
maxProd = product;
startIndex = 0;
endIndex = i;
} else {
product /= arr[i - n];
if (product > maxProd) {
maxProd = product;
startIndex = i - n + 1;
endIndex = i;
}
}
}
}
System.out.println("Start index: " + startIndex + ", endIndex: " + endIndex + ", product: " + maxProd);
}
Consider 2 cases:
1) String contains odd number of characters. Then the number of all characters in the string should be even except one character which is located in the middle.
2) String contains even number of characters. Then all characters should be even.
For simplicity I assumed that there are only English capital letters. If not its minor fix to change it.
public static void main(String[] args) {
String s = "AABB";
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'A']++;
}
int middleChar = -1;
StringBuilder sb = new StringBuilder(s.length());
int i = 0;
for (i = 0; i < count.length; i++) {
if (count[i] % 2 == 1) {
if (count[i] == 1 && middleChar == -1) {
middleChar = i;
count[i]--;
} else {
break;
}
} else if (count[i] != 0) {
for (int j = 0; j < count[i] / 2; j++) {
sb.append((char) (i + 'A'));
count[i]--;
}
}
}
if (i != count.length) {
System.out.println("Could not create the palindrome.");
return;
}
if (middleChar != -1) {
sb.append((char) (middleChar + 'A'));
}
i = count.length - 1;
while (i >= 0) {
if (count[i] == 0) {
i--;
continue;
}
sb.append((char) (i + 'A'));
count[i]--;
if (count[i] == 0) {
i--;
}
}
System.out.println(sb);
}
public static Node swapElRec(Node head, int k) {
if (head == null) {
return null;
}
Node current = head;
Node next = head.next;
head.next = null;
int i = 0;
while (next != null && i < k - 1) {
Node temp = next.next;
next.next = current;
current = next;
next = temp;
i++;
}
if (next != null) {
head.next = swapElRec(next, k);
}
return current;
}
I was logged out :D
- thelineofcode February 15, 20141) First you have to find a candidate to which ai and aj will be adjusted. To do this
count numbers and choose number which appears most often.
2) Take one number which is smaller then the candidate ai and one which is bigger aj and increment/decrements them respectively.
3) The result is equal candidate's number of occurrence + 2.
There is one border condition when the candidate is the biggest number in the array which means that you cant find aj to decrement. In that case you have to check if
'candidate's number of occurrence' - 'numOfOccurr of the secend most frequent number' >=1. Otherwise change the candidate to the second most frequent number.
Data:
P(0) = 0.4
P(1) = 0.6
Observation:
P(0) * P(1) = P(1) * P(0) = 0.4 * 0.6 = 0.6 * 0.4
The probability of generating pairs (0, 1) and (1, 0) is equal.
Solution:
Generate the pair of numbers:
a) num1 = f();
b) num2 = f();
Keep generating num2 till num1 == num2. Once you generated two different numbers return num1. Hence P(1) = P(0) = 0.5
Code:
public int f1() {
int v = f();
int v2 = v;
while(v == v2) {
v2 = f();
}
return v;
}
This problem is known as activity selection problem. Detailed description can be found on wiki. Here is java implementation.
public static void main(String[] args) {
Comparator<Meeting> comp = new Comparator<SelectionProblem.Meeting>() {
@Override
public int compare(Meeting o1, Meeting o2) {
return new Long(o1.endTime).compareTo(new Long(o2.endTime));
}
};
Queue<Meeting> meetings = new PriorityBlockingQueue<SelectionProblem.Meeting>(6, comp);
Queue<Meeting> overlapMeetings = new PriorityBlockingQueue<SelectionProblem.Meeting>(6, comp);
initMeetings(overlapMeetings);
int rooms = 0;
int numberOfMeetings = 0;
do {
rooms++;
numberOfMeetings = overlapMeetings.size();
meetings.clear();
meetings.addAll(overlapMeetings);
overlapMeetings.clear();
Meeting currentMeeting = meetings.poll();
while (!meetings.isEmpty()) {
Meeting nextM = meetings.poll();
if (nextM.startTime >= currentMeeting.endTime) {
currentMeeting = nextM;
} else {
overlapMeetings.add(nextM);
}
}
} while (overlapMeetings.size() + 1 != numberOfMeetings && !overlapMeetings.isEmpty());
if (!overlapMeetings.isEmpty()) {
rooms += overlapMeetings.size();
}
System.out.println("Number of rooms: " + rooms);
}
I assume that the pool hast to consist of at least two 0s.
Java:
public static void main(String[] args) {
int poolSize = 0;
boolean secPool = false;
int[][] m = { { 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 1 }, { 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
if (m[i][j] == 0 && poolSize == 0) {
poolSize = findPool(i, j, m);
} else if (m[i][j] == 0 && poolSize > 0) {
secPool = true;
break;
}
}
if (secPool) {
break;
}
}
System.out.println("Found pool: " + (poolSize > 1 && !secPool));
}
public static int findPool(int i, int j, int[][] m) {
if (m[i][j] == 1 || i < 0 || i > m.length - 1 || j < 0 || j > m[0].length - 1) {
return 0;
}
m[i][j] = 1;
int left = findPool(i, j - 1, m);
int right = findPool(i, j + 1, m);
int up = findPool(i - 1, j, m);
int down = findPool(i + 1, j, m);
return left + right + up + down + 1;
}
Java:
transpose("abcde".toCharArray(), "bcdae".toCharArray());
public static void transpose(char[] s1, char[] s2) {
int i = 0;
System.out.println(Arrays.toString(s1));
System.out.println(Arrays.toString(s2) + "\n");
while (i < s2.length) {
if (s2[i] == s1[i]) {
i++;
System.out.println(Arrays.toString(s1));
} else {
int j = i;
while (j < s1.length - 1 && s2[i] != s1[i]) {
char temp = s1[j];
s1[j] = s1[j + 1];
s1[j + 1] = temp;
j++;
}
}
}
System.out.println("\n" + Arrays.toString(s1));
System.out.println(Arrays.toString(s2));
}
You can also use .charAt() if you want to save some space but I think it's not the key in this question.
- thelineofcode February 08, 2014I believe we can solve it in the same way which was described here: id=5568707711467520.
In this case the weight is equal population.
Create to auxiliary arrays
- 'row' where row[i] contains multiplication for i-th row - (-1 if product is < 0 ; 1 if product > 0; 0 if product == 0)
- 'col' where col[j] contains multiplication for j-th column. Rules are the same as for rows
I think the rest is self explaining if you check the implementation.
Code:
public static void main(String[] args) {
int[][] m = { { 1, 2, 3, 1 }, { 1, 0, -1, 2 }, { -1, 1, 1, 1 } };
int[] row = new int[m.length];
int[] col = new int[m[0].length];
Arrays.fill(row, 1);
Arrays.fill(col, 1);
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
if (m[i][j] < 0) {
row[i] *= -1;
col[j] *= -1;
} else if (m[i][j] == 0) {
row[i] = 0;
col[j] = 0;
}
m[i][j] = 1;
}
}
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
m[i][j] *= row[i] * col[j];
}
}
}
If I understand you question correctly you want to count all digits from numbers in range <1 - n>. I'm not sure if there is any better approach then brute force:
public static void main(String[] args) {
int[] counters = new int[10];
BigInteger n = new BigInteger("1000000");
BigInteger start = new BigInteger("1");
while (start.compareTo(n) == 0 || start.compareTo(n) == -1) {
String s = start.toString();
for (int i = 0; i < s.length(); i++) {
counters[s.charAt(i) - '0']++;
}
start = start.add(BigInteger.ONE);
}
int num = 0;
for(int c : counters) {
System.out.println("Number: "+(num++)+" - count: "+c);
}
}
The only problem is that we have to deal with BigIntegers to handle the worse case. (assuming Java implementation). I would suggest the interviewer to run this code in parallel by multiple threads where each thread would compute numbers from some subrange of the original problem and then combine the results.
- thelineofcode February 06, 2014I can't see the picture.
- thelineofcode February 06, 2014Trie is better from HashTable with respect to space complexity. If you have to words with common prefix e.g abc abcde you still have to create to separate keys in HT whereas in trie the words share common prefix part.
But if access time is the most important factor the HT is better. So I think you should have explained both approaches and compare their pros and cons.
I think my solution is not the most optimal but it should solve the problem.
For any permutation of words in the dictionary check if the longest common substring between concatenated dictionary's words and input string is equal to the input string.
Keep generating permutation till the match is found.
1) Sort the list first.
2) Using binary search find last number which is not bigger then k. Lets say this number is located at position 'p'.
3) Create to pointer which initially are at the following positions:
- start = 0
- end = p
4) Check following conditions:
pseudo code:
while (start < end) {
int sum = arr[start] + arr[end];
if(sum == k) {
print arr[start], arr[end];
start++;
end--;
} else if (sum > k) {
end--;
} else {
print arr[start], arr[end];
start++;
}
}
O(nlogn)
- thelineofcode February 05, 2014@charu1806 n can be as big as possible. Basically I don't know why you think that the program can't handle bigger values so here is short explanation.
There are a few rules which has to be taken into account.
1) The result has to be the shortest possible number since any additional digit increment the value.
2) Factors of n has to be sorted in ascending order 828 is bigger then 288.
3) The biggest digit which can be placed at single position is 9 so we start from this value and keep appending it to the result till the number is divisible by 9.
4) Repeat the process for the remaining factors till number is equal 1.
Java:
public static String findFactors(int number) {
String result = "";
int factor = 9;
while (factor > 1 && number > 1) {
while (number % factor == 0) {
number /= factor;
result = factor + result;
}
factor--;
}
return result;
}
I believe in case when there are several odd numbers you can solve it in two ways:
1) The one which you have already mentioned using HashSet-Time O(n), Space O(n)
2) Sort the array and then iterate keeping the running counter of the current number. When you reach a new number check if the counter is odd and print number if it is. Time O(nlogn), Space O(1)
@Ricky consider three cases:
1) a[m] == m - this is what we want to get if this condition is met the index is returned.
2) arr[m] > m e.g. {0,1,5,6,7} - a[3] = 5. Since we know that array is sorted and contains distinct elements we can skip the right side of the array because all elements >=3 are incorrect.
3) arr[m] < m e.g. {-2,-1,0,1,2} - a[3] = 0. We can skip the left side of the array because all elements <= 3 are incorrect.
Just like in case of binary search.
I've just realized that @Nasser Ghazali was right and the current implementation is not working correctly although he removed his comment. The general idea didn't changed though. This is still backtracking problem.
1) Start iterating from the end of the string.
2) Count duplicated characters.
3) Once you find a point at which characters are not the same remove the following duplicated characters.
4) Recursively repeat the process
Fixed implementation:
@Nasser Ghazali thanks for pointing it out.
- thelineofcode April 12, 2014