Amazon Real Interview Questions

Question: Three Sum

Question: Add Two Numbers

Question: Array GCD Finding

Question: Array Maximum Increasing Index

Question: Array Remove Alternate Duplicate Characters

Question: Best Time to Buy and Sell Stocks

Question: Binary Tree Child Sum

Question: Binary Tree Extract Leaves To Double Linked List

Question: Binary Tree K Nodes Apart

Question: Binary Tree Level Order Traversal

Question: Group Anagrams

Question: Insert Delete Get Random in O(1)

Question: Kth Largest Element in an Array

Question: Letter Combinations of a Phone Number

Question: Line Maximum Points

Question: Lin Reflection

Question: Linked List Cycle

Question: Linked List Reverse Nodes In K Groups

Question: Linked List Swap Adjacent Nodes

Question: Linked List With Next and Ranom

Question: Longest Palindromic Substring

Question: Lowest Common Ancestor of a binary Tree

Question: Merge K Sorted Lists

Question: Minimum Cost Climbing Stairs

Question: Min Stack

Question: Number of Islands

Question: Palindrome Linked List

Question: Product of Array Except Self

Question: Rectangle Area

Question: Rectangle Overlap

Question: Reverse Linked List

Question: Robot Move With Obstacles

Question: Rotate Image

Question: Subsets

Question: Top K Frequent Words

Question: Trapping Rain Water

Question: Two Sum

Question: Validate Binary Search Tree

Question: Valid Parenthesis

Question: Word Break

Question: What would an API look like for the interactions between a plane and air traffic control.  

Question: OO design: Black Jack Game.   

Question: What is the Big O time for insertion in Doubly Linked Lists. Revise the complexity for the popular datstructures

Question: Find the least common ancestor of given two nodes in a tree

Question: Design a single machine, single user system for hotel table reservations.

Constraints: assume 16 tables with capacity 4, 16 tables with capacity 8. Can book for just 1 hr. Max 2 months in advance.

Which classes, which data-stuctures?

A1. Array of size 32. Each element in the array contains linkedList sorted by startTime where each link represents timeslot that is already booked/reserved.

(A2) What happens when a party of 16 requests for a table. You can join tables which are next to each other. Implement this.

A2. Get a list of tables which are available in the requested time period, check if there is a contiguous set of tables which total up to 16 and then reserve those tables.

------

Question:

(B1) Design a deck of cards.

B1. Deck class. Card class. Suit enum. Value Enum. Card contains Value and Suit enums. Deck contains an array of 52 cards. Constructor of Deck initializes 52 card class.

Card should expose comparable interface.

Deck should expose Shuffle and iterator interface.

Some considerations: Should Deck be singleton? Should Deck be made generic to accept different types of cards? Should Desk be made threadsafe?

(B2) Now assume 10 million users are using this card deck.

B2. If there are 10 million users on the same machine using 10 million Decks, then we don't really need 520 million cards.

Each Card instance is immutable. So we just need 52 card instances which are shared between 10 million Decks.

-------

Question:

(C1) Given a binary tree, print all the leaf nodes.

C1: Leaf nodes: Preorder traversal limited to leaves.

(C2) Now, print all the left most nodes, and all right most nodes ( assume there is a triangle around the binary tree, so all nodes which falls on that triangle , print them in clockwise ordering).

C2: Left side: Preorder traversal limited to nodes which matches certain criteria.

    Right side: Only visit those nodes that meet certain criteria - Post Order traversal.

------

Question:

(D1) Given an array which contains series of 0s and series of 1s, find the index where 1s start.

How would you test this method?

D1: binary search O(logN)

     Testcases: null array, empty array, array with just one element - 0, array with just one element - 1.

           array with only 0s. array with only 1s. 5 element array with 2 0s and 3 1s, array with numbers other then 0 and 1.

Question:Assume input array has infinite length, how will you find the index in O(logn) time?

Question:: 2 step process: (i) Find the block in which transition from 0 to 1 happens. (ii)Then find the exact index within that block.

For #i, consider first block with size K, if no transition in this block, then check next block with size 2K, then 4K, then 8K. Once we find the block with transition then step#ii is simple binary search.

----------

Question: print list of nodes at each level of a binary tree

Question: Most efficient algorithm for sorting infinitely long array

Question: find sub-strings from a string which are valid dictionary words.  

Question: impelementation of hashmap (check other popular ds implementation as well)

Question: Implement the functions bool Add(), bool Remove(), and bool Contains() for a hash set of integers. (Then some questions followed about how to determine when to add more buckets)  

Question: Given a 2-dimensional array in which each position is a 1 or 0, how you find (AKA write a function that returns) every block of contiguous 1s? An analogy is to pretend that zeros are water and 1s are land, so find every island. 

Question: Given two parameters, the first parameter being a string of words with no spaces, the second being a dictionary with all thinkable words, return the first string with spaces put in between the words.

Question: find largest BST

Question: Finding all the occurrences of a  given string in another one

Question: constructing a sorted hashtable class

Question: Doubly linked list, 

Question: print matrix in spiral form, 

Question: how to compare two huge file in two different locations

Question: Write a program to do integer multiplication, and then try to make it multithreafed/parallel in multi cpi (the job was to develop software for multi processor system).  

Question: implement a file system

Question: implement a poker game

Question: 3 stacks using an array

Question: Given the root of a tree count it's nodes. Whats the time complexity of your answer?

Question: You are given an array that contains numbers increasing up to the maximum then decreasing. ( [1,2,3,2] , [2,3,6,7,2,1], etc) Find the largest number. Whats the time complexity of your answer?  

Question: Provide two algorithms: one to serialize a binary tree, the other to deserialize it. 

Question: Implement the floodfill (aka paint bucket) function of the Windows Paint program.

Question: find the maximum contiguous subsequence in a bar chart.

Question: Determine whether the binary representation of a number is a palindrome or not, code it on a white board.  

Question: Swap every other element in a linked list. e.g. a->b->c->d becomes b->a->d->c  

Question: Write class for trie and searching in a trie  

Question: Design a system to count in a sliding window  

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

Question: What is the best way to find files containing a US phone number in a collection of more than 10000 html files.  

Question: How would you find a duplicate number in a very large unsorted array of ints.  

Question: K most frequent integers from array of integers.  

Question: Search an element in a sorted, rotated array. Time complexity should be O(log n)

Question: Design a traffic signal control system or traffic light system

Question: Trap rain water problem, Swap linked list nodes(swap nodes and not data) 

Question: Create a clone of a special linked list which each node can have an extra pointer which points to a random element in the list. O(n) time, and O(1) space

Question: how to implement an online shopping site aggregator?

Question: Design a time based validation check that can be applied to api, for example hitting google's map api more then 50 times in a minute will result in error, similarly design a system that checks in the no of calls that are happing in the sliding windows of given size.

Question: Design a realtime ranking system , for example given a app like candy crush i would like to display user his current rank , globally, country wise etc  

Question: Design Dashboard System

Question: left view of a tree (BFS not accepted).

Question: cross product of m*n matrix

Question: design railway ticketing system

Question: coin change problem, find the coins to be used

Question: Given a BST, find all pairs of nodes which add up to a certain number k

Question: abstract data types

Question: You have a e-shop and you must implement the shop card. The e-shop has some bonuses that if you buy for example 3 same stuff one is free, if you buy this stuff there is 25% free etc.  

Question: do a moving average with a window. 

Question: design resource pool

Question: Create Doubly link list from a BST

Question: Design a solution similar to google news.

Question: How to build a distributed hash.

Question: diameter of a tree

Question: Given an integer, find the next biggest integer whose digits are in increasing order.

Example:

Input: 118

Output: 123

Input: 127

Output: 234

Input: 987

Output: 1234

Question: given a very large file (Billion lines in Tera Bytes) and you have only few GB of memory, what is your approach to search a word in the entire file and print the line number in efficient way.  

Question: Print the binary tree in zig zag level order

Question: Given a single linked list of integers determine if it is palindrome. like 1 2 3 4 3 2 1. Need to support 1 2 3 3 4 3 3 1 as well. No extra allocation or space should be consumed.( can use some temp variable).

Question: In an array of integers, find pair of integers whose sum is equal to closest to K

Question: Subroot in a Binary tree with longest leaf-to-leaf path

Question: Given a adjucency matrix view of a graph find connected components in it

Question: Two sorted arrays. you can start from any one them, and  then at common element you may or may not jump to other array. Continue in this manner till you reach the end of an array. Find the path that results the maximum sum

Question: Write a code to reverse binary bit pattern for an integer without using any string or utility methods?  

Question: Convert a BST to sorted Double linked list

Question: Design Elevator

Question: largest contigous sub array sum

Question: Given a sorted circularly linked list of Nodes that store integers and a new Node, insert the new Node into the correct position. (Duplicates allowed)  

(This assumes the list has at least one item)

void insertInOrder(Node* header_node, Node* new_node)

{

    if (header_node->next == nullptr)

    {

        header_node = new_node;

        new_node->next = new_node;

        return;

    }

    Node* prev = header_node;

    Node* curr = header_node->next;

    while (true)

    {

        // We past the node

        if (curr->value > new_node->value)

        {

            insertAfter(prev, new_node);

            break;

        }

        // We are at the node

        else if (curr->value == new_node->value)

        {

            insertAfter(curr, new_node);

            break;

        }

        else

        {

            // Finished thru the list, new node is bigger than everything else

            if (curr->next == header_node)

            {

                new_node->next = header_node;

                curr->next = new_node;

                break;

            }

            prev = prev->next;

            curr = curr->next;

        }

    }

}

void insertAfter(Node* node, Node* new_node)

{

    new_node->next = node->next;

    node->next = new_node;

}

Question: How many times will a robot need to retrieve bins if it is given an array of bin ID's and it can only hold N bins at a time? When the robot is already holding N bins, it will return the least recently retrieved bin and store the new bin.  

Question: Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder. 

Question: write stringbuilder class

Question: Randomly shuffle an array. Follow up questions on ensure that no items remain in their original places.  

Question: Design Google docs

Question: Binary tree expression parser

Question:  How to retrieve recent 5 queries that was searched on AWS dashboard  

Question: You have a huge data file (gigabytes in size) full of URLs, one per line. There are many duplicates throughout the file. How would you process this data to produce an output file with one unique URL per line, followed by the number of occurrences?  

=>This is a plain MapReduce question. In Mapper you Emit(URL, 1), combiner combines and shuffles them, then in reducer you get (URL, array of occurrences) and then just sum up those occurrences. Simple WordCount like question. Just tests if you know what's a MapReduce.

Question: design an alarm clock

Question: implement ip routing table

Question: Map/reduce problem on list of web page access logs to produce top 3 pages visited in order by a user  

Question: multithreading related questions

Question: Giving an array of integers from 1 to n-1 in random order where n is the size of the array. Find duplicates in the array and identify its runtime. Can you do it with inplace solution? 

Question: Graph question which utilizes BFS to determine if one can fly from a to b, given a graph of cities that has flight to.  

Question: Write breadth-first search in a matrix  

Question: use add operation to perform sub, mul, and divide.

Question: find-all-anagrams-in-a-string

Question: Design question to find the most frequent sequence of web page views from a log file of all the web pages viewed  

Question: Rotate a matrix 

Followup: Write a function that rotates a 2-dimensional array clockwise or counter clockwise 90 degrees depending on a given parameter, which I believe was either -1 or 1, which told you which way to rotate it. You are given the 2D array as a parameter as well.  

 

Question: Given a list of weighted edges between nodes, find the minimum cost spanning tree  

Question: Given the upper left and lower right coordinates of two rectangles, determine if they overlap  

Question: longest palindromic substring

Question: Create and return a deep copy of a singly linked list where each node also has an additional pointer to a random node in the list. 

Question: Given an input stream of strings, find the most frequent string. 

Question: Given an input stream of strings, find the first, unique string.  

Question: reverse the second half linked list. Followup: reverse nodes from i to k position in the given linked list. Followup:reverse a doubly linked list

Question: Given a graph of possible electricity connections (each with their own cost) between cities in an area, you are asked to find the cheapest way to supply power to all cities in the area. This is simply a way of asking you to construct a minimum spanning tree from a well-connected graph.

Question: Find all print all possible combinations of given digits. Followup: find largest number by using the combination of the digits in a given number, e.g., 1023=>3210

Question: Use Array to implement heap + LC101 Symmetric Tree  

Question: Efficiently produce all permutations of a string

Question: Binary tree path sum

Question: Merge two binary search trees in O(1) space

122) Shortest distance between the cities by visiting only them once

Question: Given an array of integers, check if an element exists twice in the list, using an efficient data structure and algorithm. Also compute Time and Space complexity. 

Question: Find the closest node in BST.

Question: Secret santa question  

Question: all possible combinations of items in a list

Question:  You are given a linkedlist with next and arbitary pointers. Create a new linkedlist similar to the given linkedlist. You need to create a code for deep copy of a linkedlist.  

Question: How to find a number which exist odd times in a list

Question: Find H index (Leetcode question)

Question: Convert Sorted Linked List to Binary Search Tree.

Question: In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions. 

Question: There are N  jobs each with multiple inputs and one output. You have to schedule these jobs in order. One job's input could be output to another one. The result should be the list of jobs that are in order. (This is exactly what happens in map reduce kind of job. The output of intermediate stages is input to the following stages). Input and outputs are namespace or directory where the data is persisted.

Question: How to construct a data structure that supports representing, storing and simple mathematical operations like addition, multiplication, on a very very large number, say 2^200.  

Question: window sum problem

Question: Use hashmap to solve a currency exchange question

Question: Capture valid email ids from the stream of characters with no option of storage.

Question: Design movie playlist

Question: How would you implement a service like twitter? 

Question: Design telecommunication billing system

Question: How would you design the game Snake?

Question: Design the high level communictions and protocols required for an air traffic control system.

Question: Given an array of 1s and 0s, cound the "islands" composed of contiguous 1s in the "sea" of 0s.  

Question: longest increasing sequence in an array of random numbers

Question: Tiny URL system design

Question: DFS matrix path-searching problem 

Question: Design an online shopping site for Amazon Tutoring -

Question: round robin policy

Question: How to find duplicate values in BST  

Question: remove duplicates from an array

Question: create a circular linked list with a search method

Question: 2-sum, 3-sum, 4-sum

Question: Compare hash map with binary search tree.  

Question: Find if events in a list overlap given the start and end times.

Question: OOD. design a system for ATM 

Question: Given an array of person objects that contain a name and gender, sort the array such that all females are before males in the array.

Question: Write a program to shuffle a deck of 52 cards and shuffle them equally to 4 players.

Question: design facebook/twitter/library/microwave/vending machine/elevator

Question: reverse words in a string

Question: create popular data structures - linked list, hash set, hash map, binary tree, stack, queue

Question: merge sorted linked lists

Question: how to traverse a maze and arrive at a destination

Question: Topological sorting: You have a list of packages A, B, C such that A is  dependent on B,C,D and B is dependent on D and C is dependent on E etc. Print the sequence of packages to run

Question: pairwise swap of elements in a linked list

Question: Given a log file of various exception messages, how would you calculate the number of times each occured

Question: Difference between Hashmap and LinkedHashMap

Question: Read in an n by n matrix and shift each element over by one position along the edges 

Question: Write a function to implement Huffman encoding.

Question: Sketch out a shortest path algorithm on a graph on the whiteboard 

Question: design a trie

Question: How would you color a graph (2-colors, 3-colors) such that no two neighboring nodes are colored the same?

Question: Given a list of k coordinates, find n closest to the origin.

Question: How can merge sort be run in-place.

Question: .find gcd of an array of integers

Question: print the elements in a n by n 2d array in a spiral shape

Question: Meeting scheduler for effective room-meeting mapping

Question: find the max subtree sum.  

Question: implement merge sort, quick sort, heap sort

Question: Given a stream of words find the most occurring word. Also find the top 100 distinct most occurring words.  

Question: Given a facebook graph of friends, write a function to return the fewest number of edges between a person A and a person B. 

Question: design a cloud based storage product  

Question: Linked list with random pointer

Question: About how to schedule the given ads to get a maximum value of them

Question: Find all the phone numbers in 100 HTML file. (Regular expression)

Question: A file contains 1 million coordinates of planets, find the the first 100 ones closest to earth.  

Question: design the Amazon Ad scheduler 

Question: SHORTEST RANGE IN K SORTED LISTS

Question: Save all leaf nodes of a Binary tree in a Doubly Linked List by using Right node as Next node and Left Node as Previous Node.

Question: Given an array,find the maximum j – i such that arr[j] > arr[i]

Question: Remove Alternate Duplicate characters from a char array you have to do it in Place. Like keeping only the odd occurences of each character.

Example: Input: “you got beautiful eyes”

Output: ”you gtbeaiful es”

Allowed Time Complexity was O(n) and Space Complexity was O(1)

Question: In a file there are 1 million words . Find 10 most frequent words in that file.

Question: Find all nodes at k-distance from a given node in a binary tree

Question: Clone a linked list with next and random pointer

Question: Serialise and Deserialise a linked list with next and random pointer.

Question: Construct a binary tree from given inorder and preorder traversals.

Question: Return a tree such that each internal node stores sum of all its child nodes. Each leaf node stores zero.

Question: How will you implement linked list with 1 million nodes? How will you access 999999 th node? Give some optimal design strategy and implementation.

Question: Reversal of Linked List in groups of K.

Question: Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.

Question: Check whether given binary tree is balanced or not. Definition was no two leaves should have height difference of greater than one.

Question: Remove duplicates from string in place in O(n).

Question: Connect nodes on same level in a binary tree.

Question: Find sum of data of all leaves of a binary tree on same level and then multiply sums obtained of all levels.

Question: Given a matrix of characters and a word.

you have to count the number of occurrences of that word in that matrix. you can move to any of the eight valid directions from current position.

You are given an string as input which represents a path. You have to normalize that path inplace(NO EXTRA SPACE).

e.g.input : "\a\b\c\..\..\file.txt" output: "\a\file.txt"

Question: Least common ancestor of two nodes in a binary tree

Question: Given two sorted arrays (with repetitive elements) find the kth minimum number from both arrays.

Question: Given the root to a binary tree, a value n and k.Find the sum of nodes at distance k from node with value n

Question: Find an element in a rotated array

Question: The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days.

For example, if the given array is {100, 180, 260, 310, 40, 535, 695}, 

the maximum profit can earned by buying on day 0, selling on day 3.

Again buy on day 4 and sell on day 6. 

If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.

Question: Given two linked lists both represent a number. Create a linked list that contains its sum.

Question: Given a binary search tree , print the path which has the sum equal to k and has minimum hops. i.e if there are multiple paths with the sum equal to k then print the path with minimum number of nodes.

Question: A MxN matrix containing integers (positive, negative and zero’s). For every position containing 0, mark the corresponding row and column as 0.

Question: Rotate MxN matrix by 90 degress.

Question: Find the nth number that contains the digit k or is divisible by k. (2 <= k <= 9)

Question: Write a program to connect next left node in a binary tree. Also first node of each level should be pointing to last node of next level? (Without using Queue)

Question: Convert a binary tree to its sum tree(each node is the sum of its children)

Question: Given a directed graph. Construct another graph from given graph such that if path exists from vertices  A to vertices B and from B to C, then path from A to C and from C to A also should exists.

Question: Implement hashmap on your own. Write good hashing function for string.

Question: Given an array, arrange the elements such that the number formed by concatenating the elements is highest.

E.g.: input = [9, 93, 24, 6], 

the output should be: [9,93,6,24].

 This is because if you concatenate all the numbers, 993624 is the highest number that can be formed.

Question: Given a string, find the longest substring which is palindrome.

Question: Given that integers are read from a data stream. Find median of elements read so for in efficient way. For simplicity assume there are no duplicates.

Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.

Question: Given unsorted array and a number K. Find 2 numbers such that sum is K.

Question: Given n-ary tree. zigzag level order traversal.

Question: Given string s and string t find whether all permutation of t is present as substring in s.

Question: Design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack. Implement popMin() function which would pop minimum element from the original stack.

Question: Given a set of intervals like 5-10, 15-20, 25-40, 30-45, 50-100. Find the ith smallest number in these intervals. Assume there are no duplicate numbers.

e.g:  1st smallest number = 5   6th smallest number = 10

7th smallest number = 15 and so on. 

Question: Given an array which is first strictly increasing and then strictly decreasing. Find an element in this array.

Question: Given a string example : shoppingwithflipkartiseasy, Now we are given this string and a dictionary containing valid words , now we need to break the sentence into words separated by space. Output : shopping with flipkart is easy

Question: Given a series 2,3,4,5,6,8,9,10,……, here in this series all the numbers are present which have factors only and only either 2,3 or 5. Need to write a node to generate nth number for the series . With best approach and complexity

Question: Given a tree with edge weights, find any path in the tree with maximum sum of edges.

Question: Merge k sorted arrays.

Question: Given a maze, a start point and end point find the shortest path to reach the end point from the starting point.

Question: Given a sentence and a set of characters. Find the minimum window within which the set of characters can be found in the sentence in any order.

Question: You are given a string of 0’s and 1’s you have to find the number of substrings in the string which starts and end with a 1.

eg : input : 0010110010 output : 6

Question: You are given a mapping like a -> 1, b-> 2… z-> 26. You have to print all possible combinations of a given number using the above information.

eg : input : 121 output : aba,la,au

Question: Given a dictionary of 50,000 words. Given a phrase without spaces, add spaces to make it a proper sentence.

e.g:input:  thequickbrownfoxjumpoverlazydog

output: the quick brown fox jump over lazy dog

Question: Given an unsorted array of n integers which can contain integers from 1 to n. Some elements can be repeated multiple times and some other elements can be absent from the array. Count frequency of all elements that are present and print the missing elements.

Examples:Input: arr[] = {2, 3, 3, 2, 5} 

Output: Below are frequencies of all elements 

1 -> 0        2 -> 2        3 -> 2        4 -> 0        5 -> 1

Question: Get the next bigger number using the same digits of a number. 

Eg, For 123456, next number would be 123465

Question: Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 islands

Input : mat[][] = 

{{1, 1, 0, 0, 0},

 {0, 1, 0, 0, 1}, 

  {1, 0, 0, 1, 1},

  {0, 0, 0, 0, 0}, 

 {1, 0, 1, 0, 1}}

Output : 5

Question: Given two strings in lowercase, the task is to make them anagram. The only allowed operation is to remove a character from any string. Find minimum number of characters to be deleted to make both the strings anagram?

If two strings contains same data set in any order then strings are called Anagrams.

Examples:

 Input : str1 = "bcadeh" str2 = "hea"

Output: 3

We need to remove b, c and d from str1.

 

Input : str1 = "cddgk" str2 = "gcd"

Output: 2

 

Input : str1 = "bca" str2 = "acb"

Output: 0

Question: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Examples:

 

Input: arr[]   = {2, 0, 2}

Output: 2

Structure is like below

| |

|_|

We can trap 2 units of water in the middle gap.

 

Input: arr[]   = {3, 0, 0, 2, 0, 4}

Output: 10

Structure is like below

     |

|    |

|  | |

|__|_| 

We can trap "3*2 units" of water between 3 an 2,

"1 unit" on top of bar 2 and "3 units" between 2 

and 4.  See below diagram also.

 

Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

       | 

   |   || |

_|_||_||||||

Trap "1 unit" between first 1 and 2, "4 units" between

first 2 and 3 and "1 unit" between second last 1 and last 2

Question: Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

Insert

Remove

Replace

All of the above operations are of equal cost.

Examples:

 Input:   str1 = "geek", str2 = "gesek"

Output:  1

We can convert str1 into str2 by inserting a 's'.

 

Input:   str1 = "cat", str2 = "cut"

Output:  1

We can convert str1 into str2 by replacing 'a' with 'u'.

 

Input:   str1 = "sunday", str2 = "saturday"

Output:  3

Last three and first characters are same.  We basically

need to convert "un" to "atur".  This can be done using

below three operations. 

Replace 'n' with 'r', insert t, insert a

Question: Given a string with repeated characters, task is rearrange characters in a string so that no two adjacent characters are same.

Note : It may be assumed that the string has only lowercase English alphabets.

Examples:

 Input: aaabc 

Output: abaca 

 Input: aaabb

Output: ababa 

Input: aa 

Output: Not Possible

Input: aaaabc 

Output: Not Possible

Question: This problem is know as Clock angle problem where we need to find angle between hands of an analog clock at a given time.

Examples:Input:  h = 12:00, m = 30.00

Output: 165 degreeInput:  h = 3.00, m = 30.00 Output: 75 degree

Question:  How to find three element from 3 arrays that have sum of 0. What's the time complexity and space complexity of your algorithm.

Question: The difference of linked list and array. Time complexity of deleting and adding an element to linked list and array.  

Question:  how do you choose the best model among all possible models?

Question:  explain neural network

Question:  assumptions of linear regression model

6) if you have large number of predictors how to you handle them??

Question:  what if you have large number of positive observation vs few number of negative observations?  

Question: How to write a function to make a biased coin from a fair coin and vice versa

Question:  Describe some criterion for model selection? Why is dimension reduction important?

Question: The real question is they collected purchase record data at a store for the whole year, how to find the reason why customer walked into a store.

Question: What are the assumptions for using a logistic regression? What is the loss function for it? How would you build a recommendation system in certain scenarios?  

Question: Find the longest palindrome in a string. 

Question:  Write a function to merge k number of sorted lists. 

Question: How would you design Amazon's recommender system (from an algorithms stand point, not a technical one).  Designing recommendation system for amazon website, model choices, evaluation criteria, and reasons why these would be the best choice.  

Question:  find k largest number in an array

Question:  general classification problem - what about a case where there is a class with low prior.

Question:  Lots of questions about statistical inference, linear regression and logistic regression.

Question:  How can you find a unique list of customers who visited on day 1 and then came back for a visit on day 2? 

Question:  How does GMM/HMM work

Question: Name some dimensional reduction method; I said PCA and we talked a bit about how PCA works and what's the physical intuiation

Question:   How K-means work, what kind of distance metric would you choose, what if different features have different dynamic range

Question:  How GMM works (EM algorithm)  

Question:   Coding: search a 2D matrix

Question:  Explain: conditional random field

Question:  Coding: edit distance

Question:  Explain: EM algorithm

Question:  a general workflow optimization problem

Question:  Write a code to switch a k-th element with (N-k)-th element in a linked list of length N.  

Question:  find first n prime number

Question:  Given a bar plot and imagine you are pouring water from the top, how to qualify how much water can be kept in the bar chart.  

Question:  Given a table with three column, (id, category, value) and each id has 3 or less category (price, size, color). Now, how can I find those id's for which the value of two or more category matches to one another? For eg: ID1 (price 10, size M, color Red), ID2 (price 10, Size L, Color Red) , ID3 (price 15, size L, color Red) Then the output should be two rows: ID1 ID2

and ID2 ID3  

Question: Matrix with numbers start from top left and move to bottom left. You can move left or down. Maximize the total sum on your path op left and move to bottom left.  

Question:  Find common elements between two arrays that are sorted

Question:  Find rectangle within a matrix, starting at origin and giving the largest sum

Question:  find permutation of string s within another string b