EPavlova
BAN USERFind k times the max longestSequence when one 0 is replaced with 1.
Time complexity is O(kn).
int longestContinuousSequence(boolean[] bits, int k) {
int zeros = 0;
int ones = 0;
for (boolean bit : bits) {
if (!bit)
zeros++;
else
ones++;
}
if (ones == 0)
return Math.min(k, bits.length);
if (zeros == 0)
return bits.length;
int max = Integer.MIN_VALUE;
int maxIndex = - 1;
while (zeros > 0 && k > 0) {
int prefix = 0;
int suffix = 0;
for (int index = 0; index < bits.length; index++) {
if (!bits[index]) {
if (suffix == 0) {
suffix = 1;
}
else {
if (max < suffix + prefix) {
max = suffix + prefix;
maxIndex = index - suffix;
}
prefix = suffix - 1;
suffix = 1;
}
}
else {
if (suffix == 0 )
prefix++;
else
suffix++;
}
}
if (max < suffix + prefix) {
max = suffix + prefix;
maxIndex = bits.length - suffix;
}
bits[maxIndex] = true;
k--;
zeros -= 1;
}
return max;
}
refactored a little bit
boolean isValidShuffle(String apple) {
if(apple.length() <= 1)
return true;
int[] freq = new int[26];
int max = Integer.MIN_VALUE;
for (char ch : apple.toCharArray()) {
freq[ch -'a'] ++;
if(max < freq[ch -'a']) {
max = freq[ch -'a'];
}
}
return max > (apple.length()+ 1)/2? false: true;
}
An implementation to back up my statement above
boolean isValidShuffle(String apple) {
if(apple.length() <= 1)
return true;
int[] freq = new int[26];
int max = Integer.MIN_VALUE;
for (char ch : apple.toCharArray()) {
freq[ch -'a'] ++;
if(max < freq[ch -'a']) {
max = freq[ch -'a'];
}
}
return (max > (apple.length()*1.0/2.0 + 0.5))? false: true;
}
I think that it is a little tricky question - actually you can do insertion sort for both lists with O(n^2) complexity, but if you use skip lists , complexity will be O(nlog(n)), suppose that there was a place for conversation. Jasper could you elaborate whether interviewer asked you to optimize O(n^2) complexity or pushed you to proceed to the next question?
- EPavlova February 09, 2016boolean isArithemticProgression(int[] nums) {
if(nums.length <=1)
return true;
int sum = 0;
int n = nums.length;
int diff = nums[1] - nums[0];
int min = Integer.MAX_VALUE;
for (int num : nums) {
min = Math.min(num,min);
sum += num;
}
if(sum == (2*min + (n - 1) * diff)*n/2) {
return true;
}
return false;
}
Iterative version
public int kthSmallest(TreeNode root, int k) {
int h = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (!stack.isEmpty() || current != null) {
if (current!= null) {
stack.add(current);
current = current.left;
}
else {
h += 1;
current = stack.pop();
if(h == k)
return current.val;
current = current.right;
}
}
return 0;
}
Here is one approach with complexity O(m1*n1 +m2*n2) without using Rabin Karp fingerprints. Take the whole matrix and create one directional array as concatenating rows with some character which is not digit (to separate row ends). Then search with Acho Korasic for all occurence of each row of pattern in matrix vector and store where you find row match in some addtional two dimensional array of matrix size Then next phase is to iterate through all this additional matrix column by column and to check if there is a collumn with consecutive numbers (this means consecutive pattern rows because each number is a label of pattern's row)
- EPavlova February 05, 2016I think that this is 2D pattern matching problem . Brute force approach leads to O(n1*n2*m1*m2) where n1 - number rows in matrix, n2 - columns and m1 - rows in submatrix m2 - columns in submatrix;
If we use string pattern matching algorithms like Rabin Karp and KMP complexity could fall to O(n1*n2 +m1*m2). All depends on what an interviewer expects to be discussed and written on 45 minutes phone interview
{{
String twoComplements(String str) {
if(str == null || str.length() == 0)
return str;
StringBuilder strBuf = new StringBuilder();
for (int index = 0; index < str.length(); index++) {
if(str.charAt(index)== '0') {
strBuf.append('1');
}
else
strBuf.append('0');
}
int index = 0;
for (index = str.length() - 1; index >=0 ; index--) {
if(strBuf.charAt(index)== '0') {
strBuf.setCharAt(index,'1');
break;
}
else
strBuf.setCharAt(index,'0');
}
if(index < 0) {
strBuf.insert(0,'1');
}
return strBuf.toString();
}
}}
If there are another type of reading we could change solution like that:
ways(p) = ways(p-m)+ways(p-n)+....ways(p-s) ,
where ways(i) - number of ways we can read i pages
p - number of pages, m,n....s - ways we can read book - m pages per minute, n pages and so on.
Dynamic programming, similar to LCS problem. Problem space is defined via maxSub[i,] maximum length of palindrom subset in sub array [i,j];
int maxPlaindromSubseq(int[] nums) {
int maxSub[][] = new int[nums.length][nums.length];
for (int i = 0; i < nums.length; i++ ) {
maxSub[i][i] = 1;
}
for (int len = 2; len <= nums.length; len++) {
for (int i = 0; i <=nums.length - len; i++ ) {
int j = i + len - 1;
if (nums[i] == nums[j]) {
maxSub[i][j] = Math.max(maxSub[i + 1][j - 1] + 2, maxSub[i][j]);
} else {
maxSub[i][j] = Math.max(maxSub[i][j - 1] , maxSub[i][j]);
maxSub[i][j] = Math.max(maxSub[i+1][j], maxSub[i][j]);
}
}
}
return maxSub[0][nums.length - 1];
}
I am not sure that I properly understand the problem but we could sort tasks by task frequences - most frequent first and than execute the largest group of different taks till it is possible and wait between them - this is greedy approach. for example we have AAAAAABBBBCCCD - > we produce ABCD_ABC_ABC_AB_A_A -> 10
- EPavlova January 27, 2016There is a recurrent formula - dp[i] = Math.max(nums[i+k-1], dp[i-1]), where dp contains all our problem states (dp[i] is the max element in subarray with length k that start at index i).
{
void findMaxKSubArray(int[] nums, int k) {
if (nums.length < k) {
throw new IllegalArgumentException();
}
int dp[] = new int[nums.length - k + 1];
int max = Integer.MIN_VALUE;
for (int i = 0; i < k; i++) {
max = Math.max(max, nums[i]);
}
dp[0] = max;
for (int i = 1; i <= nums.length - k; i++) {
dp[i] = Math.max(nums[i+k-1], dp[i-1]);
}
for (int i = 0; i <= nums.length - k; i++) {
System.out.print(dp[i]+ " ");
}
}
Lowest common ancestor direct application
Here is my implementation.
public class Employee {
private String name;
private List<Employee> reportee;
private Employee manager;
Employee(String name) {
this.name = name;
reportee = new ArrayList<>();
}
public void setManager(Employee m) {
manager = m;
}
public void addReprotee(Employee e) {
reportee.add(e);
e.manager = this;
}
//O(log(n)) time complexity, O(1) memory
static Employee closestCommonManager2(Employee a, Employee b) {
Employee e1 = a;
Employee e2 = b;
int h1 = 0;
int h2 = 0;
while (e1 != null || e2 != null) {
if (e1 != null) {
e1 = e1.manager ;
h1++;
}
if (e2 != null) {
e2 = e2.manager ;
h2++;
}
}
int diff = Math.abs(h1 - h2);
if(h1 > h2) {
e1 = a;
e2 = b;
} else {
e1 = b;
e2 = a;
}
while (diff > 0) {
e1 = e1.manager;
diff--;
}
while (e1 != e2) {
e1 = e1.manager ;
e2 = e2.manager ;
}
return e1;
}
//O(log(n)) time complexity, O(log(n)) memory
static Employee closestCommonManager(Employee a, Employee b) {
Stack<Employee> ls1 = new Stack<Employee>();
Stack<Employee> ls2 = new Stack<Employee>();
while (a != null || b != null) {
if (a != null) {
ls1.push(a);
a = a.manager ;
}
if (b != null) {
ls2.push(b);
b = b.manager;
}
}
while(!ls1.isEmpty() && !ls2.isEmpty()) {
if (ls1.peek() != ls2.peek()) {
break;
}
a = ls1.pop();
ls2.pop();
}
return a;
}
public String toString() {
return name;
}
}
int convertString(String num) {
int res = 0;
boolean isNeg = false;
if (num.charAt(0) == '-')
isNeg = true;
else
res= res * 10 +(num.charAt(0) - '0');
for (int i = 1; i < num.length(); i++) {
res= res * 10 +(num.charAt(i) - '0');
}
return isNeg ? - res : res;
}
Thank you for the answers William.
Here is my solution - dynamically programming - partition problem
boolean canSplitEqually(int[] nums) {
int sum = 0;
for ( int item : nums) {
sum += item;
}
if (sum%2 != 0) {
return false;
}
boolean can[] = new boolean[sum+1];
can[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int s = sum; s + 1 > 0; s--) {
if (can[s]) {
if(s+nums[i] <= sum)
can[s+nums[i]] = true;
}
}
}
return can[sum/2];
}
Lexicografically generated permutations O(n*n!)
boolean nextPerm(int [] nums)
{ int i = nums.length - 2;
while(i >= 0) {
if(nums[i] < nums[i + 1])
break;
i--;
}
if (i == -1) {
return false;
}
int j = nums.length - 1;
while(j > i) {
if(nums[j]>nums[i])
break;
j--;
}
if (j != i) {
swap(i,j,nums);
}
int k = i + 1;
int l = nums.length - 1;
while(k < l) {
swap(k,l,nums);
k++;
l--;
}
return true;
}
void swap(int i, int j, int[] arr) {
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
void generatePermutation(int[] nums) {
while (nextPerm(nums)) {
for (int i : nums)
System.out.print(i);
System.out.println();
}
}
Could you provide some clarification because I am not sure that I understand the problem well. If complexity should be 2^n, than we are talking about splitting the list in 2 subsets which have equal sum. I mean we have 1,2,5,4 and we split on {1,5} and {2,4} .Otherwise complexity is linear.
One offtopic question - is it true that you know the status of your interveiw at the end of the day (on site) I mean you are in or out, or this is a myth.
ok in theory if you know a1+a2+..ak, a1^ a1 + a2^a2 + a3^a3 +a4^a4+...ak^ak,.....
a1^k+....ak^k, you will get a1,a2....ak when you solve this equation in some way.
a1+....ak is n*(n+1)/2 - sum_of_array, a1^ a1 + a2^a2 + a3^a3 +a4^a4+...ak^ak is n*(n+1)*(2n+1)/6 - sum of cubes of array elements... sum of powers - there is a formule which convert to polinom of n - sum of k-th degree of array items
I personally prefer to avoid such calculation and to sort array with O(n) complexity.
What is missing are the constraints that array contains only unique numbers in range 0.. n-1. This make the problem very ease. Here is implementation with O(n) time complexity
void swap (int i, int j, int[] arr) {
char ch = arr[i];
arr[i] = arr[j];
arr[j] = ch;
}
void swap (int i, int j, char[] arr) {
char ch = arr[i];
arr[i] = arr[j];
arr[j] = ch;
}
void permutate(int[] pos, char[] chars) {
int index = 0;
while (index < chars.length) {
if(index != pos[index]) {
swap(index,pos[index],chars);
swap(index,pos[index],pos);
}
else {
index++;
}
}
}
actually you should take into account fact that intergers are in range [0 .. n - 1] and n (array size). So we know that each number has a frequency between 0 and n. Suggest that we modify array and multiply each item by (n+1). For example we have array [1,1,1,0,3] n = 5. We multiply by 6 and the result is [6,6,6,0,18]. Then we iterate through we take each number val and calculate orig value i = value/6 and increment the i index of array with 1
In our case i = 6/6 = 1 , we increment a[1] ,becomes 7 then we continue with second number 6 and a[1] becomes 8 and by thrid 6 a[1] becomes 9, by 0 a[0] becomes 7,and by 18 a[3] becomes 1. Then we move through array and devide by mod each element by n+1, reminder is frequency. Here is some implementation
void findFrequency (int[] array) {
int n = array.length;
int m = (n+1);
for (int i = 0; i < n ; i++) {
array[i] *= m;
}
for (int i = 0; i < n ; i++) {
array[array[i]/m] += 1;
}
for (int i = 0; i < n ; i++) {
System.out.println( "number "+i+" : "+ array[i] % m);
}
}
Here is my solution
class ListNode<T extends Comparable<T>> {
private T val;
private ListNode<T> next;
ListNode (T v) {
val = v;
}
}
ListNode<Integer> merge (ListNode<Integer> n1, ListNode<Integer> n2) {
if (n1 == null)
return n2;
if (n2 == null)
return n1;
if (n1.val.compareTo(n2.val)<0) {
n1.next = merge (n1.next, n2);
return n1;
}
else {
n2.next = merge (n1, n2.next);
return n2;
}
}
}
Find height (n1 ) and height(n2). Get their difference and traverse the deepest node with difference steps upward .In this was both nodes with equal height.
Then traverse both nodes n1 and n2 further till they reach to the first common node - this will be their parent, otherwise we return null because nodes are from different trees.
Complexity (log(n)), memory O(1)
class Node {
private Node parent;
private Node left;
private Node right;
Node (Node l, Node r, Node p) {
left = l;
right = r;
parent = p;
}
}
int getHeight(Node n) {
int h = 0;
while (n != null) {
n = n.parent;
h++;
}
return h;
}
Node getLowestParent(Node n1, Node n2) {
Node tmp = n1;
int s1 = getHeight(tmp);
tmp = n2;
int s2 = getHeight(tmp);
int min = Math.abs(s1 - s2);
while (min > 0) {
n1 = n1.parent;
min -= 1;
}
Node curr1 = n1;
Node curr2 = n2;
while (curr1 != null || curr2 != null) {
if(curr1 == curr2) {
return curr1;
}
curr1 = curr1.parent;
curr2 = curr2.parent;
}
return null;
}
Modifed merge sort. We split array on tho subarrays and calculate local quaz for both subarray (divide phase). Then in merge phase (conquer pahse) with O(n) complexity update quaz of the whole array on the basis of already calculated values in divide phase.Original array is converted to one that is sorted but original indexes are stored.
int[] mergeQuaz(int[] input,int l,int r, int[] qaz) {
if( l < r ) {
int mid = l + (r - l)/ 2;
int a[] = mergeQuaz(input,l,mid ,qaz);
int b[] = mergeQuaz(input,mid+1 ,r ,qa);
int indexA = 0;
int indexB = 0;
int output[] = new int[a.length + b.length];
int outIndex = 0;
while (indexA < a.length) {
if(indexB == b.length) {
qaz[a[indexA]] += b.length - indexB;
output[outIndex] = a[indexA];
indexA++;
} else {
if (input[a[indexA]]< input[b[indexB]]) {
output[outIndex] = a[indexA];
qaz[a[indexA]] += b.length - indexB;
indexB = 0;
indexA++;
} else {
output[outIndex] = b[indexB];
indexB++;
}
}
outIndex++;
}
while(indexB<b.length) {
output[outIndex] = b[indexB];
outIndex++;
indexB++;
}
return output;
}
return new int[] {l};
}
I use BFS to find the shorter path between m and n.
public class ConvertNumber {
private static class Paar {
int val;
int dist;
Paar(int v, int d) {
val = v;
dist = d;
}
}
int getMinOperation(int m, int n) {
if (m == n)
return 0;
if ((m < 0) && (n > 0))
return -1;
Queue<Paar> q = new LinkedList<>();
q.add(new Paar(m,0));
while (!q.isEmpty()) {
Paar current = q.poll();
Integer el = current.val;
if (el == n) {
return current.dist;
}
else {
if ((n >= 0) && (m >=0)) {
if (el - 1 >= 0)
q.add(new Paar(el - 1,current.dist + 1));
q.add(new Paar(el*2,current.dist + 1));
} else {
if (el-1 >= n)
q.add(new Paar(el-1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return - 1;
}
}
We could use bisection method to calculate sqrt(5) only one time - log (n) complexity , or we can declare sqrt(5) as precalculated constant - 2,23606, so we shoudn't calculate sqrt(5) . The same regards golden ration - we shall store constants only. Here is small modification :
long findFibCount(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
double fi = 1. 618033;
doublde sqrtFive = 2.2360679
int index = (int) (Math.log(n * sqrtFive +0.5) / Math.log (fi));
int res = (int)((Math.pow(fi,index) /sqrtFive ) +0.5);
if (res != n) {
index +=1;
}
return index;
}
What were the constraint for numbers m and n - positive, negative? what should be system logic if iti is impossible to convert one number to the other ?
Here is my solution . I use BFS to find the shorter path between m and n.
public class ConvertNumber {
private static class Paar {
int val;
int dist;
Paar(int v, int d) {
val = v;
dist = d;
}
}
int getMinOperation(int m, int n) {
if (m == n)
return 0;
if ((m < 0) && (n > 0))
return -1;
Queue<Paar> q = new LinkedList<>();
q.add(new Paar(m,0));
while (!q.isEmpty()) {
Paar current = q.poll();
Integer el = current.val;
if (el == n) {
return current.dist;
}
else {
if ((n >= 0) && (m >=0)) {
if (el - 1 >= 0)
q.add(new Paar(el - 1,current.dist + 1));
q.add(new Paar(el*2,current.dist + 1));
} else {
if (el-1 >= n)
q.add(new Paar(el-1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return - 1;
}
}
We could use Binet's formula for finding the n- th fibonachi number. Actually Fibonachi numbers are very famous numbers because of their golden rule ratio. O(1) time and memory complexity
long findFibCount(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
double sqrtFive = Math.sqrt(5);
double fi = (1.0 + sqrtFive )/2.0;
int index = (int) (Math.log(n *sqrtFive +0.5) / Math.log (fi));
int res = (int)((Math.pow(fi,index) / sqrtFive ) +0.5);
if (res != n) {
index +=1;
}
return index;
}
Repgeraldgloria02, Android test engineer at Achieve Internet
I am a personal trainer. I design programs and provide nutritional advice and coaching. I wanted to share my knowledge ...
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
RepHenryMelvin, Korean Air Change Flight at AMD
Hello, everybody! My name is Henry,I am a picture-drawer.Art drawing & painting classes for adults, kids, teens.We have ...
I think that the problem is not to restore initial string, but to generate from some sequence S ( of dictionary words) string X (for example if X is "Ajavdoeceehr" and there are dictionary words Java, code, here , string javacodehere could generate X.
- EPavlova February 20, 2016