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
XOR the numbers, then see how many 1s there are in this value
Reasoning:
We know that a ^ a = 0 , so 1 ^ 1 = 0 and 0 ^ 0 = 0
But, 1 ^ 0 = 1 and 0 ^1 = 1, so we see that we can find differences by xoring
Some code:
int numSwaps(int a, int b) {
int c = a ^ b;
int output = 0;
while (c != 0) {
out += c & 1;
c =>> 1;
}
return out;
}
For non sparse numbers, there's not really way to generalize getting a bigger sparse number, so here you just have to increment the number, check if sparse, increment, check (so on and so forth in the brute force approach. Now, let's look at sparse bitstrings:
Assuming they have greater than or equal to 4 bit positions, we can see something:
If it ends in:
1000, we can keep it sparse by adding 1
x1000 -> x1001
If it ends in:
1010, we keep it sparse by adding a 0,
x1010 -> x10100
If it ends in 1001:
x1001 -> 1010
For all other combinations of sparse bitstring, we will do the brute force approach, but this is a quick optimization
public void getSeeds(int n) {
for (int i = 1; i <= n; i++) {
if (isSeed(n, i)) {
System.out.println(i);
}
}
}
public boolean isSeed(int target, int num) {
return (getDigitProduct(num) * num == target);
}
public int getDigitProduct(int n) {
if (n == 0) {
return 0;
}
return (n / 10 == 0) ? n : getDigitProduct(n/10) * (n % 10);
}
Node mergeList(Node a, Node b) {
Node currA, currB, currC, cHead;
currA = a;
currB = b;
cHead = null;
//add first- address edge cases
if (a == null && b == null) {
return null;
}
if (a == null && b != null) {
return b;
}
if (a != null && b == null) {
return a;
}
if (currA.value <= currB.value) {
cHead = currC = currA;
currA = currA.next;
}
else {
cHead = currC = currB;
currB = currB.next;
}
while (true) {
if (currA == null) {
while (currB != null) {
currC.next = currB;
currB = currB.next;
currC = currC.next;
}
break;
}
if (currB == null) {
while (currA != null) {
currC.next = currA;
currA = currA.next;
currC = currC.next;
}
break;
}
if (currA.value <= currB.value) {
currC.next = currA;
currA = currA.next;
currC = currC.next;
}
else {
currC.next = currB;
currB = currB.next;
currC = currC.next;
}
}
return cHead;
}
First, sort the times by end time in a list L. Now, start from the first interval, do interval scheduling to see how many intervals are valid with the first interval.
Remove such intervals and put into one bucket.
Now with the first interval left in L, do the same thing. repeat this process until there are no intervals left in L. The number of buckets generated is the number of rooms needed.
Keep 2 stacks, s1 and s2.
For node 1, traverse down to the root while push Nodes onto the s1 until the root is on top of the stack.
For node 2, traverse down to the root while push Nodes onto the s2 until the root is on top of the stack
Now, pop from both stacks and compare ancestors. If the Nodes popped are the same, it is a common ancestor, so record this as the current ancestor. when it comes to nodes popped that are not the same, we have a reached a non-ancestor. Return the current ancestor to get the least one.
Seems pretty straightforward:
public void outputPairs(int n) {
int prev, curr, temp;
prev = curr = 1;
for (int i = 1; i < n + 1; i++) {
printPair(prev % 10, curr % 10);
temp = curr;
curr += prev;
prev = temp;
}
}
public void printPair(int a, int b) {
System.out.println("["+a+", "+b+"]");
}
This sounds like a type of bucketsort.
Create a hashtable mapping characters in O to a number counting its occurences in t
append characters that don't exist in o to the beginning of the output string.
Finally go through and add the number of a character corresponding to o
public String reorder(String t, String o) {
HashMap<String, Integer> H = new HashMap();
for (int i = 0; i < o.length; i++) {
h.put(o.charAt(i), 0);//put o chars in hashmnap
}
StringBuffer output = new StringBuffer();
for (int i = 0; i < t.length; i++) {
if (h.keyExists(t.charAt(i))) {
h.put(t.charAt(i), h.get(t.charAt(i)) + 1);//increment the value here
}
else {
output.append(t.charAt(i));
}
}
int copyNum = 0;
for (int i = 0; i < o.length; i++) {
copyNum = h.get(o.charAt(i));//get number of times this character occured
for (int j = 0; j < copyNum; j++) {
output.append(o.charAt(i));
}
}
returnt output.toString()
}
Recursively check all unique combinations
public List sumOfNumber(int n) {
Hashtable h = new Hashtable();
sumOfNumberHelper(n, h, "");
List output = newList<String>();
for (String s : h.values()) {
output.add(s);
}
return output;
}
public List sumOfNumberHelper(int n, Hashtable h, String prev) {
if (n < 0) {
return;
}
if (n == 0) {
h.add(prev.hashCode(), prev);
}
for (int i = 1; i < n; i++) {
sumOfNumberHelper(n - i, h, prev.append(i))
}
}
I'll admit I couldn't figure this out on my own and had to look it up.
This is what I found:
Algorithm:
First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.
Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4
I'm not really sure, conceptually how it works, so if someone has some insight on that, that would be great. Nevertheless, here is some code implementation of it:
public void fixArray(int[] arr) {
int pairStart, numPairs;
pairStart = x.length/2;
numPairs = 1;
for (int i = 0; i < x.length/2 - 1; i++) {
swapPair(arr, pairStart--, numPairs++);
}
}
public void swapPair(int[] arr, int startIndex, int numPairs) {
for (int i = startIndex; i < arr.length && i < startIndex + numPairs*2; i += 2) {
swap(arr, i, i + 1);
}
}
public void swap(int[] arr, int e1, int e2) {
int temp = arr[e1];
arr[e1] = arr[e2];
arr[e2] = temp;
}
Keep a hashtable (Call it h)
Keep a sum which represents the dot product value (Call it s)
Now, the idea is that we will add to h whatever mapping we encounter when reading the lines. If there is no such mapping for the vector position, we will add the mapping. if there is, then we simply multiply the value by the mapped value and then add it to the sum (s)
Return s.
For example, we first add the key value pair <1, 4>
When we encounter <1, 7>, we see that there already exists a mapping for the key <1>
So we look at the value to that key (4) and multply it by our current value (7) and add to the sum. Same thing happens when <5, 3> is originally added - nothing happens, but when we see that we can add <5, 1>, we multply 3 and 1 and add to the sum.
public boolean isBST(Node n) {
if (n == null) {
return true;
}
boolean checkRight = (n.right == null) ? true : (n.right.value > n.value) ? true : false;
boolean checkLeft = (n.left == null) ? true : (n.left.value < n.value) ? true : false;
return checkRight && checkLeft && isBST(n.left) && isBST(n.right);
}
First, it might be helpful to use string split here since it saves room.
Two tricky things are just going to be knowing how many days are in each month. secondly, we need to take into account leap years (the formula for which is annoying to remember).
It is a good idea to split up the code when writing this, and you will see that it is not so bad.
public int dayFromDate(String date) {
String[] info = date.split("-");//split the string up so we can retrieve data more easily
int d, m, y;
d = Integer.parseInt(info[2]);//parse this info
m = Integer.parseInt(info[1]);
y = Integer.parseInt(info[0]);
int output = 0;
for (int i = 1; i < m; i++ ) {//go through all of the months starting from january and add the number of days for each month into a sum
output += numDays(i, y);
}
return output + d;
}
public int numDays(int month, int year) {// given a month and a year, return how many days are in that month
int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
if (month == 1 && isLeapYear(year)) {// if we encounter a leapyear, and the month we check is february, return 29 instead of 28
return 29;
}
return days[month - 1];
}
public boolean isLeapYear(int year) {// check if a year is a leapyear
return (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0));
}
Good point.
Then basically, I'd arrange it in this way instead.
We are looking for local maxima in the array and then compare the distance between them.
for (int i = 0; i <bargraph.length; i++) {
if (bargraph[i-1] < bargraph[i] && bargraph[i] > bargraph[i+1]) {
//check this local max with the previous local max and find the water between them and add
}
}
I think this modification should work
- SK March 19, 2015I think the intuition is that you know that 2 peaks will either be the same, the first one will be bigger than the other or the second will be bigger than the first. Keep one variable for peak1, one variable for highestPeakSoFar (hpsf)
We will iterate through the bar graph, starting with peak1 = element 0. If we encounter a peak p that ends up being greater than or equal to peak1, we will calculate the amount of water sumOfWater += (Min(peak1, p) - element). Then, we set p as peak1 and repeat the process from there. If we don't encounter a higher peak, we simply set hpsf as the highest peak we've encountered so far that is smaller than peak1. This is because this smaller peak wouldn't affect the water unless it is the final peak.
Finally, if we can't find anymore high peaks, we do the calculation with hpsf,
sumOfWater += (Min(peak1, hpsf) - element)
We are guaranteed To be done with this in 2n operations, which runs in O(n)
It may seem like it's overcomplicating things at first, but the standard way of doing these kinds of problems involve the stack method as it gives a better range of possibilities if we want to expand the problem to take into account, for instance, order of ops, or even parenthetical expressions.
Your solution is definitely more simple, be more space efficient, and just as correct, don't get me wrong, but the stack method gives us more to discuss with a potential interviewer and serves as a good model to understand for a lot of problems similar to this (see checking balanced parentheses problem for example).
Hey anon, let's consider the following:
A2((AB3)2(C2D)4)5
First, we know that this is equivalent to:
A2((A1B3)2(C2D1)4)5, so let's work from this one for ease of the algorithm.
Stack: 1
We start out with this.
Now, we begin from the right. We will push a (1 * 5) onto the stack. We do this because we know that whatever is to the left of the 5, there will be 5 of it. We encounter a ")" which means that this multiple will affect everything within some parenthesis, so we won't pop it just yet.
Stack : 1/5
Next, we encounter a 4. We know that whatever is left of the 4 will be multiplied by 4, but also , since we have a 5 on top of the stack, multiplied by 5 because of the outside multiple.
Stack: 1/5/20
We encounter a ")" which means to continue since this multiple will apply to whatever is in the parenthesis.
Encounter a 1, so push (20 * 1) on the stack.
Stack: 1/5/20/20
Now, we encounter our first Element (D), and we know that there will be 20 Ds so far. So in our list of Elements, add 20 to D. Since we encountered an element, we can pop off the stack
Stack : 1/5/20
Encounter a 2, so push (2*20) on the stack.
Stack: 1/5/20/40
Now, we see we have Element C, so add 40 to C in the list and pop off the stack:
Stack : 1/5/20
Since we encounter an open parenthesis "(", we pop off the stack signaling that we are done with an encounter of some in parenthesis expression:
Stack : 1/5
Now, we begin on a new parenthesis set, which is succeeded by a "2":
Stack : 1/5/10
Push (3*10),
Stack : 1/5/10/30
Add 30 to B
Pop 30
Stack : 1/5/10
Push(1 * 10)
Stack : 1/5/10/10
Add 10 to A
Pop 10
Stack : 1/5/10
Encounter a "(", pop 10
Stack : 1/5
Encounter another "(", pop 5
Stack : 1
We see a 2, so push (2*1)
Stack : 1/2
Add 2 to A, pop off 2
Stack : 1
We are done.
I've considered this problem more today and I think it's even more simple than what I had originally explained.
We will keep one stack, call it s. We first begin by pushing a "1" onto s.
Now, we will start reading the string from the end to the beginning. If we encounter a number, we will multiply this number with the number currently on top of the stack and then push this product onto the stack. When we encounter a close parenthesis ")", we will copy whats on the stack and push on top of the stack. When we encounter an open parenthesis "(", we will pop whatever is on the stack. Finally, when we encounter an element, the number that is currently on top of the stack will be the number of atoms of that element is described by that specific portion of the string.
Pretty Straight forward:
public String modify(String orig) {
String[] toModify = orig.split(" ");
StringBuffer out = new StringBuffer();
for (int i = 0; i < toModify.length; i++) {
out.append( (stringIsOdd(toModify[i])) ? capitalize(toModify[i]) : reverse(toModify[i]) );
out.append(" ");
}
return out.toString();
}
public String capitalize(String s) {
return s.toUpperCase();
}
public String reverse(String s) {
StringBuffer out = new StringBuffer();
for (int i = 0; i < out.length(); i++) {
out.append(s.charAt(out.length() - i - 1));
}
return out.toString();
}
public boolean stringIsOdd(String s) {
return (s.length() % 2 == 1);
}
We know the head will have a null parent. Now that we have a head, we will know the 2nd level of the tree will be the nodes that have the head as a parent, so organize the tree by how those nodes are organized.
You can keep a queue- put 50 into it first, then search the list for nodes that attach to 50. add those to the queue. dequeue 50. search the list for nodes that attach to the nodes in the queue, add to the queue and dequeue the lists you found nodes for. continue this process until both the list and the queue are empty.
Some very loose pseudocode:
buildTree(list) {
Node head;
Queue treeQueue = ;// initializeQueue
for (info in list) {
head = node who's parent is null;
}
list.remove(head);
treeQueue.enqueue(head);
Node current;
while(list != empty) {
current = treeQueue.dequeue();
for (node in list) {
if (node's parent is current) {
enqueue(node);
if (node.isLeft) { current.left = node;} else { current.right = node}
}
}
}
return head;
}
For the first:
isSame(Node n) {
if (n == null) {
return true;
}
Node l = n.left;
Node r = n.right;
boolean a, b, c;
a = (l == null) ? true : (l.value == n.value) ? true : false;
b = (r == null) ? true : (r.value == n.value) ? true : false;
c = (l == null) ? true : (r.value == l.value) ? true : false;
return (a && b && c && isSame(l) && isSame(r));
}
We know that we will have encountered a sentence by the time we have reached a period in a string. So, what we can do is create a queue, enqueue all strings until a period is reached. Then we create a new queue and repeat the process. There should be one queue for each sentence. Finally, starting from the first queue until the last queue, dequeue and print, then start from the first queue again until the last queue- dequeue and print. Continue this process until all queues are empty
- Skor March 17, 2015Usually with this, we'd use the shunting yard algorithm to evaluate this with order of operations- convert to RPN then use 2 stacks. Since order of ops is being ignored here, this makes our lives a lot easier.
Keep one stack for numbers and another for operators. Start from the end of the string, pushing numbers on top of the number stack and operators on top of the operator stack.
Now that every number is pushed on the number stack and every operator is pushed on the operator stack we begin.
With whatever operator is on top of the operator stack, pop the top number, use the operator on the popped number and the currently top of the number stack number, then place this resulting number on top of the number stack. Pop the operator from the operator stack.
Repeat this process until there is one number on the number stack and no operators on the operator stack. If this isn't the result, then the string is invalid.
Assume you have k processors/cores.
We will now create k queues of Messages, one for each processor. The idea is now that each core will process Messages in its respective queue.
Now, when publisher sends a message to the broker, the broker will put the message in the queue with the least number of Messages currently in it, which would be in O(k) time. If k is a small number, like 4 or 8, this would be trivial. However to scale up with many different processors, you could use a min heap to keep track of the queues that have the least number of messages.
If we assume that the MessageBroker is what contains the mapping between publisher and subscriber, then simply keep a hashtable that holds this mapping. Because processors would only read the hashtable for mappings, without changing it, then this would be threadsafe and there would be no need for mutex in the general case. However, if subscribers needs to be updated by the broker, processing can be stalled to do updates with the mutex.
If we want to scale up, the hashtable could be split, so that updates in one partition of the hashtable wouldn't affect performance of reading other partitions.
The idea here is that given some node N, if it is a left child of node M, we want to find the fixed value of M, then add this value to N since M will be bigger than N.
Then, we want to find the fixed value of N by adding the sum of every right child of N.
public int fixBST(Node current, int parentValue) {
if (current == null) {
return 0;
}
current.value += fixBST(current.right, 0) + parentValue;
fixBST(current.left, current.value);
}
Assume that we start out with 2 people in A, 3 people in B, and 5 people in C. We are currently maintaining the ideal percentage. Now, if we decide to add a person to a room, there is no way we can maintain this ideal percentage because we will have 11 people, so we can't get the exact percentages since you can't put a fraction of a person into a room. The best place to add a person would be in the room with the highest percentage since this would lead to the smallest difference of ideal percentages over all of the rooms.
So we know that in the case that we have an ideal percentage, we should add a person to the room with the highest ideal percentage (in this case, room C).
Now, we can see that the percentages of the rooms will be lower for A and B, but higher for C. Since we can't take people out of rooms, we can only add people. Adding to C would be unwise, since it is already over the ideal percentage, so we will look at A and B. whichever has a greater difference that is lower that the average, we will add a person to the room.
We continue this heuristic to get the best case percentages at any given time...
With this heuristic, we add in this order to each room:
CBACBCACBC
If you go through it, you will see how stable the percentages are throughout
You can keep a secondary 2D array with each element keeping 2 boolean values P and A.
Pass through the perimeter elements of the continent and check to see if these values have direct access to P or A. Then Pass through again checking to see if they have direct access to P or A, again through neighbors with smaller heights.
Now that we have checked the outer perimeter, we will check the first inner perimeter twice again- Check all outward neighbors of elements- if any of these outward elements are smaller in height, OR the current element's A and P boolean values with that of the neighbors.
Continue this until you get to the middle element.
Finally, pass through all of the elements and return those that have both boolean values set to true.
Assuming rectangle with height of m and width of n,
Runtime: 3m*n
Space: m*n
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 ...
- SK April 01, 2015