Rupa Sundar: September 2015

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

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:

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:

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

Rupa Sundar

Tuesday 22 September 2015

Answers

Monday 21 September 2015

Interview questions