axecapone
BAN USER- 9 Answers Careercup related question
Hey folks
- axecapone July 20, 2012
I am looking at interviewing with companies like Google and Facebook which are considered very competitive. Careercup has been very resourceful in helping me look at these problems.
When I see problems on Careercup questions, I cant get an idea if its phone interview or in person. Most problems are tagged as "phone interview". Sometimes the problem is super hard and is called "Phone interview" while some really simple ones are "in person" interview.
So my question is what kind of questions can I expect in "in person" interview? Some example questions would help me get a better understanding.| Flag | PURGE
@Zasa1010
First of all, a data structure that hogs 2GB of memory IS unreasonable in any scaling application. 2GB for one data structure is ridiculous. Secondly oxford has about 300k words. So requirement is 4GB. Thirdly, in real life applications like Facebook, words are not limited to just English. There are other things like usernames which can themselves go into the millions.
So in short, this storing everything in memory wont work. Even if its just english dictionary, I am sure the interviewer will not be happy with such a program.
Much simpler Java solution
public static boolean isInterleaved(String str1, String str2, String strI) {
if(str1 == null || str2 == null || strI == null)
return false;
if(strI.length() != str1.length() + str2.length())
return false;
if( strI.length() == 0 &&
str1.length() == 0 &&
str2.length() == 0)
return true;
if(str1.length() != 0 && str1.charAt(0) == strI.charAt(0))
return isInterleaved(str1.substring(1), str2, strI.substring(1));
else if(str2.length() != 0 && str2.charAt(0) == strI.charAt(0))
return isInterleaved(str1, str2.substring(1), strI.substring(1));
else
return false;
}
@eugene, @Gayle: Thanks for the feedback. Will sure keep this in mind.
@Gayle: I have watched some of your videos on youtube. Great stuff!! I kind of get the perspective of the interviewer which makes it easier as an interviewee. Your pointers and content seems to be more focused towards new grads (pardon me if I am wrong but thats the only content I have watched so far). Is the interview process any different for people with little work experience (in my case about 2 years)?
In a singleton pattern, the class always has a reference (static) to the object. Extend this to 5 object references and you have a Fiveton. I presume that the class using the singleton object must know which object to use.
A clarification: So when an object is GCed, you decrement count, create new object but not increment count again??
In this pattern, the object does not get GCed unless you explicitly release the reference and create a new object simultaneously. Additionally if the object is getting GCed and constructed, then make the references 'volatile' to prevent any concurrency issues.
@Anonymous
Firstly what is the tree made of? X values, Y values, f(x,y)?Without all these details, I don't see how red black trees solve this problem.
The fundamental question is "Can we atleast find the number of pairs in less than O(n^2)?" May be its not possible in which case no datastructure can help. Without an answer to this question and without sufficient details on your data structure, you can understand why I am saying your answer is vague.
Here's my analysis.
For complexity less than n^2, it means that we don't check every pair of points which means there needs to be a way to order along both x and y simultaneously. This is not possible because for each point, Xi and Yi are independently chosen. So sorting on one axis does not guarantee any particular order on the other axis and sorting on both axis is not possible.
Makes sense? If not, whats wrong?
Matrix is not a good idea because if I give you 100 nodes and 99 resistance in series, you get a 100x100 matrix with a lot of zeros.
I don't know how to explain in few words without writing code but one way is "topological sort". At each node, have a variable named oneByResistance
oneByResistance = 1/(1/(oneByResistanceOfParent) + edgeResistance) (For root oneByResistanceOfParent should not be added).
Process the whole graph and final resistance is 1/(OneByResistance) of last node processed. Hope this helps
Accuracy of the interview type is debatable (Many ask online contests and class assignments here) but I guess if there is no correlation, it does not matter.
I have another question. These days there seems to be a heavy emphasis on "writing clean code on white board". What is the expectation here? Is there any room for error?
A tree data structure is such that a node can have only 1 parents, all nodes are connected and no cycles [Wiki is my source].
Leet, your first step is correct to find the root. Then you can simply start with the root and find all its children, connect them to root and also push them to queue. As long as queue is not empty, remove first element from queue, add all its children and push its children to the queue. In the end you will have a tree. [Basically this is kind of reverse BFS]
Why? Since all nodes are connected, you will find all nodes as you traverse the above algorithm. Since all nodes have only one parent, they are pushed into the queue only once and processed only once.
Given below is the code. Basically, imagine each bit position to be a periodic impulse train of periods 2, 4, 8, 16, 32 .... So the period of the impulse train at 8th bit is 2^i. A 1 appears in the train only when atleast 50% of a period is complete. So the number of ones 25% completed period is 0 but no of ones in a 75% period is 0.25*(no of ones in full period). With that in mind, given below is the solution
package org.axecapone.programming;
public class NoOfOnes {
private int val = 0;
public NoOfOnes(int i) {
val = i;
}
public int countOnes() {
int copy = val + 1;
int divisor = 2;
int count = 0;
while(divisor <= copy) {
count += (copy/divisor)*(divisor>>1);
if(copy%(float)divisor - (divisor>>1) > 0)
count += ((copy%(float)divisor) - (divisor>>1));
divisor = divisor<<1;
}
if(copy%(float)divisor - (divisor>>1) > 0)
count += ((copy%(float)divisor) - (divisor>>1));
return count;
}
public static void main(String[] args) {
NoOfOnes test = new NoOfOnes(7);
System.out.println(test.countOnes());
}
}
Create a prefix tree for every number that is added by using each digit as a node.
1. To insert, just move along the tree if the digits exist or create and move on. Do this 4 times for each number O(1)
2. Delete: Move down the tree 4 times using the digits and kill the root node (1)
3. Search: Move down the tree 4 times. If node missing, return -1 O(1)
4. Get any: Move down the tree 4 times choosing child nodes at random. Report the number O(1)
My solution
public class sampleSort123 {
private static headNode = null;
private static tailNode = null;
// ASSUMPTION: headNode and tailNode are given to us.
public static moveToHead(Node node) {
// Disconnect the node from the doubly linked list
Node leftNode = node.getLeftNode();
Node rightNode = node.getRightNode();
leftNode.setRightNode(rightNode);
rightNode.setLeftNode(leftNode);
headNode.setLeftNode(node);
headNode = node;
return;
}
public static moveToTail(Node node) {
// Let the address be of Long type
// Disconnect the node from the doubly linked list
Node leftNode = node.getLeftNode();
Node rightNode = node.getRightNode();
leftNode.setRightNode(rightNode);
rightNode.setLeftNode(leftNode);
tailNode.setRightNode(node);
tailNode = node;
return;
}
private static sort123Array() {
Node currentNode = headNode;
while(currentNode.getRightNode != null) {
if(currentNode.getValue() == 1)
moveToHead(currentNode);
else if(currentNode.getValue() == 3)
moveToTail(currentNode);
}
}
}
Its a binary tree not a binary "search" tree. It does not matter what and how you insert. All that binary tree guarantees is that every parent has two children. So inserting duplicates on left or right does not matter.
- axecapone November 03, 2012