X
BAN USER 1of 1 vote
AnswersGiven N integer array, I want to fill the array with product of all numbers except the number in that cell.
 X in United States
What is the complexity ? Do not worry about 0's or negative numbers in the array.
[Interviewer was more interested in how the multiplication/division gets effected as number of bits required to represent the intermediate products increases.] Report Duplicate  Flag  PURGE
Google Applications Developer Algorithm  2of 4 votes
AnswersGiven a screen with all pixels having one of two colors. Now I will click on a random pixel.
 X in United States
Then that pixel & all the adjacent pixels with same color should change the color to the second color.
adjacent = vertically or horizontally above or blow.
Edit: Question seem to be not clear to some ppl. Giving an ex:
Given below & clicked on 2nd row, 2nd col
W B W W B W
B B W W B W
W B B B W B
W B W W B B
Covert to
W W W W B W
W W W W B W
W W W W W B
W W W W B B Report Duplicate  Flag  PURGE
Google Applications Developer Algorithm
/* It deals with single digit numbers only.
Easily extendible to numbers with Scanner or such Io classes.
*/
public int reverseDepthSum (String input)
{
// String input = "{{1,1},2,{1,1}}";
char[] strArray = input.toCharArray();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int depth = 0, maxDepth = 0;
for (int i = 0; i < strArray.length; i++) {
if (strArray[i] == '{') {
depth++;
if (depth > maxDepth)
maxDepth = depth;
} else if (strArray[i] == '}')
depth;
else {
if (Character.isDigit(strArray[i])) {
if (map.containsKey(depth))
map.put(depth, map.get(depth) + Character.getNumericValue(strArray[i]));
else
map.put(depth, Character.getNumericValue(strArray[i]));
} else {
// "," => no op
}
}
}
int result = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
result += (maxDepth  entry.getKey() + 1) * entry.getValue();
}
return result;
}

X
May 29, 2017 public static void reverseWords(String str){
StringBuilder string = new StringBuilder(str);
Matcher matcher = Pattern.compile("\\w+").matcher(string);
while(matcher.find()){
reverseStr(string, matcher.start(), matcher.end()1);
}
System.out.println(string);
}
private static void reverseStr(StringBuilder str, int i, int j){
while(i<j){
char tmp = str.charAt(i);
str.setCharAt(i, str.charAt(j));
str.setCharAt(j, tmp);
i++;
j;
}
}

X
July 25, 2015 /**
*
* @param array
* @param K  num of positions shifted
* @return  index of the element in original array
*/
public static int binarySearchShiftedArray(int array[], int K, int beg, int end, int elem){
int mid = beg + (endbeg)/2 ;
int mid1 = ( mid + K) % (array.length ); //shifted mid
if(elem < array[mid1]){
return binarySearchShiftedArray(array, K, beg, mid1, elem);
}
else if(elem > array[mid1]){
return binarySearchShiftedArray(array, K, mid+1, end, elem);
}
else return mid1;
}

X
July 25, 2015 f(n) = log3(n) + (n is power of 3 ? 1 : 0);
f(3) = f(2) = 1;
f(1) = f(0) = 0; //trivial
Not sure, why dynamic programming needed. Looks to me like, O(1) computation.
ex: f(27) = 1 + f(9); //divide into 9,9,9, compare 2 9's
f(9) = 1 + f(3); //divide into 3,3,3, compare 2 3's
f(3) = 1;
formla gives f(27) = log3(27) + 0
ex: f(12) = f(4) + 1 //4,4,4
f(4) = f(3) + 1; //2,2
f(3) = 1;
formula gives f(12) = log3(12) + 1 = 3;
(Please verify if f(n/3) needs to be considered in forumla instead of log3(n) before accepting)
Dynamic programming :
O(n), n=num of grids in the game
//+ve=>ladder, ve=>snake, 0=>neither
LadderSnakeValue[i] = +/K;
//initialize first roll consequences
MinRolls[100]=0;
MinRolls[99>94]=1;
for(int i=93; i>0; i){
int minRolls=INT_MAX;
//find min of all possible rolls
for(int roll=1;roll<=6;roll++){
int reachable;
if(LadderSnakeValue[i+roll] < 0) //Snake
continue;
else{
reachable = LadderSnakeValue[i+roll]+i; //add ladder value to current position
if(MinRolls[reachable] + 1< minRolls) minRolls = 1+MinRolls[reachable]; //1 for current roll + num of min rolls from climbed position
}
}
MinRolls[i]=minRolls;
}
return MinRolls[1];

X
July 19, 2015 My understanding of question :
Start time can be anything, but endTime  startTime = 1 hr.
Now we need to find the intersecting time period with most number of intervals.
One way could be:
Design each interval as a node, and if interval1 and interval2 intersect, then add edge between node1 to node2.
Now find the node with max degree(max num of edges from the node). This is the interval intersecting with most others.
Now simply find intersection of all intervals of this node with its adjacent ones  to get overlap.
To be exact, below is a better hashcode suggested by Effective java book.
@Override
public int hashCode() {
int result = 17;
result = 31 * result + a[0];
result = 31 * result + a[1];
result = 31 * result + a[2];
return result;
}
But above(approximate one) is good enough, as its close to java.lang.String's hashcode implementation if am not wrong.
These numbers are chosen as they are oddprimes and in depth detail can be found in the book.
 First read 1 number from each of K streams, and build a PriorityQueue
 After that keep removing top from PQ, and add next number from the same stream(from which top came)
 if this stream is over, just move on
 Now repeat this while PQ is not empty
public static void sortKStreams(File f[], int K)
throws IOException{
PriorityQueue<NumNode> PQ = new PriorityQueue<NumNode>(3);
Scanner scanners[] = new Scanner[f.length];
//insert 1 number each from one stream
for(int i=0; i<K; i++){
scanners[i] = new Scanner(f[i]);
if(scanners[i].hasNextInt()){
int inp = scanners[i].nextInt();
PQ.add(new NumNode(inp, i));
System.out.println("INITIAL BUILD Adding:" + inp + " from stream=" + i);
}
}
//While PQ is not empty
while(PQ.isEmpty() == false){
//read next min from PQ
NumNode nextMin = PQ.remove();
System.out.println("Final result " + nextMin.getNumber());
//read one element from the stream that provided min last time, and add to PQ
//Note: as streams get exhausted, PQ size decreases linearly
int nextReadVal = 1;
Scanner sc = scanners[nextMin.getStreamNumber()];
if(sc.hasNextInt()){
nextReadVal = sc.nextInt();
System.out.println("Adding to PQ: Value:" + nextReadVal + ", From stream=" + nextMin.getStreamNumber());
PQ.add(new NumNode(nextReadVal, nextMin.getStreamNumber()));
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Autogenerated catch block
e.printStackTrace();
}
}
for(int i=0; i<K; ++i){
scanners[i].close();
}
}

X
July 13, 2015 This can transformed to :
 Construct each interval as a node.
 Connect two nodes if those intervals overlap, to build an "undirected graph"
(Note: graph could be a forest also(disconnected components))
 Now problem is : how many of N nodes can be colored with K colors ?
/**
* Given root, serialize the tree by traversing in preorder
* @param root
* @throws IOException
*/
public static void serialize(Node root, PrintWriter pwtr) throws IOException{
if(root == null){
pwtr.print(Integer.MAX_VALUE + " "); //delimiter
return;
}
else{
pwtr.print(root.get() + " ");
serialize(root.left, pwtr);
serialize(root.right, pwtr);
}
}
/**
* Read back the preorder and reconstruct the tree
* @param fis
* @return
* @throws IOException
*/
public static Node deserialize(Scanner scanner) throws IOException{
int value = 0 ;
if(scanner.hasNextInt()) value = scanner.nextInt();
else return null;
if(value == Integer.MAX_VALUE) return null;
Node root = new Node(value);
root.left = deserialize(scanner);
root.right = deserialize(scanner);
return root;
}
/**
* Manual serialize/deseialize
*
* @throws IOException
*/
public static void demo() throws IOException{
Node root = BinaryTreeUtil.buildTree();
//serialize
PrintWriter pw = new PrintWriter("binarytree.blob");
serialize(root, pw);
pw.close();
//deserialize
File file = new File("binarytree.blob");
Scanner scanner = new Scanner(file);
root = deserialize(scanner);
scanner.close();
}

X
July 09, 2015 This solution works.
But, in checking, you dont need to compare all sums. Simply compare if highest segment is longer than sum of smaller ones. Remaining two conditions will hold.
Ex: if A1 > A2 > A3.
Then if A1 > A2 + A3, remaining two will be true automatically. (since A1 > A2 & A1 > A3).
So total complexity = O(nLogn) + O(n) ( Sorting + comparision )
public static int getMaxParanthesisDepth(String str){
int maxDepth=0;
int potentialMaxDepth=0;
int curDepth = 0;
for(int i=0; i<str.length(); ++i ){
//left brace
if(str.charAt(i) == '('){
curDepth++;
potentialMaxDepth++;
}
//right brace
else if(str.charAt(i) == ')')
{
curDepth;
//unmatched right brace
if(curDepth < 0){
System.out.println("unmatched brace");
maxDepth = 1;
break;
}
//one nest is processed
if(curDepth == 0){
if(potentialMaxDepth > maxDepth){
maxDepth = potentialMaxDepth;
potentialMaxDepth=0;
}
}
}
}
////unmatched left brace
if(curDepth != 0){
System.out.println("Unmatched braces");
return 1;
}
else return maxDepth;
}

X
June 04, 2015 Say length of string=n
rotate by=k
for all indexes i from 0 > (n1)
if (i<k) newIndex = n  1  i;
else newIndex = i k;
This will be very simple if saving first substring (klength) into a temp string.
Also simple, if we can copy to a new string.
If needs to happen in place w/o extra space, do the 3 string reverse operations..
one for String[0..k1], second String[k..n1] and third on the resulting string of 1,2 operations.
Some possibilities:
1. Threading issues. ("Synchronize" correctly in java to fix the issue)
2. Memory issues: (memory leaks of java objects or connections can be the reason)
3. In test suites lik JUnit, object model remains in memory and order of test cases run is not guaranteed. So make sure no singleton instances are leaking from one test case to another.
/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n1) ;
count++;
}
return count;
}
Now, we can simply terminate after 3rd iteration (if n is still != 0) & declare the result.
Maximum complexity = 3 operations.
/* Function to check if it has 3 bits */
boolean has3Bits(int n)
{
unsigned int count = 0;
while (n)
{
if(count == 3) return false; //more than 3 bits
n &= (n1) ;
count++;
}
if(count == 3) return true;
else return false; //less than 3 bits.
}

X
May 27, 2015 'ing is correct, except its highly inefficient, if finding one such sequence of words is enough.
Its like exploring all the paths in a tree, even after 1 path lead to the solution.
As soon as one of the recursive calls inside the for loop returns true, we are done! we can return true and set of words visited through that iteration(recursively).
Past 1 hour = Current time to cur_min60 mins.
We need 2 data structures.
1. For each minute maintain map of  {product_id, current_min_frequency}
2. Heap(priority queue) of all product_ids in the last hour, priority by current_hour_frequency
How to maintain:
As each new request/product_id is read in,
1. Add to current min  prod_id, freq in current min [if already present, increment current_min_freq]
2. Increment current_hour_frequency in priority queue, and reheapify
After each min,
1. remove the pair for (curre min  60 mins)
2. decrement current_hour_freq by cur_min_frequency of that oldest mint in Priority Queue, and reheapify. If cur_hour_freq reaches 0, delete that product_id's node from min_heap.
When queried, get the top 10 elements from heap.
A simple way may be:
1. In the first scan  Find all positions of given key. And number of elements less than key. Now you know
 (a) first position of the key in the result array (with key in the middle and lesser ones on left etc..)
 (b) last position of the key in the result array
2. Move all key elements to middle [from indexes (a) to (b)]
3. Now keep two pointers one always pointing to lesser ones and other to greater ones and swapping at every contradiction.
Each step is O(n).
// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return 1
int Ceil(node *root, int input)
{
// Base case
if( root == NULL )
return 1;
// We found equal key
if( root>key == input )
return root>key;
// If root's key is smaller, ceil must be in right subtree
if( root>key < input )
return Ceil(root>right, input);
// Else, either left subtree or root has the ceil value
int ceil = Ceil(root>left, input);
return (ceil >= input) ? ceil : root>key;
}
copied from geeksforgeeks, thought will help others..
For each character, that is either the first char or the last char of any string, compute these two details:
1. Length of longest sequence beginning with this char
2. Length of longest sequence ending with this char
If a string has same char as prefix and suffix only count the one which is longer.
Now for each character from above set,
Compute the length by summing (1) + (2) above.
Pick the character with max sum, as answer.
INPUT: ab; ba; aac
Algo:
a  begString: aac, length=2
a  endString: ba, length=1;
b  begString: ba, length =1;
b  endString; ab, length=1;
c  endString: aac, length=1;
for a, sum=2+1=3
for b, 1+1=2;
for c, 1+INF=INF
Output: a [max length=3]
Complexity: O(n). Simply read each character of each string from beginning & ending till it matches with adjacent character and find the above lengths.
Edit: To address the case where max length seq is in the middle of a string, for each char  also keep track of longest length "inside" a string globally(across all strings). This can be easily done by using a map or such data structure.
Solution by Sunny above seems to be more complete & elaborative.
Ex: String2 = "ABC"; String1="AXBYCZ". Answer = true;
Simple Algo:
First look for 1st char, then 2nd char in remaining string and so on..
boolean f(String str1, String str2)
{
int begIndex = 0;
for(int i=0; i<str2.length; ++i){
int pos = str1.indexOf(str2.charAt(i), begIndex);
if(pos == 1) return false;
begIndex = pos+1;
}
return true;
}
Need more details in problem def, for more sophisticated solution.
 X June 22, 2013If its a phone interview, simple recursion with visited mark on all visited cells should do..
Here is pseudo code:
================
int f(srcRow, srcCol, tgtRow, tgtCol, numStepsSoFar){
/* boundary check row/cols */
if outOfBoundary(sRow, sCol)  outOfBoundary(tRow, tCol)
return Integer.MAX_VALUE;
if(sRow==tgtRow && sCol==tgtCol) return numStepsSoFar;
visitedCells.add(sRow, sCol);
if(!visisted(srcRow+1, sCol+1) num1=f(sRow+1, sCol+1, numStepsSoFar+1);
if(!visisted(srcRow1, sCol+1) num1=f(sRow1, sCol+1, numStepsSoFar+1);
if(!visisted(srcRow+1, sCol1) num1=f(sRow+1, sCol1, numStepsSoFar+1);
if(!visisted(srcRow1, sCol1) num1=f(sRow1, sCol1, numStepsSoFar+1);
return min(num1, num2, num3, num4);
}

X
June 22, 2013 One straight forward way may be:
Maintain a LinkedList of nodes with <timeStamp, request> pairs.
As requests come, keep adding to this linked list (sorted by timestamps).
Maintain 3 pairs of pointers.
1st pair of pointers = lastSecondStart, lastSecondEnd
2nd pair=lastMinuteStart, lastMinuteEnd
3rd pair=lastHourStart, lastHourEnd
After every second do below:
lastSecondStart = lastSecondEnd>next;
lastSecondEnd=move right to node by a 'second' using currentTime & node.timeStamp;
lastMinuteStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastMinuteEnd=lastSecondEnd;
lastHourStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastHourEnd=lastMinuteEnd;
Essentially 3 traversals to right. Num of nodes depends on num of requests in that second.
Caveats: 1.If there are not too many requests this works.
2. Concurrent requests can be handled by making add() method synchronized. But too many of these can tamper performance.
Recursive solution:
public static int nDiceASum(int N, int A, int S){
if(N<=0) return 0;
if(N==1){
if(S >= 1 && S <= A)
return 1;
else
return 0;
}
int result = 0;
for(int i=1; i<=A; ++i){
result += nDiceASum(N1, A, Si);
}
return result;
}
Dynamic Program:
Create 2D matrix with numOfDice, sum on 2 dimensions.
So Matrix[s][n] = Sum( Matrix[si][n1]) for i = 1>A
Initialize first row, first column
Matrix[1][1] = 1;
for(int numDice=2; numDice<n; ++numDice)
Matrix[1][numDice] = 0;
for(int sum=2; sum<S; sum++){
if(sum <= A) Matrix[sum][1] = 1;
else Matrix[sum][1] = 0;
}
Now compute Matrix[Sum][NumDice] to get the result using below loop
for(int s=2; s<=Sum; s++)
for(int n=2; n<=NumDice; n++)
Matrix[s][n] = Sum(Matrix[si][n1]) with i from 1>A;

X
June 15, 2013 On similar lines  instead of trying to store them in bit array (or a binary number), we can simply iterate over [min, max] range and compute the max range that has all numbers present in given array.
This has fewer constraints. Only constraint : [min, max] range should be reasonable. Numbers can be negative/big/repeated etc.
 X February 12, 2018