# c Interview Questions

interview questions shared by candidates

## c Interview Questions

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

Find the minimum depth of binary search tree 10 Answersisn't this? int mindepth(node* root) { if(root==NULL) return 0; return 1 + min(mindepth(root->left),mindepth(root->right)); } You wouldn't get an on-site interview with this answer. Your code is not optimal, although it looks short. Here is the trick: you don't have to traverse entire tree to find out the minimum. think about this example. L side of the root node has only one item, so the deep is 1, R side of the root has one million items. Why do you have to traverse through all one million nodes, if you can get the min from the L side right away? It can be solved using the previous recursive code and also can be solved using Breadth First Traversal, by starting the traversal from the root of the tree, and when reach a leaf then this is the min depth return the number of steps from the root to this leaf Show More Responses public int minDepth(Node root) { Map depthMap = new HashMap(); depthMap.put(root, 0); List toVisit = new ArrayList(); toVisit.add(root); while(!toVisit.isEmpty()) { Node curr = toVisit.remove(0); if(curr.getLeft() == null && curr.getRight() == null) { // first leaf node is the minimum depth return depthMap.get(curr); } else { if(curr.getLeft() != null) { depthMap.put(curr.getLeft, depthMap.get(curr) + 1); toVisit.add(curr.getLeft()); } if(curr.getRight() != null) { depthMap.put(curr.getRight(), depthMap.get(curr) + 1); toVisit.add(curr.getRigth()); } } } return -1; // not good } use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast! Someone said you need to pass 3 questions to be qualified to on-site... Use BFS to iterate the tree, keep track of the "level" you're currently at. When a childless node shows up, return the level number. Code: public static int MinDepth(Node root) { if (root==null) { return 0; } Queue queue = new LinkedList(); queue.add(root); queue.add(new Sentinel()); int depth = 1; while(!queue.isEmpty()){ Node current = queue.poll(); if (!(current instanceof Sentinel)) { if (current.left==null && current.right==null) { break; } else { if (current.left!=null) queue.add(current.left); if (current.right!=null) queue.add(current.right); } } else { depth++; if (!queue.isEmpty()) { queue.add(new Sentinel()); } } } return depth; } void mindepth(node* cur, int curdepth, int& best) { if(curdepth >= best) return; if(cur == null) { best = curdepth; return; } mindepth(cur->left, curdepth + 1, best); mindepth(cur->right, curdepth +1, best); } best = inf; mindepth(root, 0, best); public class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<div>q = new LinkedList<div>(); q.add(root); int enqueuedNum = 1; int visitedNum = 0; int lastLevelNum = 1; // initialized to be 1, whichever child tree node is null, then finish // the operation and return the current minDepth int minDepth = 1; while (true) { TreeNode n = q.poll(); visitedNum++; if (n.left != null) { q.add(n.left); enqueuedNum++; } if (n.right != null) { q.add(n.right); enqueuedNum++; } if (n.left == null || n.right == null) { return minDepth; } if (lastLevelNum == visitedNum) { lastLevelNum = enqueuedNum; minDepth++; } } } }</div></div> |

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

Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes). 8 AnswersRecursively: - convert the left subtree (returns a dbl-linked list (DLL) with a head ptr & tail ptr) - convert the right subtree (same) - connect the left DLL tail to the right DLL head bi-directionally - return the combined list (head = left-head, tail = right-tail) struct StackEntry { Node *pNode; bool fVisit; }; inline void linkNodes(Node *pLeft, Node *pRight) { pLeft->pNext = pRight; pRight->pPrev = pLeft; } inline void visitNode(Node **ppFirst, Node **ppPrev, Node *pNode) { if(ppPrev == NULL) { *ppFirst = pNode; *ppPrev = pNode; } else { linkNodes(*ppPrev, pNode); *ppPrev = pNode; } } void doubleLink(Node *pRoot) { stack stack; Node *pFirst = NULL; Node *pPrev = NULL; StackEntry rootEntry = {pRoot, false}; stack.push(rootEntry); while(stack.size() != 0) { StackEntry &top = stack.top(); stack.pop(); if(top.fVisit) { visitNode(&pFirst, &pPrev, top.pNode); } else { StackEntry entry; if(pNode->pLeft != NULL) { entry.pNode = pNode->pLeft; entry.fVisit = false; stack.push(entry); } entry.pNode = pNode; entry.fVisit = true; stack.push(entry); if(pNode->pRight != NULL) { entry.pNode = pNode->pRight; entry.fVisit = false; stack.push(entry); } } } if(pPrev != NULL) { linkNodes(pPrev, pFirst); } } class TreeNode { TreeNode* left; TreeNode* right; int value; } TreeNode* MakeCircularDoublyLinked(TreeNode* head) { DoublyLink(head, head); return MakeCircular(head); } TreeNode* MakeCircular(TreeNode* node) { TreeNode* leftEnd = node; while (leftEnd->prev != NULL) { leftEnd = leftEnd->prev; } listNode* rightEnd = node; while (rightEnd->prev != NULL) { rightEnd = rightEnd->prev; } rightEnd->next = leftEnd; leftEnd->prev = rightEnd; return leftEnd; } listNode* DoublyLink(TreeNode* current, TreeNode* prevTreeNode) { if (current == NULL) { return NULL; } current->left = DoublyLink(current->left, current); if (current->left != NULL) { current->left->right = current; } current->right = DoublyLink(current->right, current); if (current->right != NULL) { current->right->left = current; } if (prevTreeNode->left == current) { // we are processing the left subtree, return the rightmost // element to the parent while (current->next != NULL) { current = current->next; } } else if (prevTreeNode->right == current) { // we are processing the right subtree, return the leftmost // element to the parent while (current->prev != NULL) { current = current->prev; } } return current; } Show More Responses Detailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html Java, non-recursive. O(n) time, O(1) space: import java.util.Stack; public class TreeToCircList { public static class Node { public Node left = null; public Node right = null; public int data; } public void convert(Node node) { boolean leftChecked = false; Node prev = null; Node start = null; Stack s = new Stack(); while(node != null) { if(leftChecked == false && node.left != null) { s.push(node); node = node.left; } else { // Perform the linking node.left = prev; if(prev != null) prev.right = node; else start = node; // Mark start of the list prev = node; if(node.right != null) { node = node.right; leftChecked = false; } else if(s.empty() == false) { node = s.pop(); leftChecked = true; } else { node = null; } } } // Find the first node to link with the last node if(prev != null) { start.left = prev; prev.right = start; } } } Thanks to recursion .. this is a sorted linked list .. to make it circular just make a pointer from the last to the head. :) bst_node* getList(bst_node* nd) { if(nd == NULL) return NULL; bst_node* head; bst_node* l = getList(nd->lft); bst_node* r = getList(nd->rt); if(l != NULL) { head = l; head->lft = nd; nd->lft = r; } else { head = nd; head->lft = r; } return head; } void print_list(bst_node* bst) { bst_node* head = bst; while(head != NULL) { cout val lft; } } void BinTree::convert() { Node * head, * tail; convert_to_dlist(root, head, tail); Node * current = head; while(current != tail) { cout val right; } cout val val left; } cout val left, lhead, ltail); convert_to_dlist(node -> right, rhead, rtail); if(lhead == NULL && rhead == NULL) { head = node; tail = node; head -> left = head; head -> right = head; } else if(lhead == NULL && rhead != NULL) { head = node; head -> right = rhead; rhead -> left = head; tail = rtail; head -> left = tail; tail -> right = head; } else if(lhead != NULL && rhead == NULL) { head = lhead; head -> left = node; node -> right = head; tail = node; tail -> left = ltail; ltail -> right = tail; } else { head = lhead; tail = rtail; ltail -> right = node; node -> left = ltail; node -> right = rhead; rhead -> left = node; head -> left = tail; tail -> right = head; } return; } Solution by recursive in-order traversal. To make code simply I did not make linked list circular. It can be done by simply modification to return both head and tail and connect them outside recursion. Node Convert(Node root) { if (root == null) return null; Node last = null; return InOrder(root, ref last); } Node InOrder(Node node, ref Node last) { Node left = null; if (node.Left != null) left = InOrder(node.Left, ref last); node.Left = last; if (last != null) last.Right = node; last = node; if (node.Right != null) InOrder(node.Right, ref last); return left ?? node; // return the smallest node which will be the head } |

### Software Engineer at Ooyala was asked...

Given two integer arrays. Find the Largest Common sub array. For example, arr1 = {1,2,3,2,3,2} arr2={2,2,3,3,4,5}, the largest common sub array is {2,2,3,3} 8 AnswersI try to an array as a hash table. index is the element, value is the times the element appears in arr1, and then traversal arr2, with the hash table. The problem of my algorithm is that I need to know the range of the arrays' element value, because I need to use that to define the size of my array. The interview asked me if I was familiar with the STL hashmap, which i was not Was this asked in phone interview ? sort + join - looks like the answer Show More Responses The question is confusing.You are sayin common sub array but the sub array is present only in 2nd array. common sub array should be {2,3} instead of {2,2,3,3} it seems from the answer that the question is actually the longest common subsequence, which is a dynamic programing problem this has several answers but no need for dynamic programming solution. 1. sort + join - O(nlogn) 2. keep counts for integers in array or hashmap - O(n) but need lot of extra space O(n) Seems the question is to give an array with the common elements between the two arrays. If this is the case, you should use a HashMap. The keys are numbers in the first array. The value is the number of times each one shows up. Have an array for the result. Then go over the second array. Look for each number in the hashMap. If it's there and the value is greater than 0, append it to the result and reduce in 1 the value in the hashmap for that number. public static Integer [] commonElements ( int [] a, int [] b ){ java.util.HashMap h = new java.util.HashMap (); for ( int e: a ){ if (h.containsKey(e))h.put(e, h.get(e)+1); else h.put(e, 1); } java.util.ArrayList resultAL = new java.util.ArrayList (); for ( int e: b){ if ( h.containsKey(e)&&h.get(e)>0){ resultAL.add(e); h.put(e, h.get(e)-1); } } Integer[] result = resultAL.toArray(new Integer [ 0 ]); return result; } |

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

Define binary search tree. Develop a procedure to verify a binary search tree. 6 AnswersNot very difficult. Asked for answer in code. Interviewer took notes for each line I wrote. Was interested in each statement I made about the algorithm, esp. why I took each approach. How do you verify a binary search tree? Will you get all the values from binary search tree and check if they are in order? can someone explain? @Bala Recursively: Check node.left node.value. Also, that all subvalues of node.left node.value. Make sure you do checking for edge cases (ie. leaf nodes, etc). Show More Responses recursive solution is a good option i guess.. its definitely easy to code. However i think we can have it done more efficiently if we just perform a BFS on the given tree. and every time just check tht the left child is smaller and right chiled is greater than or equal to the current node. If we successfully search the entire tree then it is a proper BST otherwise its not. public static boolean checkTree(BSTNode node, Integer leftLimit, Integer rightLimit) { if(node == null) return true; if(leftLimit != null && leftLimit > node.info) { return false; } if(rightLimit != null && rightLimit < node.info) { return false; } return checkTree(node.left,leftLimit,node.info) && checkTree(node.right,node.info,rightLimit); } bool IsValidBST(Node root, int min, int max) { if(root == null) return true; if (root.iData > min && root.iData < max && IsValidBST(root.LeftChild, min, root.iData) && IsValidBST(root.RightChild, root.iData, max)) return true; else return false; } |

Asked to implement a function that takes an integer and returns whether or not the number had an odd or even number of 1 bits. 6 AnswersIt started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n). If the task is only for positive numbers, then my solution would be: bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; do { result |= ((n % 2) == 1); n /= 2; } while ((n / 2) != 0); return result; } Show More Responses mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster. > bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; while(n != 0) { result |= ((n & 0x01) == 1); n >> 1; } return result; } masking is faster than a mod operator, and bit shifting is faster than divisions i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011. I guess changing the line to: result ^= ((n & 0x01) == 1); will do the job... PC, your solution is incorrect. It will always return true if the number has at least one set bit. |

Assume that you are given the head and tail pointers of a doubly linked list where each node can also have a single child pointer to another similar doubly linked list. There are no cycles in this structure outside of the traditional double links. Write a procedure in C++ that flattens this structure into a single list. 7 AnswersI found out later that this problem is one of several classic programming questions taken from an interview book. Such a list has an obvious recursive structure, but it is large and so recursion is not practical. Consequently, an iterative approach is necessary. The invariant for such an approach maintains the flat list to the "left" and the possibly fat list to the "right." Do you know the name of the book? I don't know the particular book it was taken from. However, a colleague recommends the book: _Programming Interviews Exposed_ by John Mongan The second edition is available, but a third edition (with two additional authors) is on its way and available for pre-order on Amazon. There are several other similar books. For example, _Cracking the Coding Interview: 150 Programming Questions and Solutions_ by Gayle Laakmann McDowell _Programming Pearls_ by Jon Bently _Puzzles for Programmers and Pros_ by Dennis Shasha _How Would You Move Mount Fuji?: Microsoft's Cult of the Puzzle -- How the World's Smartest Companies Select the Most Creative Thinkers_ by William Poundstone and many others you can probably find by looking at Amazon's recommendations when viewing the descriptions of those books. Show More Responses Didn't get any notification that you had replied to this, and just found it again when reviewing my studies. Thanks! Glad to help! And many of those coding-specific books include lots of questions about operations on linked lists. I have a feeling that the questions asked to me probably come from that set of books (or a book that shares a source with one of those). There might be some variation, but the basic principles should be the same. PseudoCode Solution: class ListNode(prev, next, sub_list) def flatten_list(node): if node == None: return [] elif is_tailI(node): return [node.value] + flatten_list(node.sub_list) else: return [node.value] + flatten_list(node.sub_list) + flatten_list(node.next) The PseudoCode solution mentioned above is *NOT* the desired answer because it involves recursion. As mentioned in the first comment, recursion is not allowed due to the very large structure of this list. The correct solution makes use of loop invariants. |

identify the number of 1s in an integer is odd or even 7 Answershint is XOR void OnesAreOdd(int n) { int i=0; while(n!=0) { n=n&(n-1); i++; } return (i&1==1)?true:false; } Above solution is incorrect. void OnesAreOdd(int n) { int i=0; while(n!=0) { n=n&(n-1); i=i^1; } return i==1?true:false; } Show More Responses Was taken from: http://graphics.stanford.edu/~seander/bithacks.html unsigned int v; // word value to compute the parity of bool parity = false; // parity will be the parity of v while (v) { parity = !parity; v = v & (v - 1); } Hey guys, why are you thinking the question means binary 1s? I think it means decimal 1s. Let number be c int count = 0; while ( c != 0 ) { count += (c & 1); c >> 1; } if ( count%2 == 0) printf("Number of 1s are even); Easy dumb solution, convert the number to string and count. sprintf(str, "%d", num); int i=0, cnt=0; while (str[i]!='\0') { if (str[i++]=='1') cnt++; } if (cnt%2) printf("odd"); else printf("even"); |

### Systems Software Engineer at NVIDIA was asked...

Given a page size and a number, align the number with the nearest page. (Note: This was a phone interview question. The interviewer and I used an online document to share ideas about this problem. 5 Answers//naive solution: int getAlignedValue(int pageSize, int valueToAlign) { int index = valueToAlign/pageSize; return index * pageSize; } //faster solution: int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & !(pageSize-1); } I think that at the faster solution you mean int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & ~(pageSize-1); } Note: There is a difference between !(pageSize-1) and ~(pageSize-1) ~(0x11) is 0xee !(0x11) is 0 @The Dude Good catch! I didn't think about that. (Fortunately, I didn't have to execute the code in the interview--I just typed it in a program similar to Google Docs.) Thanks! Show More Responses I just wanted to point out that the "faster solution" only works if the pageSize is assumed to be a power of 2. For example, suppose pageSize = 10 (or 01010 in binary), and valueToAlign = 24 (or 11000 in binary), then the fast method would give 16, but it should be 20. Anyways, thanks for posting the question and solution. @observer I see how the mask works out for the alignment, why it is works mathematically? Thanks |

### Software Engineer at Goldman Sachs was asked...

How to remove a node from a singly-linked list when only given the pointer to the node 6 AnswersYou have to use some pointer/memory trickery thisNode.data = thisNode.next.data temporaryNode = thisNode.next.next delete thisNode.next thisNode.next = temporaryNode The post by "jobseeker" assumes that we know the node BEFORE the node to be deleted. This assumption is not consistent with the problem definition, but makes it solvable. Show More Responses Milly, jobseeker's assumption is reasonable, we should not delete the node before removing it from the list (if it was created by the list) Milly: jobseeker is right in that you don't delete the "node to be deleted". You delete the node that FOLLOWS the "node to be deleted", only after swapping the values of the two. node ->val=node->next->val; node ->next=node->next->next; |

Find k largest/smallest number in a series of numbers. What data-structures will you use? Code it on white board. 5 AnswersFor K smallest number in series you can use a max heap of size k. When you find a new number and it is smaller than root of heap, swap it with root and heapify. @Ajit: What're the initial values of the max heap? What happens to the first value that comes in? Use selection sort for 'max' ( or for 'min') If K > series.length/2 then reverse the criteria- like in stead of looking for 15th highest out of 20 element array - look for (20 -15 =) 5th lowest and so on.... Show More Responses I think there's a cool solution which involves doing a pivot operation (like quicksort) until you have the top/bottom k numbers sorted. It's possible that you can get the top k numbers in a single pass of the array if you happen to choose a good pivot, and in general takes very few passes to find the top k numbers. I coded it up in C a while back: http://privatepaste.com/1f1df9d8f0 You just call select with your list, the min index, max index, and top k numbers, respectively. It can be easily changed to find the min (just reverse the swap condition) @Jordan, I can no longer get at your privatepaste link, so if you see this post I am interested in answers to the following: - since partition sizes are inherently not controllable by your choice of pivot, how do you land on an exactly k-sized partition (or even a k-sized total of the leftmost/rightmost N partitions)? - how do you choose pivots reliably to perform this (if it isn't reliable, then it isn't always a good answer just like pathological inputs for quicksort without randomizing the pivot selecting) - do you still just sort the partition(s) once you reach a k-sized set? I assume they want them in-order. I would just use a heapsort that short-circuits once K elements have been popped from the internal sifting loop, which does minimal processing and returns them in-order (C# example): public void FindKLargest(T[] A, int k) { . Heapify(A); . int end = A.Length - 1; . int k_offset = Math.Max(Math.Min(k, end), 1); . int stop = end - k_offset; . while (end > stop) . { . // Save the root heap item as done . Swap(ref A[0], ref A[end]); . // Separate heap from saved item . end--; . // Re-sift the new root item . SiftDown(A, 0, end); . } . // the K largest entries are now in ascending order at the end of A } |