Information Technology interview questions | Glassdoor

# Information Technology interview questions

www.google.com  /  HQ: Mountain View, CA

4,823 Interviews

3.4 Difficult

www.apple.com  /  HQ: Cupertino, CA

4,026 Interviews

3.0 Average

www.microsoft.com  /  HQ: Redmond, WA

3,941 Interviews

3.2 Average

## Interview Questions

Sort: Relevance Popular Date

Oct 1, 2010

### Software Engineer at Apple was asked...

Jun 19, 2012

Jul 18, 2010
 Write some pseudo code to raise a number to a power. 10 Answers pretty 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; }

Feb 25, 2012
 Find the second largest element in a Binary Search Tree 16 Answers find 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

Sep 6, 2010

Jan 21, 2010
 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 Answers It 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

### Software Development Engineer In Test (SDET) at Expedia was asked...

Apr 18, 2012
 Describe and code an algorithm that returns the first duplicate character in a string? 7 Answers Simple Python example. Not sure it's most efficient. def findDup(str): match=[] i=1 while (i

Mar 19, 2009
 What sort would you use if you required tight max time bounds and wanted highly regular performance. 6 Answers Vector 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)

### Director of Solutions Marketing at Opower was asked...

Sep 14, 2012
 How do you convince a CIO of a utility to care about energy efficiency? 5 Answers This 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...

Dec 9, 2010
 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 Answers 45. 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
110 of 123,685 Interview Questions