Team Lead/ Tech Lead interview questions – page 9

What will the following code snippet do, when is it passed the root of a binary tree ?

Each node in a given list has an additional link called random that can point to any node (can also be null). we need to make a clone of the list without using any additional space (need to allocate memory only for new nodes 1', 2', 3',...). Comp...

Given an array of n number, one number is repeated n/2 times. Find the number.

You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?

Design a system to manage clock room ( used at railway station). Like what data structure, how ? I gave O(1) time solution + small space complexity.

Convert a given binary search tree to circular linked list.

Given a binary tree, find a path which sum to a given target. the path can start from node, go to the left subtree and also to the right subtree...

Given an array with positive and negative integers and an integer k, find the subarray(consecutive) whose sum is k. This is different from subset sum problem.

How to find last unique character in a given string? Unique character means non-repeated number. Give an optimized way.

The inorder representation of a tree 41523 and preorder is 211513, draw it.

Max and avg. height of binary tree?

There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. Lists are in orders of descending powers. Constraints: no extra space i.e., O(1) space O(m+n) time complexity...

Write code to check whether given tree is BST or not. ( initially I gave O(n^2) he said optimize then I gave O(n) and O(n) space then he said we don't have this much space then I was able to do in O(n) and O(1) space). 3. Whether code is thr...

There is a linked list of numbers of length N. N is very large and you dont know N. You have to write a function that returns k random numbers from the list. Numbers should be completely random.

Find the median of two sorted arrays. Eg. a1[] = {1, 2, 7, 8} a2[] = {3, 9, 12, 23}, then find the median of the array created by merging them, ie {1 2 3 7 8 9 12 23}

Write a function that returns a node in a tree given two parameters: pointer to the root node and the inorder traversal number of the node we want to return. The only information stored in the tree is the number of children for each node.

Implement a Queue using a Stack ADT. He told me to write tight code for this as well. He wanted optimized methods for this, and asked me to enumerate different ways of optimizing this data structure, and to analyze each one. After I did that...

Find 5th Maximum in BST given bst is of 4 / 2 6 / / 1 3 5 7

Given a binary tree, find the largest subtree that's also a BST.

Given a large string, you have to find out largest string such that all its character are consecutive.

Write a code to find the tree from a given tree such that each node in resultent node value= sum of it's childs

Given a table of prefix rules (similar to regex) and the corresponding actions. Given a string, find the most specific rule that can be applied and carry out the corresponding action. For ex, a.*->f1() a.b.c.*->f2()<b...

Given a pointer to a node in a singly linked list, how do you delete the node?

Find the median of a Binary Search Tree. You are passed the root of the tree, and you should return the median which is the middle element, if the number of elements is odd, or the average of the two middle elements if the number of elements is ev...

You have been given a Two Dimensional Array and One Dimensional Array.. You have to return true if 2D array consists of given 1D Array 2D array Consists of 1D array means all the elements of 1d are present contiguously in left side, right side...

Given two linked lists, write a function to check if the two lists are identical or not.

Given a BST, a number s and a group of numbers g, check whether all the elements of g occur in the same path,all elements sum upto s without including root and the leaf

What is the difference between following two statements?

Insert an element in a linked list at the end , given the start pointer.

Given 2 string A ,B. write a code to find all character of A exists in B or not?