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 |x-y| 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^32-2;| 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
AnswersWarm-up 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 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 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
Check if a word is paliendrome, if yes return. Starting from i=1 append i-th character to the left of the string. Check if a new string is a paliendrome.
public String paliendrome(String s) {
if (isPaliendrome(s)) return s;
String out = s;
for (int k=1; k<s.length(); k++) {
Char c = s.charAt(k);
s = c+s;
if (isPaliendrome(out) break;
}
return out;
}
public boolean isPaliendrome(String s) {
int i = 0, j = s.length()-1;
while (i<j)
if (s.charAt(i--) != s.charAt(j--))
return false;
return true;
}
Given a sum s that can be combined by 5s and 3s there exist non-negative integers x,y such that s = 5*x + 3*y. From this if follows that (s-5*x)%3 = 0. You can check all possible x and examine the modulo.
A sample code is shown below:
public boolean isSumOfCoins(int s) {
int final A = 5;
int final B = 3;
if (s%A == 0 || s%B == 0)
return true;
for (int x = 0; x<s/A; x++)
if ((s-A*x)%B == 0)
return true;
return false;
}
First, sort the array in ascending order. Second, for each element k in the array do the following:
1) Set index 'i' to 0, 'j' to N-1
2) Compute the sum of three, if the sum equals zero return true, otherwise:
a) If the sum is greater than zero you want to decrease the sum, this can be achieved only by decrementing 'j'
b) If the sum is less than zero increment 'i'
Sorting is O(N log N), the scanning is O(N^2), hence the complexity is O(N^2).
A sample code is shown below:
public boolean sumsToZero(int[] a) {
int N = a.length;
Arrays.sort(a);
for (int k=0; k<N; k++) {
int i = 0; j = N-1;
while (i < j) {
int sum = a[k]+a[i]+a[j];
if (sum > 0 || j == k) j--;
else if (sum < 0 || i == k) i++;
else return true;
}
}
return false;
}
Frist, sort events by its start time. Second, start with the first event, put it to the stack. Check if the 'new' event has overlap:
a) If NOT, add it to the stack.
b) If YES, it can intersect only with the last event (events were sorted). If the stop time of this new event is less the stop time of that on the stack, replace them.
Retun the size of the stack;
A sample code is below:
public int maxEvents(Event[] a) {
Arrays.sort(a); // assume Event is Comparable
int N = a.length();
Stack<Event> stk = new Stack<Event>();
stk.push(a[0]); // push the first event on the stack
for (int k=1; k<M, k++) {
Event curr = a[k];
Event last = stk.peek();
if (last.stop >= curr.start) // no overlap
stk.push(e);
else // overlap
if (curr.stop < last.stop) {
stk.pop(); // replace event
stk.push(curr);
}
}
return stk.size();
}
public class Event implemnts Comparable<Event>{
public int start;
public int stop;
...
}
Yet another solution:
Perform a recursive DFS - the element from an array can either be or not be in the set, hence the solution is O(2^N) time complexity. Pick one number with index 'i' and check the sum with number of index 'j>i', remember the sum. Pick a number with index 'k>j' and check the sum.... and so on and so forth, do this recursively for every combination.
The key point is to keep a track of a sequence of numbers in each recursive call. To achieve this one can use a single Stack. The number of elements on the stack corresponds on a depth of recursion. Once the elements on the stack sums to zero the stack is printed out. However, we still continue with the recursion.
A sample code is shown below:
private static Stack<Integer> stk;
public static void printSets(int[] a) {
stk = new Stack<Integer>();
printSets(a, 0, 0);
}
private static void printSets(int[] a, int hi, int sum) {
// Check the sum
if (sum == 0){
for (int y : stk) // print the set
System.out.print(y+”, ”);
System.out.println();
}
// Recursion - cehck for every higher index
for (int k=hi; k<a.length-1; k++) {
int x = a[k];
stk.push(x); // add to the stack
printSets(a, k+1, sum+x);
stk.pop(); // remove from the stack
}
}
For couples I propose the following:
1) Sort the keys, if the keys are comparables, use some sort O(N log N), if the keys are integers you may consider radix sort O(N)
2) Use two pointers 'left' and 'right' and set lef toi the first elem of the array, the latter on to the end of array.
3) Check if the sum is zero, YES -> add to the set, increase 'left', decrease 'right', NO -> cehck if sum is greather than zero. If yes do 'right--' otherwise 'left++'
The procedure on sorted array is O(N) hence, depending on sort implemetation, the solution is either O(N) or O(N log N)
A sample code for integers is below:
public static List<Integer[]> findCouples(int[] a) {
My.sort(a); // radix sort or compare-based sort (merge sort)
List<Integer[]> out = LinkedList<Integer[]>();
int i = 0; int j = a.length-1;
while(i<j) {
int x = a[i];
int y = b[j];
if (x+y == 0){
out.add(new int[] {x, y});
i++;
j--;
}
else if (x+y > 0) j--;
else i++;
}
return out;
}
Now, the question is how to extend it to something else then couples. For sum of 3 the scanning on already sorted array will be O(N^2).
- autoboli January 09, 2015Use a queue to perform BFS. Enqueue 'null' at the end of each depth. Print the node values as they come from the queue. When you see 'null' then (i) print carriage return character (ii) enqueue null again. Do until queue size is 1 and contains only 'null'.
A sample code is below:
public static class printTree (Node root) {
Queue<Node> q = LinkedList<Node>(); // an empty queue
q.add(root);
q.add(null); // use null as 'end of certain depth' marker
do {
Node x = q.remove();
if (x != null)
System.out.print(x.toString());
if (x.left != null) q.add(x.left);
if (x.right != null) q.add(x.right);
else {
System.out.print("\r");
q.add(null);
}
}
while(q.size()>1 || q.peek() != null);
}
Nice idea as well. The only thing I don't like is to create every permutation of the string as mentioned above. So far both the trie with sorted key and the hash table with sorted key seems like valid solution to this problem.
I still have an impression that there must be something better.
Well, it is more complicated I think. How about this:
OFFLINE:
1) Take only <=4 char words from dictionary
2) Sort each word, keep unsorted word as well
3) Put it to the trie
If a char node in the trie is the final char it will contain a reference to a list of unsorted dictionary words e.g.
a-b-c --> {abc, cab, bac}
a-a-f-l --> {alfa fala}
ONLINE:
1) Sort 's'
2) Search in trie and return corresponding list of words.
It should be O(1) time. Well.... no it is not gonna work :( The problem is that you should search for all sorted substrings of 's' Hence, it does not sound like an elegant idea......
It is not very clear what sould the algorithm do, i guess the goal is to convert an integer into a different base. First, it seems that reminder should be
remainder =(n%base) ;
Second, be aware of base greather than 9. Then the output string has no sense since you won't distinguish between '10' and '1 and 0'.
- autoboli January 07, 2015Imagine that each string is a node in a graph G. Then each pair represents an edge E between the nodes. (i) Buld this graph G and (ii) then explore it by a DFS or BFS from source node. A DFS example is below:
// G - undirected graph, v - vertex (location id)
int[] pathTo;
boolean[] isVisited[];
public Iterable findPath(Graph G, int source, int destination) {
int N = G.V(); // # of vertices (locations)
for (int k=0; k<N; k++) { // init arrays
pathTo[k] = -1;
isVisited[k] = false;
}
// DFS path search
dfs(G, source);
// Path does not exist
if (pathTo[destionation] == -1) return null;
// Backtrack while pushing to the stack
Iterable out<Integer> = Stack<Integer>();
int aux = pathTo[destination];
while(aux != -1) {
out.push(aux);
aux = pathTo[aux];
}
return out;
}
public void dfs (Graph G, int v) {
if (isVisited[v])
return;
isVisited[v] = true;
// recursively visi all adjacent nodes
for (int w : G.adjacent(v))
if (!isVisited[w]) {
dfs(G, w);
pathTo[w] = v;
}
}
One can use a symbol table (map) where KEY = 'Url', VAL = List of 'content'. Given a new [Url, content] pair do:
Check if the KEY is present in a table:
a) Not present - create an empty list VAL and add content to it, add KEY, VALUE pair into the symbol table.
b) Is present - chack VAL list if it contains the 'content', if yes do nothing, if no add the 'content' to the VAL list;
Depending on how critical is the application you can use different implementation of the symbol table e.g.: a hash table O(1) amortized under assumption of good hash function or a red black BST O(log N) guaranteed.
You can use anything unless you do not copy the tree or additional complexity is not constant. I am thinking of recursive algorithm that transfer each BST subtree into a linked list and then merges. Here is the sketch:
public Node convertBST(node root) {
root = bst2linkedList(root);
return connectLinkedList(root);
}
// Use only 'left' to form a singly linked list.
private Node bst2linkedList (Node curr) {
// Leaf node
if (cur.left == null && cure.right == null)
return curr;
// Left subtree
Node aux;
if (curr.left != null) {
aux = bst2linkedList(curr.left);
curr.left = aux;
}
// Right subtree
if (curr.right != null) {
aux = bst2linkedList(curr.right);
Node last = curr.right;
// This can be further optimized such that
// 'right' points directly to the last node:
while (last.left != null)
last = last.left;
curr.right = last;
last.left = curr;
curr = curr.right;
}
return curr;
}
// Connect 'right' to form a doubly linked list
private Node connectLinkedList(Node root) {
Node curr = root;
while (curr.left != null) {
Node next = cur.left;
next.right = curr;
}
return root;
}
(i) run DFS in order to find connected components
(ii) count number of DFS calls (not including recursive calls)
(iii) return this number
public class Board {
private boolean[][] board;
private int M,N, cnt;
private int[][] labels;
public int clusters(boolean[][] board) {
this.M = board.length;
this.N = board[0].length;
this.cnt = 0;
this.labels = new int[M][N];
for (int k=0; k<M*N; k++) // init labels to 0's
labels[k/M][k%n] = 0;
for (int k=0; k<M*N; k++) { // search for all cluster by DFS
int i=k/M, j=k%N;
if (boadr[i][j] && labels[i][j]==0) {
cnt++;
dfs(i,j);
}
}
return cnt;
}
public void dfs(int i, int j) {
labels[i][j] = cnt;
for (int p=i-1; p<=i+1; p++) // check 8 neighbours
for (int q=j-1; q<=j+1; q++)
if (p>=0 && q>=00 && p<M && q<N && labels[p][q]==0)
dfs(p, q);
}
}
I propose the following: (i) Traverse the tree by a depth-firsr-search (DFS) and print the nodes as they come from a queue. (ii) The remaining thing is to detect the the new line (a change in the depth). This can be solved by queueing a null reference as shown in the code below:
public void printTree(Node root) {
Queue<Node> q = LinkedList<Node>();
q.add(root);
q.add(null); // null serves as a depth marker
while (!q.isEmpty()) {
Node curr = q.remove();
if (curr != null) {
System.out.print(curr.val+” ”);
if (curr.left != null) q.add(curr.left);
if (curr.right != null) q.add(curr.right);
}
else {
System.out.println(); // print new line
if (q.isEmpty()) break;
q.add(null);
}
}
}
public class Node {
public Node left;
public Node right;
public String val;
}
What I propose is to find connected components of "0s". If some connected component does not touch a border of a game board the game is over:
1) Go through "0"s on the board and recursively visit all neighbour "0s" by depth-first-search. When visiting a "0" mark it as visited in auxiliary array.
2) Keep track of whether all visited "0"s in one connected component are inside the board (not touching the border).
This solution shoult be O(MN) in time and space.
public class GO {
private boolean[][] marked;
private boolean[][] board;
private int M,N;
// Find conected component on unmarked “0” and
// check if the component touches a border of the board.
public isGamveOver(boolean[][] board) {
this.M = board.length;
this.N = board[0].length;
this.board = board;
marked = new boolean[M][N];
for (int k=0; k<M*N; k++) // init as false
marked[k/M][k%N] = false;
for (int k=0; k<M*N; k++) {
int i = k/M, j=k%N;
if (isValid(i, j) && !marked[i][j]) {
boolean isOver = dfs(i, j);
if (isOver)
return true;
}
}
return false;
}
// DFS - recursively mark connected component (CC)
private boolean dfs(int i, int j) {
marked[i][j] = true;
boolean out = !isBorder(i,j);
// Check 8 neighbours, if CC hits the border
// out turns to “false”;
for (int ii = i-1; ii<=i+1; ii++)
for (int jj = j-1; jj<=j+1; jj++)
if (isValid(ii, jj) && !marked[ii][jj])
out &= dfs(ii, jj);
return out;
}
// Is it a border of the board?
private boolean isBorder(int i, int j) {
return (i==0 || j==0 || i==M || j==N);
}
// Is it inside the board and “0”?
private boolean isValid(int i, int j) {
return (i>=0 && j>=0 && i<M && j<N && !board[i][j]);
}
}
It depends on interpretation. My interpretation is that there are events in the calendar e.g. football matches. The goal is to find a maximum number of football matches I can actually see.
- autoboli January 10, 2015If the sorted events were, say: 1-4, 2-3, 4-6, 6-8, 7-9, 9-10
Below is a trace of the stack in every iteration, there are three possible oprations when new event comes, these are: add, keep, replace
1: stack: 1-4
2: stack: 2-3 // replace, 2-3 intersects but ends earlier
3: stack: 2-3, 4-6 // add, does not intersect
4: stack: 2-3, 4-6 // keep, 6-8 intersects and ends later
5: stack: 2-3, 4-6, 7-9 // add, does not intersect
6: stack: 2-3, 4-6, 7-9 // keep, 9-10 intersects and ends later
It looks correct to me. I can see no more than 3 football matches.