Engineer I Interview Questions

I did 2 pass on input string.

I also did two passes on the input string. I created the following helper classes: Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator). InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1". Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it. One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle.

I used a different approach by making use of a queue: - parse the string, and push in the operands and operators onto a queue - evaluate the queue My general approach was this: - read in lhs, operator and rhs - if operator is "+" or "-", enqueue lhs and operator > if string is empty, we are done parsing --> enqueue rhs > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further - else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate. (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug) // Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression. string getCurr(string& str); int eval(string str) { if (str.empty()) return -1; // operand / operator queue std::queue q; // construct it char buf[5]; while (!str.empty()) { string lhs = getCurr(str), oper = getCurr(str), rhs = getCurr(str); // evaluate directly if (oper == "*") { int res = atoi(lhs.c_str()) * atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } // evaluate directly else if (oper == "/") { int res = atoi(lhs.c_str()) / atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } else // "+" or "-" { q.push(lhs); q.push(oper); // finished parsing the expression if (str.empty()) q.push(rhs); else // restore the string str = rhs + str; } } // evaluate the queue int res, rhs; string oper; res = atoi(q.front().c_str()); q.pop(); while (!q.empty()) { oper = q.front(); q.pop(); rhs = atoi(q.front().c_str()); q.pop(); if (oper == "+") res += rhs; else // "-" res -= rhs; } return res; } string getCurr(string& str) { if (str.empty()) return ""; string curr(""); // operator if (str[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/') { curr += str[0]; str = str.substr(1); } else // a number { do { curr += str[0]; str = str.substr(1); } while (!str.empty() && str[0] >= '0' && str[0] <= '9'); } return curr; }

N^2 and can be improved to n logn using binary serach.

or could be linear time if you're allowed to use a hash table

I'm pretty sure hash table is the answer they were looking for...

The general idea is to keep a pointer n elements back from the current element as you're traversing the linked list looking for the last node. There are some edge cases when coding it. O(n) time, O(1) space.

How about? Traverse once find length. Then find n-kth element. Still linear complexity in time and 0 addl space

That works too. The first way you only traverse once though.

This is a simple bit manipulation problem. If you study before your interviews, this is a common area to study.

void count_Bits(int inp){ int count = 0; for (int y = inp; y >=1;y = y /2 ){ count++; } cout<< "number of bits : " << count<< endl; }

If you take a simple log base 2 of the integer, that should give you the number of bits, right?

Add up all number in the array and find the difference between the sum of 1 to 100.

Another way since the interviewer asked for as my solutions as possible 1. Create another array of 100 elements and initialize to 0 2. Traverse through the first array and mark the corresponding spot in the second array 3. Now traverse through the second array and find the spot that is still marked as 0 - that is your missing element Note: You'll have to do a subtract by 1 since the numbers are from 1-100 and your array count will be from 0 to 99.

sum of 1 to 100 can be got by using Gauss's formula n(n+1)/2. If we subtract the sum of all numbers in the array with the result we got from formula, it's the answer.

Tried brute forcing it, O(n^2) too bad. Did it using HashTables.

Here is an O(N) solution with HashMap. By the way, I think the fail case should be -1 instead of zero since zero is a valid possibility. public static int findDuplicate3Chars(String s) { HashMap map = new HashMap(); StringBuilder b = new StringBuilder(); int inputLength = s.length() - 3; for (int i = 0; i < inputLength; i++) { for (int j = 0; j < 3; j++) { b.append(s.charAt(i + j)); } String key = b.toString(); if (map.containsKey(key)) { return map.get(key); } map.put(key, i); b.setLength(0); } return -1; }

Related previous job experience where a lot of things had to be juggled at once.

pourquoi vous ne traduisez en français?