madi.sagimbekov
BAN USERThe solution is to build maxHeap of 100 elements according to the distances of planes to the tower, and each time a plane is detected or distances are changed heap must be rebuild, it means at any moment you can show the 100 planes which are closest to the tower.
- madi.sagimbekov December 24, 2015The problem is to find nearest 100 planes, in your solution what if there are less than 100 planes within radius RadiusLimit? what if there is no plane within radius RadiusLimit?
- madi.sagimbekov December 24, 2015long pow(int a, int b) {
long x = pow(a, b/2);
if (b % 2 == 0) {
return x * x;
} else {
return x * x * b;
}
}
I think firstly we should ask what type of elements are in array, if it is small integer numbers, we can create a boolean array X with size equal to maximum element, and iterate through given array and make X[arr[i] - 1] = true if its false, otherwise return arr[i].
If the length of given array is greater than the maximum element in array and if elements are nonnegative integers, we can just iterate through given array and check if a[i] < 0 then return i, else a[a[i]] = -a[a[i]],
if elements are not integers or contain negative numbers etc, we can use hashmap to solve it.
split string with delimeter #, lets say result arrays size is x, if 8*x + 1 is not perfect square then output "invalid", if any array element is empty then output "invalid", else
get biggest element from M element and add to SUM, where M is initially 1, after finding max value among M elements increase M by 1 (M++), return SUM.
public class TriangleSum {
public static void main(String... args) {
String str = "1#2#30#5#6#1#4#5#8#3#98#24#12#1#9";
String[] a = str.split("#");
int n = a.length;
int sqrt = (int) Math.sqrt(8 * n + 1);
double sqrt2 = (double) sqrt;
double sqrt3 = Math.sqrt(8 * n + 1);
if (Math.abs(sqrt2 - sqrt3) > 0.000001) {
System.out.println("Invalid");
return;
}
int next = 1;
int count = 0;
int ind = 0;
int max = 0;
int sum = 0;
int val;
while (ind < n) {
if (a[ind].equals("")) {
System.out.println("Invalid");
return;
}
val = Integer.parseInt(a[ind]);
if (val > max) {
max = val;
}
ind++;
count++;
if (count == next) {
next++;
count = 0;
sum += max;
max = 0;
}
}
System.out.println(sum);
}
}
Just create one new array with size max + 1, where max is max size of two given arrays.
and starting from the end of both array add elements, save to new array the remainder when sum divided by 10, and save to temp variable carry.
import java.util.*;
public class AddArrays {
public static void main(String... args) {
int[] a = {9, 9, 9};
int[] b = {9, 9, 9, 9, 9};
int[] sum = sum(a, b);
System.out.println(Arrays.toString(sum));
}
private static int[] sum(int[] a, int[] b) {
int al = a.length;
int bl = b.length;
if (al < bl) {
return sum(b, a);
}
int[] sum = new int[al + 1];
int carry = 0;
int s;
for (int i = al - 1; i >= 0; i--) {
s = carry;
if (i - al + bl >= 0) {
s += b[i - al + bl];
}
s += a[i];
sum[i + 1] = s % 10;
carry = s / 10;
}
sum[0] = carry;
return sum;
}
}
Second question is to find the diameter of a tree and return the mid vertex of diameter.
- madi.sagimbekov November 17, 2015O(nlogn) time complexity, O(1) space complexity
import java.util.*;
public class WaveArray {
public static void main(String... args) {
int n = args.length;
if (n == 0) {
return;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(args[i]);
}
Arrays.sort(a);
int half = n / 2;
for (int i = half; i < n; i++) {
int t = a[i];
a[i] = a[(i - half) * 2];
a[(i - half) * 2] = t;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
O(nlogn) time complexity, O(1) space complexity
import java.util.*;
public class WaveArray {
public static void main(String... args) {
int n = args.length;
if (n == 0) {
return;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(args[i]);
}
Arrays.sort(a);
int half = n / 2;
for (int i = half; i < n; i++) {
int t = a[i];
a[i] = a[(i - half) * 2];
a[(i - half) * 2] = t;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
Your solution needs O(nlogn) time and O(n) extra space, can be solved with constant space complexity, just swap elements in place, see code below.
- madi.sagimbekov November 17, 2015yes, you are right, enough to check if stack is empty or not
- madi.sagimbekov November 17, 2015Just convert all ints to string, and use String comparator
import java.util.*;
public class MaxNumber {
public static void main(String... args) {
if (args.length == 0) {
return;
}
int n = args.length;
Integer[] ints = new Integer[n];
for (int i = 0; i < n; i++) {
ints[i] = Integer.parseInt(args[i]);
}
Arrays.sort(ints, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.toString().compareTo(o1.toString());
}
});
for (int i = 0; i < n; i++) {
System.out.print(ints[i]);
}
System.out.println();
}
}
How about )))((( ?
- madi.sagimbekov October 25, 2015use stack, if it is "open" bracket push it into stack, else pop element from stack and check if it is "open" bracket, if yes - continue, else return false
Here is the code:
public class ValidExpr {
public static void main(String[] args) {
String expr = "()";
System.out.println(isValid(expr));
}
public static boolean isValid(String input) {
Stack<Character> stack = new Stack<>();
for (Character c : input.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (!stack.isEmpty()) {
char k = stack.pop();
if (k != '(') {
return false;
}
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
public class ReverseString {
public static void main(String[] args) {
String input = " the quick brown fox jumps over the lazy dog";
char[] c = input.toCharArray();
int i = 0;
int j = c.length - 1;
while (i <= j) {
while (c[i] == ' ') {
i++;
}
while (c[j] == ' ') {
j--;
}
char k = c[i];
c[i] = c[j];
c[j] = k;
i++;
j--;
}
System.out.println(new String(c));
}
}
import java.util.*;
public class ArraySum {
public static void main(String[] args) {
int[] arr = {2, 5, 10, 7, 9, 3, 12, 8};
int K = 17;
List<Integer> sum = new ArrayList<>();
List<String> idx = new ArrayList<>();
int size;
for (int i = 0; i < arr.length; i++) {
size = sum.size();
if (arr[i] <= K) {
sum.add(arr[i]);
idx.add(i + "");
}
for (int j = 0; j < size; j++) {
if (sum.get(j) + arr[i] <= K) {
sum.add(sum.get(j) + arr[i]);
idx.add(idx.get(j) + ", " + i);
}
}
}
for (int i = 0; i < sum.size(); i++) {
if (sum.get(i) == K) {
System.out.println(idx.get(i));
}
}
}
}
public class IntegerSearch {
public static void main(String[] args) {
long[] a = {1354255942L, 2482224421L, 8689451784L, 2255478996L, 5418255689L, 8754962548L};
for (int i = 0; i < a.length; i++) {
if (contains(a[i], "22244")) {
System.out.println(a[i]);
}
}
}
private static boolean contains(long input, String search) {
int size = search.length();
long s = Long.parseLong(search);
long diff;
int shift = 0;
boolean match;
while (s <= input) {
diff = input - s;
match = true;
for (int i = shift; i < shift + size; i++) {
if (diff % Math.pow(10, i) != diff % Math.pow(10, i + 1)) {
match = false;
break;
}
}
if (match) {
return true;
}
s = s * 10;
shift++;
}
return false;
}
}
For the 2nd question,
Just sort each word separately, and find the duplicates (sort collection and find equal neighbor elements)
The rat fell in the tar -> eht art efll in eht art - > art art efll eht eht in
Actually LCM = (product of numbers)/GCD^(numbers count - 1)
*GCD of all numbers to the power of amount of numbers minus one;
Or just exactly one char should be count to odd, if x is odd
- madi.sagimbekov April 06, 2015If x is odd there should be not at least but at most one char count to odd
- madi.sagimbekov April 06, 2015Time complexity is O(N^2), without using any extra storage.
- madi.sagimbekov April 02, 2015public class Example {
public static void main(String[] args) {
int[] arr = {0, 5, 1, 2, 2, 1, 1, 3, 5, 2, 1};
int mfCount = 0;
int smfCount = 0;
int mf = 0;
int sfm = 0;
for (int i = 0; i < arr.length - 1; i++) {
int count = 1;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count > mfCount) {
smfCount = mfCount;
mfCount = count;
sfm = mf;
mf = arr[i];
} else if (count > smfCount) {
smfCount = count;
sfm = arr[i];
}
}
System.out.println(sfm);
}
}
max value of an array element is 255, so we can just sort both arrays using counting sort or bucket sort (time complexity is O(n)).
then just start comparing from smallest element, if they are equal compare next ones, if element in first array is greater, then compare with the next element of second array an so on,..
here is the code:
public class Test {
public static void main(String[] args) {
int[] a = {5, 8, 255, 45, 10, 9};
int[] b = {1, 4, 211, 8, 210, 5, 10, 9};
int[] resa = countingSort(a);
int[] resb = countingSort(b);
int i = 0;
int j = 0;
while (i != a.length && j != b.length) {
if (resa[i] == resb[j]) {
System.out.println("common element: " + resa[i]);
i++;
j++;
} else if (resa[i] > resb[j]) {
j++;
} else {
i++;
}
}
}
private static int[] countingSort(int[] a) {
int[] count = new int[256];
int[] output = new int[a.length];
for (int i = 0; i < a.length; i++) {
count[a[i]]++;
}
for (int i = 1; i < 256; i++) {
count[i] = count[i] + count[i - 1];
}
for (int i = 0; i < a.length; i++) {
count[a[i]]--;
output[count[a[i]]] = a[i];
}
return output;
}
}
"Check if it contains a sequence of at least 3 zeros in the middle (i.e "10010001") this will enable for fitting a 1 in the middle."
You cannot just put 1 in the middle to get next sparse number,
for example 10010010 is less than 10010101 but also sparse.
Repkatierlaursen123, Analyst at ABC TECH SUPPORT
Hello I am working in Maxprofit as a Data coder operator.I have been working here for 5 years.When ...
Just use right hand rule for a robot, always go forward, if it is not possible turn right and go forward, until robot finds the exit.
- madi.sagimbekov April 26, 2016