teli.vaibhav
BAN USER- 0of 0 votes
AnswersSearch for a sorted integer in an integer array that has been rotated multiple times.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Samsung Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersGiven an alphabet where we do not know the order of the letters also do not know the number of letters.
- teli.vaibhav in United States
We are give an input list of tuples where each entry in the list gives an ordering between the 2 letters
Determine the alphabet order.
Ex-
<A, B>
<C, D>
<C, E>
<D, E>
<A, C>
<B, C>
Order is A, B, C, D, E| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
AnswersHow would you design Amazon Lockers?
- teli.vaibhav in United States
Amazon Lockers - Customers can use these lockers to have their products delivered. These lockers are physically available to customers at the same or several nearby zip codes.| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersThe amazon site was working just fine until yesterday. But in the past 24 hours processing the customer orders is taking a really long time.
- teli.vaibhav in United States
How would you debug and fix the issue?
When I asked if anything had changed in the past 24 hours, I was told several new products had been added after which the performance issues were noticed.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Debugging - 3of 3 votes
AnswersGiven the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
- teli.vaibhav in United States
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersYou are given 2 lists -
List 1: List<Demand> is a list of Demand objects.
List 2: List<Supply> is a list of Supply objects.
Return a result fulfillment List<Demand,List<Supply>>.
This means each demand could be satisfied by more than one supplies.class Demand { Date startDate; Date expirationDate; int quantity; } class Supply { Date startDate; Date expirationDate; int quantity; }
The Demand and Supply refers to that of groceries. You must map supplies to a demand only if the supply still has at least 3 days remaining to its expiration before the demand can be fulfilled.
- teli.vaibhav in United States
A demand is said to be fulfilled 24 hours after all demands have been mapped to correspondingly available supplies.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswerWrite code for the partition subroutine in Quicksort.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswerHow would you Design a HashTable?
- teli.vaibhav in United States
In what ways would you attempt to address collisions?| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersFor this problem, we would like you to think of a single line of text, and justify that text into a buffer,where the first character of the line of text is in the first spot in the buffer and the last character of textis in the specified slot in the buffer.
In ruby, you might define this function as follows:def justify(line, length)
It might be called like this:
puts justify("The quick brown fox jumps over the lazy dog.", 52)
It produces a string that looks like this:
- teli.vaibhav in United StatesThe quick brown fox jumps over the lazy dog. 1234567890123456789012345678901234567890123456789012 (You have 7 characters remaining in the buffer)
| Report Duplicate | Flag | PURGE
RealSelf Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is indexing in a database?
- teli.vaibhav in United States
What are the underlying data structures you think are involved in indexing of a database?
What are some upsides and downsides of using indexing?| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of integers. Find the surpasser count of each element of the array.
- teli.vaibhav in United States
"A surpasser of an element of an array is a greater element to its right"
ex -
Input: [2, 7, 5, 3, 0, 8, 1]
Output: [4, 1, 1, 1, 2, 0, 0]| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the first unrepeated character in a given string. Solve this in a single pass.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
- teli.vaibhav in United States
ex-
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven a string which may contain parenthesis. We must verify the validity of the string.
- teli.vaibhav in United States
ex-
1) "<ad675+-fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question -
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex - <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
- 1 Answer Printing all permutations of a String with repeated characters
I wanna print all permutations of lets say a char[] array for simplicity. This array contains a few repeated characters.
- teli.vaibhav December 17, 2013
I need to get the result without going into any previous results.
ex- say we have ['a','c','a','b']
I will print "aacb" when I encounter is the first time and I must not print it the second time, neither can I look into the previous result.| Flag | PURGE - 0 Answers Time and Space complexity
Could someone tell me what the time and space complexity of an iterative + recursive algorithm would be?
- teli.vaibhav December 15, 2013
ex:-
The following code snippet prints binary sequences. i.e if n=2,
The output is
00
01
10
11
public static void printBinarySequence(int n)
{
if(n<0)
return;
int[] temp = new int[n];
printBinarySequenceAux(n,0,temp);
}
private static void printBinarySequenceAux(int n, int d, int[] temp) {
if(d==n)
{
printArray(temp);
return;
}
for(int i=0;i<=1;++i)
{
temp[d]=i;
printBinarySequenceAux(n,d+1,temp);
}
}| Flag | PURGE - 7 Answers Space complexity for Recursive Binary Search
Space complexity for Iterative Binary Search would obviously be O(1) but with the recursive algorithm I believe the stack would use O(log n) space. However, everywhere I read I see the worst case complexity for BS O(1). Could someone please help me understand.
- teli.vaibhav November 07, 2013| Flag | PURGE
Beautiful..
- teli.vaibhav May 03, 2014SOAP requires the knowledge of an API which leads to the resource. This is generally a WSDL.
REST involves directly interacting with the resource using simple HTTP methods like GET,POST,PUT,DELETE,etc.
Simply search for the root node of the smaller tree in the larger one. Once that is found, do a simultaneous traversals as the follows :
eq(t1, t2) = t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)
By doing this you can break once equality fails.
Complexity in the worst case is still O(m+n). However, the average case is much better.
1) Abstraction
2) Encapsulation
3) Polymorphism
4) Inheritance
1) ArrayList is preferred when the search we are looking for is random index based.
2) LinkedList is preferred when we have require to perform several add and delete operations anywhere in the list.
3) There is more memory overhead in case of LinkedList as the data is an Object (data+node) whereas only data in the case of ArrayList.
4) ArrayList has an Array implementation internally which is of size 10 by default. This makes addition of elements relatively faster in LinkedList as there is no resizing.
5) Iteration is relatively faster in the case of ArrayList as the memory locations are ordered.
Infinite number of elements but you can choose to implement the Queue yourself and place a restriction on the max number of elements you wanna be able to add.
So you had a Google and Microsoft interview on the same day!
Either a weird coincidence or some simple homework.
Store both the numbers in char arrays and perform addition of individual chars from the last to the first index in both the arrays with the appropriate carry.
It looks lame for google standards but is all I can think of :)
There are 256 ASCII characters if you include the extended ones. :P But since this question was asked at Infosys I doubt if the interviewer thought so much.
- teli.vaibhav January 06, 2014You are making the assumption that all characters belong to the english language.
- teli.vaibhav January 06, 2014I'm not sure about C but simply use a HashMap in Java.
- teli.vaibhav January 06, 2014Sort the smaller of the two given arrays. O(log n)
Use Binary Search to search each element for the other array in the sorted one.
Total Time complexity O(n*log n + m*logn)
Hey can you please explain what you mean by being put into the constant pool in the .class file and when this happens. The first thing I said to myself after looking at the question was 5 objects would be created. Clearly I am missing out on something conceptual here.
- teli.vaibhav November 11, 2013What is that supposed to mean?
- teli.vaibhav November 10, 2013lol
- teli.vaibhav November 08, 2013Simply build a Max Heap.
T.C
O(n) + O(log k)
=> O(n) overall.
There is nothing like left and right in a BTree. The number of branches from a node depend on the order of the tree.
- teli.vaibhav November 03, 2013Don't read too much into it dude. Just found something, figured the intention of the question and attempted it.
- teli.vaibhav November 01, 2013Also, the stack solution gives you O(2*m*n). Although 2 is too small and is ignored for large values. You will ultimately end up spending more time.
- teli.vaibhav October 28, 2013I posted the code below. Its simple in-place swapping. It would save me O(m*n) space when either m or n are large.
- teli.vaibhav October 28, 2013On second thoughts, it would be more impressive to come up with your stack solution first and then to point out there was a way the same time could be achieved inplace (O(1) space) and that if 'n' was huge you'd prefer the latter.
- teli.vaibhav October 28, 2013Apologies, I just realized the solution was expected in C#.. lol
- teli.vaibhav October 28, 2013Using a stack would use extra space. Why waste the space when it can be avoided and the problem can be in the same time.
- teli.vaibhav October 28, 2013A straight forward solution in O(m*n) time and O(1) space :
public void modifyArray(char[][] inputArray)
{
if(inputArray == null)
return;
int maxRow = inputArray.length-1;
int maxColumn = inputArray[0].length-1;
int iIndex1= 0;
int jIndex1 = 0;
int iIndex2= maxRow;
int jIndex2 = maxColumn;
while(iIndex1<=iIndex2)
{
jIndex1 = 0;
jIndex2 = maxColumn;
while(jIndex1<=maxRow)
{
if(iIndex1 == iIndex2 && jIndex1 == jIndex2)
return;
swap(inputArray,iIndex1,jIndex1,iIndex2,jIndex2);
jIndex1++;
jIndex2--;
}
iIndex1++;
iIndex2--;
}
}
private void swap(char[][] inputArray, int iIndex1, int jIndex1,
int iIndex2, int jIndex2) {
char temp = inputArray[iIndex2][jIndex2];
inputArray[iIndex2][jIndex2] = inputArray[iIndex1][jIndex1];
inputArray[iIndex1][jIndex1] = temp;
}
This solution would work for any (m*n) 2-d char array.
- teli.vaibhav October 28, 2013@swapnil: Your solution isn't complete. You just found the sum of the A.P in O(1) time. But to find the missing term, you must iterate through the entire array and then find the real sum. The difference of the 2 sums would give you your missing term.
However, all this in O(n).
rdx's solution on the other hand is very elegant.
Exactly what came to my mind.
You could construct a multiple Trie structure as follows :
The last node of each country in the CountryTrie would contain an object that maintains the count of the visit + another StateTrie object maintaining the states for the country.
And each state in the StateTrie would similarly contain an object maintaining a CityTrie+count.
I'm guessing this would save us a lot of space.
@anuj : Read the solution again.
- teli.vaibhav October 27, 2013I found a very nice explanation somewhere, so am pasting it here :
A process is an executing instance of an application, for example when we double click on MSWord, a process is launched. A thread on the other hand is only a path of execution within a process.
A process can contain multiple threads. When you start Word, the operating system creates a process and begins executing the primary thread of that process.
A thread can do anything a process can do. But since a process can consist of multiple threads, a thread could be considered a ‘lightweight’ process. Thus, the essential difference between a thread and a process is the work that each one is used to accomplish. Threads are used for small tasks, whereas processes are used for more ‘heavyweight’ tasks – basically the execution of applications.
Another difference between a thread and a process is that threads within the same process share the same address space, whereas different processes do not. This allows threads to read from and write to the same data structures and variables, and also facilitates communication between threads.
Using a Trie would make a lot of sense here.
Say what you desire to store are phone numbers, at the leaf nodes we could save the name of the contact.
This would enable us with a quick search (number based) , add or delete/edit operation in optimized space.
I am guessing further applying some compression algorithm over the Trie could further optimize the space usage.
Please correct me if I'm wrong.
Isn't that better than not synchronizing it and winding up with more than one instances of the class?
- teli.vaibhav June 08, 2013I dont think we are asked to find the frequency of a given word in a sentence here.
There needs to be a clarification on what is the meaning of number of 'a' words in the question.
We could consider using two BloomFilters here, one for each file.
And since BloomFilters are not 100% accurate. We could compare the resulting BloomFilters of both the files if they match close to say something like ~97% (value depending on the efficiency of the HashFunction) then we could say they are identical.
Please correct me if I'm wrong.
This could be done in one scan.
We use 2 pointers evenRef and oddRef.
evenRef points to the first element of the array and oddRef to the last.
Now we increment and decrement the even and odd references respectively according to the element we encounter in the array and make appropriate swaps.
This process is repeated until both the references meet.
public static void reArrangeArray(int[] inputArray)
{
int n = inputArray.length;
int evenRef=0,oddRef=n-1;
while(evenRef<oddRef)
{
while(inputArray[evenRef]%2==0)
evenRef++;
while(inputArray[oddRef]%2!=0)
oddRef--;
swapAtIndices(inputArray,evenRef,oddRef);
evenRef++;
oddRef--;
}
}
private static void swapAtIndices(int[] inputArray, int evenRef, int oddRef) {
int temp=inputArray[evenRef];
inputArray[evenRef]=inputArray[oddRef];
inputArray[oddRef]=temp;
}
Please correct me if I'm wrong.
- teli.vaibhav June 05, 2013I can think of a simple solution..
XOR all lines and save the result in a variable 'res'.
If n is odd,
answer=res
If n is even,
if(line1.equals(line2))
answer=res^line1
else
answer=res^line3.
it would work if the given 'n' is odd..
- teli.vaibhav May 25, 2013elegant..
- teli.vaibhav May 10, 2013Using Tournament tree would be O(n) time complexity but the number of comparisons would be minimum..
- teli.vaibhav May 05, 2013'A' and 'N' i mean..
- teli.vaibhav April 22, 2013I think only 'A' must be the input.
- teli.vaibhav April 22, 2013Thanks so much for pointing that out. I have edited it appropriately now. Please check and let me know if any issues.
God knows it wasn't easy! :-)
Feel free to propose a better solution..
- teli.vaibhav April 21, 2013Nope it is not recursion for sure..
- teli.vaibhav April 21, 2013Simple Recursive solution:
public void printBorder(TreeNode root)
{
System.out.print(root.element+ " ");
printLeftBorderExceptLastElement(root.left);
printAllLeafNodes(root);
printRightBorderReverseExceptLastElement(root.right);
}
private void printRightBorderReverseExceptLastElement(TreeNode root) {
if(root.right==null)
{
if(root.left!=null)
{
printRightBorderReverseExceptLastElement(root.left);
System.out.print(root.element +" ");
}
return;
}
printRightBorderReverseExceptLastElement(root.right);
System.out.print(root.element + " ");
}
private void printAllLeafNodes(TreeNode root) {
if(root==null)
return;
if(root.left==null && root.right==null)
{
System.out.print(root.element + " ");
return;
}
printAllLeafNodes(root.left);
printAllLeafNodes(root.right);
}
private void printLeftBorderExceptLastElement(TreeNode root) {
if(root.left==null )
{
if(root.right!=null)
{
System.out.print(root.element + " ");
printLeftBorderExceptLastElement(root.right);
}
return;
}
System.out.print(root.element+ " ");
printLeftBorderExceptLastElement(root.left);
}
Time Complexity is O(n)
Space Complexity is O(h)=>O(n)
Please correct me if I'm wrong.
Apologies. I intended to call method1, has been edited now.
- teli.vaibhav April 20, 2013Using recursion:
public static void printSpirally(int[][] input)
{
int n=input.length;
printSpirallyAux(input,0,0,n-1,n-1);
}
private static void printSpirallyAux(int[][] input, int rowStart, int columnStart,int columnEnd,int rowEnd) {
if(rowStart>rowEnd)
return;
int i=rowStart;
int j=columnStart;
while(j<=columnEnd)
{
System.out.print(input[i][j++]);
}
j--;
i++;
while(i<=rowEnd)
{
System.out.print(input[i++][j]);
}
i--;
j--;
while(j>=columnStart)
{
System.out.print(input[i][j--]);
}
j++;
i--;
while(i>rowStart)
{
System.out.print(input[i--][j]);
}
printSpirallyAux(input,rowStart+1,columnStart+1,columnEnd-1,rowEnd-1);
}
Please correct me if I'm wrong.
- teli.vaibhav April 20, 2013I know this is lame, but here is what I could think of:
public class Print100Times {
int i=0;
public void method1(int elementToBePrinted)
{
if(++i<=100)
{
System.out.print(elementToBePrinted);
method2(elementToBePrinted);
}
}
private void method2(int elementToBePrinted) {
if(++i<=100)
{
System.out.print(elementToBePrinted);
method1(elementToBePrinted);
}
}
public static void main(String[] args)
{
Print100Times p=new Print100Times();
p.method1(0);
}
}
There is no loop and technically speaking there is no recursion either. :P
- teli.vaibhav April 20, 2013So like say with an ArrayList or LinkedList or a Stack or anything in the java API or for that matter even of our own custom API, it is possible to implement these methods because we know how our class looks. Did you happen to find out what kind of a class implementation was expected?
- teli.vaibhav April 19, 2013Iterator is an interface which each of the collection classes implement in their own way which includes the implementation of the 3 methods mentioned. It appears like you are being asked to create your own collection type because unless you know what your collection looks like, it doesnt make sense to implement these methods.
Please correct me if I'm wrong.
public static void printTruthTable(int n)
{
int[] out=new int[n];
printTruthTableAux(n,0,out);
}
private static void printTruthTableAux(int n, int d, int[] out) {
if(d==n)
{
printArray(out);
return;
}
for(int i=0;i<=1;i++)
{
out[d]=i;
printTruthTableAux(n,d+1,out);
}
}
private static void printArray(int[] out) {
char res;
for(int a:out)
{
res= a==0? 'F' : 'T';
System.out.print(res + " ");
}
System.out.println();
}
Time complexity would be O(n^n)
Space complexity of O(n).
Please correct me if I'm wrong.
public static void collectDataFromFileAndPutIntoMap(String loc)
{
Map<String,Integer> m=new HashMap<String,Integer>();
File f=new File(loc);
try {
BufferedReader br=new BufferedReader(new FileReader(f));
String s=null;
String[] tok;
while((s=(br.readLine()))!=null)
{
for(String s1: s.split(" "))
{
if(m.get(s1)==null)
m.put(s1,1);
else
m.put(s1, m.get(s1)+1);
}
iterateOverHashMap(m);
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
private static void iterateOverHashMap(Map<String, Integer> m) {
Iterator it=m.entrySet().iterator();
while(it.hasNext())
{
Map.Entry pairs=(Map.Entry) it.next();
System.out.println(pairs.getKey() + "----" + pairs.getValue());
}
}
This is definitely not the most efficient solution but still a working one at that :)
- teli.vaibhav April 19, 2013
RepSandyBMartinez, iOS Developer
Searching for a simple and delicious homemade treats for dogs?Visit Healthy Dog treats online store and shop the best ...
RepWilliamDGiles, Cloud Support Associate at ADP
Spent 2001-2006 creating marketing channels for tar worldwide. Was quite successful at building tobacco for farmers. Won several awards for ...
Although as mentioned by several others the best and easiest way to ensure singleton behaviour would be by instantiating the class into the variable declaration, sometimes when the Singleton object has a lot of overhead and may or may not be used in your application, you should use lazy load and the best way to do it is by exploiting the 'volatile' keyword which ensures that the JVM supplies the latest version of Singleton within the Synchronized code.
- teli.vaibhav May 04, 2014