lakshaman
BAN USERSQL Injection: exploits the queries that do not use bind variables.
e.g. on a login page if we are directly substituting the user and password fields as below:
select 1 from users where username = '<<userinput>>' and password = '<<userpasswd>>';
a malicious user can supply the password string as
xyz ' or 'a'='a
which would be valid SQL and will always return a result.
Secret Santa should mean shuffle the contents of an array where if the index of element represent a person the content would represent the person who is assigned [for gifting] to him.
Input would : 0 , 1, 2, 3, 4 ...n
Output should be : shuffled contents such that a[i] != i
Iterate over elements of the array:
copy the content to next cell
copy the content of last cell to first cell.
The approach can be randomized by picking the shift distance randomly instead of 1.
As alex said a BST can be reconstructed from the preorder traversal alone.
It appears the question should actually have been for a binary tree. For binary trees none of three traversals inorder, preorder or postorder alone can uniquely identify the tree. For a binary tree inorder traversal and either a postorder or preorder traversal can uniquely identify the tree.
Importance/Requirement of Inorder traversal:
The inorder sequence will resolve the left-right problem, and the other sequence (pre or post) will tell us the roots of the various subtrees. For example, if inorder is CBA, and preorder is CAB, then we know that C is at the root, and both B and A are in the right subtree
The current solutions posted above are all O(n) only.
- lakshaman February 08, 2014If the problem were on a 3 D matrix and you iterate over it. It does not become O(n^3)