Design a data structure such that given a stream of numbers, you can find the maximum of the numbers at any point and also all the numbers.
Given an array of 1s and 0s arrange the 1s together and 0s together in a single scan of the array. Optimize the boundary conditions.
Find the common ancestor of two given nodes in a binary tree, how do you exploit the properties of a given BST for the same problem.
You’re given a function getsort(data) that sorts the data given. The function sorts in place and does not use any extra memory. How do you validate the function with respect to 1) it sorts 2) it does not use extra memory
Explain the Traveling Salesman problem? What is an NP-complete problem? What is the Hamiltonian cycle problem?
Find out the least common ancestor in a binary tree.
2nd Question Ans: add all the numbers in one pass. that will give you no of 1’s and place taht many 1’s in the array and then rest 0’s.
O(n)
and no need to use check condition operaton.
Regards
That’s two passes through the array. One to read (and add) and one to write. My way would be to read a value, if it’s a ONE, move it to the front of the array (or just leave it in place) and if it’s a ZERO, swap it out to the end of the array. Inc/dec/leave alone counters as required, then continue. Stop when the 1s counter == 0s counter.
1.i think link list must be used
2.use a position var which keeps track of the position of 0 which gets swapped when nxt instance of 1 occurs and then mov pos to nxt instance of 0 and continue abv operation
3.probably use a prefix and infix order of the tree and keep track of the ancestors of each node in a double dimension array
3 Comments on Basic programming questions
2nd Question Ans: add all the numbers in one pass. that will give you no of 1’s and place taht many 1’s in the array and then rest 0’s.
O(n)
and no need to use check condition operaton.
Regards
That’s two passes through the array. One to read (and add) and one to write. My way would be to read a value, if it’s a ONE, move it to the front of the array (or just leave it in place) and if it’s a ZERO, swap it out to the end of the array. Inc/dec/leave alone counters as required, then continue. Stop when the 1s counter == 0s counter.
1.i think link list must be used
2.use a position var which keeps track of the position of 0 which gets swapped when nxt instance of 1 occurs and then mov pos to nxt instance of 0 and continue abv operation
3.probably use a prefix and infix order of the tree and keep track of the ancestors of each node in a double dimension array