nunbit romance
BAN USER- 9 Answers How much does a masters degree in CS worth in landing a software engineer job in Sillicon Valley?
I have a BCS, but can't seem to land an offer in major software companies. I really studied hard to prepare for onsite interviews. Somehow I get most of questions right, but most companies seem to be looking for something more in my academics. I was able to land offers at small consulting companies and business application development firms, but not major software companies (you probably know which ones I am referring to). Anyways I am now thinking of pursuing a masters degree in CS at one of the top universities in US. For those of you working at major software companies, could you provide some insights? Thank you.
- nunbit romance July 19, 2007| Flag | PURGE
I sort of agree. But then, I have seen a couple of Phd students getting hired by Google. I think it depends on the candidate's programming aptitude. Having a PhD alone does not qualify you for getting hired. I think consistently improving your programming skill is the key.
Also, in general, a lot of PhD students seem to get PhD's because they prefer to research or stay in academia. Thus, companies seem surprised when they see a PhD candidate for a software development job. I am not sure if this is good or bad from the candidate's perspective.
class Singleton {
public: static Singleton *getInstance();
Singleton();
~Singleton();
Singleton(Singleton &another);
private: static Singleton *instance;
};
Singleton *Singleton::instance = 0;
Singleton *Singleton::getInstance() {
//here: obtain_lock for mutual exclusion.
if (!instance) {
instance = new Singleton();
return instance;
}
else
return instance;
}
the problem is that in multi-threaded environment, if two threads fight for a singleton object, we may have two threads with different data values. the singleton object itself exists as one, but the values within the object may be manipulated by the two threads by having its local copy and manupulation, etc...
Thus, a mutex problem. this can be solved by having lock mechnism at the location shown above.
i am not sure about this one too. here is another pigeonhole sorting algorithm.
iterate through the entire array and check the min and maximum. this take O(n). now, instead of count sorting each element into individual buckets. have buckets of certain ranges.
Now, say you have buckets such that
b[0]: 0-100000
b[1]: 100001-200000
b[2]: 200001-300000
....
b[9]: top of range
you can say that top buckets + x items in some middle bucket add to 1000000 items and they are the top 1 million numbers.
i guess my point is that eventhough the range might be unpredictable, if you read it, it does not hurt your O(n) algorithm.
not operator would not work in this case.
for example,
A=00000000
~A = 11111111
where swap(A) should return 00000000
i think UNIX/linux has a command called "comm" which finds common lines in two files.
BTW, I like the hashtable approach better than the BST approach. it is more efficient than BST. is there a reason why BST is favored?
Hi. I assumed that my hash_map would compute hash value given the line as a string. hmm... I think the runtime O(n) still does not change since "n" refers to the number of lines.
I think from the question itself, it is okay to assume that the runtime depends on the number of lines and not anything else (like number of words / characters).
in order to check if a tree is BST, one must do an in-order traversal and check if the elements are in increasing order.
suppose the tree nodes contain int as values.
bool isBST(node *root) {
if (!root) return true; //if no tree, it is BST, or false depending on your def.
vector<int> v;
traverseInorder(root, v);
int i=0;
while (i+1 < v.size()) {
if ((int)v.get(i+1) > (int)v.get(i)) return false;
}
return true;
}
//recursive
void traverseInorder(node *root, vector<int> &v) {
if (!root) return;
else {
traverseInorder(root->left);
v.insert(root->value);
traverseInorder(root->right);
}
}
//or iterative
void traverseInorder(node *root, vector<int> &v) {
if (!root) return;
stack<node *> s;
s.push(root);
while(!s.empty()) {
node *cur = s.pop();
if (cur->left) s.push(cur->left);
v.insert(cur->value);
if (cur->right) s.push(cur->right);
}
}
I think the above solution will work as well, but this solution is cleaner and it gives the option to stay away from recursion. At an interview, I would suggest this one first and then if the interviewer wants something else, i would give the solution above.
The recursive method is possible, but for me, it is hard to follow.
Iterative one is easy.
void reverse(node **head) {
if (!*head) return;
node *cur = *head;
node *prev = NULL;
node *next = NULL;
while (cur) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head = prev;
return;
}
I would use the following algorithm (in pseudocode):
use a hashmap to store <hashkey, linenum>.
hashmap<string, int> hash_map;
int curLineNum = 0;
while (!end of line) {
line = readline(curLineNum);
val = hash_map.getValue(line);
if (val) {
compare (line, readline(val));
if equal {found duplicate line!}
}
else hash_map.insert(line, curLineNum);
curLineNum++;
}
return (!found);
}
Explanation: the algorithim is very simple. as you encounter a new line,
check if the hashmap already has a value at that key slot. if it does, then
we will look up the line at that line number, which is stored as the value in
the hashmap.
The key idea is to store line number instead of the actual line because we can retrieve the line later when we become suspicious the lines might be the same.
This is O(n) algorithm assuming that the hashmap implementation allows O(1) retrieval and n represents the number of lines.
I am guessing the special char '!' is used as a pivot for reversing the words before and after it. i.e. ABCD E!FG HI! => E DCBA!IH GF!
This is similar to the conventional reverseWord problem.
#define SPECIAL_CHAR '!'
void reverseWords(char str[]) {
if (!str) return;
int cur=0;
int start=0;
while (str[cur]) {
if (str[cur]==SPECIAL_CHAR) {
reverse(str, start, cur-1);
start=cur+1;
}
cur++;
}
start=cur=0;
while (str[cur]) {
if (str[cur]==SPECIAL_CHAR || str[cur]==' ') {
reverse(str, start, cur-1);
start=cur+1;
}
cur++;
}
return;
}
void reverse(char *str, int beg, int end) {
while (beg < end) {
char temp = str[beg];
str[beg] = str[end];
str[end] = temp;
beg++; end--;
}
return;
}
i have a couple of test cases in mind but what does the question mean by "handle special chars"? can you give an example of special char?
Could you clarify the question a bit more? Do the number of black pixels and white pixels have to be equal? Also, are subsquared filled with one color only?
- nunbit romance June 11, 2007?
- nunbit romance June 10, 2007Hi Gayle :)
For the first part, you are right. my solution is incorrect. One would have to keep the incoming data in sorted order.
About the second part, I was ranting about the fact that the question is very vague. But again, you are right. in an interview, I would ask what form of input I am getting rather than complain that the question is too vague :)
yes. depends on how you difine 'duplicate' documents. note 'similar' not equals 'duplicate'.
- nunbit romance June 09, 2007what is the point of this question? i would be really frustrated if i get this kind of question in an interview.
there are many ways of solving this. like the previous answer, initialize the 100 variables to 0 and find 100 distances to stars.
you don't have to use a heap or whatever. just keep the max distance in your collection of 100 stars and if the new star is closer than your max, the new star is now replaces furthest one in your collection.
Now, in order to get 100 closest stars, start from the smallest range and increase the range searching for stars until 100 of them are found. But, this is stupid because we are scanning closest to furthest until 100 closest are found. this does not involve any data structure or CS knowledge. So, reminding ourselves that this is a programming interview question, we have to make up some crap and get to the next question.
moscovita: i figured out where the number "10" is coming from.
look at: http[colon]//www[dot]ryanbyrd[dot]net/techramble/?p=16
this says the optimal number is 10. but this is simply wrong.
if you look at the equation he is using:
f(x) = 100/x + (x-1)
the variable x denotes the size of interval, not the number of trials.
the answer 10 is interval size 10, which leads to 19 trials which is worse than the arithmatic series answer 14.
thus, your interview probably did not understand the answer and picked up that magic number somewhere off the web.
moscovita: the correct answer is 14. why would the interviewer say 10? i don't nderstand why he/she would do that. that shows that the interviewer simply did not understand even his own question.
it would be funny if the interviewer tried to verify his own claim and go "oops! i meant 14. i am glad i am interviewing you and not the other way around."
for god's sakes, buy the book! it's only 20 something bucks and it is definitely worth the money.
- nunbit romance June 08, 2007node *find(node *root, int val) {
if (!root) return NULL;
if (root->val == val) return root;
if (val < root->val) return find(root->left);
else return find(root->right);
}
I think the primary reason for making a choice between inheritance and interface is to make the distinction of having default behavior of the object.
In inheritance, the child class extends the parent class's behavior as the default and this is the case for all other subclasses of that parent class.
In interface, you are simply defining a common set of operations that may be entirely different depending on the implementation.
token string match. O(mn) so is this the way to do this?
- nunbit romance April 04, 2007look at PIE :)
- nunbit romance April 03, 2007int bitcount(unsigned int x)
{
int num = 0;
while (x)
{
if (x & 1 == 1) or x = x&(x-1);
{ num++; num++;
}
x = x>>1;
}
return num;
}
that sounds about right.
- nunbit romance March 29, 2007#include "queue.h"
typedef struct nodeT
{
struct nodeT *leftChild;
struct nodeT *rightChild;
int val;
} node;
node *bfs(node *root, int targetVal)
{
if (!root) return null;
Queue q<node *>;
q.enqueue(&root);
while (!q.isEmpty())
{
node *cur = q.dequeue();
if (cur->val == targetVal) return cur;
else
{ if (cur->leftChild)
queue.add(&(cur->leftChild));
if (cur->rightChild)
queue.add(&(cur->rightChild));
}
}
return null;
}
pointer is a variable type that stores address in memory.
int main()
{
node *head = new node(1);
node *second = new node(2);
node *tail = new node(3);
head->next = second;
second->next = tail;
}
#include "hashtable.h"
node *common(node *head1, node *head2)
{
if (!head1 || !head2)
return null;
node *cur1 = head1;
node *cur2 = head2;
hashtable tbl<int>; //assuming i have a hash table or map
while (cur1)
{
tbl.add(&cur1, 1);
cur1 = cur1->next;
}
while (cur2)
{
int val = 0;
val = tbl.get(&cur2);
if (val == 1) return cur2;
else cur2=cur2->next;
}
return null;
}
I would claim that this has O(max(m,n)) runtime assuming the two lists have m and n elements respectively.
hash table insertion takes O(m) time and second iteration takes O(n) time. Hence, O(m) + O(n) <= O(max(m,n)).
this questions seems really ambiguous. what does the textbox do? display an ad on the msn page?
- nunbit romance November 22, 2007