# Information Technology interview questions

## Interview Questions

An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element. 22 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. 0 100 Add 1-100 to a hash of 100 elements. Then compare each element with the hash.. Answer in o(n) |

### Senior Software Engineer at Facebook was asked...

Write some pseudo code to raise a number to a power. 10 Answerspretty trivial... int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; } Show More Responses In Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}" If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations. Because it uses dynamic programming and is lots more efficient than your algorithm. If the power is not integer, use ln and Taylor series If I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1. There is a way to do this in a logN way rather than N. function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1); } This is from Programming pearls.. interesting way. small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; } |

### 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 Above answer is wrong. it has to be something like this. public static int findSecondLargest(Node node) { Node secondLargest = null; Node parent = null; Node child = node; if (node!=null && (node.hasLeftChild()||node.hasRightChild())) { if (node.hasRightChild()) { while (child.hasRightChild()) { parent = child; child = child.rightChild(); } secondLargest = parent; } else if (node.hasLeftChild()) { child = node.leftChild(); while (child.hasRightChild()) { child = child.rightChild(); } secondLargest = child; } } return secondLargest; } 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 |

### 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; } Hello, Thank you for sharing your interview experience. As a small team of ex-Google employees, we have recently launched a new website, interviewjoy.com, where you can earn money by sharing your interview experiences/insights with other job candidates. (It is a marketplace for sharing job interview insights). Posting an interview consultancy service is totally free & anonymous and we are giving 50 USD sign-up bonus for the first 500 users. You are kindly invited to interviewjoy.com to check it out. Users already started making money on the website! Best Regards.. (For more information: onboarding@interviewjoy.com) |

Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this? 6 AnswersIt can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming. Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!? Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Show More Responses Awesome!! The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features It wasn't 100% clear to me, then I found the Wiki page http://en.wikipedia.org/wiki/Summed_area_table |

Describe and code an algorithm that returns the first duplicate character in a string? 7 AnswersSimple Python example. Not sure it's most efficient. def findDup(str): match=[] i=1 while (i<len(str) and len(match)==0): for j in range(i): if str[j]==str[i]: match=[j,i] i+=1 return match if __name__ == '__main__': print findDup('asdf') print findDup('asdfasdf') pass first clarify if it is ASCII or UNICODE string For ASCII, create BOOL checkArray [128] = {false}; walk the string and update the index of checkArray based of the character. for (int index=0;index< strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } public class FirstDupCharacter { public static void main(String[] args) { System.out.println(findDupCharacter("abcdefghiaklmno")); } private static Character findDupCharacter(final String input) { final Set set = new HashSet(); Character dup = null; for (int i = 0; i < input.length(); i++) { if (set.contains(input.charAt(i))) { dup = input.charAt(i); break; } else { set.add(input.charAt(i)); } } return dup; } } Show More Responses String samp = "Testing"; samp = samp.toLowerCase(); char chararr[] = samp.toCharArray(); int size = chararr.length; char repeat = ' '; for (int i=0;i<size && repeat==' ';i++) { for (int j=i+1;j<size && repeat==' '; j++) { if (chararr[i]==chararr[j]) { repeat = chararr[i]; } } } System.out.println("First Repeating character :: "+repeat); for (int i=0;i<size;i++) { if (samp.indexOf(chararr[i]) != samp.lastIndexOf(chararr[i])) { System.out.println("First repeating char ::"+chararr[i]); break; } } public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index < characters.length; index++ ) { // insert the character into the map. // returns null for a new entry // returns the index if it previously if it existed Integer initialOccurence = charsMap.put(characters[index], index); if ( initialOccurence != null) { return initialOccurance; } //there where no characters that where duplicates return -1; } } Another python solution: def findFirstNonRepeatedCharInOneIteration(str1): for i,j in enumerate(str1): if j in str1[:i] or j in str1[i+1:]: print "First non-repeated character is "+ j break str1 = "abcdefglhjkkjokylf" findFirstNonRepeatedCharInOneIteration(str1) |

### Senior Software Engineer at Google was asked...

What sort would you use if you required tight max time bounds and wanted highly regular performance. 6 AnswersVector sort. Guaranteed to be O(n log n) performance. No better, no worse. That is so say, a "Balanced Tree Sort" is guaranteed to be O(n log n) always. Show More Responses Merge sort and heapsort are always guaranteed to be n*log(n). Quicksort is usually faster on the average but can be as bad as O(n^2), although with very low probability. Heapsort also does it sorting in-place, without needing an extra buffer, like mergesort. Lastly, heapsort is much easier to implement and understand than balancing trees mentioned by earlier posts. for something like this you generally want bubble sort or insertion sort. It's not about being fast it's about being consistent. Make it do exactly the same thing every time. Use a sorting network. There's some precomputation time, but runtime will be very consistent (the only variability is branch prediction performance) |

How do you convince a CIO of a utility to care about energy efficiency? 5 AnswersThis is a bit of a trick question. CIO really does NOT care about efficiency because it means less revenue. However, some states are mandating efficiency programs and so the CIO wants to do this as cost effectively as possible. Some utilities in some states also face competition for energy consumption, so a customer engagement program that makes consumers feel good about their utility will help with rate approvals and satisfaction ratings, which will boost the bottom line overall. He cares because if he can lower the system peak number, he can lesson the amount of spinning reserves he must have in place, whixh in effect is stranded capital. CIO cares since as a company executive he needs to work with his customers (operating unit executives) to cut costs and increase revenues. By providing a solution that mines data to assist customer to save energry usage - the CIO is prioviding a solution for the utility to flatten its energy demand curve. Show More Responses CIO at a utility does not buy this product, nor would she/he care about this. Not their lane. Simple. You demonstrate a cost savings analysis comparing efficient energy use to inefficient energy use. Use a graph of the inefficient use, compare to an efficient use, then run assign the value. That is just one way. This of course assumes that the inefficient use cost more then the cost to correct the problem. But if you do make the changes you can leverage the changes into a PR piece and get a double benefit (efficient use and a "look at us going green!" piece.) |

### 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 3 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 |

In a given sorted array of integers remove all the duplicates. 6 AnswersIterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N The array is already sorted, no need for a set. example: 2,2,5,7,7,8,9 Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n) public RemoveDuplicates() { int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 }; int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ; for (i = 1; i <= ip.Length - 1; i++) { if (ip[i - 1] != ip[i]) { op[j] = ip[i - 1]; j++; } } if (ip[ip.Length - 1] != ip[ip.Length - 2]) op[j] = ip[ip.Length - 1]; int xxx = 0; } Show More Responses def removeDuplicatesSecondApproach(inputArray): prev = 0 noRepeatIndex = 0 counter = 0 for curr in range(1,len(inputArray)): if (inputArray[curr] == inputArray[prev]): counter = counter + 1 prev = curr else: inputArray[noRepeatIndex+1] = inputArray[curr] noRepeatIndex = noRepeatIndex + 1 prev = curr inputArray = inputArray[:-counter] return inputArray if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } Apologies for the previous incomplete answer int[] inpArr = {1,2,2,3,4,5,5,5,8,8,8,9,13,14,15,18,20,20}; int[] opArr = new int[inpArr.length]; int opPos = 0; for(int i= 0; i<=inpArr.length - 1; i++) { if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } |