smarthbehl
BAN USER- 2of 2 votes
AnswersGiven an array of positive integers(>0) , you have to insert '+','*','(',')' signs basically plus multiply and brackets such that value of resultant expression becomes maximum.
- smarthbehl in United States
Hint: Consider case of continuous ones
You have to print the resulting expression| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 1of 1 vote
AnswersGiven an array consisting of N Numbers.
- smarthbehl in United States
Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.| Report Duplicate | Flag | PURGE
Google Software Engineer
Assumption: Both A and B has same number of digits
1.) Make an array with 10 entries {0,9}
2.) Parse through A and increment count of each digit in array as it occurs
3.) Start parsing through B , let say first digit is D1 , try to find the digit larger than D1 from array made in 1 , this at max is 9 steps (so O(1) ) .
If there is a digit then make that the current digit of larger number and rearrange remaining digits from array in step 1
If there is no digit greater than
check if there is a digit equal to D1 ,
->decrement count for array formed in step 1
-> for new digit first digit is D1
else not possible
We can use hashing to support first 3 operations in Θ(1) time. How to do the 4th operation? The idea is to use a resizable array (ArrayList in Java, vector in C) together with hashing. Resizable arrays support insert in Θ(1) amortized time complexity. To implement getRandom(), we can simply pick a random number from 0 to size-1 (size is number of current elements) and return the element at that index. The hash map stores array values as keys and array indexes as values.
Following are detailed operations.
insert(x)
1) Check if x is already present by doing a hash map lookup.
2) If not present, then insert it at the end of the array.
3) Add in hash table also, x is added as key and last array index as index.
remove(x)
1) Check if x is present by doing a hash map lookup.
2) If present, then find its index and remove it from hash map.
3) Swap the last element with this element in array and remove the last element.
Swapping is done because the last element can be removed in O(1) time.
4) Update index of last element in hash map.
getRandom()
1) Generate a random number from 0 to last index.
2) Return the array element at the randomly generated index.
search(x)
Do a lookup for x in hash map.
Store Graph as follows
class GraphNode{
public int value;
Hashset<GraphNode> neighbours;
}
//Add all graph nodes to a list or something
Now go to each graph node and among its neighbours , which are say N
try to find two neighbours which are neighbour of each other , this forms a triangle.. this will be N square for each node having N neighbours , so worst case graph with N nodes having N-1 neighbours each , N^3 is the solution
In an array of length N you have numbers in range 1 to n-1 , there will always be a duplicate by pigeonhole principle.
Now if you have to find one duplicate it is easy.
1.) Start with temp = 0; and do a while true loop
2.) If value at array[i]=-1 then i is the duplicate number and return.
3.) else
set temp = array[array[i]];
array[array[i]] = -1;
int temp=0;
//there will always be a duplicate by pigeonhole
while(true){
if(arr[temp]==-1) return temp;
temp = arr[arr[temp]];
arr[arr[temp]] = -1;
}
Let us do an inorder traversal of Binary Tree (Its not BST so no sorting) and store pointer to all the nodes in array indexed from 0 to n-1 -> Space Complexity = O(n) .
Now select the random number between 0 to n-1 and return that node in O(1)
1.) Starting from a very basic implementation we can have a trie or suffix tree , each node of trie maintaining a LRU cache to support trends in auto complete as well.
The actual solution will be much more complicated than this
You can probably enqueue a video id , each time video is viewed and some background process can pick items from queue and can maintain dictionary which it increments every time a video is picked and can write back to DB when dictionary reaches a certain size.
Since counts are always increasing so if multiple copies of background processes can run
Maintain LinkedIn Persons as GraphNode and a connection as an edge from one graph node to another.
Now Do a breadth first search and while enqueuing connection in queue store the level as well .. when you find the desired person you will know its level also
BASICALY BFS
class Person{
Hashset<Person> friendList = new Hashset<Person>() // like a hashset
}
class Thing{
HashSet<Person> LikedBy = new HashSet<Person>();
}
// Now when someone like Thing T , add that person to hashset of T and if likes are greater than friends of person who likes T then iterate through friend list of person and Find if they exists in hashset of T or vice versa
-- Use union find algorithm to find if there are cycles in graph , if not then
1.) Create a directed graph from A->B if B is dependent on A.
2.) Keep set of vertices which have no dependencies, basically no incoming vertices
Then run Topological sort
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
int findValueClosestToX(TreeNode root, int x)
{
if(root==null) return null;
if(x==root) return root.val;
if(x-root>0)
{
if(root.right!=null)
{
int valReturn = findClosestToX(root.right,x);
return (Math.Abs(x-valReturn) > x-root.val ? root.val :valReturn );
}
else{
return root.val;
}
}
else{
if(root.left!=null){
int valReturn = findClosestToX(root.left,x);
return (Math.Abs(x-valReturn) > x-root.val ? root.val :valReturn );
}
else{
return root.val;
}
}
}
1.) Given two sorted arrays of Size N1 and N2 , you have to find the element at Kth position when both are merged.
2.) Take the element at index k*N1/(N1+N2) from array with size N1
i.e int N1Mid = k*N1/(N1+N2)
Now from second array take int N2Mid = K-N1Mid-1
3.) Now if N1[N1Mid] > N2[N2Mid] , search on right side of second array i.e from N2Mid To End and left side of first array N1Start to N1Mid-1 (like Binary Search) ... reduce k by number of elements left in second array
else do the other way around , seach on right side of first and left side of second reduce K
4.) Keep on doing this recursively
Here is the code
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
You can use something like a suffix tree for better results.
For a simple answer you can use trie
84 gb instead of 840 gb <Correction above>
- smarthbehl July 14, 2015For 7 billion people representing phone number as 12 bytes 10bytes + international code , you will need 70 billion bytes minimum 1 million = 1 mb , 70 billion=70000 million , 70 gb *12 = 840 gb... Average ram size is 8gb so you cannot store all this information in memory ..
You will need a distributed data structure, may be something like a distributed hash table.
1.) Given a song name , split the words from song name.
2.) Insert word in Trie if it doesn't exist, Trie as a data structure should have at each node , a list of songs.
3.)So when you insert Every and Everything
Each node till y in Every should point to list of two songs and after y should point to one song only.
An Idea may not work
- smarthbehl August 27, 20151.) Find the minimum and maximum in the array , Range of array is maximum - minimum
2.) Number K should always lie within this range to give adequate results.
3.) Now find the middle of range (maximum - minimum)/2 , and add this to minimum value , we get the middle of this range.
4.) Now find differences for middle , middle-1, middle+1 , and use the idea of binary search on this range ... i.e take search from minimum to middle-1 or search from middle+1 to maximum , which ever gives less sum