- A period of time where users login and logout, given a sets of login
and logout time pairs, write a function that can show the number of
users online at any given time.
- Intersection of n sets without using a hash table.
- Implement a LRU(Least Recently Used) cache
- Implement a function to compute cubic root
what is the time complexity?
- Given a matrix with 1′s and 0′s, find the number of groups of 1′s. A group is defined by horiz/vertically adjacent 1′s.
- Given a matrix of numbers in which some may be zero. If a cell
contains a zero, set all the cells in the corresponding column and row
to zero.
- You are given a set of numbers 0 – n. Given a k, print all subsets of size k. Give the time complexity of the algorithm.
- Given an unsorted array of integers, find a 3-element subset that sums to zero..Complexity…?
- Multiply two big integers which don’t fit into an built-in integer
type. How would you represent big numbers as a data structure? Write the
function to multiply two big integers.
- Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0
- How to implement Sqrt(double k) efficiently? OR Compute the square root of a number down to a certain precision.
ie sqrt(num, precision) returns a number that is in-between sqrt(num) – precision and sqrt(num) + precision.
- How to implement multiple inheritance in Java
- Given set of coins and each coin has its unique probability to be
head up, say double[] probs stores the probability values for all coins,
print out all different cases and accordingly probability.
- Find the min and max in an array. Now do it in less than 2n
comparisons. (they were looking for the solution that finds both max and
min in about 3/2 n comparisons).
- FInd the maximum sum of a sub-sequence from an positive integer
array where any two numbers of sub-sequence are not adjacent to each
other in the original sequence. E.g 1 2 3 4 5 6 –> 2 4 6
- Given an array of integers, now we want to erase all 0′s (can be
other value), and we want the result array condensed, meaning no empty
cell in the array.
- given a list of words with a same size and a big string that
contains one of the permutation of all the words combined(say p), find
the startindex of the string p in the big string
- Reverse a Linked list (Recursively/Non recursively)
- Write the actual code to parse a regular expression including “*”,
which stands for 0 or more characters, “+”, which stands for 1 or more
characters, and “.”, which stands for 1 exact character.
- print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3
- search needle in haystack problem. Make it more robust.
- Implement a function rotateArray(vector arr, int r) which
rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives
4 5 1 2 3.
- Implement a function string balanceParanthesis(string s); which
given a string s consisting of some parenthesis returns a string s1 in
which parenthesis are balanced and differences between s and s1 are
minimum.
Eg – “(ab(xy)u)2)” -> “(ab(xy)u)2″
“)))(((” -> “”
- All Possible balanced parenthesis problem
- How will you design TinyUrl?
- How will you design facebook newsfeed. Focus was on a design which
could handle the huge number of status updates and display them on each
of the user’s friend’s wall.
- Implement a function
char* readLine();
which returns single lines from a buffer. To read the buffer, you can makes use of a function
int read(char* buf, int len)
which fills buf with upto len chars and returns the actual number of
chars filled in. Function readLine can be called as many times as
desired. If there is no valid data or newline terminated string
available, it must block. In order to block, it can use read function
which in turn will block when it doesn’t have anything to fill the buf.
- Find Kth smallest element in a BST.
- Implement a queue data structure given only stacks. What is the time complexity of enqueuing and dequeuing operations?
- Given a Binary Search Tree, iterate over the elements without using recursion.
- Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and
an input integer, what is the best way to organize the data and allow
for quick search based on the input, etc.
- Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.
- Print a singly-linked list backwards, in constant space and linear time.
- Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).
- Given a set of words, group them into sets of anagrams.
- Given a string, remove all the duplicate characters (not necessarily consecutive)
- Write a function to tell if two line segments intersect or not.
- Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ).
- Write a function that computes log2() using sqrt().
- Given a list of n objects, write a function that outputs the minimum
set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln
n)?
- Write a function to prettify Json objects
- Given sorted arrays of length n and 2n with n elements each, merge first array into second array.
- You are given intervals of contiguous integers, like [1, 10), [15, 25), [40, 50), which are non-overlapping and of a fixed size.
Design a data structure to store these intervals and have the operations of insert, delete, and find functions
- Design a system to detect typos and provide suggestions to users.
Design and implement an algorithm that would correct typos: for example,
if an extra letter is added, what would you do?
- Find the n-th smallest element in a binary tree.
- Print a binary tree in infix order. Recursive and iterative.
- Design the Facebook Credit system which is a application where users
can buy/trade virtual currency and can use the virtual currency to
purchase Facebook services, like paid apps.What's the advantage of the design?How would the total credit points of a user be calculated based on my design?
- Write a code to convert an ASCII representation of a positive integer to it's numeric value.
- Write a function to take two arbitrarily long numbers in the form of
Strings and multiply them, returning another String with the product.
- Given a binary tree, write a function to find the length of the longest path in the tree.
- Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
- Find the minimum depth of binary search tree.. http://www.glassdoor.com/Interview/Find-the-minimum-depth-of-binary-search-tree-QTN_127018.htm
- Print a binary search tree. Each level on a new line.
- Implement the div operator without using / or %
- You are trying to rob houses on a street. Each house has some +ve
amount of cash. Your goal is to rob houses such that you maximize the
total robbed amount. The constraint is once you rob a house you cannot
rob a house adjascent to that house.
- Given a matrix print it clockwise from the first element to the very inner element.
- Given an array of integers and size find 3 integers that sum to zero.
- You are going to take some numbers as an input from a file. You need
to witer a program to find longest increasing sequence. You should
process it as soon as you are taking an input. After finishing the last
input immediately you should be able to tell the sequence.
Input: 1 5 3 4 6 4
Output: 3 4 6
- A file contains 10 billions of Strings and need to find duplicate
Strings. You have N number of systems available. How will you find
duplicates?
- Given a set of integers, print out all its subsets.
- Code a program to check if a given string is matching a given regular expression
- Each key on the telephone represents a list of letters. Given a
telephone number, please write a program to output all the possible
strings the telephone number represents.
- write a function to check if a graph was bipartite.
- Given two binary trees, return true if they have same elements (irrespective of tree structure)
- Given a string, remove all chars from the string that are present in say another string called filter.
- Given two events, each with a start and end time, implement a boolean check to see if they overlap.
- Print out all combinations of k numbers out of 1...N
e.g. when k = 2, n = 4
Print out 12, 13, 14, 23, 24, 34
- runtime complexity of binary search and the average num of guesses
it takes to find a number between 1 to 1000. Given the numbers 1 to
1000, what is the minimum numbers guesses needed to find a specific
number if you are given the hint "higher" or "lower" for each guess you
make.
- Advantage of B Trees - Used in databases for indexing. Adv. Less
number of memory lookups because of less hierarchy. Large fanout.
- Given a set of inputs in a log file:
log:
example:
1,2
1,1
2,1
3,1
1,2
out:
1,2
2,1
3,1
The output should be all the unique numbers and the count associated with them.
- Given an array, print the largest subarray that has elements in an increasing order
- How do you find sequences of consequtive integers in a list that add to a particular number.
- Given a score S, and individual points p1,p2,...,pn. give all combinations of p that add up to s.
- Given a large string (haystack), find a substring (needle) on it.
- Given a list of strings, for each string, find if it has an anagram in the list.
- Function to compute the number of ways to climb a flight of n steps.
Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant
space.
n = 3.
1 1 1
1 2
2 1
3
Ans = 4
- Interweave a linked list. Do it in Linear time and constant space.
Input: A->B->C->D->E
Output: A->E->B->D->C
- Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping.
Input: face
Map: {a -> @, 4, A}
Output: f@ce, f4ce, fAce
- Get numeric number out of a roman string, linear time
Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
Input/Output:
II = 2, III = 3, IV = 4
VI, VII, VIII
IX = 9
XL = 40,
XLIX = 49
- Merge 'k' sorted arrays, each array may have max 'n' elements
- how does hash map implementation looks like
- Implement strstr in C
- Write some pseudo code to raise a number to a power.
- Given an array of integers, find the maximum number that can be
reached by summing the best possible consecutive subsequence of the
array.
- Design a linked list operation that takes a singly-linked list (only
forward ptrs, no backward ptrs) as input and reverses the list.
- Given a 1TB file of serialized 4 byte integers, and 2GB of ram, sort
the integers into a resulting 1TB file. My interviewer was very
collaborative in entertaining various solution ideas until we came up
with a combo that would work performantly and reduce the number of
passes over the 1TB file and intermediate files.
- Write a list class where the only data structure available is a stack
- Determine the 10 most frequent words given a terabyte of strings.
- Use basic arithmetic operations (+-*/) to implement sqrt function.
- Print out all the permutations of a string
- Write a function that prints out all subsets of a given set of numbers.
- Write a function that takes in two binary strings and returns their sum (also a binary string).
- Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.
- Generate a new array from an array of numbers. Start from the
beginning. Put the number of some number first, and then that number.
For example, from array 1, 1, 2, 3, 3, 1
You should get 2, 1, 1, 2, 2, 3, 1, 1
Write a program to solve this problem.
- given the utitlies getFriend(User u) and areFriends(User u1, User
u2), write the function which takes as parameter the array of users and
return a bool saying if you can divide the users in 2 groups s.t. if u1
and u2 both belong to a certain group, they are not friends.
- remove duplicates in a string.
- Given a file with 3-letter words, print all 3x3 with each row, column and diagonal being one of the words from given file.
- Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph).
- Given n+1 buckets with n of them with ball inside and move(a,b)
function, that moves ball from bucket a to bucket b. Each ball has a
different number from [1,n] on it. Move balls, so each bucket has a ball
with matching number in it.
- Implement a power function to raise a double to an int power, including negative powers.
- Given a String containing java-script assets, write a parser which will output the String with proper indentation.
- Given a certain state of an Othelo game board, location on the
board, a certain piece to place on the given location, update the board
and make the required validations
- Given a collection of words, return a collection of anagrams found in the
given collection
- Output a single linked list in reverse, in linear time and constant space, and recursively
- Pascal’s Triangle – print a row
- Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).
0 comments:
Post a Comment