n-ary tree serialize and deserialize question. Write both methods.
Design a thread-safe circular queue using fixed size memory allocation. Any type of data could be pushed in. No overwrite is allowed. Further: Optimize performance, can you do it without lock?
A^2+B^2+C^2+D^2= N. Given a N, print out all possible combination for ABCD. Can utilize DP?
Extract all the the combinations of a target substring that appear in a source string. I.e: target: "abc", source:"abcdefgbcahijkacb12df", solution: {abc, bca, acb}
Given a rotated sorted array, find where it is rotated
If you have a computer with no division operator, how do you do it
How to reverse the words in a sentence in place?
All the possible ways to find the minimum values in an unsorted array.
Design an efficient service that allocates phone numbers to mobile customers.
Design a HashMap
Find out whether parentheses are right in a string
Select K largest number from N
What's the difference between a non-exclusive lock and an exclusive lock?
Write a memory manager oriented towards millions of very small allocations (less than 10 bytes)
Write an algorithm to print out all the words in a boggle board
Given a list of sorted words, output the order of the letters used to sort them.
You are given 2 strings. Find all symbols that are in both strings.
You are given a BST-tree. Find duplicated values.
Design cache with LRU policy. Elaborate on performance. O(1) time complexity was expected.
Write an algorithm to decide the shortest path from one letter to another letter on TV's remote control.
find a path between two nodes in a graph
Find the maximum consecutive sum of integers in an array.
Implement iterator for a list of lists which may contain empty lists.
How to inorder traverse binary tree without recursion?
You are given an array that represents bills in certain currency (For example 1, 2, 5, 10) and an amount, for example 17. You should output the number of possible combinations of bills that sum to the given amount. For example, {10, 5, 2} is valid combination, {10, 5, 1 ,1} also.
I did not ask questions like does the order of bills matter, i.e. is {10, 5, 2} same as {2, 10, 5}.
Write a program that reads a file, randomizes it's lines and writes the output to another file.
Design a system or algorithm to catalog all of the worlds books?
Find the balance point in an array. (The index where the sum of the elements to the left it is the same as the sum of the elements to the right of it.)
I was given a number of intervals on the integer number line and had to write a program in Java that takes two sets of intervals and creates a set of intervals that combines them
What data structures would you use to model a family tree? How can you determine whether two persons are related or not?
Implement a function boolean matches(String text, String pattern) to find match pattern in the string, pattern can be separated but the order of letters in pattern cannot be changed.
Implement an interface to statistics the frequency of new value added.
Make an algorithm to extract the skyline from the rectangles.
Estimate the total storage size of GMAIL
Implement a blocking queue in Java.
Implement a system to serialize and deserialize strings
Design a 4-way software cache driver.
Compare HashTable and Binary Tree(pros and cons, why use binary tree in some place, the time complexity of insert, delete of hashtable and binarytree)
find the longest prefix
Find the intersection of two integer lists
If you have an unsorted array of numbers from 1-100, except 1 of those numbers is missing, how do you determine which number is missing
How do you implement a hash?
Remove duplicate lines from an large text
Out of 10 coins, one weighs less then the others. You have a scale. How can you determine which one weighs less in 3 weighs? Now how would you do it if you didn't know if the odd coin weighs less or more?
Given inputs from Google Search, you have K chunks. Each chunk is individually alphabetically ordered (apple, banana, cat) ... (*apple, *banan, *cat). You want to merge all chunks into a single list. How would you do it? What limitations are there to your approach?
How to find the max number of a shift buffer queue. For instance, there is an array like 5, 6,8,11,1,2, how to find the max number, which is 11 in this example.
Judge if a Sudoku solution is right.
Write a program to compute if one string is a rotation of another.
Given two sorted integer arrays, write an algorithm to get back the intersection.
Given the daily values of a stock, find how you can lose the most with one buy-sell trading.
Given a set of strings, a number 'n', and a function that takes a string and gives back a score, find the n largest scored strings in the set.
Describe what you will do to enhance the indexing performance of the map service.
Reverse all the words in a string
Quad tree
Write the binary search.
Analyze quick sort.
Game of Life - write a function to calculate next state of the board based on current state
You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum
Given an array of structs: write a function that finds equal values in all the structs in the array
Implementing a system for fast anagrams retrieval given a large file of words
You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum
Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).
Write a code to find out if two string words are anagrams
Create a graph class and graph traversal algorithms.
Maximum contiguous sub sequence sum problem.
What are the side effects of typing your password in the user name field?
Given a graph, find if it represents a tree
Card game, given 4 cards. If by +,-,/,* and () you can make 24, you win. Write a program to play this game.
Find a number in a sorted array with duplicates in O(log n) time.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Given a string of characters, find the character with the highest frequency
Design a networked 'snake' multiplayer game. What are the problems and issues to be solved? When the network 'splits' I want the game to continue for all players.
Write a function to convert a collection of strings into a single string and a function to convert it back.
Given a bitmap of open and closed cells, where you can traverse through open cells but not closed ones and a set of origin points on the bitmap, write a program to find the shortest path to every reachable open cell from any of the origin points.
Find the largest 100 numbers out of a list of a trillion unsorted numbers
Implement a stack that pops out the most frequently added item.
Write a function to perform incremental search
Given an unsorted array of integers, find first two numbers in the array that equal a given sum.
-
You have a 64bit integer counter set to 0. How long it will take to overflow the counter given that you are incrementing it at 4Ghz speed.
Comparisons of trees and hash tables. What are the tradeoffs of using one versus another.
Quickly estimate 2^64 without using a pen/paper.
Computing average power of last 5 minutes.
Serialize an array of integers in an arbitrary way. Imagine a 4x4 grid where the cells are visited in a snakelike pattern.
Given a list of integers, Print out all triples that sums to zero.
Write a function that will return the second longest string in a list of strings. You have to do a single pass on the list.
Given a 2D boolean array. Return the length of the biggest square where all elements inside it is true.
Implementing a system for fast anagrams retrieval given a large file of words
If you have a ransom letter and magazines, can you construct the ransom letter from the words in the magazine.
Discuss data structures for reading URL->File content (crawler data e.g.) and remove duplicates.
In a sorted array, find the number closest to a given number
Design the friend suggestion of facebook, write a code, complexity, reverse a sentence such that the ordering of words is reversed but the words aren't changed.
Explain pointer arithmetic
What guarantees does the synchronized keyword give when used on a method? When a thread calls the synchronized method, can another thread call a method that isn't synchronized on the same object?
Code game of life
Algorithm to get Index of a permutation when all permutations arranged in lexicographical order and its Complexity.
Discuss and implementation of flattening a binary search tree into string representations.
Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t. 2. Can we do better if we seek (x,y) for which x+y=t?
print out the powerset of a set. use any programming language you want.
Write a function that computes the intersection of two arrays. The arrays are sorted. Then, what if one array is really larger than the other array?
Imagine you are creating a program that can handle multiple requests at a time and respond to them as they come. Define run time, classes, and methods.
Find the number of connected components in a Graph.
Card game, given 4 cards. If by +,-,/,* and () you can make 24, you win. Write a program to play this game
Implement B+tree
How can you optimize the code written for B+ tree.
Create a Java method that clones a DAG (Directed Acyclic Graph).
Given a tree and leaf node, write the code to make the leaf node as root of tree.
Write the code to check if graph is bipartite or not?
Write a stack that keeps track of min and max elements.
Write a priority queue<E> with three methods. Insert(E Element, int priority). E Pop(), update(E Element, int new_priority)
Giving a windows size K and an array of size N, find the minimum of each window as it slides through the array
Write the code for "moving of the robot": there is a "generator" -- each time generate 1/0, when 1 the robot will move up, when 0 will go down, write the function to make the robot move up forever.
Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.
Design the battle ship game
Btree traversal
Write code to shift a string with rotation [a, b, c << 2 = c, a, b]
Write classes representing expression tree for a simple calculator. You care only about constants and basic binary operators. Write function evaluating expressions.
How to count frequencies of characters in a string. What if the string is too huge? When is it reasonable to distribute across machines? How to find the most frequent character in the distributed scenario with a minimum data exchange between machines?
Convert a one dimensional array of Strings containing [a,b,c, d,e ...z] to 2 dimensional array of a2[aa,bb,cc]
Find the next larger node and write down code in BST
Search smallest value from a tree. What if you have enough memory, how to improve the speed?
Make an algorithm that, having N cards in N+1 slots (one slot empty), reach a final configuration (given initial one), showing all the steps. A move is valid only if it is moving one card from to the empty spot (letting the card's place now empty).
Find the number of inversions in an array (describe & code)
Find collinear points in a given set of 2D points (describe & code)
How much ways is it possible to use to go on the top of stairs with n stairs if we can go up by 1 or 2 steps?
write a string splitting function that did not copy the string
How to build a distributed algorithm to compute the balance of the parentheses?
Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t. Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t.
You are given a text file too large to fit in memory and 3 strings A, B, C. For each string, you have a sorted array listing the positions of the string in the file (e.g., inverted indices). Find the smallest window containing the 3 strings. Order of appearance does not matter.
Many questions about advanced C++ language features such as solutions to the "diamond" multiple inheritance problem and how to implement a virtual constructor.
Remove a node from a singly linkedlist without knowing the head node. All you have is the node itself.
If you had a list of appointments (each appointment has a begin time, an end time, and a boolean hasConflict), how would you efficiently go through them and set the hasConflict boolean for each. You cannot assume they are sorted in any way. Keep in mind that one appointment may be very long, etc.
How do you find the median of a set of numbers?
What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
How would you sort a file which is too large to fit in memory.
Given a directory with lots of files, find the files that have the same content (the file names are different). I think file format is not considered, since when I said the size of the file with the same content should be the same, the interviewer did not deny it.
Partition an array in such way zeros to be moved on the left side of the array, other numbers on the right side of the array. Extra storage not allowed, only in-place.
write code to find the second shortest path between two given nodes in an undirected graph.
You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.
How would you sort a file which is too large to fit in memory.
What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
when you are doing "read()" call what it happening under the hood in user space?
Given two binary search trees, write function which tells if two such trees are the same – (i.e. same info in the nodes, same branching to left and right at every node).
How to find a median in a large file of 64-bit integers
Input is a 4x4 table with letters. One starts from any of the 16 elements and can move in one step to any of the 8 neighboring cells not visited before (up, down, left, right, up-left, etc, no hyperspace jumps between rows 1 & 4, columns 1 & 4). Every time step is made letter in that cell is added so a word is built as we walk. These generated words are looked up in external dictionary (function to look up in the dictionary is provided, I did not understand significance of this dictionary well) and the goal of the exercise is to output all words generated by all possible table walks and which are contained in the dictionary.
It is a phone interview. Given a box of pencils with different colors, design an algorithm to find the duplicate pencils with the same color
write code to find the second shortest path between two given nodes in an undirected graph.
What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.
We can calculate the variance of a set of number by first finding the average and then getting square of the differences with each number. Another way of doing this is to actually find the summation of square of all the numbers and then deducting an expression involving square of the average. The question was, what the flaw of using the second approach.
Remove a node from a singly linkedlist without knowing the head node. All you have is the node itself.
Partition an array in such way zeros to be moved on the left side of the array, other numbers on the right side of the array. Extra storage not allowed, only in-place.
Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.
Given a directory with lots of files, find the files that have the same content (the file names are different). I think file format is not considered, since when I said the size of the file with the same content should be the same, the interviewer did not deny it.
Write an algorithm to test if n is power of 2
Given 2 numbers x and y, check if x is an integer power of y. For instance, x = 8, y = 2 would return true and x = 10 and y = 2 would return false since the first one is an integer power but the second isn't.
Given a dictionary of words, decrypt it using a given decrypt() function
If you had a days worth of queries, how would you sort the queries by the letter q, and then return a sufficiently random sample of 1000 queries. How do you ensure randomness?
Design an algorithm, which can record the largest number in an ever-upgrading sequence.
How to choose pivot in quicksort
What happens when you enter a search query on google ? ideas about sorting results ?
Reverse a linked list in place
The mouse in the maze problem. Shortest paths to reach outside
Reverse the bits in a 32 bit integer. Write C code for that.
Given a search terms, find the minimum window containing all the words
Given a grid that contains rectangles, write a function that will return all the rectangles that overlap with each other.
Suppose you have an arbitrarily connected graph with n nodes. Come up with an algorithm to identify each set of connected nodes (i.e. identify all the islands in the graph). What's the complexity? Can you find a solution in O(n log n)?
Sort the entries in database in single pass?
How would you implement Google spelling correction algorithms?
Implement a method that matches an entire string with star wildcard pattern, e.g. returns true for ("*ogle", "Google"), but false for ("fragile*", "agile") - without using regular expression language support.
Print all shortest paths in a grid (Cartesian), given the starting and the ending point.
Write code to check the validity of a suduko square
Implement the Iterator pattern with a class that will be constructed using two iterable objects and that will iterate through the elements of both objects
Give the descending order of the following 4 terms, assume that n is infinite. n!(n factorial), n^n, 2^n, n^(google)
Convert decimal number 99 to base 7.
Design the back-end for facebook.
Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection.
efficiently search for an input word in an unbounded dictionary.
Imagine dropping a Rubik's Cube into a bucket of paint. How many of the cubes will get paint on them?
Given a function double f(double x), 0<=x<=1, f(x) is increasing. f(0)<0, f(1)>0. Find x s.t. f(x)\approx 0.
What is the fastest way to sort 1 million integers when integers are from the range [1,100]?
How would you count the frequency of letters in a word/ file?
Writing the code to convert numeric amount of price into English words.
Given the pre-order and in-order traversing result of a binary tree, write a function to rebuild the tree.
How to reverse a tree
How would you write a sort routine to ensure that identical elements in the input are maximally spread in the output?
Design a utility similar to Google suggest. How can you do it?
write a function to calculate X^N
use mutex and semaphore to implement producer-consumer problem
There is a parking lot of cars that is full except for a single spot. Write some code to take it from one arbitrary configuration to another moving only one car at a time into the empty spot. Analyse the time complexity, how would you improve it, etc.
design algorithm to reverse the content in the memory.
Find the maximal and minimal number in an array of integers
How many rotations does earth make on its axis while going around the sun for one year.
Given a list, return the first pair of duplicates in the list.
Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array?
Given unsorted sequence of billions of numbers that cannot all fit in memory at the same time, find the median of these values.
No comments:
Post a Comment