Meta Data Structures & Algorithms Interview Questions

Michael B. - "Problem: Given a modified binary tree, where each node also has a pointer to it's parent, find the first common ancestor of two nodes. Answer: As it happens, the structure that we're looking at is actually a linked list (one pointer up), so the problem is identical to trying to find if two linked lists share a common node. How this works is by stacking the two chains of nodes together so they're the same length. chain1 = node1 chain2= node2 while True: chain1 = chain1.next chain2=chain"See full answer

Divya R. - "class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode temp=root; for(int i=0; i<word.length(); i++) { if(!temp.children.containsKey(word.charAt(i))) { temp.children.put(word.charAt(i), new TrieNode()); } temp=temp.children.get(word.charAt(i)); } temp.isEndOfWord=true; } public boolean search(String word) { TrieNode temp=root; for(int i=0; i<word.length(); i++) { if(!temp.children.containsKey(word.charAt(i))) { return false; } temp"See full answer

Rishabh R. - "sum of continuous subarray and keep checking if arr[i]==arr[j]. if true increase count;"See full answer

JOBHUNTER - "def findAlibaba(countOfRooms, strategy): #countofrooms: num rooms #listRooms rooms to look for alibabba possiblePlaces = [] #initialize rooms for i in range(countOfRooms): possiblePlaces.append(True) for i in range(len(strategy)): roomToCheck = strategy[i] #Room is marked as unavailable possiblePlaces[roomToCheck] = False #Next day calculatins nextDayPlaces = [] for j in range(countOfRooms): nextDayPla"See full answer

Vaibhav D. - "Make current as root. 2 while current is not null, if p and q are less than current, go left. If p and q are greater than current, go right. else return current. return null"See full answer

Ina K. - "HashMap supports insert, search, delete and retrieve in O(1). It stores data as key value pairs."See full answer

Rishabh R. - "if decreasing arr, start from end and keep checking if next element increases by 1 or not. wherever not, put that value there."See full answer

Rasika D. - "A doubly linked list is like a train where the engine is its head, and the compartments doors are interconnected, you can travel though them. The last compartment is the tail and is not connected with anything. Following is a visual: Head C1 C2 C3....Cn Tail Pseudocode: **class Node: Data pointer next pointer prev End class DLL = NULL //pointer to list insertion: if DLL is NULL: head = new Node() DLL = head DLL.prev = NU"See full answer

Rishabh N. - "I first asked few clarifying questions like the return array may need not contain the list of building in the same order, to which the interviewer agreed. Then I came up with an approach where we iterate the array from right to left and keep a max variable which will keep the value of the current max. When we find an item which is greater than max we update the max and add this element into our solution. The interviewer agreed for the approach. I discussed few corner scenarios with the interview"See full answer