c Interview Questions | Glassdoor

# c Interview Questions

270

interview questions shared by candidates

## c Interview Questions

Sort: RelevancePopular Date

Dec 9, 2010
(); 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++; } } } }

Apr 24, 2011

Dec 16, 2010

### Software Development Engineer In Test at Amazon was asked...

Jan 27, 2012
 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 Responsesmod 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 divisionsi 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.

Jan 24, 2010
 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 Responsesrecursive 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; }

### Software Development Engineer II at Amazon was asked...

Nov 22, 2011
 Find k largest/smallest number in a series of numbers. What data-structures will you use? Code it on white board.6 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 ResponsesI 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, 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 }For those of you who think building a max/min heap is O(nlogn) since heapify is O(logn) and heap build is O(n), but you are incorrect. Building a binary heap is actually O(n) because heapify depends on the height of the node, hence becoming O(h). Find more here: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/

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

Apr 27, 2012
 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.7 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 ResponsesI 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? ThanksThe interviewer could be looking for some bit ops. But, the following one, works even page size isn't a power of 2. int mod = (value_to_align % page_size); value_to_align -= mod; if (mod > (page_size - mod)) { value_to_align += page_size; }Have you tried using this website? www.rooftopslushie.com It says you can get career advice and interview prep info from Nvidia employees.

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

Jul 31, 2010
 How to remove a node from a singly-linked list when only given the pointer to the node6 AnswersYou have to use some pointer/memory trickerythisNode.data = thisNode.next.data temporaryNode = thisNode.next.next delete thisNode.next thisNode.next = temporaryNodeThe 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 ResponsesMilly, 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;

### Tegra Systems Software Engineering at NVIDIA was asked...

Feb 27, 2012
 identify the number of 1s in an integer is odd or even7 Answershint is XORvoid 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 ResponsesWas 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");

May 9, 2011