People Tech Group interview question
TR1 Questions (Technical Coding - DSA): 1. Find the Kth smallest element in an unsorted array. Discuss multiple approaches and their time complexities. 2. Given an array of strings, find the longest common prefix. 3. Find the element that appears only once in a sorted array where every other element appears twice. (Implement an O(log n) binary search approach.) 4. Reverse a singly linked list. Questions for TR2: 1. Given an input string and a search substring, write a method to find the number of occurrences of the search substring in the input. 2. Given a list of Employee objects, filter out duplicates based on employeeId, keeping the one with the most recent updated_date.
Interview Answer
Anonymous
1. public int findKthSmallest(int[] nums, int k){ PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : nums) { maxHeap.offer(num); if (maxHeap.size() > k) maxHeap.poll(); } return maxHeap.peek(); } 2. public String longestCommonPrefix(String[] strs){ Arrays.sort(strs); String first = strs[0]; String last = strs[strs.length - 1]; int i = 0; while (i < first.length() && i < last.length() && first.charAt(i) == last.charAt(i)) { i++; } return first.substring(0, i); } 3. public int findSingle(int[] nums){ int low = 0, high = nums.length - 1; while (low < high){ int mid = (low + high) / 2; if (mid % 2 == 1) mid--; if (nums[mid] == nums[mid + 1]) low = mid + 2; else high = mid; } return nums[low]; } 4. public ListNode reverseList(ListNode head){ ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } TR 2: 1. public int findOccurrenceOfAString(String input, String search){ int count = 0; int index = 0; while ((index = input.indexOf(search, index)) != -1) { count++; index += search.length(); } return count; } 2. public List filterEmployees(List employees){ Map employeeMap = new HashMap<>(); for (Employee emp : employees){ int id = emp.getEmployeeId(); if (!employeeMap.containsKey(id) || emp.getUpdated_date().after(employeeMap.get(id).getUpdated_date())) { employeeMap.put(id, emp); } } return new ArrayList<>(employeeMap.values()); }