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(n1) + fib(n2); }
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[i1][j]), S[i1][j  1]) + 1;
}
}
return S;
}

SK
May 19, 2015 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);
}

SK
May 13, 2015 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);
}

SK
May 08, 2015 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;
}

SK
May 07, 2015 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;
}

SK
May 05, 2015 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);
}

SK
April 27, 2015 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
(x1)(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;
}

SK
April 27, 2015 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 hindex 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;
}

SK
April 18, 2015 Sure,
The hashtable will be what notifies us if we've reached a nonunique 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 nonunique (0 for unique, 1 for nonunique). When we update the hashtable so that we have uncovered a nonunique 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 nonunique, 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 nonunique 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;
}

SK
April 18, 2015 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.
1234567891011121314151617181920
We know that we will delete 5, 10 and 15 in this case. So, for the block from index 69 will be shifted left 1. block index 1114 will shift over by 2. 1619 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);
}

Skor
April 04, 2015 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 ...
Open Chat in New Window
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