Software Developer interview questions – page 26

Given a Integer, find the maximum number that can be formed from the digits. Input : 8754365 output : 8765543

Given a binary search tree. Traverse only the left sub-tree

Design data structure that supports insert(), remove(), find-max(), delete-max() operations. All operations should run in O(1) time. Lots of discussion was there, discussed many approaches

Check whether given link list represents palindrome

Given a n-ary tree. Devise an algo which determines the position at which the 3rd B is present from the given index in constant time complexity

Given a dictionary with limited words. Check if the string given to you is a composite of two words which are already present in the dictionary

Given a single linked list of certain nodes. Switch adjacent nodes. Eg. 1 2 3 4 will be 2 1 4 3

A stream of characters is coming, at any moment you have to tell 'k' elements closest to a given number (code)

Find median of an unsorted array. (code)

Find sum of all numbers that are formed from root to leaf path (code) expected time complexity O(n)

Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. For example : ABC -> A BC, AB C, ABC, A B C

Preorder traversal without using recursion

Given an array of integers, find the length of the longest consecutive sub array which forms an AP

Given a binary tree, connect all the nodes at the same level. Each node will have a next pointer; you have to make it point to the next node to its right in the same level. If there is no such node, make it point to null

Given an array in which consecutive elements differ by 1, i.e. a[i] – a[i + 1] = 1 or -1, and an element x, find the element in the array

Given an array, find the Next Greatest Element to the right for each element

Given an expression, remove unnecessary parenthesis. For example if (((a + b)) * c) is given make it (a + b) * c, as it evaluates in the same way without those parenthesis also

Given an array of integers, find the maximum product which can be formed by three numbers

getMax() function for a queue in O(1)

Given a binary tree and an integer x, return whether the binary tree has a path from root to a leaf whose values sum to x

Gievn a binary tree and return all root to leaf node pathss row,col and value

He then asked me to give test cases for testing this program

Given two unsorted arrays of numbers and asked me to find the intersection

getMax() function for a stack in O(1)

Edit distance problem (DP)

Find loop in linked list. Proof of algo

Given a sorted array(array can contain duplicates). Find the first occurance of given key elements in this array

Now array is rotated..solve same

Spiral order traversal of bt

Given a road network of a city. Each road represents an edge and need atleast one guard at any end of the road to put it in observation. Derive a algorithm to deploy minimum guard s.t that each road have atleast one guard