Meta Data Structures & Algorithms Interview Questions

Ugo C. - "function preorderToInorder(preorder) { let inorder = []; let stack = []; let root = preorder[0]; stack.push(root); for (let i = 1; i 0 && stack[stack.length - 1] 0) { root = stack.pop(); inorder.push(r"See full answer

GalacticInterviewer - "Approach 1: Use sorting and return the kth largest element from the sorted list. Time complexity: O(nlogn) Approach 2: Use max heap and then select the kth largest element. time complexity: O(n+logn) Approach 3: Quickselect. Time complexity O(n) I explained my interviewer the 3 approaches. He told me to solve in a naive manner. Used Approach 1 had some time left so coded approach 3 also The average time complexity of Quickselect is O(n), making it very efficient for its purpose. However, in"See full answer

Sam J. - "static int[] sortKMessedArray(int[] arr, int k) { // your code goes here int len = arr.length; for(int i=1;i-1 && arr[j]>key){ arr[j+1] = arr[j]; j--; if(moves >= k){ break; } else { moves++; } } arr[j+1] = key; } return arr; } `"See full answer

Guilherme F. - "A much better solution than the one in the article, below: It looks like the ones writing articles here in Javascript do not understand the time/space complexity of javascript methods. shift, splice, sort, etc... In the solution article you have a shift and a sort being done inside a while, that is, the multiplication of Ns. My solution, below, iterates through the list once and then sorts it, separately. It´s O(N+Log(N)) class ListNode { constructor(val = 0, next = null) { th"See full answer

Anonymous Mongoose - "Given a Binary Tree, the task is to find its vertical traversal starting from the leftmost level to the rightmost level. If multiple nodes pass through a vertical line, they should be printed as they appear in the level order traversal of the tree. The idea is to traverse the tree using dfs and maintain a hashmap to store nodes at each horizontal distance (HD) from the root. Starting with an HD of 0 at the root, the HD is decremented for left children and incremented for right children. As we"See full answer

Rahul J. - "find total sum. assign that to rightsum traverse from left to right: keep updating left sum and right sum, when they match return the index. else if you reach end return -1 or not found"See full answer

Michael B. - "Problem: Given an input string txt consisting of alphanumeric characters and the parentheses characters '(' & ')', write a function which removes the minimum number of characters to return a version of the string with properly balanced parenthesis. Answer: You can do this with a counter. Psuedo-Python Start with counter = 0 output = [] Iterate through the string, every time you encounter a '(', increment the counter. Add the character to the output. If you encounter a ')', decrement the coun"See full answer

Ankita G. - "Merge Sort"See full answer

Samuel M. - "function main(){ const v1=[2,3, 4, 10] const v2= [3,4 ,5,20, 23] return merge(v1,v2); } function merge(left, right){ const result=[]; while(left.length>0&& right.length>0){ if(left[0]0){ result=result.concat(left) } if(right.length>0){ result=result.concat(right) } return result; }"See full answer

Alvaro R. - "bool isValidBST(TreeNode* root, long min = LONGMIN, long max = LONGMAX){ if (root == NULL) return true; if (root->val val >= max) return false; return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max); } `"See full answer

Ugo C. - "function merge(L1, L2) { let L3 = { data: null, next: null }; let prev = L3; while (L1 != null || L2 != null) { if (L1 == null) { prev.next = L2; L2 = L2.next; } else if (L2 == null) { prev.next = L1; L1 = L1.next; } else if (L1.data < L2.data) { prev.next = L1; L1 = L1.next; } else { prev.next = L2; L2 = L2.next; } prev = prev.next; } return L3.next; }"See full answer

Mahaboob P. - "int[] sqSorted(int[] nums) { int i = 0, j = nums.length-1; int k = nums.length-1; int[] sqs = new int[nums.length]; while(i n1) { sqs[k--] = n2; j--; } else { sqs[k--] = n1; i++; } } for(int n: sqs) System.out.println(n); return sqs; }"See full answer

Bhaskar B. - "This could be done using two-pointer approach assuming array is sorted: left and right pointers. We need track two sums (left and right) as we move pointers. For moving pointers we will move left to right by 1 (increment) when right sum is greater. We will move right pointer to left by 1 (decrement) when left sum is greater. at some point we will either get the sum same and that's when we exit from the loop. 0-left will be one array and right-(n-1) will be another array. We are not going to mo"See full answer

Techzen I. - "Implemented the Java code to find the largest island. It is similar to count the island. But in this we need to keep track of max island and compute its perimeter."See full answer

Anonymous Roadrunner - "from typing import List def traprainwater(height: List[int]) -> int: if not height: return 0 l, r = 0, len(height) - 1 leftMax, rightMax = height[l], height[r] res = 0 while l < r: if leftMax < rightMax: l += 1 leftMax = max(leftMax, height[l]) res += leftMax - height[l] else: r -= 1 rightMax = max(rightMax, height[r]) "See full answer

Srihitha J. - "my answer: void* memcpy(void* dest, const void* src, size_t n) { unsigned char* uDest = static_cast(dest); const unsigned char* ucSrc = static_cast(src); for(size_t i= 0; i(dest); const unsigned c"See full answer