Answers

Power set of given set:
    http://www.geeksforgeeks.org/power-set/

Interview questions

Amazon:
----------
1) Given a rotated sorted array, find the first occurrence of a certain number X with the lowest possible complexity(both time and space).

X = 6
Arr = 8,9,9,1,3,4,4,4,6,6,7,7

Ans = 8

2) Given a linked like defined so...

typedef node_t {
int data;
node_t* next;
}Node;

check if the linked list is a palindrome without using any extra space and with the lowest possible complexity(both time and space).

write code for following API

BOOL is_palindrome(node *Head);

3) write an algorithm to find the next largest node in a binary tree.

typedef treenode_t{
int data;
treenode_t *parent;
treenode_t *left;
treenode_t *right;
}TreeNode;

TreeNode* find_next_largest_element(TreeNode *node);

Written:

• Program to find the run length encoding of a string.
• Program to check whether there exists a root to leaf path having a given sum in a binary tree.

Round 1:

• Program to implement an LRU cache.
• Program to convert a sorted array to balanced binary search tree.
• Program to reverse a single linked list in groups of k recursively.
• Design a data structure for implementing dictionary.

Round 2:

• Program to recursively calculate a^n.
• Design a data structure for an infinite stream of numbers such that it's optimized for insertion, deletion, searching, finding kth largest and kth smallest.

1. Given a BST and 2 numbers a,b. Find the number of hops to reach from a to b. 

2. Given a set of unsorted numbers without a range, find the median. No sort operations should be used. Solution should be of the order n log n.

written: 
1. convert sorted array to BST
2. next larger number in a given array for an index
3. find first non-repeative char in a string

interview:
1. find longest path in a tree
2. implement dictionary

Microsoft : 
------------
a) Write a function which simply returns 0X00000000 if input value is 0 else 0XFFFFFFFF. Condition is no branching , no looping and no ternary operators.
Solutions

1 2 3 4

int bit(int n) { return (!n + (n|~n)); }

b) Infinite bit stream is coming (one bit at a time). At a given time tell whether number is divisible by 3 or not
Solution:

1 2 3 4 5 6 7 8 9

sum=0; while(bit stream is coming) { sum=sum<<1+1*(current bit); if(sum%3==0) printf(“divisible\n”); else printf(“not divisible”); }

c) Check whether a given string consists the substring of type “ab*c”
Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

char *str=INPUT STRING int i=0,flag=0; while(str[i]) { if(str[i++]==’a’) { while(str[i]==’b’) i++; if(str[i++]==’c’) { printf(“substring found”); flag=1; break; } } } if(!flag) printf(“substring not found”);

Written:

• Program to rotate a matrix by 90 degree counter clockwise in place.
• Program to sort a single linked list containing only 0s, 1s and 2s.
• Program to correct a binary search tree in which only any two nodes have been swapped.

Round 1:

• Given two sorted arrays, find the (set) difference of two.
• Routine to output the elements of the inorder traversal of a binary tree one by one on its each call.

Round 2:

• Given a set of courses along with the prerequisite courses for these courses, write a program to find the minimum number of semesters required to wrap up all the courses.

Suggested:

------------

Books : Programming Interviews Exposed
Lectures : Algorithms Lectures on Youtube from MIT
Sites: Careercup,GeeksForGeeks,Leetcode.com

More questions can be found at:

1. http://www.thelearningpoint.net/computer-science/programming-interview-questions---microsoft-amazon-google-facebook

2. http://ashayraut.wordpress.com/interview-preparation-best-100/