SK
BAN USER
- 0of 2 votes
AnswersGiven a List of Strings, return the number of sets of anagrams.
- SK in United States
For instance, given:
<abc,cab,dac,beed,deb,few,acd>
return 5| Report Duplicate | Flag | PURGE
Google Algorithm - 0of 0 votes
AnswersThe following is code that defines a modified recursive implementation of the fibonacci sequence:
fib (n) { if (n == 0) { print (“0”); return 0; } if (n == 1) { print (“1”); return 1; } return fib(n-1) + fib(n-2); }
We see that whenever we reach 0, we print out a 0 and when we reach 1, we print out a 1.
- SK in United States
Write an efficient algorithm that will print how many times 0 and 1 are printed out when a given n is input to the fibonacci function.
Examples:
numberOfOnesAndZeros(2) -> One “1” is printed out, One “0” is printed out
numberOfOnesAndZeros(3) -> One “1” is printed out, Two “0”s are printed out
numberOfOnesAndZeros(14) -> 233 “1”s printed, 377 “0”s printed| Report Duplicate | Flag | PURGE
Student - 0of 0 votes
AnswersLet's define an array as "pointy" if it monotonically increases from element 0 to some element k and then monotonically decreases from k onwards. (0 <= k).
- SK in United States
Example: [1,2,3,4,5,4,3,1]
Not Pointy: [1,2,3,5,3,6,1]
Given an array "s", modify it so that it is pointy.| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswerFind the intersection of 2 binary search trees. Remember that this is a set.
- SK in United States| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswersYou are given a String of number characters (S), like the following for example:
- SK in United States
"132493820173849029382910382"
Now, let's assume we tie letters to numbers in order such that:
A = "0"
B = "1"
C = "2"
...
M = "12"
N = "13"
...
Y = "24"
Z = "25"
Write an algorithm to determine how many strings of letters we can make with S, by converting from numbers to letters.| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersWe can find the minimum of an integer array in n operations. We can find the maximum of an integer array in n operations.
- SK in United States
How can we find both the min and max of an integer arrays in less than 2n operations?
Hint: Specifically in 3n/2 + c operations| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersGiven two binary trees, A and B,
- SK in United States
we can define A as a subset of B if the root of A exists in B and if we can superimpose A on B at that location without changing B. (That is, the subtrees from the root of A and the node in B that is the same as the root of A are the same),
Example:
A:
5
4 7
B:
6
5 12
4 7 8 10
A is a subset of B in this case.
B1:
6
5 12
4 7 8 10
1
A is still a subset of B1, even though B1 extends one more level than A.
Write an algorithm to determine if one tree is a subset of another tree| Report Duplicate | Flag | PURGE
Google Algorithm
Assume 32 bit integer
bit_vector = vector<int>;
void setTrue(index) {
int remainder = index % 32;
bit_vector[index/32] |= 1 << remainder;
}
void setFalse(index) {
int remainder = index % 32;
bit_vector[index/32] &= ~(1 << remainder);
}
void setAllTrue() {
for (int& i : bit_vector) {
i |= 0xFFFF;
}
}
void setAllFalse() {
for (int& i : bit_vector) {
i &= 0;
}
}
bool getIndex(index) {
int remainder = index % 32;
return (bit_vector[index/32] >> remainder) & 1;
}
def reverseString(theString):
operatorList = ['*', '+', '-', '/']
finalString = ""
i = len(theString) - 1
while (i >= 0):
currentNum = ""
while (i >= 0 and theString[i] not in operatorList):
currentNum = theString[i] + currentNum
i -= 1
totalString += currentNum
if (i >= 0):
totalString += theString[i]
i -= 1
Let's look at the pattern of binary representations of consecutive ones vs. non-consecutive ones. Let's shift the number over by 1 bit (on the bottom):
01001
10010
01101
11010
011001
110010
We see that if we AND the numbers, consecutive-one numbers produce non-zero values, so our check if the binary representation has consecutive ones is this;
bool consecutiveOnes(int n) {
return ((n << 1 & n) != 0);
}
Loop through checking the following condition:
boolean isIntersecting(float[] arr, int n) {
if ((arr[n-1] < arr[n - 3]) && (arr[n] > arr[n-2])) {
return true;
}
if (n < 5) {
return false;
}
if ((arr[n-1] < arr[n - 3]) && (arr[n - 5] > arr[n - 1]) && (arr[n] > (arr[n-2] - arr[n-4])) {
return true;
}
return false;
}
do malloc of size (sizeInBytes+sizeAlignment), then from the starting pointer, find the first address that %sizeAlignment gives you 0.
if size is 1000 and alignment is 64, and malloc gives you a pointer at location 129 for example, it will extend from address 129 to 1093. From 129, we need to find the first pointer that %64 is 0, so we do (129/64 + 1)*64 = 192. From 192, we mark this as the beginning of the allocated space, and we mark 192 + 1000 -> 1192 as the end of the block.
Not sure how to stop memory from being used though.
To delete, Keep track of this distance from the new pointer to the original malloc pointer address.
Keep a stack, then iteratively, find the path from the head to the Node you are considering. Each node you visit, push onto the stack. Now, when u reach your target node, you will begin to pop from the stack. The first Node you pop from the stack that has a higher value than your target node is the inorder successor. If all of the nodes on the stack are smaller than the target node, your target node is the last Node in the inorder traversal so the next node after that must be null.
public Node findSuccessor(Node n, Node head, Stack s) {
Node current = head;
while (true) {
if (current == null || current.value == n.value) {
break;
}
if (current.value < n.value) {
s.push(current);
current = current.right;
}
else if (current.value > n.value) {
s.push(current);
current = current.right;
}
}
while (s.size() > 0) {
if (s.peek().value > n.value) {
return s.peek();
}
s.pop();
}
return null;
}
Assume
k = # of digits per number
n = # of numbers in file
Suffix Tree for the numbers. Assume O(k) suffix tree construction for each number. Then, we would perform this n time for a suffix tree construction of O(nk). Now, we can simply look up the number in the suffix tree in O(k) time.
We can keep nodes and connections between nodes represents friendship. Each Node can have a hash table of "Liked Things". Such that every time a person likes something, there will be an observer object for all friends. Then the observer checks to see if the "Liked Object" exists in the respective Node's hashtable.
- SK July 14, 2015Create a Node for each Entry with the following structure:
Node {
List<Strings> info
int index
boolean visited
}
For every string entry in "info", hash the Node into the Hashtable. Then, for each node, run DFS. Add all the Nodes to a visited list, and make a set out of these nodes. Next, run DFS for another Node. We know that if it is visited, then it already exists in the set. Keep running DFS until we exhaust all Nodes.
This can be written in a recursive fashion as such:
F(M, N) = F(M- 1, N) + F(M, N- 1)
Because we have to maintain the order of processes. If we started with Ma, next could either be Mb or Na (which is represented by F(M- 1, N)). Likewise, if we start with Na, next could either be Nb or Ma (which is represented by F(M, N - 1)).
In code, something like this could work:
public int num(int m, int n) {
if (m < 0 || n < 0) {
return 0;
}
if (m == 0) {
return 1;
}
if (n == 0) {
return 1;
}
return num(m , n-1) + num (m - 1, n);
}
We can then memoize to make it more efficient.
- SK July 11, 2015If we have something like a1 > a2, a2 > a3, a3 > a1, we know that there is no ascneding order. So we can create a graph based on the comparisons. Create nodes for each element. and then if element x > element y, direct the graph from node y to x. Run some sort of graph algorithm like DFS with cycle detection. If we detect a cycle, we know that we can not order in ascending order.
- SK July 09, 2015You have to take into account the fact that cuboids might not fit directly into the bigger cuboid- the volumes might be divisible, but physically, it might not be viable.
For example, if we take rectangles of size 4x3, our area would be 12. If we try to fit squares of 2x2 into that area, at first we might think just to divide 12 by 4 to get 3 squares that fit, but if you actually draw it out, you can only really get 2 squares to fit.
So, we need to break this down based on how many ways we can divide each dimension by 2, and take the floor of that, since anything above that would just be extra space.
boolean canFit(int x, int a, int b, int c) {
return (((a/2)* (b /2) * (c/2)) >= x);
}
Keep k variables. Each variable represents a factor. Each iteration, output the min variable then increment it by the respective factor. If a variable is equal to the currently output value, increment it (to avoid duplicates). When you've outputed n numbers, you are done.
O(kn) time, O(k) space
public static void printFactors(int[] values, int n) {
int[] variables = new int[values.length];
int output = 0;
int i = 0;
int toIncrement = 0;
while (i < n) {
toIncrement = 0;
for (int j = 0; j < variables.length; j++) {
if (variables[j] < variables[toIncrement]) {
toIncrement = j;
}
}
if (output < variables[toIncrement]) {
output = variables[toIncrement];
System.out.println(variables[toIncrement]);
i++;
}
variables[toIncrement] += values[toIncrement];
}
}
Find max element with binary search. Then do binary search on the subarray of all numbers to the left of the max, then do another binary search on subarray on all numbers to the right of the max.
log(n) for max
log(n/2) for left subarray
log(n/2) for right subarray
-> 3log(n) time -> O(logn)
Hash the values of all elements. Then go through, and for each element x, check if x + 1 or x -1 exist in the hashtable. If so, add such elements to a specific set. With all the sets, go through and check which set has the greatest number of elements. Return that set.
- SK June 10, 2015Find the max and set it as the first element (whatever rotation results in that) seems to be the greedy approach and can give a good approximation, but I don't know if this works all the time.
The goal is to get the biggest cluster of big numbers at the left side of the rotated array, but I am not sure of an algorithm to do this
I had this idea too, but i'm not sure if it's better than brute force- mainly because for every combination you try, you have to see if adding digit 0,1,2,3,4,5,6,7,8,9 are in the hashtable. This means, you will (at worst case) test 10 digits each time, and do this 100,000 times, which is worse than brute force of 500,000 checks
- SK June 01, 2015this is a mean question to ask.
i think the approach is to give a stream of numbers such that every 5 consecutive numbers gives you a unique number. I don't know how to do this though.
There is another option which is to keep a hashtable of all numbers from 0 to 10000, then when you add another number to the stream, you check which digit you can add and see if this new digit with the last 4 numbers in stream are already in the hashtable? This ends up being more cumbersome than brute force though...
Say k = size of each sequence. Check all subsequences length k from k = 1 to n/2. Keep track of the min/max of subsequences. If subsequences are non intersecting and the max of one is smaller than a min of the other, you've found your answer. This is expected to be an O(n^3) algorithm
- SK May 22, 2015public static void main(String[] args) {
String s = "careercup";
generateAll18(s, 1, s.length() - 1);
}
public static void generateAll18(String s, int i, int j) {
if (i >= j) {
return;
}
String s1, s2, s3;
s1 = s.substring(0, i + 1)+(j- i - 1)+""+s.substring(j, s.length());
s2 = s.substring(0, i)+(j - i)+""+s.substring(j, s.length());
s3 = s.substring(0, i+1)+(j - i)+""+s.substring(j + 1, s.length());
System.out.println(s1);
System.out.println(s2);
System.out.println(s3);
generateAll18(s, i+ 1, j-1);
generateAll18(s, i + 1, j);
generateAll18(s, i, j - 1);
}
Modify this by adding a hashtable to remove duplicates
- SK May 22, 2015This is a case of using bitwise dark magic
public int bitsSet(char[] arr) {
int currentRep;
int count = 0;
for (int i = 0; i < arr.length; i += 4) {
currentRep = hammingWeight[i] << 24 | hammingWeight[i + 1] << 16 | hammingWeight[i + 2] << 8 | hammingWeight[i + 3];
count += hammingWeight(currentRep);
}
}
public int hammingWeight(int i) {
//bit magic here- there is a way to do this in O(1)
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Reppaulajheineman, Consultant at Bank of America
Hello, I am from Las Vegas, NV.Completed a Diploma course in Advanced Technological Developments and Staff Management. I have ...
Bloom filter will work only for the false case, not the true case.
- SK April 04, 2021One other way to optimize for space could be to keep two levels of hashsets. One regular one, one for contiguous ranges. If in your regular hashset you find that you have hashed numbers in, say, a contiguous block of 10 (like 0-9 inclusive), you can remove them from regular hashshet and then add 1 to your range hashset. Now, as you are checking a new number n, check to see if n/10 exists in the range hashset. If not, check in the regular hashshet.
This can incredibly reduce your space usage.
One more thing, this seems more like an open ended question to see how many questions you can ask about details and come up with different solutions for it rather than one with one correct answer.