Data Structures & Algorithms Interview Questions

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

Anonymous Unicorn - "input_logs = [ f"{senderid} {receiverid} {transaction_count}" "1 2 2", "3 2 42", "2 2 22", "1 1 12", "2 1 1", "2 5 4", "4 2 15" ] input_threshold = 20 exptected_output = [ list of user_ids that made more than 20 transactions sorted by number of transactions in descending order "3", # 42 transactions "2", # 27 transactions (22 + 1 + 4) #"4", # 15 transactions #"1" # 14 transactions (2 + 12 + 1) ] def gettopapi_users(logs, thres"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

Rafał P. - "def changeString(org: str,target:str) -> bool: lOrg = len(org) lTarget = len(target) \# They have to be equal in lenght if lOrg != lTarget: return False counter1 = Counter(org) counter2 = Counter(target) \# Counter internally iterates through the input sequence, counts the number of times a given object occurs, and stores objects as keys and the counts as values. if counter1 != counter2: return False diff = sum(org[i] != target[i] for i in range(n)) return diff == 2 or (diff == 0 and any(v > 1 f"See full answer

Sean L. - " import pandas as pd def findaveragedistance(gps_data: pd.DataFrame) -> pd.DataFrame: #0. IMPORTANT: get the unordered pairs gpsdata['city1']=gpsdata[['origin','destination']].min(axis=1) gpsdata['city2']=gpsdata[['origin','destination']].max(axis=1) #1. get the mean distance by cities avgdistance=gpsdata.groupby(['city1','city2'], as_index=False)['distance'].mean().round(2) avgdistance.rename(columns={'distance':"averagedistance"}, inplace=True) "See full answer

Anzhe M. - "It's a 2Sum question with duplicate array elements."See full answer

Tiago R. - "function generateParentheses(n) { if (n < 1) { return []; } if (n === 1) { return ["()"]; } const combinations = new Set(); let previousCombinations = generateParentheses(n-1); for (let prev of previousCombinations) { for (let i=0; i < prev.length; i++) { combinations.add(prev.slice(0, i+1) + "()" + prev.slice(i+1)); } } return [...combinations]; } `"See full answer

Sarvesh G. - "def calc(expr): ans = eval(expr) return ans your code goes debug your code below print(calc("1 + 1")) `"See full answer

XponentShift32 - "solving to find a cycle in directed graph"See full answer

Mridul J. - "We have a list of documents. We want to build an index that maps keywords to documents containing them. Then, given a query keyword, we can efficiently retrieve all matching documents. docs = [ "Python is great for data science", "C++ is a powerful language", "Python supports OOP and functional programming", "Weather today is sunny", "Weather forecast shows rain" ]"See full answer

Jasmine Y. - "It depends on the size of the dataset. You want enough samples in both the testing, training and evaluation sets. If there is enough data, 70/20/10 is a good split"See full answer

Azeezat R. - "/* You are with your friends in a castle, where there are multiple rooms named after flowers. Some of the rooms contain treasures - we call them the treasure rooms. Each room contains a single instruction that tells you which room to go to next. * instructions1 and treasurerooms_1 * lily* --------- daisy sunflower | | | v v v jasmin --> tulip* violet* ----> rose* --> ^ | ^ ^ | "See full answer

Yash N. - "import time class Task: def init\(self, description, interval=None): self.description = description self.interval = interval self.next_run = time.time() class SimpleTaskScheduler: def init\(self): self.tasks = [] def add_task(self, description, interval=None): self.tasks.append(Task(description, interval)) def run(self, duration=60): end_time = time.time() + duration while time.time() < end_time: curr"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

Anonymous Unicorn - "Count items between indices within compartments compartments are delineated by by: '|' items are identified by: '*' input_inventory = "*||||" inputstartidxs = [1, 4, 6] inputendidxs = [9, 5, 8] expected_output = [3, 0, 1] Explanation: "*||||" 0123456789... indices ++ + # within compartments ^ start_idx = 1 ^ end_idx = 9 -- - # within idxs but not within compartments "*||||" 0123456789... indices "See full answer

Anonymous Owl - "def validateIP(ip): """ @param ip: str @return: bool """ \# ip needs to be in X.X.X.X \# X is from 0 to 255 \# split the ip at "." split = ip.split('.') if (len(split) != 4): return False for number in split: if (int(number) 255): return False return True"See full answer

Nitin P. - "public static void sortBinaryArray(int[] array) { int len = array.length; int[] res = new int[len]; int r=len-1; for (int value : array) { if(value==1){ res[r]= 1; r--; } } System.out.println(Arrays.toString(res)); } `"See full answer