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
If you think of the plot as a matrix of 1s and 0s, where 1s are available land and 0s are unavailable land (land with buildings already there), then this problem reduces to finding the maximum size square submatrix. Which has a dynamic solution of O(n^2)
public int[][] findMaxSubmatrix(int[][] mat) {
int[][] S = new int[mat.length][mat[0].length];
for (int i = 0; i < S[0].length; i++) {
S[0][i] = mat[0][i];
}
for (int j = 1; j < S.length; j++) {
S[j][0] = mat[j][0];
}
for (int i = 1; i < S.length; i++) {
for (int j = 1; j < S[0].length; j++) {
if (mat[i][j] == 0) {
continue;
}
S[i][j] = Math.min(Math.min(S[i][j - 1], S[i-1][j]), S[i-1][j - 1]) + 1;
}
}
return S;
}
Order the indices based on start and end time such that the start times are ordered in buckets and within those buckets, the end times are ordered.
In your example, we order from
[1,2][5,6][1,5][7,8][1,6]
to
[1,2][1,5][1,6][5,6][7,8]
Now iterate through these indices. As long as:
end time of the previous index > start time of current index
this index will be in a set.
public static void printRational(int a, int b, int n) {
String output = "";
int div, mod, currA, currB, i;
i = div = mod = 0;
currA = a;
currB = b;
output += (a/b)+".";
for (;i < n; i++) {
mod = currA % currB;
mod *= 10;
while (mod < currB) {
mod *= 10;
output += "0";
i++;
}
output += mod/currB+"";
currA = mod;
}
System.out.println(output);
}
public static void getBitStrings(String s) {
listPossibilities(s, "", 0);
}
public static void listPossibilities(String bitString, String currentString, int currentIndex) {
int length = bitString.length();
if (currentIndex == length) {
System.out.println(currentString);
return;
}
if (bitString.charAt(currentIndex) == '?') {
listPossibilities(bitString, currentString + '0', currentIndex + 1);
listPossibilities(bitString, currentString + '1', currentIndex + 1);
return;
}
listPossibilities(bitString, currentString + bitString.charAt(currentIndex), currentIndex + 1);
}
public static void shuffle(int[] a) {
int n = a.length;
for (int i = 0; i < a.length - 1; i++) {
int randNum = (int) (Math.random() * (n - i));
swap(randNum, n - i - 1, a);
}
}
public static void swap(int e1, int e2, int[] arr) {
int temp = arr[e1];
arr[e1] = arr[e2];
arr[e2] = temp;
}
I don't feel like writing the code for this, but the process is basically to BFS from the guards, and for each empty space, record the depth from the guard in the BFS -> depth of parent + 1. Since we will do multiple BFS's record the minimum depth if it this is possible.
- SK May 05, 2015The pattern is that starting from index 2, each pair acts as a compression of terms in the last element. For index 2, it indicates that there was one 1 in the last element. For index 3, it indicates that there was one 2 and one 1 in the last element. In index 3, it indicates that there was one 1, one 2, and two 1s in the last element. So on and so forth. Code below:
public String getSequence(int n) {
String current = 1+"";
for (int i = 1; i < n; i++) {
current = analyzeInt(current);
}
return current;
}
public String analyzeInt(String x) {
if (x.length() == 1) {
return 1+""+x;
}
int currentCount = 1;
String output = "";
int i = 0;
for (i = 1; i <= x.length(); i++) {
currentCount = 1;
while (i < x.length() && x.charAt(i - 1) == x.charAt(i)) {
i++;
currentCount++;
//System.out.println(currentCount);
}
output += currentCount+""+x.charAt(i - 1)+"";
}
return output;
}
public boolean isBST(Node n) {
if (n == null) {
return true;
}
Node left, right;
left = n.left;
right = n.right
boolean leftCondition, rightCondition;
leftCondition = (left == null) ? true : (left.value < n.value) ? true : false;
rightCondition = (right == null) ? true : (right.value > n.value) ? true : false;
return leftCondition && rightCondition && isBST(n.left) && isBST(n.right);
}
You know that you will reach k by following the pattern 1,2,3,4,... if 1 + 2 + 3 + 4 + 5 +...a = k
What does this remind us of?
1 + 2 + 3 + 4 + 5 +...x = (x)(x + 1)/2
So, we can work from here and see if there's an x such that this case is true. If not, then our answer is (n)(n+1)/2
If so, we do
(x-1)(x)/2 + remaining steps starting from x +1.
remaining steps starting from x + 1 would be (n + 1)(n + 2)/2 - (x)(x+1)/2
So our final answer would be
(x - 1)(x)/2 + (n + 1)(n + 2)/2 - (x)(x+1)/2
public int numSteps(int k, int n) {
if (!integerSolutionExists(k)) {
return getSum(n);
}
int x = (int) solveQuadratic(k);
return getSum(x - 1) + getSum(n) - getSum(x);
}
public int getSum(int x) {
return (x * (x + 1))/2
}
public boolean integerSolutionExists(int k) {
return(Math.floor(solveQuadratic(k)) == solveQuadratic(k));
}
public double solveQuadratic(int k) {
return (-1 + Math.sqrt(1 - 4 * (-2 * k)))/2;
}
We can DFS starting from some cell travelling until the DFS reaches a 0. We record the number of visited cells as we DFS and return this value. Let's call this DFS function F.
We now do F on every cell, and return the maximum value found from the Fs.
There are of course many ways of optimizing this, but this is the general idea.
We know that if we order the array from largest values to smallest values, that we can keep basically incrementing h values until we get to a number that is smaller than its current index- Since bigger numbers have more flexibility in being considered in the h-index count.
public int getH(int[] arr) {
int h = 0;
for (int i = 0; i >= 0 && arr[i] >= i + 1; i--) {
if (arr[i] >= i + 1) {
h++;
}
}
return h;
}
Sure,
The hashtable will be what notifies us if we've reached a non-unique character, because we will have multiple things in our value to the key of such a character. Our secondary array serves to flag characters that are non-unique (0 for unique, 1 for nonunique). When we update the hashtable so that we have uncovered a non-unique char, we will know to update the secondary array at the index for that char. The pointer of the secondary array will tell us the first character that is non-unique, so we only want to move it when the hashtable update results in an update in that array at the position of that pointer. So we increment this pointer until it gets to 0, indicating the first non-unique character.
Let's keep a secondary array that will tell us whether the character at the index has a copy.
We will also keep a hashtable, call it h, with key value pair of this <char, indices of char>.
Finally keep a pointer on the secondary array.
We pass through the list and add characters to the hashtable. If there is already a value for the key to that char, we set the position in the secondary array to 1. If we set a value to 1 and the secondary array pointer is pointing there, we increment this pointer until it points to a 0.
at the end, return the character at the position the pointer is pointing to.
Some code:
public char firstUnique(String s) {
HashMap<Character, ArrayList<Integer>> h = new HashMap<Character, ArrayList>();
int[] valid = new int[s.length()];
int ptr = 0;
char currentChar;
for (int i = 0; i < s.length(); i++) {
currentChar = s.charAt(i);
if (!isUnique(currentChar, i, h, valid)) {
for (Integer i : h.get(currentChar)) {
if (i == ptr) {
while (arr[ptr++] != 0) {}
}
}
}
}
if (ptr >= s.length()) {
return '';
}
return s.charAt(ptr);
}
public boolean isUnique(char c, int currIndex, HashMap h, int[] arr) {
if (h.exists(c)) {
h.get(c).add(currIndex);
arr[currIndex] == 1;
return true;
}
ArrayList<Integer> toAdd = new ArrayList<Integer>();
toAdd.add(currIndex);
h.put(c, toAdd);
return false;
}
You can start by BFSing from the top left corner, with the exception that you will only keep BFSing if the value is increasing. Keep a secondary 2D array with lists of parent pointers for each element of the array. When every element has been visited, we now will have a graph of parents in our secondary 2D array. For all elements bordering the east coast, traverse through all of the parent pointers. If one of the pointers reaches the west coast, increment a global count of possible paths.
- SK April 17, 2015Let's assume we don't know the order at which the characters are arranged in the word.
We first do a pass through of the alphabet O(26), to see what letters we "hit", so we know which letters are in the word and how many of that specific letter there is.
Now, we will have a string of unorganized letters, so we will sort these letters into (let's call it) string S. You will see why in a little bit.
We know that the dictionary could be interpreted as a list. To match strings, we can check their hashcodes. But there are so many different ways of arranging strings that this can be very cumbersome. Luckily, we can sort a string's letters by ascii value (for example), to get a hashcode that applies to all combinations of strings. We simply sort every word in the dictionary and compare its hash value to that of S. When we get a match, we will have found the word we're looking for.
If N = # of words in dictionary and k = length of target word and m = length of longest word in dictionary, our system runs in:
O(26) + O(klogk) + O(Nmlogm) + O(n), for a big O of O(Nmlogm)
We can do this with two stacks.
On S1, push characters from s onto it. On S2, push characters from p onto it.
Now, when we enocunter * or ., append this to the push on the stack.
Now, look at the top of the two stacks. If they match, pop both off. If they don't, then you know that there is no match. If there is '*' with a character on S2, pop from S1 however many times the character would exist. If we encounter a ., this is wildcard, so we can pop from S1 and S2 however many times we need be. The goal is to get S1 completely empty. If this happens, then we have found a match. If not, there is no match.
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20
We know that we will delete 5, 10 and 15 in this case. So, for the block from index 6-9 will be shifted left 1. block index 11-14 will shift over by 2. 16-19 will shift over by 3. Here we see a pattern. Because of continuous shifts, each block of numbers not divisible by 5 will shift left one more than the last block.
So, something like the following:
public void editBytes(byte[] arr) {
int leftShiftAmount = 0;
int i = 5;
for (i = 5; i < arr.length; i+=5) {
memmove(arr[i] - leftShiftAmount, arr[i + 1], sizeof(byte)*4);
leftShiftAmount++;
}
int clearIndex = i - 5 - leftShiftAmount + 4;
for (clearIndex = i - 5 - leftShiftAmount + 4; clearIndex < arr.length; clearIndex++) {//clear the garbage at the end, or you can just truncate up to this point
arr[clearIndex] = 0;
}
}
- SK April 07, 2015This is the correct algorithm overall. Just one nitpick. As you probably know, you may not know the range of numbers passed in to create the hashtable with. It may be helpful to have a preliminary run through of the array to find the max element so that you can more accurately instantiate your hashtable to the right size.
- SK April 07, 2015Sure- here you go
public boolean triangleTripletExists(int[] arr) {
mergeSort(arr);
int i, j, k;
i = 0;
j = 1;
k = 2;
for (k = 2; k < arr.length; k++) {
if (isTriplet(arr[i++], arr[j++], arr[k])) {
return true;
}
}
return false;
}
public boolean isTriplet(int a, int b, int c) {
boolean first, second, third;
first = ((a + b) > c);
second = ((a + c) > b);
third = ((c + b) > a);
return (first && second && third);
}
Obviously, the bad way of doing this would be to try all triplet combinations and see if there is one triplet that works.
A better way of doing it focuses on the fact that triangles are more likely to occur when the 3 lengths are close to each other. Example: 3,4,5 are closer numbers than 3,4,6, so they are more likely to be a triangle than 3,4,6.
With this in mind, we sort the list of segments- presumably in O(nlogn) with merge sort. Then in O(n) time, we traverse the sorted list. Set i = 0, j = 1, k = 2.
Check if array[i], array[j], array[k] are a triangle. If not, increment i, j, k then repeat the process.
Add and Remove are trivial. But for the mode, we can do this in O(1) time.
When you add to the stack, you keep a hashtable containing a mapping between number and count and the location of the number in the heap. <Number, Count, Heap Location>. Now, you can keep a max heap of pairs <Number, Count>. When you add a number to the stack, you update it in the hashtable. Next, if the number doesn't exist in the heap, we add it to the heap (in logn time), then update the hashtable to point to it. If it DOES exist in the heap already, we remove it from the heap, then add it again with its new count to the heap in O(logn) time.
In total, adding to the stack would take 2logn -> O(logn). Getting the mode would be O(1), as it would just be looking at the top of the max heap.
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 ...
This is code I had written for the DP problem. When you get matrix S, you find the maximum number in it and this maximum number will be at the bottom right corner of the square and the number will tell you how big the square is.
- SK May 19, 2015