once i had appeared to amazon interview, questions are as follows, Hello all,
These are the questions for Amazon interview i faced on last Saturday. ============================== =============== 1st Round -- written (coding) ============================================= Write functions for Q 1,2, 3 . Think of complexity and optimization also. 1> (easy) write a function to swap consequent nodes in a link list. i/p= head to list 1-> 2-> 3-> 4-> 5-> 6-> 7->NULL 0/p= head to list 2-> 1-> 4-> 3-> 6-> 5-> 7->NULL Do not swap values , swap nodes. node* swapNode(node *Head) ; 2> (medium) Write a function which will tell u whether given tree in balanced or not. Tree in balanced only if diff between height of roots left-subtree and right subtree is 0,1 or -1.Otherwise it is imbalaced (The problem was check only root is balanced or not, If any other subtree's root is imbalaced and root is balanced the result should return true i,e tree is balanced. Though you, for your improvement/knowledge, can write it a function in which it will check whether all the nodes are balanced or not) i/p= root of tree o/p= 1-true if tree is balanced 0-false if tree is imbalanced bool IsBalanced(Node *root); 3> (Hard) Convert Binary tree into the DLL but in following format. (Do not assume that it is complete binary tree). You have to convert those nodes of tree into the linklist nodes like nodes->left in tree will denote that its nodes next element in linklist and nodes->right in tree will denote that its nodes prev element in linklist Extra space is allowed. 1 --------------------- ------------ 2 <-------------------------- 3 <------- --------> 4 -----------> 5 -------------->6 ----------->7 ---- -------8 <----9<----10<----11<-----12<---13<---14<--- 15--- --------> so on in zig-zag manner so linklist will look like NULL <-- 1 <=> 3 <=> 3 <=> 2 <=> 4 <=> 5 <=> 6 <=> 7 <=> 15 <=> 14 <=> 13 <=> 12 <=> 11 <=> 10 <=> 9 <=> 8 --> NULL Node * createDLL(Node *root) ======================================================= 2nd Round = One on one - interview checking approach and datastructure Use ======================================================= In this round they asked me two question. They tried to check two things.How I approach the problem and use which data structure. 1> Reg expression. He asked me , what would be my approach if i have to implement a '?' operator in reg expesion which matches either with character before it or with nothings like ac?de can have two matching strings acde(('c' matched)) and ade('c'not matched) a?b can have two matching strings ab(('a' matched)) and b('a'not matched) After my answer Then he asked me to think about approach and use of datastructure which I can use so that i can easily add new operator like '-' '*' etc. 2> Store a binary tree into file and again reading file create it. Your approach and a datastructure you will use. Finally not selected but a nice interview. If u have question please feel free to ask me On Tue, Nov 8, 2011 at 10:03 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: > Thanks rahul > > > On 8 November 2011 03:32, rahul sharma <rahul23111...@gmail.com> wrote: > >> apti + technical + 3 prog (mainly linked list) >> >> On Tue, Nov 8, 2011 at 3:09 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: >> >>> >>> >>> -- >>> Regards >>> Kumar Raja >>> M.Tech(SIT) >>> IIT Kharagpur, >>> 10it60...@iitkgp.ac.in >>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.