autoboli
BAN USER 0of 0 votes
AnswersGiven unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance xy is minimized.
 autoboli in United States
Example:
x: 01
y: 10
Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^322; Report Duplicate  Flag  PURGE
Google  10of 10 votes
AnswersYou are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:
 autoboli in United States
If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.
You are not allowed to use any conditional operator (including ternary operator).
Follow up: Solve the problem without utilizing arithmetic operators '+  * /'. Report Duplicate  Flag  PURGE
Google  0of 2 votes
AnswersYou are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.
 autoboli in United States
Write a function that subtract two integers 'a  b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.
Example:
s_a: 8 4 0 2
s_b: 4 2 0 1
result: '1024' Report Duplicate  Flag  PURGE
Google  3of 3 votes
AnswersGiven two binary numbers each represented as a string write a method that sums up the binary numbers and returns a result in the form of binary number represented as a string. You may assume that input fits in the memory and the input strings are, in general, of different length. Optimize your solution, do not use unnecessary 'if' branching.
example:sumBinary('0111101', '1101')
returns
 autoboli in United States
'1001010' Report Duplicate  Flag  PURGE
Amazon  4of 4 votes
AnswersYou are given an unsorted sequence of integers 'a'. Find the longest subsequence 'b' such that elements of this subsequence are strictly increasing numbers. Elements in the subsequence 'b' must appear in the same relative order as in the sequence 'a'. You may assume that 'a' can fit to the memory.
 autoboli in United States
Example:
input: a = [1 2 100 100 101 3 4 5 7]
output: b = [1 2 3 4 5] Report Duplicate  Flag  PURGE
Google  0of 0 votes
AnswersWarmup question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop.
 autoboli in United States Report Duplicate  Flag  PURGE
Google  13of 13 votes
AnswersA book contains with pages numbered from 1  N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.
 autoboli in United States
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occure five times in that string.
Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13}  the book has 414 pages
input d=4 k=0;
output {1, 3}  the book has 13 pages Report Duplicate  Flag  PURGE
Google  4of 4 votes
AnswersYou are given an array of integers 'a' that can fit in a memory. Write a method that retuns an array of the same lenght such that each element 'i' of this array is a sum of 'a' except the element a[i]. You are not allowed to use '' operator.
 autoboli in United States Report Duplicate  Flag  PURGE
Google  0of 0 votes
AnswersGiven a sorted doubly linked list, write an algorithm to convert this list into a binary search tree (BST). The BST will be used to represent a set. You may expect that client will use it to search for presence of a key in the set.
You may assume that you are given the following Node implementation that you can not exted or modify:public class Node { public Node prev, next; public int key; }
You algorithm is not allowed to create any other instance of the Node.
 autoboli in United States Report Duplicate  Flag  PURGE
Google  0of 0 votes
AnswersYou are given a string 's' and you are given a dictionary of english words. You goal is to write an algorithm that returns all words from the dictionary the can be formed by characters from that string 's'.
 autoboli in United States
Example:
s = "ogeg"
following words can be formed from 's': go egg ego . . .
Further it is given that string 's' always consists of four lower case characters. Lets say that the dictionary is contained in a file and can be fitted in the memory. It is up to you which data structure you use to represent the dictionary.
How would you design an efficient algorithm? Follow up: What if the dictionary file can not be fitted in the memory? Report Duplicate  Flag  PURGE
Google  3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
 autoboli in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1). Report Duplicate  Flag  PURGE
Google Algorithm
def compute_distance(w,q):
assert len(w) == len(q)
dist = 0
for k in range(len(w)):
if w[k] != q[k]:
dist = dist +1
return dist
def miss_splell(words, query):
result = []
for w in words:
if len(w) == len(query):
dist = compute_distance(w, query)
if dist == 1:
result.append(w)
if len(result) == 3:
break
return result

autoboli
March 06, 2019 Implemented as DFS via recurrent function. Each we passe a message 'msg' and a pointer 'k'. If msg[k] is the dollar sign, this char is replaced by a digit from the 'digit_set' and the recuurent function is called with the modified message and increased pointer k+1.
The complexity of the soution is O(2^k) in time and O(n^k) in memory where k is # of dollars and n is # of digits.
def replace_dollar(msg):
results = []
digit_set = set(list(msg.replace('$','')))
_replace_dollar(msg, 0,results, digit_set)
return results
def _replace_dollar(msg, k, results, digit_set):
if k == len(msg):
results.append(msg)
elif msg[k] != '$':
_replace_dollar(msg, k+1, results, digit_set)
else:
for digit in digit_set:
_replace_dollar(replace_at_k(msg, k, digit), k+1, results, digit_set)
def replace_at_k(msg, k, digit):
return msg[:k] + digit + msg[k+1:]

autoboli
March 05, 2019 The problem can be viewed as a graph problem. "Given the graph, determine if the graph is bipartite". In other words, is it possible to color the graph using two colors such that no nodes with the same color are connected? Proposed solution assumes that the graph is connected:
(i) using the pairs, construct a graph G
(ii) chose any node as a source node
(iii) starting from the source node, perform BFS, at each step, color the neighbors, toggle the color. If a neighbor is already colored with different color, the graph is not bipartite, return None
(iv) group nodes by color and return two sets
class Bipartite:
def __init__(self, G):
self.G = G
self.st = {}
def test(self, src):
if (self._is_bipartite(src)): return self._split()
else: return None
def _is_bipartite(self, src):
q = deque()
q.append(src) # enqueue source
color = 0 # initial color label
while not q.empty():
curr = q.pop()
if st.has_key(curr):
continue # skip node
self.st[curr] = color
for node in G.neighbours(curr):
if not st.has_key(node):
q.append(node)
else if self.st[node] == color:
return False
color = color^1 # toggle color label
return True
def _split(self):
A = set()
B = set()
for node in st.keys():
if st[key]: A.add(node)
else: B.add(node)
return A,B

autoboli
March 12, 2017 Hi JeffD,
(i) For example 2 1 1 1 1 2 the algorithm will work as follows:
2 1 1 1 1 2
2 (1+1) (1+1) 2
2*2*2*2 = 16
However we can do better:
2 1 1 1 1 2
(2+1) 1 1 ( 1+2)
(2+1) (1+1) (1+2)
3*2*3 = 18
Hence you are right Jeff, the algorithm is NOT correct.
(ii) In sake of braces, you never get something like 1(2) since the while loop inserts '*'.
So the question is, how to fix the algorithm and is it feasible to slove this task in O(N) linear time?
The problem can be solved recursively or iteratively, there are two problems to solve:
(i) How to reduce the problem to smaller one
(ii) In which order to pick operand couples
(iii) How to chose between multiplication and addition
First, notice that without loss of generlity we can pick any two adjacent numbers, perform desired operation and replace the two numbers with the result, which forms a new reduced problem. For instance, let have a sequence of bumbers "a,b,c,d,e", let pick a couple b,c, hence the new reduced problem is a, x, d, e where x=(b '*' or '+' c).
Second, notice that since interers are positive, the only case when an addition is benefical is only when at least one member of the couple equals '1', otherwise multiplication yields the same or greater result.
Third, notice tha we wont to first get rid of '1' using addition, than it remains only to perform multiplication. If the '1' has two neighbours, it is benefical to sum it with the lower neighbour. To illustrate this consider example below:
Correct: 3,1,2 > 3*(1+2)=9
Incorrect: 3,1,2>(3+1)*2 = 8
The algorithm sketch may look like this:
1) Reduce problem by geting rid of '1's by addition with lower neighbour
2) Multiply all remaining elements.
What remains is to print the expression to the standart output. The sample code may look like as follows:
public int findMax(int[] a) {
if (a.length>1) {
System.out.println(a[0]);
return a[0];
}
Node<Integer> la = new Node<Integer>();
Node<String> sa = new Node<String>();
for (int k=0; k<a.length; k++) {
la.add(a[k]);
sa.add(""+a[k]);
}
getRidOfOnes(la, sa);
/* Multiplication  no '1's left */
res = 1;
while(true) {
res *= la.val;
System.out.print(ls.val);
if(!la.isLast()) System.out.print("*");
else break;
la = la.next;
ls = ls.next;
}
System.out.println();
return res;
}
private void getRidOfOnes(Node<Integer> curra, Node<String> currs) {
while(curra != NULL) {
if(curra.val != 1) {
curra = curra.next;
currs = currs.next;
continue;
}
if (!curra.isFirst() && !curra.isLast()) { // has both neighbours
if(curra.prev.val>curra.next.val) addWithNext(curra, currs);
else addWithPrev(curra, currs);
}
else if (curra.isFirst() && !curra.isLast()) // has only right neighbour
addWithNext(curra, currs)
else if (curra.isLast() && !curra.isFirst()) // has only left neighbour
addWithPrev()
curra = curr.next;
}
}
private void addWithNext(Node<Integer> curra, Node<String> currs) {
curra.val += curr.next.val;
curra.next = curra.next.next;
currs.val += "("+curr.val+"+"+curr.next.val+")";
currs.next = curra.next.next;
}
private void addWithPrev(Node ...) {...}
Notice that the Node class is a custom doubly linked list datastructure.
 autoboli August 27, 2015Notice that this problem is very similar to the leverorder tree traversal. This problem can be implemented by a queue.
The only difference is that while in odd levels we traverse left to right in the even layers me traverse right to left. We will traverse the the tree while keeping track of even/odd layer. This will affect the order we put the nodes on the queue.
The goal is to count a number of connected components in a graph. The problem can be solved by BFS or DFS. Let consider a BFS solution. For simplicity, let assume that the land is represented as a 'boolean[][] map' array and let assume that we can modify it. The solution may look like this:
Initiate a counter to zero
(i) Start at the top left corner of the map, find a land element ('true') and put its coordinates in a queue.
(ii) Dequeue an element and unmark it in the map as 'false'
(iii) Add its adjacent land neighbours to the queue
(iv) If the queue is not empty go to (ii) otherwise increment counter and continue with (i);
Return counter
A sample code is shown below:
public class Components{
public static int count(boolean[][] map) {
int M = map.length;
int N = map[0].length;
int cnt = 0;
for (int i=0; i<M; i++)
for (int j=0; j<N; j++)
if(map[i][j]) {
visit(new Coord(i,j));
cnt++;
}
return cnt;
}
private static visit(boolean[][] map, Coord curr) {
Queue<Coord> q = new Queue<Coord>();
q.add(curr);
do {
curr = q.remove();
map[curr.i][curr.j] = 0;
for (c : adj(curr)) q.add(c);
}
while(!q.isempty());
return;
}
private static Iterable<Coord> adj(boolean[][] map, Coord curr) {
int M = map.length;
int N = map[0].length;
LinkedList<Coord> lst = new LinkedList<Coord>();
for (int i = curr.i1; i <= curr.i+1; i++)
for (int j = curr.j1; j <= curr.j+1; j++)
if (i>=0 && i<M && j>=0 && j<N && map[i][j])
lst.add(new Coord(i,j));
return lst;
}
}

autoboli
July 17, 2015 Given an integer array 'a' of the length 'N' the problem can be solved as follows:
For each 'i' in 0 to N1:
(i) generate a random number 'k' that is betweem 'i' and N1
(ii) swap elements a[i] and a[k]
public static void shuffle(int[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int k = i + random()*(Ni) // random in (i, N1)
int aux = a[i];
a[i] = a[k];
a[k] = aux;
}
}
This algorithm yields in a uniform shuffling, hence all possible permutations are equally possible.
 autoboli May 07, 2015Imagine that we would like to print all subsets. Then each integer from array 'int a[]' is member of the subset or not. This can be solved recursively by passing two additional arguments 'int lo' and 'String accum'. Given the index 'lo' we either add a[lo] to an accumulation string or not, increment 'lo' and perform recursive call. We stop and print the 'accum' string as soon as 'lo' is equal to the length of 'a'.
Now, given problem is essentially the same except one modification of the base case. We print the string if and only if its length is equal to 'k', the length of the subset.
A sample code is shown below:
public static void print(int K, int N) {
int[] a = new int[N];
for (int k=0; k<N; k++) a[k] = k+1;
print(a, K, 0, "");
}
private static void print(int[] a, int K, int lo, String s) {
if (s.length() == K) System.out.println("'" + s + "'");
if (s.length() >= K) return;
if (a.length == lo) return;
print(a, K, lo+1, s);
print(a, K, lo+1, s+a[lo]);
}

autoboli
April 28, 2015 I would propose modified quick sort as follows:
(i) Shuffle array
(ii) Select pivot
(iii) Partition the array and get rank of the pivot
(iv) If rank is 'k' done otherwise go to (ii) and repeat on sub array
public static int findRank(int x[], int rnk) {
int a = new int[x.length];
// Defensive copy, avoid side effect on x
for (int k=0; k < x.length; k++)
a[k] = x[k];
shuffle(a);
return findRank(a, rnk, 0, a.length1);
}
private static int findRank(int a[], rnk, int lo, int hi) {
int mid = partition(a, lo, hi);
if (rnk < mid) return findRank(a, rnk, lo, mid1);
if (rnk > mid) return findRank(a, rnk, mid+1, hi);
return a[mid];
}
private static int partition(int[] a, int lo, int hi) {
int p = a[lo];
int i = lo;
int j = hi+1;
while (true) {
while (a[++i] <= p) if (i == hi) break;
while (a[j] > p) if (j == lo) break;
if (i >= j) break;
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
The methods swap and shuffle are omitted for brevity. The algorithm is probabilistic guaranteed of O(N) with the worse case quadratic performance.
I know there exist an algorithm for median which has guaranteed worse case performance O(N), maybe this algorithm can be modified and used. It would be nice if someone post and explain this solution.
I would propose the solution via heap. Since sorting all stars and keep the first million is not feasible (O N log N) one can use a heap which yields O(N log K) where K is a short list size. Notice that we are not even asked to return these stars in sorted order.
Let's try to design an algorithm:
(i) Use a max heap (or max Priority queue if you will)
(ii) Fill the heap with first one million values
(iii) Comapre each new value with the top of heap
a) if bigger do nothing
b) if smaller replace top of the heap
Finally, the heap contains top 1 million closest stars. A sample code is shown below:
public Star[] findClosest(Star[] sky, int K) {
PriorityQueue<Star> pq = new PriorityQueue<Star>();
int N = sky.length;
if (N <= K) return sky;
for (int k = 0; k < k; k++)
pq.add(sky[k]);
for (int k = K; k < N; k++) {
Star mystar = sky[k];
if ( less(mystar, pq.peek()) ) {
pq.remove();
pq.add(mystar);
}
}
return(Star[]) pq.toArray();
}
private boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public class Star implements Comparable<Star> {
public int id;
public float dst;
public int compareTo(Star other) {
if (this.dst > other.dst) return 1;
if (this.dst < other.dst) return 1;
return 0;
}
}

autoboli
April 27, 2015 I would propose the following: If the binary tree is BST, at any given node as a root, it has the following properties:
(i) The left most node in the right subtree is greater or equal to the root.
(ii) The right most node in the left subtree is less than a root.
Given the root of a binary tree one can recursively check for these two properties. A sample code is shown below:
public static boolean isBST(Node root) {
return checkLeft(root, root.val) && checkRight(root, root.val);
}
private static boolean checkRight(Node x, int val) {
if (x == null) return true;
if (x < val) return false;
return checkRight(x.right, val);
}
private static boolean checkLeft(Node x, int val) {
if (x == null) return true;
if (x >= val) return false;
return checkLeft(x.right, val);
}

autoboli
April 27, 2015 This task can be solved by a recursive algorithm. Let assume that the input array 'a' contains unique integers 19 and we are give a target value 'x'. Notice that when we use one number from 'a', lets say number 'y = a[j]', we have to solve exactly the same problem with the new target value 'x_new = x  y'.
Hence, we can solve the task recursively while checking for two basecases: (i) target value is zero which means sums to original target value or (ii) target value is less than zero which means does not sum to the original target value. The last thing is to keep track of the values used so far and if the basecase (i) occurs push the string on the stack. Finally, we return th stack of strings to the client.
A sample code is shown below:
private static Stack<String> out;
public static Iterable<String> sumsTo(int[] a, int x) {
out = new Stack<String>();
sumsTo(a, x, "");
return out;
}
private static void sumsTo(int[] a, int x, String accum) {
if (x == 0) out.add(accum);
if (x <= 0) return;
for (int k = 0; k < a.length; k++)
sumsTo(a, xa[k], accum + a[k]);
}
One should clarify with the interviewer how the code should behave if zero is contained in 'a' which may yield an infinite numer of permutations. If the numbers in a[] are not unique one can handle duplicate permutations via symbol table (Hash or Tree Map).
 autoboli April 27, 2015Hi Marcello! Could you think about some super simple code that builds the tree given the binary image? Maybe that would be tough during the interview given the fact you only have about 40min and whiteboard only. The method signature would be something like this:
public static QuadNode buildQuadTree(boolean[][] img);

autoboli
April 25, 2015 When I read the problem to me it was obvious that I have some extra information about the numbers a,b and c, its max and min values, and interviewer wants me to take advantage of this extra information. Otherwise the problem would be just to find median of five integers [ a b c d e f] which is far less interesting task and maybe something the interviewer does not want.
 autoboli April 24, 2015Quadtree is a tree with branching factor of four. In this context it is probably used for dividing screen space recursively into four quadrants. The important question is 'how and what for we will use it for'? Now I am guessing, I think that we will deal with the case when there is a binary picture given and we want to zoom out (or scale down) the image by factors of two.
Lets design the node, each node:
(i) will contain four links to children
(ii) will contain color
(iii) will contain portion of white pixels in its subtree
(iv) if node is a leaf, its number of white pixels will be either 0 or 1;
Then the query 'numberOfPixelsGivenColor' will be straightforward. The datastructure may look like this:
public class QuadNode {
boolean col;
int nwhite;
QuadNode[] children;
public QuadNode(boolean col) {
this.col = col;
this.nwhite = 0;
this.children = new QuadNode[4];
}
public void addChild(QuadNode node, int k) {
this.children[k] = node;
this.nwhite += node.nwhite;
}
public int nwhite() { return this.nwhite; }
}
I am not sure this is exactly what interviewer was asking for.
 autoboli April 23, 2015The second problem:
Comparing to the first problem we are now also given 'min' and 'max'. Notice that min and max are actually two of the input integers a,b and c. One can use two important properties of the bitwise XOR operator:
a) If we XOR two identical numbers we get zero.
b) If we XOR any number with zero we get identity.
The solution is then to XOR all values. A sample code is shown below:
public static int median(int a, int b, int c, int min, int max) {
return a^b^c^min^max;
}
Example: Let say that min = c, max = b then it follows
a^b^c^min^max = a^(b^max)^(c^min) = a^0^0 = a
The first problem: Maybe it is too simple but I would propse the following solution:
public static int median(int a, int b, int c) {
if ( (a <= b && b <= c)  (c <= b && b <= a) ) return b;
if ( (b <= a && a <= c)  (c <= a && a <= b) ) return a;
return c;
}
The question is how the function should behave if the input does not contain unique integers.
 autoboli April 23, 2015The key question is if it is a single or multiple query. If multiple queries are expected than I would propose @zsalloum's solution with a hash map:
OFFLINE:
(i) Create a hash map, key  numeronym, val  List of strings, full words
(ii) For each word from dictionary, comute its numeronym and use it as a key
and add it to the hash map.
ONLINE:
(i) use the given numeronym as a key
(ii) return a list of words from hash map.
Offline O(N) time complesity, online O(1) amortized.
I would propose the following solution:
public static String makeNumeronym(String s) {
if (s == null  s.length() < 3) return s;
int N = s.length();
return s.charAt(0) + (N2) + s.charAt(N1) + "";
}
Btw, isn it that marcus > m4s? Is it something the interviewer expected?
 autoboli April 23, 2015Let's first solve simplified problem: Let assume that we are only interested if there exist a solution such that 'target' integer can be expressed by combination of given integers in array 'a', operators '+  * /' and braces '( )'. For instance, given integers 30 2 2 and a target value 16 then 16 = (2+30)/2, however there is no solution if the target value was 8.
Notice that if you remove two numbers from the array 'a' of the length N, apply an operator to these values and append the new value to the array 'a', you obtain a new array of the length N1. Now you have to solve exactly the same problem as in the beginning, however with reduced size to N1.
Hence the problem can be solved recursively, in each recursive call try all pairs from 'a' with all operators, while reducing the problem. Eventually the array contains a single integer, the base case. If the integer is equal to the target value we are done : the target value can be expressed as valid mathematical expression composed of given operators, braces and by given N integers. Otherwise we have to explore different branch of the tree.
There are two important remarks:
1) Let assume that noninteger division is not allowed
2) Division operator is not symmetric, hence in general x/y != y/x
This must be carefully handled in the code.
Finally, to solve the original problem we have to modify the recursive algorithm such that it will be able to keep track of the expression. This can be implemented via linked list of strings.
A sample code is shown below:
public static String decompose(int[] a, int target) {
LinkedList<Integer> x = new LinkedList<Integer>();
LinkedList<String> expr = new LinkedList<String>();
for (Integer y : a) {
x.addLast(y);
expr.addLast(y+"");
}
return decompose(x, expr, target);
}
private static String decompose(LinkedList<Integer> x, LinkedList<String> expr, int target) {
if (x.size() == 1) { // Base case
if (x.get(0) == target) return (expr.get(0)+" = "+target);
else return null;
}
for (int i = 0; i<x.size(); i++) {
for (int j = i+1; j<x.size(); j++) {
int a = x.get(j);
int b = x.get(i);
String ae = exp.get(j);
String be = exp.get(i);
for (int k=0; k<5; k++) {
// Copy of the integer list
LinkedList<Integer> xnew = new LinkedList<Integer>() ;
for (Integer y : x) { xnew.addLast(y); }
xnew.remove(j); xnew.remove(i);
// Copy of the expression string list
LinkedList<String> exprnew = new LinkedList<String>();
for (String s : expr) { exprnew.addLast(s); }
exprnew.remove(j); exprnew.remove(i);
// Handling division and zero
if ( k==3 && (b==0  a%b != 0)) continue;
if ( k==4 && (a==0  b%a != 0)) continue;
// Applying operator
int res = applyOperator(a, b, k);
xnew.addFirst(res);
// Merging expression strings
String e = stringOperator(ae, be, k);
exprnew.addFirst(e);
String ans = decompose(xnew, exprnew, target);
if (ans != null) return ans;
}
}
}
return null;
}
private static int applyOperator(int a, int b, int k) {
switch (k) {
case 0: return a+b;
case 1: return ab;
case 2: return a*b;
case 3: return a/b;
}
return b/a;
}
private static String stringOperator(String ae, String be, int k) {
if (ae.matches(".+[+*/].+")) ae = "(" + ae + ")";
if (be.matches(".+[+*/].+")) be = "(" + be + ")";
switch (k) {
case 0: return ae + "+" + be;
case 1: return ae + "" + be;
case 2: return ae + "*" + be;
case 3: return ae + "/" + be;
}
return be + "/" + ae;
}
Notice that division is handled by two cases: 'k=3' for 'a/b' and 'k=4' for b/k. Indeed it works, example:
input: 4, [5 7 13 169]
output: (7+(169/13))/5 = 4
I would prose the following solution:
(i) Extract kth digits from the end of the strings (if index exceeds dimension return '0').
(ii) Sum these digits and the carry
(iii) Compute resulting digit as modulo 2
(iv) Compute new carry as inreger division by 2
(v) Do until digits and carry are all zero.
A sample code is shown below:
public static String sumBinary(String a, String b) {
int carry = 0;
StringBuffer sb = new StringBuffer();
int k = 0;
while (true) {
int da = getChar(a, k)  '0'; // extract digit
int db = getChar(b, k)  '0';
int aux = da + db + carry;
if ( aux == 0 && !(k<a.length() && k<b.length()) )
break;
sb.append(aux%2);
carry = aux/2;
k++;
}
return sb.reverse().toString();
}
private static char getChar(String s, int k) {
int idx = s.length()1k;
return (idx >= 0)?s.charAt(idx):'0';
}

autoboli
April 22, 2015 I would propose the following solution:
(i) iterate through the elements of the array
(ii) keep track of the longest positive sequence
A sample code is shown below:
public static void findPosSeq(int a[]) {
int N = a.length;
int maxIdx = 1;
int maxLen = 1;
int len = 1;
int idx = 1;;
boolean flag = false;
for (int k = 0; k < N; k++) {
if (a[k] > 0) {
if (flag == true) {
len++;
}
else {
len = 1; // new sequence
idx = k;
flag = true;
}
}
else {
flag = false;
if (len > maxLen) {
maxLen = len;
maxIdx = idx;
}
}
}
if (maxLen > 0)
System.out.println("Length "+maxLen+", starting index "+maxIdx);
else
System.out.println("No positive sequence detected.")
}
The algoritnm is O(N) time and O(1) space complexity. After modification it should work also with stream.
 autoboli April 15, 2015Assuming that a string is ASCII I would propose the following solution:
(i) Create histogram whit 128 bins initiated to zero and create counter
(ii) Initiate left/right pointers to 1st and 2nd char in a string
(iii) Move right pointer if substring contains less or equal 'm' unique characters
Move left pointer if substring containc more than 'm' unique characters
(iv) Keep track of the longest substring
The solution should be O(N) time O(1) memory. A sample code is shown below:
public static String longestSubstring(String s, int m) {
int N = s.length();
int[] h = new int[128];
int cnt = 0;
int left = 0, right = 0;
int from = 0, to = 0;
while (left < N && right < N) {
if (cnt <= m) {
char c = s.charAt(right++);
if (h[c]++ == 0) cnt++;
}
else {
char c = s.charAt(left++);
if (h[c] == 0) cnt;
}
if (to  from < rightleft ) {
from = left;
to = right;
}
}
return s.substring(from, to);
}

autoboli
March 12, 2015 I would propose the following:
Let's say that array int[] a can fit into the memory
(i) use all numbers as a key and put it in a set
(ii) for each j in length a[]
compute x = sum  a[j]
if x is in the set
print pair a[j], x
remove x from the set
The the set construction is O(N), query to the set, if implemented via hash, is O(1) amortized and finally last loop is O(N)
A sample code is shown below:
public static void printPairs(int a[], int sum) {
HashSet<Integer> st = new HashSet<Integer>();
for (int x : a)
st.add(x);
for(int y : a) {
st.remove(y);
if (st.contains(sumy)) {
System.out.println(y + ", " + (sumy));
st.remove(sumy);
}
}
}
Notice that since the number is removed from the set, all possible pairs are printed only once. Notice also that this code works only for distinct integer values in the array.
 autoboli March 12, 2015The problem is essentially checking an element existence in a set. One can use a lookup table implemented via HashSet. Given the collection of names one first build a the lookup table which takes O(N) time. Then the query is just to check if a given value is present in the lookup table which is O(1) amortized time.
A sample code is show below:
public class NameFinder {
HashSet<String> st;
public NameFinder (String[] names) {
st = new HashSet<String>();
for (String s : names)
st.add(s.toLowerCase().trim());
}
public boolean query(String name) {
boolean bin = st.contains(name.toLowerCase().trim());
if (bin == true) System.out.println("YES");
else System.out.println("NO");
return bin;
}
}

autoboli
February 24, 2015 I guess that asking this type of question the interviewer wants us to work us with singly linked list. One can use two pointers 'head' and 'tail' pointing to a head and tail of the linked list. Then the process would be (i) link tail.next to head and (ii) update head, update tail, (iii) set tail.next to null to avoid circular list. A sample code is shown below:
public void reverseList(Node list) {
if (list == null  list.next == null) return;
int N=1;
Node head = list;
Node tail = list;
while(tail.next != null) { // get tail and list length
N++;
tail = tail.next;
}
for (int k = 0; k < N1; k++) {
tail.next = head;
head = head.next;
tail = tail.next;
tail.next = null;
}
list = head;
}
public class Node {
public Node next;
public int val;
}

autoboli
February 24, 2015 Open Chat in New Window
 autoboli March 06, 2019