c Interview Questions
interview questions shared by candidates
c Interview Questions
An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element. 127 Answers100 1. calculate the sum of elements in array say SUM 2. sum of numbers 1 to 100 is(n* (n+1))/2 = 5050 when n==100 3. missing element is (5050-SUM) 100 Show More Responses The parameters of the question do not allow you to determine what element is missing. Either more information should be supplied, or all answers are equally correct. How could an array size of 99 elements contain 1 - 100? Should either be integers 1-99 or 2-100 , in either case there is no missing element. All indices are accounted for. Sum them and then subtract them from 5050. In general, if an array of size n - 1 elements has unique elements from 1 to n, then the missing element can be found by subtracting the sum of the elements in the array from sum(1 ... n) = n * (n + 1) / 2. Alternately, one could use a boolean array of length n with all values set to false and then for each value, set array[val - 1] to true. To find the missing value, scan through the array and find the index which is set to false. Return index + 1. This requires O(n) memory and two passes over an O(n) array (instead of constant memory and one pass), but has the advantage of actually allowing you to verify whether or not the input was well formed. Admittedly, this question is poorly posed; however, the answer they are looking for refers to the syntax/nomenclature of some (not all) programming languages to index arrays starting at “0.” As such the 1-100 stored values would be in entries 0-99 of the array. Read the question. Here are the steps to solve it: 1) find the sum of integers 1 to 100 2) subtract the sum of the 99 members of your set 3) the result is your missing element! Very satisfying! Sort array. While loop with an index variable with condition of next element being 1 greater than previous element. When loop breaks, return the value of the index. Doing the expected sum and subtracting the actual gives the run time of O(2n), however a bucket sort will almost always do it in less time (somewhere between O(n) and O(2n)): 1. create a 101-int (or boolean) array (to have a 100-index) 2. traverse original and for each int, assign value in bucket array to 1 or true. 3.After first traversal, traverse created array starting at one, and when value is false, print it. 100 100 coz in array it initial value starts frm 0 to 100. or else 4 further clarification u can study array chapter in c or c++ 100 Show More Responses The question: "An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element." The information states that the integer count is 1 to 100. I take this to be inclusive of all elements in the array so that the missing inters would be subjective to their arrangement or random. In other words, I do not have enough information to say which one. 1 I need more information. 1. Are the integers unique in this array? 2. Do I have enough information to find the sum of the integers in the array (or some aggregation)? If sum is available, then, the answer is 5050-sum{integers}. Bucket Sort works and summation works. I think both are good, practical and clever solutions. I think sorting the array then searching may be unnecessary computation. Another interesting method which may be faster. SIMD computers may do this particularly quickly: Do a bitwise operation on all the elements: Result = Array[0] xor Array[1] xor ... Array[98] xor 1 xor 2 xor ... xor 100 Result = Missing number. Explanation: When you xor 2 identical numbers your result = 0. For example, 5 xor 5 -> 101 xor 101 = 000. (5 in decimal is 101 in binary). Knowing that "xoring" 2 identical numbers results in zero is useful. Now we apply this useful info to the problem. Array is Identical to a list of 1,2,3,...,100 except for one number. In other words 1,2,3,...,100 duplicates all of array's elements and adds one extra element that is missing in Array. Therefore, we now have 2 instances of each element in the Array in addition to one extra element in 1,2,3,...,100. We can see when you xor two duplicate numbers you get zero. Because we have pairs for all numbers in Array and one extra number we are essentially "xoring" the missing number with zero. When we xor the missing number with zero we get the missing number. (For example, 6 xor 0 -> 110 xor 000 = 110) The question states that one (not two or three or n) element ("value") from 1 to 100 is missing. There are 99 elements ("values") in the array. The question implies that the data is well-formed because it states that only element is missing. It doesn't ask you to find the missing value(s), but the one (singular) missing element. With the problem constrained, the solution falls out. Subtracting from 5050 is an elegant solution, but not obvious as to why it works. The array of booleans is more obvious, but doesn't scale well. I agree with one of the answers in this thread...5050-sum(elements) = missing item. Other approach that crossed my mind is something similar to binary search. Check the index of 50th element: if A(50) == 50, the missing element > 50, else if A(50) > 50, missing element <50. Do this iteratively. The number of comparisons would be log 100 = 7. Add 1-100 to a hash of 100 elements. Then compare each element with the hash.. Answer in o(n) Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses Show More Responses One or more comments have been removed. |
Data Scientist Intern at LinkedIn was asked...
Find the second largest element in a Binary Search Tree 16 Answersfind the right most element. If this is a right node with no children, return its parent. if this is not, return the largest element of its left child. One addition is the situation where the tree has no right branch (root is largest). In this special case, it does not have a parent. So it's better to keep track of parent and current pointers, if different, the original method by the candidate works well, if the same (which means the root situation), find the largest of its left branch. if (root == null || (!root.hasRightChild() ) { return null;} else return findSecondGreatest(root, root.getValue()); value findSecondGreatest(Node curr, value oldValue) { if(curr.hasRightChild()) { return (findSecondGreatest( curr.getRightChild(), curr.value)); } else return oldValue; } Show More Responses The above answer is also wrong; Node findSceondLargest(Node root) { // If tree is null or is single node only, return null (no second largest) if (root==null || (root.left==null && root.right==null)) return null; Node parent = null, child = root; // find the right most child while (child.right!=null) { parent = child; child = child.right; } // if the right most child has no left child, then it's parent is second largest if (child.left==null) return parent; // otherwise, return left child's rightmost child as second largest child = child.left; while (child.right!=null) child = child.right; return child; } Soln by "mindpower" works. Thank you. I am trying to solve a similar problem Find the 2nd nearest high(in in-order traversal) value for a given node Eg: Given nums: 12 7 14 3, construct a BST. If the given value is: 7 then we should return 14 (in the sort order: 3, 7, 12, 14) if the given value is: 3 then we should return 12 (in the sort order: 3, 7, 12, 14) Generic solution in C# for any k. Notice that this example can be easily changed to find the k-th smallest node by doing a depth-first recursion on root.Left first, and then a tail recursion on root.Right. public Node GetKthLargest(int k) { return GetKthLargest(ref k, this.Root); } Node GetKthLargest(ref int k, Node root) { if (root == null || k < 1) return null; var node = GetKthLargest(ref k, root.Right); if (node != null) return node; if (--k == 0) return root; return GetKthLargest(ref k, root.Left); } recursion is not needed. SecondLargest(Node root, Node secondLarge) { if(root.right==null) return root.left; Node secondLargest = root; while(secondLargest.right.right==null) secondLargest=secondLargest.right; return secondLargest; } int getmax(node *root) { if(root->right == NULL) { return root->d; } return getmax(root->right); } int secondmax(node *root) { if(root == NULL) { return -1; } if(root->right == NULL && root->left != NULL) { return getmax(root->left); } if(root->right != NULL) { if(root->right->right == NULL && root->right->left == NULL) { return root->d; } } return secondmax(root->right); } In-order traverse the tree. The second last element in the array in the answer. In Python: def find_second_largest_bst_element(root, parent=None): if parent is None: # BST root if root.right is None: # no right subtree if root.left is not None: # if a left subtree exists... return root.left else: # root is the only element of the BST return False else: if root.right is None: # right-most element if root.left is not None: # left subtree exists return root.left else: # leaf return parent else: # check right subtree find_second_largest_bst_element(root.right, root) find_second_largest_bst_element(root) For kth smallest, descend the left subtree first. class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def findKthLargest(root, k): global count if root is None: return findKthLargest(root.right, k) count += 1 if count == k: print root.value return findKthLargest(root.left, k) count = 0 r = Node(10, Node(5, Node(2), Node(7)), Node(30, Node(22), Node(32))) findKthLargest(r, 3) // solution in java // main routine Node findSecondMax(Node root) { if(root == null || (root.left == null && root.right == null) return null; else { Node max = findMax(root); return (max.parent == null) ? findMax(max.left) : max.parent; } } //helper routine, recursive implementation.... can also be done non-recursively Node findMax(Node root) { return (root.right == null) ? root : findMax(root.right); } Show More Responses Find the largest number in the binary tree and delete it. And again find the largest number. Short and fast. Reverse in-order traversal of the BST, keeping a count of # of visited nodes. This methods works great to return the kth largest element in a BST. mindpower's solution looks right One or more comments have been removed. |
Senior Software Engineer at Google was asked...
Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. 8 AnswersO(size of array) time & space: First, realize that saying the element should be the product of all other numbers is like saying it is the product of all the numbers to the left, times the product of all the numbers to the right. This is the main idea. Call the original array A, with n elements. Index it with C notation, i.e. from A[0] to A[n - 1]. Create a new array B, also with n elements (can be uninitialized). Then, do this: Accumulator = 1 For i = 0 to n - 2: Accumulator *= A[i] B[i + 1] = Accumulator Accumulator = 1 For i = n - 1 down to 1: Accumulator *= A[i] B[i - 1] *= Accumulator Replace A with B It traverses A twice and executes 2n multiplicates, hence O(n) time It creates an array B with the same size as A, hence O(n) temporary space # A Python solution (requires Python 2.5 or higher): def mult(arr, num): return reduce(lambda x,y: x*y if y!=num else x, arr) arr = [mult(arr,i) for i in arr] # O(n^2) time, O(n) space Create two more arrays. One array contains the products of the elements going upward. That is, B[0] = A[0], B[1] = A[0] * A[1], B[2] = B[1] * A[2], and so on. The other array contains the products of the elements going down. That is, C[n] = A[n], C[n-1] = A[n] * A[n-1], and so on. Now A[i] is simply B[i-1] * C[i+1]. Show More Responses def without(numbers): lognums = [math.log10(n) for n in numbers] sumlogs = sum(lognums) return [math.pow(10, sumlogs-l) for l in lognums] Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1) #include #define NUM 10 int main() { int i, j = 0; long int val = 1; long A[NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Store results in this so results do not interfere with multiplications long prod[NUM]; while(j < NUM) { for(i = 0; i < NUM; i++) { if(j != i) { val *= A[i]; } } prod[j] = val; i = 0; val = 1; j++; } for(i = 0; i < NUM; i++) printf("prod[%d]=%d\n", i, prod[i]); return 0; } void fill_array ( int* array, size ) { int i; int t1,t2; t1 = array[0]; array[0] = prod(1, size, array ); for(i = 1; i < size; i++){ t2 = array[i]; array[i] = prod(i, array.size(), array)*t1; t1 *= t2; } int prod(start, end, array){ int i; int val(1); for(i = start; i < end; i++ ) val *= array[i]; return val; } One or more comments have been removed. |
AT&T Sales Representative at AT&T was asked...
How do you make people choose a product they don't want. 6 AnswersMake them feel a sense of loss if they don't have the product! Highlight the must-have features. First of all I will build trust and communicate with his human basic needs I will explore his feelings and wishes; what he like and what he doesn't Then I concentrate on the benifits and advantages he may got with the new products Show More Responses Really? You don't. Understand their pain, their needs, their likely use cases, then sell them what they do need. In the long run, matching the solution to their needs is aligned with their wants and will yield a happier, more loyal, and better relationship with the brand. Xfzxffv C,c |
IT Developer at FDM Group was asked...
How many unique handshakes if each person in a group of 10 give handshakes out to each and every other individual. (a) 100 (b) 50 (c) 45 (d) 20 (e) 10 5 Answers45. Imagine it as a polygon of side 10. Or draw out triangle, square, pentagon, and see the pattern yourself, if you don't know the algorithm. true, or 9+8+7+...+2+1 Or just do: (10 Combination 2) = 10!/(2!8!) = 45 Show More Responses n(n+1)/2 Where n =9 Answer: 45 One or more comments have been removed. |
Product Manager at Google was asked...
You notice that adwords revenue for a certain word has dropped in Italy for the last 30 days. How do you go about determining why that has happened? 4 AnswersThis is a test to see how you think on your feet. Adword Revenue : No. of impressions * Click Thru Rate * Cost Per Click Anyone of the three parameters could decline to have an overall reduction in revenue. No. of Impressions could go down if a. The internet usage has fallen for some socio-culturaal reasons in Italy b. The usage of Google search has reduced because of may be some competitor applicaton launch or some major marketing promotion activities c. Some major technical issues has come up may be in the Google servers which is resulting in higher latency in Google Search applications resulting in reduced usage Click Thru Rate might have gone down 1 Major shift is usage clusters Keywords used have changed resulting in changed search behavior where in people are less prone to click thru. 2 Some technical issues like adds not displayed properly Same major flaw in random add picking might have got introduced 3. Some recent layout change has been there and peope are yet to get accustomed with the changed layout Reduced CPC: 1. People are spending less on Adwords and hence bidding less 2 Due to the keyword change, the new cluster CPC is much lesser. 1. Determine the amount of decrease in month over month percentages, and make sure this isn't a trend. 2. Assuming we've seen similar decreases in conversions and clicks, 30 days is a month's time. Let's say this is in August, when the entire country uses the majority of their average of 42 vacation days per year. That's a factor. 3. Given you've said decreases in revenue and assuming all click and conversion data remained the same month over month, we may look for broken dynamic revenue variable conversion codes on the page source. Was there a site update? Show More Responses One or more comments have been removed. |
Q2: A pnp transistor with its base connected to a voltage source, the V source is connected to a +10V source. The emitter of the transistor is connected to a resistance, and then to the same +10V source. The collector side is connected to a capacitor, which is not charged at t=0-. Given the graph of Vsource = 10 V stepping up at t = 0 to further, draw the graph of Vout. Vout is between the point of collector and capacitor. 3 AnswersANS: Vout should be constantly -10V until t=0, and will hit V=0 V linearly from V=-10 V after t=0. Hi, Can you explain why it linearly increases? Are you assuming that Collector is tied to -10V? The pnp transistor is completely cutoff for the given biasing. The only way the capacitor is going to charge is through leakage currents. It is very slow and takes a lot of time. Please advise me if my analysis is correct. I just made it back from Lutron's HQ and I was asked for the same question. My first approach will be identifying a PNP BJT, and elaborating all 4 BJT operating regions. Before t = 0, since q = 0, by using Q = CV, we can tell that the voltage across the capacitor is 0. Hence, Vo = -10V before t = 0. Recall the capacitor's current equation: I = C*(dv/dt), we can solve for the slope of changing voltage -> dv/dt = I/C. Here, I is simply the BJT's collector current, which can be found by looking at the BJT's emitter current. Given that the (beta) parameter is infinite, we see the base current to be 0. Now, at this point, we need to look for I_E. Since the R is given to be 9.3k, and VEE = 10V, it is natural to assume V_EB = 0.7V, and thus the voltage across R = 9.3V. Therefore, I_E = 9.3/9300 = 1mA. Voila, we now values for all currents: I_E = I_C = 1mA, and I_B = 0A. Plug the I_C value into the equation: I_C/C = dv/dt (C = 1uF). We know that the slope of the voltage change is 1000V/second, or 1 Volt per millisecond. Now, we know the capacitor voltage raises at 1V/ms from -10V, but we also need to know where is the upper limit. Looking back to the BJT basics about operating regions and BJT's 2-diode model, it is not hard to identify that this PNP BJT must operate in "Saturation" region (NOT IN "ACTIVE" REGION!). The boundary of that region is V_BC <= 0.7V (I hope everybody is able to solve for this). Hence, 0.7V will be the upper limit for capacitor voltage. At this point, you will have a flat line at Vo = -10V before t = 0. and raises at 1V/ms for 10.7ms and hit Vo = 0.7V. From t = 10.7ms and on, the Vo stays at 0.7V. |
How would you generate sales. 2 AnswersPursuing all my friends who are just now in the stage of life where they need insurance for things. Identify the target market( Lower income families age 45-85) drop 1000 piece mailings every week to target market. As the 1to2% leads come in generated from the mail piece I would call prospects, verify they have a checking account, make an appointment. This is a one call close so you should sell 70% of appointments. Ask for referrals and knock on doors to the left and to the right and across the street. Also, I would knock on doors in the above mentioned neighborhoods. There is $20 behind every door and I would knock on as many as I could. Final Expense is an easy sell, you just have to get out there and work. Randy C. |
What would your final grade be (for the year) for a child that scored averages of 18%, 68%, 70% and 72% (high school math)? 2 AnswersI said that I would give them a C (70). They liked this answer. The by the book way to score this is to give the kid the average of all 4 quarters - and an F. I said that this would kill the spirit of the kid and the interest to learn. They followed up with "what if there was abuse in the home during Q1? a divorce? homelessness?" and a few others. "Would it matter if the kid was rich and drove to school in the BMW?" That student’s final grade would be and 57%. Of course I’d have to explain to them why because the student averaged 70% and 72% in two separate quarters, but the work separately of those quarters term averages doesn’t count towards the work of the other |
Java Software Engineer at Help Scout was asked...
Write a method to determine if a string starts with an uppercase letter. 2 Answerswouldn't it just be return string.charAt(0) == string.charAt(0).toLowerCase() bool lower(string s) { if (s.length() == 0) {return false;} char f = s.at(0); return (f > 64 && f < 91); // ascii values } Here’s a C++ implementation that might (not) work. Not so good with Java. |