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
public String compressString(String s) {
String out;
int currentCounter = 1;
for (int i = 1; i < s.length; i++ {
while (i < s.length && s.charAt(i) == s.charAt(i - 1)) {
currentCounter++;
i++;
}
out += s.charAt(i-1) + currentCounter;
currentCounter = 0;
}
return out;
}
We know that if we have a rectangle (width = x, height = y), that the number of ways to get from the top left corner of the rectangle to the bottom left corner of the rectangle with right and down movements will be C(x + y, x) [which is also C(x + y, y)], because this represents the way we can order R and D movements so that we end up at our destination.
Now, we can apply this to the grid by finding rectangles created by entry and exit points - such that these points represent opposite corners of a rectangle, plug in the width and height of the given rectangle into C(w + h, w), and then sum these values to get the total paths.
Runtime should be O(n^2)
I'm not sure if this is what you want, but I guess it is important to note that small bags can fit in small, medium, and large slots. Medium can fit in medium and large slots, but can't fit in small slots. And large bags can only fit in large slots (can't fit in small or medium slots). Here, we see that the token numbers should give the greatest flexibility to small bags, medium flexibility to the medium flexibility to the medium bags and low flexibility to the big bags. You can simply have 3 hashtables, one for each bag type. In the small bag hashtable, you have k slots. In the medium bag hashtable, you have 2k slots (for every possible k bags, there are 2 spots reserved- one for medium one for small). In the large bag hashtable, you have 3k slots ( 3 spots reserved - one small, one medium, one large). You can definitely set up the token number so that the token number used is flexible because of the space that is reserved for the different kinds of bag.
- SK February 28, 2015This is basically an application of BFS. We will keep 2 queues- one representing one level and the other representing another.
We start by putting the head in the first queue (Q1). Now, we BFS the head, and add all of its children to Q2 in order. We remove the contents of Q1 and make it a linked list. Now, we BFS Q2 and put all of the children of nodes in Q2 into Q1. Remove the contents of Q2 and make it a linked list. Continue this process of alternating BFS between queues until there are only null values in a queue.
Some Code:
ArrayList linkedListify(Node head) {
Queue q1, q2; //assume these are initialized or whatever
q1.enqueue(head);
ArrayList<LinkedList> ANSWER;
int counter = 0;
while (true) {
LinkedList x = (counter % 2 == 0) ? convertQueueToLinkedList(q1, q2) : convertQueueToLinkedList(q2, q1) ;
if (x == null) { break; }
counter++;
}
return ANSWER;
}
LinkedList convertQueueToLinkedList(Queue q1, Queue q2) {
if (q1.size() == 0) { return null; }
LinkedList list;//initialize
Node current;
Node listToAdd = q1.dequeue();
q2.enqueue(listToAdd.left);
q2.enqueue(listToAdd.right);
current = list.head = listToAdd;
while (q1.size() != 0) {
listToAdd = q1.dequeue();
q2.enqueue(listToAdd.left);
q2.enqueue(listToAdd.right);
current = list.head = listToAdd;
current = current.next;
}
return list;
}
If we assume we can't use regex. (Since that would somewhat trivialize this problem)
You could populate the hashtable by recursively running through all the strings and replacing * in the strings to make all combinations of letters and *.
If the length of the longest string is k, then the population of the hashtable runs in O(n * 2 ^k), but then lookup is just O(1).
You can populate the hashtable with something like the following code called on every string s with the following function call:
Example:
populateHashTable(hashtableObject, "ahmed", "", 0);
populateHashTable(HashTable h, String original, String edited, int currentCharIndex) {
if (currentCharIndex >= s.length) {
h.add(edited, true);
return;
}
populateHashTable(h, original, edited + original.charAt(currentCharIndex), currentCharIndex + 1);
populateHashTable(h, original, edited + "*", currentCharIndex + 1);
}
We can solve this by memoization. For the given array "a", we will create a 2d array called "val" which will tell us information about the corresponding index at a. For every index in val, there are 2 values- one is a pointer which points to the most previous value that is both lower than the current value we are looking at and has the most previous values in a subsequence. The second one tells us the number of values in the subsequence that the current element is in.
For example, given:
[1,10,4,5,6, 11]
vals[1][0] = 0 (10 points to 1) -> vals[1][1] = 2
vals[2][0] = 0 (4 points to 1) -> vals[2][1] = 2
vals[5][0] = 4 (11 points to 6 and not 10 because the subsequence at 6 is bigger than that of 10) vals[5][1] = 5
We just basically need to go through all of the indices in the array from left to right and populate vals.
Then, we can check which of the second values in vals is maximum. Here, we just unwind the sequence by following the pointers. Use a stack here to add to a String and the print out b.
getB(int[] a) {
int[][] vals = new int[a.length][2]; //0 index is the pointer, 1 index is the number of previously visited
for (int i = 0; i < a.length; i++) {
vals[i][0] = -1;
}
for (int i = 0; i < a.length; i++) {
checkBackwards(a, vals, i);
}
int maxValElement, maxValIndex;
maxValElement = maxValIndex = 0;
for (int j = 0; j < vals.length; j++ ) {
if (vals[j][1] > maxValElement) {
maxValIndex = j;
maxValElement = vals[j][1];
}
}
unWind(a, vals, maxValIndex);
}
checkBackwards(int[] a, int[][] vals, int currentElement) {
int maxElement, maxIndex;
maxElement = maxIndex = 0;
for (int i = currentElement; i >= 0; i--) {
if (a[i] < a[currentElement] && vals[i][1] > maxElement) {
maxElement = vals[i][1]
maxIndex = i;
}
}
vals[currentElement][0] = maxIndex;
vals[currentElement][0] = vals[maxIndex][1] + 1;
}
public void unWind(int[] a, int[][] vals, int element) {
Stack s = new Stack;
int currentVal = element;
while(vals[currentVal][0] != -1) {
s.push(a[currentVal]);
currentVal = vals[currentVal][0];
}
s.push(a[currentVal]);
while (s.size() > 0) {
System.out.print(s.pop()+", ");
}
}
Something like the following:
We modify an inorder traversal to keep track of pointers to the "current" Node we are on in the list. We can also keep track of the head and tail of the list and after the inorder traversal, we simply link up the ends of the lists to make it circular.
I wrote this quickly, so there may be some syntax bug with the pointer logic (haven't done C pointers in a while) but I think it is the correct logic:
makeCircularList(Node treeHead) {
Node *head;
Node *tail;
Node *current;
modInorder(treeHead, current, head, tail);
tail -> right = *head;
head -> left = *tail;
}
modInorder(Node n, Node *current, Node * head, Node * tail) {
if (n == NULL) {
return;
}
Node previous;
if (*head == NULL) {
head = &n;
}
tail = &n;
previous = modInorder(n.left, current);
current -> right = n;
current = &n;
current -> left = previous;
modInorder(n.right, current)
}
Some Code:
public void findMinAndMax(int[] arr) {
for (int i = 0; (i + 1) < arr.length; i+=2) {
if (arr[i] > arr[i + 1]) {
switchElements(arr, i, i + 1);
}
}
int minIndex, maxIndex, minimum, maximum;
minIndex = 0;
maxIndex = 1;
for (int i = 0; i < arr.length; i += 2) {
if (minIndex < arr.length && arr[minIndex] < minimum ) {
minimum = arr[minIndex];
}
if (maxIndex < arr.length && arr[maxIndex] > maximum ) {
maximum = arr[maxIndex];
}
minIndex++;
maxIndex++:
}
}
public void switchElements(int[] arr, int e1, int e2) {
int temp = arr[e2];
arr[e2] = arr[e1];
arr[e1] = temp;
}
Regular way of doing this is basically find minimum and maximum values each in O(n) operations, but you can do both at the same time in 3n/2 operations.
First, compare all consecutive pairs of elements, order them, then check even elements to get the min and check the odd elements to get the max.
First, pass through the array and check how many 0s there are. If there is more than one zero, then all the array elements in the output array MUST be 0.
If there is only one 0, then replace it with a 1.
After our first pass through, we will go through the array and get the product of all the array elements. let's call this product x.
Finally, we go through the array and for each element "e" in the array, its corresponding value in the new array will be x/e.
This algorithm would, thus, run in O(3n) = O(n).
I'm pretty sure that it would also work with negative numbers.
You can scan all rows, scan all columns, and scan diagonals, but instead of multiplying 4 numbers everytime, you can just do a kind of rolling multiplication - I think this is what the interviewer is looking for as far as optimization.
Say you have a row:
3,4,1,2,5,4,3
calculate x = 3*4*1*2
then when you roll, divide the first number and multiply the next number, so
x /=3
x *= 5
Of course, you can't divide by 0, so when the first number is a 0 and the new number isn't, you need to re-multiply
That way you only do 2 operations rather than 4 operations every step
Sure, (Also I made a mistake- should be left and downward, not right and downward)
Let's say our matrix is the following:
00011111
00001111
00111111
01111111
00001111
We know that the max 1 row will be the one where we reach a 0 the latest from the left. Start from the top right. Scan left until we reach a 0. When we reach a zero, record the column we are on- if this column is lower than the max row column, then we set it as the max row. When we reach 0, go down the column until we reach a 1, when we get to this scan left again until we reach 0, doing the same process. When we are at the last row and at a 0, we are done.
First row, we scan left until we get to the x
000x1111
00001111
00111111
01111111
00001111
Scan down to the first 1 we get:
00011111
00001111
001x1111
01111111
00001111
Scan left again:
00011111
00001111
00x11111
01111111
00001111
Scan down until we reach a 1:
00011111
00001111
00111111
01x11111
00001111
Left to get to zero:
00011111
00001111
00111111
0x111111
00001111
Down to the last row:
00011111
00001111
00111111
01111111
0x001111
We have seen that the row that had the smallest column was the 2nd to last one, so this is our answer. Because at worse cast we step down from top right to bottom left, we find the answer in at most 2n operations
We just want the left view, so what we can do is keep an array to hold the nodes we encounter in a traversal. We will traverse the right side before the left, ultimately overwriting nodes that are right-most with ones that are left most.
void printLeftSide(Node head) {
Node[] left = new Node[getTreeHeight(head)];
traverse(head, 0, left);
print(left.toString);
}
void traverse(Node curr, int depth, Node[] arr) {
if (curr == null) { return; }
traverse(curr.right, depth+1, arr);
arr[depth] = curr;
traverse(curr.left, depth+1, arr);
}
int getTreeHeight(Node head) {
if (head == null) { return 0; }
return Max(getTreeHeight(head.left), getTreeHeight(head.right)) + 1;
}
Sort each input array by the first number in the array:
[4, 8], [3, 5], [-1 2], [10, 12] -> [-1 2], [3, 5], [4, 8], [10, 12]
Then compare the last number of an array (L) with the first number (F) of the next array. If L + 1 is strictly < than F, then output the range we have visited so far.
We know that any number that only has 1s an 0s can be interpreted as a bit string.
We know that since our maximum bitstring for long is 1111111111 that this is the bit representing 1023.
So we simply find a conversion from all integers from 1 to 1023 (inclusive) to their corresponding bitstring values then check if this bitstring can divide our given number.
It is possible to avoid the overhead of String to long conversion by simply writing your own method for the conversion from int to long directly.
The function convertDecToLong runs in 32 operations since it will bitshift at most 32 times. Running this operations something around 1023 times will give us an estimated ~32000 operations - much better than the brute force of 1111111111 operations.
public static long min(int n) {
for (int i = 0; i <= 1023; i++) {
long possibility = convertDecFromBin(i);
if (isDivisible(possibility, n)) {
return possibility;
}
}
return -1;
}
public static long convertDecFromBin(int n) {
long output = 0;
int x = n;
int currentDecPlace = 0;
while (x != 0) {
output = ((x & 1) == 1) ? (output + (long)Math.pow(10, currentDecPlace)) : output;
currentDecPlace++;
x >>= 1;
}
return output;
}
s = our string
Keep two pointers. p1 is always one element behind p2. Every iteration, both are incremented. We check if s[p2] == s[p1] or s[p1-1]. If so, we know that we have a palindrome in some form, so we start recording the string with 2 pointers- iterate outwards until the palindrome ends and record all of the "visited" strings into an output table.
For example with the String "4racecarses", p1 and p2 are incremented until p2 = 5 and p1 = 4, s[p2] = s[p1-1]. Now, we iterate outwards: cec -> aceca -> racecar -> stop at 4racecars since the outward pointers won't match.
Back to the original loop, p2 is then at 6. Until it gets to the final element, it won't find a potential palindrome
In the end, add all single characters to the list
The algorithm is something like this:
You need to use two stacks. one for operator, one for numbers.
When you add two numbers onto the number stack and add an operator, you check if the previous operator (on the stack) is of higher precedence. if it does, then you calculate those numbers first.
I apologize, but I'm not sure what you do when you have parentheses though - it has higher operator precedence so I think you calculate everything in it until you get a close parenthesis?
If we arrange our bookings in an array {b1, b2, b3, b4,...}, we can do interval scheduling multiple times for each cab. Arrange bookings by end time into an Array A. Perform interval scheduling on A, then assign these bookings to the first cab. remove these bookings from A, then perform interval scheduling again, assign bookings to the second cab...repeat this process until there are no more bookings left to process.
- Skor February 01, 2015We loop throught and check each character with the one right before it in a while loop to see if a sequence is emerging. When the while loop is done (the streak ends), we see if we update the max value, and if we do, we also update the longest character.
Default returns the first character in the string.
char longestConsecChar(String s) {
int k, cnt = 1;
char longest = s[0];
for (int i = 1; i < s; i++) {
while (s[i] == s[i-1] && i < s) {
cnt++;
i++;
}
if (k < cnt) {
k = cnt;
longest = s[i-1];
}
cnt = 0;
}
}
I'm not sure of an O(n) solution, but I'm pretty sure you can do this in O(nlogn) using modified merge sort.
On each merge you do in merge sort, you have a left subarray (L) and a right subarray (R).
Assume that L has a candidate difference (CDL) and R has a candidate difference (CDR). On the merge, find the min from L and the max from R to get a candidate difference between L and R (CDLR). Now, for the array that L and R merge into, we will take Max(CDL, CDR, and CDLR) to be the candidate difference for the merged array.
Recursively, the answer bubbles all the way to the top.
Not enough time to complete the code, but this is the basic idea. We modify merge sort, so that whenever we add in an element from "the left side", we will add the difference between the end of the right side and the right side iterator to a hashed stored value for the element's qez.
For example, if we merge:
[11, 10, 5, 12, 20]
Our steps look like this:
[11, 10] -> [10, 11], No QEZ
[5, 12] -> QEZ of 5 is 1
[5, 12], [20] -> QEZ of 5 increases by 1, QEZ of 12 becomes 1
now when we merge
[10, 11] and [5, 12, 20]
[5] -> no QEZ change
[5,10] -> QEZ of 10 is now 2 because right pointer is pointing at 12
[5, 10, 11] -> QEZ of 11 is 2 because right pointer is pointing at 12
[5, 10, 11, 12, 20] -> No QEZ change for 12 and 20 since while loop ends the merge
Not enough time to complete the code, but the basic gist of the merge method is like this:
end refers to the location of the end of right pointer so in the case of [10, 11] and [5, 12, 20], right would be = to 2 and end would be equal to 2 + 2 = 4.
Sorry, again for incompleteness
merge(int[] arr, int[] new, int l, int r, int end, HashMap hm) {
boolean done = false;
int i = l;
int j = r;
int k = l;
while(!done) {
if (arr[left] >= arr[right]) {
new[k++] = arr[j++];
//handle ending case of merge here
}
else {
new[k++] = arr[j++];
hm.put(arr[k], hm.get(arr[k] + (end - j)) );
}
}
}
You can use a hashtable with strings as a key and an inUse boolean as a value.
When clients request a string, they are put in a queue to use the string if its inUse value is found to be "true".
It's basically a kind of manual implementation of mutex in multithreading
I think you would need a double for loop. In the outer loop, you iterate through all the houses to find one to begin at, then in the inner loop with the starting house defined in the outer loop, you will go through the rest of the houses and check to see what the best values you can make are, by continuously multiplying by the gems you encounter and only updating the values if you have visited an even number of red houses. I make an assumption that you can't have negative gems but that you can encounter a house with 0 gems, in which case your range will mess up, so you break out of the inner loop since there's nothing more you can do if you continue (since you will just multiply by 0).
int[] rangeHouse(char[] house, int[] houseGem) {
int[] optRange = new int[2];
int bestVal = 0;
int currentStart = 0;
int currentEnd = 0;
int currVal = 1;
int redCount = 0;
for (int i = 0; i < house.length; i++) {
redCount = 0;
currVal = 1;
currentStart = i;
currentEnd = i;
for (int j = i; j < house.length; j++) {
if (houseGem[j] == 0) {
break;
}
else {
currVal *= houseGem[j];
if (house[j] == 'R') { redCount++; }
if (redCount % 2 == 0 && currVal > bestVal) {
optRange[0] = currentStart;
optRange[1] = currentEnd;
bestVal = currVal;
}
}
}
}
return optRange;
}
I don't know if you are allowed to use complementary data structures, but I guess this works - we use a queue for insert and FIFO removal. We use a hashtable to keep track of modes of nodes, and finally we keep chronological track of modes with a stack (if we remove a mode, it will take us O(n) to search for the next one in the hash table, but we want this to be O(1)).
class DS {
HashTable<Node, Integer> ht;
Queue q;
Stack modeStack;
Node currentMode;
int modeNum;
insert(int element) {
Node curr = Node(element);
q.enqueue(curr);
int checkMode = ht.getValue(curr) + 1;
ht.put(Node, ht.getValue(Node) + 1);
if (checkMode > modeNum) {
curr = currentMode;
modeNum = checkMode;
modeStack.push(curr);
}
}
remove() {
Node curr = q.dequeue;
ht.put(curr, curr.getValue() - 1);
Node modeTop = modeStack.pop();
Node modeSecond = modeStack.peek();
if (ht.getValue(modeTop) < ht.getValue(modeSecond)) {
currentMode = modeSecond;
modeNum = ht.getValue(modeSecond);
return;
}
modeStack.push(modeTop);
}
findMode() {
Node mode = modeStack.pop();
currentMode = modeStack.peek();
modeNum = ht.getValue(currentMode);
return mode;
}
}
String reverseSentence(String s) {
char temp;
for (int i = 0; i < s.length / 2; i ++) {
temp = s[s.length - 1 - i];
s[s.length - 1 - i] = s[i];
s[i] = temp;
}
int p1, p2;
p1 = p2 = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ' ') {
reverseChar(s, p1, p2);
p1 = p2 = i + 1;
continue;
}
p2++;
}
return s;
}
void reverseChar(char[] c, int a, int b) {
//implement a reverse of char array at specific range here...
}
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 ...
Recursive Solution:
- SK March 05, 2015