Intern Interview Questions in United States | Glassdoor.co.in

# Intern Interview Questions in United States

35,309

intern interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

28 Jul 2009

### Project Engineering Intern at Disney Parks was asked...

29 Oct 2011

9 Dec 2013
 Find the max value in an array. The array is "semi-sorted". Here is an example: { 1 3 4 7 9 10 12 13 12 6 3 } As you can see, the array increases and then decreases at one point (13). 20 AnswersSimply walk the array to find the max in O(n) time. Compare the current max to the next element all the way until the end of the array.O(logn) approach: int max_value_in_semisorted_array(int* arr, int start, int end) { if (start == end) return arr[start]; int middle = (end + start) / 2; if (arr[middle] > arr[start]) return max_value_in_semisorted_array(arr, middle, end); else return max_value_in_semisorted_array(arr, start, middle); }No, your O(logn)-approach doesn't work. Try this: 1 5 8 10 9 8 7 6 5 4Show more responsesThe previous O(log n) approach doesn't handle arrays of odd length. int findPeak(int * array, int start, int end) { if ((start == end) || ((start == (end - 1)) && (array[start] > array[end]))) return array[start]; if ((start == (end - 1)) && (array[start] > array[end])) return array[end]; int middle = floor((start + end) / 2); if (array[middle] > array[start]) return (findPeak(array, middle, end)); else return (findPeak(array, start, middle)); } Remember to include math.h for the floor function.It seems, that it doesn't matter if the array is of odd or even length(btw, my example is not odd :)). This approach doesn't work when the max element is in the first half of your array and the middle element is greater than the first one. We cannot guarantee that if the middle element is greater than the first, our array increases monotonically from x[1] to x[middle] and we should search the max element in the range from middle to end.It is necessary to check two elements on each side of our middle element to find out where the array increases , where decreases, and where the peak is. And only then we can guarantee something about our max.The maximum is obviously just the inflection point in the list... some of the posted solutions here are absurdly complex for this.Brute force solution can be ofcourse O(N). But we can make it better: mid = (start + end )/2 if mid > mid + 1 && mid > mid - 1 return mid else if mid mid -1 search mid -> end else if mid > mid + 1 && mid mid@Mo - This won't be work for an array where the max element is hidden in the first / second half of the main array. Eg: {1,3,9,1,-2,6,2,2,5,-1}In your test case, I see that the numbers increase, decrease, increases, decreases and so on. I thought the question says the list is semi sorted. So my program assumes that the numbers increase and then decrease. We need to find the peak. At least that is my understanding.private static int recFindPeak(int[] a, int start, int end) { if(start == end) return a[start]; int mid = (start+end)/2; if((a[mid] > a[mid+1])&&(a[mid] > a[mid-1])) return a[mid]; else if(a[mid] > a[mid-1]) return recFindPeak(a, mid+1, end); else return recFindPeak(a, start, mid-1); }My codes: int findPeak(vector num) { if (num.empty()) return 0; int lower = 0; int upper = num.size()-1; while (lower num[mid+1]) return num[mid]; else if (num[mid-1] < num[mid] && num[mid] < num[mid+1]) lower = mid+1; else upper = mid-1; } }1. Walk from begin to mid comparing a[i] a[j] and stop decrementing j when this condition fails. 3. If a[i] < a[j], then return a[j], else return a[i].Show more responses1) find the pivot of the highest number of the semi sorted list ,using binary search on the array.(logn) 2) From their do the linear serach for finding max ,also compare with last element of the semi sorted list.strange, some lines missing for above solution: shouldn't be one line : if((end-start)==1 && arr[end] arr[start]) but: if((end-start)==1 && arr[end]<=arr[start]) { return arr[start]; }def maxInSemiSortedArray(inputData): low, high = 0, len(inputData) -1 while(low inputData[mid-1] and inputData[mid] > inputData[mid+1]: return inputData[mid] elif inputData[mid] < inputData[mid+1]: low = mid + 1 else: high = mid -1def maxInSemiSortedArray(inputData): low, high = 0, len(inputData) -1 while(low inputData[mid-1] and inputData[mid] > inputData[mid+1]: return inputData[mid] elif inputData[mid] < inputData[mid+1]: low = mid + 1 else: high = mid -1public static Integer getMax(int[] arr){ int max = Integer.MIN_VALUE; int start = 0; int end = arr.length -1; while(start max){ max = arr[mid]; System.out.println("max :"+max); } if( arr[mid+1] > arr[mid]){ start = mid+1; }else if( arr[mid] > arr[mid-1]){ System.out.println("arr[mid]"+arr[mid]+"arr[mid-1] :"+arr[mid-1]); return arr[mid]; } else if(arr[mid] < arr [mid-1]){ end = mid -1; } } System.out.println("Max :"+max); return max; } public static void main(String[] args){ //int[] arr = new int[]{1,3,5,4,2}; int[] arr = new int[]{1,2,4,6,7,8,5,3}; System.out.println("Max is:"+getMax(arr)); }some codes are messed up above. Here is the clean code. public static Integer getMax(int[] arr){ int max = Integer.MIN_VALUE; int start = 0; int end = arr.length -1; while(start max){ max = arr[mid]; System.out.println("max :"+max); } if( arr[mid+1] > arr[mid]){ start = mid+1; }else if( arr[mid] > arr[mid-1]){ System.out.println("arr[mid]"+arr[mid]+"arr[mid-1] :"+arr[mid-1]); return arr[mid]; } else if(arr[mid] < arr [mid-1]){ end = mid -1; } } System.out.println("Max :"+max); return max; } public static void main(String[] args){ //int[] arr = new int[]{1,3,5,4,2}; int[] arr = new int[]{1,2,4,6,7,8,5,3}; System.out.println("Max is:"+getMax(arr)); } One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.

17 Mar 2013

26 Jan 2017

### Data Scientist Intern at LinkedIn was asked...

25 Feb 2012
 Find the second largest element in a Binary Search Tree16 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 responsesThe 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 responsesFind 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. Please see our Community Guidelines or Terms of Service for more information.

1 Oct 2013

15 Feb 2012