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;
}

EPavlova
February 14, 2016 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;
}

EPavlova
February 12, 2016 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;
}

EPavlova
February 12, 2016 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;
}

EPavlova
February 09, 2016 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;
}

EPavlova
February 07, 2016 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(pm)+ways(pn)+....ways(ps) ,
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];
}

EPavlova
January 27, 2016 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+k1], dp[i1]), 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+k1], dp[i1]);
}
for (int i = 0; i <= nums.length  k; i++) {
System.out.print(dp[i]+ " ");
}
}

EPavlova
January 22, 2016 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;
}
}

EPavlova
January 20, 2016 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;
}

EPavlova
January 19, 2016 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];
}

EPavlova
January 19, 2016 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();
}
}

EPavlova
January 19, 2016 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 kth 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.. n1. 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++;
}
}
}

EPavlova
January 17, 2016 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);
}
}

EPavlova
January 16, 2016 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;
}
}
}

EPavlova
January 16, 2016 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;
}

EPavlova
January 15, 2016 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};
}

EPavlova
January 14, 2016 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 (el1 >= n)
q.add(new Paar(el1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return  1;
}
}

EPavlova
January 13, 2016 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;
}

EPavlova
January 13, 2016 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 (el1 >= n)
q.add(new Paar(el1,current.dist + 1));
if (el*2 >= n)
q.add(new Paar(el*2,current.dist + 1));
}
}
}
return  1;
}
}

EPavlova
January 13, 2016 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;
}

EPavlova
January 13, 2016
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
Open Chat in New Window
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