teli.vaibhav
BAN USER 0of 0 votes
AnswerSearch 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 SDE2 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 SDE2 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 SDE2 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 SDE2 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 SDE2 Algorithm  1of 1 vote
AnswerWrite code for the partition subroutine in Quicksort.
 teli.vaibhav in United States Report Duplicate  Flag  PURGE
Amazon SDE2 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 SDE2 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 buﬀer,where the ﬁrst character of the line of text is in the ﬁrst spot in the buﬀer and the last character of textis in the speciﬁed slot in the buffer.
In ruby, you might deﬁne 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 SDE2 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 SDE2 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 SDE2 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
public boolean swapKthFromFirstAndLast(int k)
{
ListNode current=head,slow=head,temp;
int count=1;
while(count<k1)
{
if(current==null)
return false;
current=current.next;
count++;
}
temp=current;
current=current.next;
while(current.next.next!=null)
{
current=current.next;
slow=slow.next;
}
if(temp.next==slow.next)
return false;
swap(temp,slow);
return true;
}
private void swap(ListNode a, ListNode b) {
ListNode tmp=a.next;
a.next=b.next;
b.next=tmp;
ListNode tmp1=tmp.next;
tmp.next=a.next.next;
a.next.next=tmp1;
}
Of course in the code here my ListNode head is an instance variable of my LinkedList class.
 teli.vaibhav April 18, 2013Even though 'A'^' A' is 0. Please help me understand how it would fail. The swap still happens correctly, doest it?
 teli.vaibhav April 05, 2013Hashtable would take up a lot of space. The question says the size is not known, that itself shows the input is very large. Moreover, you say the space is O(1). The space is O(n).
 teli.vaibhav March 30, 2013This is a nice solution. To make it clearer, we can say that we XOR the index of each slot with the value in the slot of the array. Finally we XOR with 'n', the size of the array. The result would be the missing one.
 teli.vaibhav March 29, 2013A BTree is not a binary tree, its a Bayer's Tree.
 teli.vaibhav March 28, 2013Though the question suggests that we just need to iterate in a for loop and print it, saying that it would almost be the same in either case and that the difference would be at the assembly level like prem has suggested would probably be correct. But pointing out that if we are allowed only a Singly Linked list and we are to iterate from the last element to the first then Array would be faster, would fetch additional points from the interviewer I suppose.
 teli.vaibhav March 15, 2013I've always heard Serializable is a marker interface. Does that mean that this interface has no declared methods?
 teli.vaibhav February 10, 2013Is there any empty class in the java library.. ? curious..
 teli.vaibhav February 10, 2013I think the scenario boils down to when one would use a BT over a BST..
 teli.vaibhav February 10, 2013Using hash is not allowed whether your write your own hash function or you use the one available in the java collections.
Sorting seems fine but it gives you O(n* log n) complexity.
A better means would be to declare a 256bit BitSet. The index of each of the slots of this bit array would represent the Ascii code.
Now we just traverse through the given string and change the bit value in the BitSet(givenString.charAt(i)) from 0 to 1.
If we confront a 1 instead of a 0 for a character then we return false.
If we successfully traverse the whole string it implies the string has all unique characters.
O(n) would be the time complexity for this.
A Binary Tree is a tree in which each node can have maximum of 2 children.
Uses could be like a folder structure or the organizational hierarchy. It is used when there are no specific rules as to which node should be where, unlike in the case of a BST or a balanced tree which follow a set f rules.
An AVL tree is a balanced BST,it basically assures that the height of your tree is k*log n where k is a constant and n is the number of nodes in the tree. This in turn reduces the time complexity of an add, delete or a search operation to O(log n) which would normally be O(n) in a binary tree and O(h) in a BST.
I guess this answers the question for which is most efficient.
I do not know much about RB trees, but it too is a balanced BST like AVL trees and I believe that the implementation of operations in an RB tree are a lot more complex than that of an AVL tree but RB trees are apparently more secure and are used by several java libraries.
Please correct me if I'm wrong.
Oh look Mr. Wise Ass poops in.. if you have some technical wisdom then please preach else go fart elsewhere..
 teli.vaibhav January 29, 2013The question is vague.. What do you mean by an array of 0s and 1s of UNKNOWN size? If I am to write a method to implement the required functionality, I would have to pass the given array as argument and if I am a java coder array.length should simply give me the size.
I am guessing a stream on 0s and 1s would make more sense here, in which case even using a Vector may not be the best of solutions as the size of the data stream could eat up all the main memory crashing our program..
Yes.. I happened to miss that condition out..
Here is the code after incorporating the condition for equality:
package com.career.cup;
class MergeWithoutDuplicates {
static int[] getMergedArrayWithoutDuplicates(int[] firstArray, int[] secondArray)
{
int firstArraySize=firstArray.length;
int secondArraySize=secondArray.length;
int i=0,j=0,k=0;
int[] resArray=new int[firstArraySize+secondArraySize];
while(i<firstArraySize && j<secondArraySize)
{
if(firstArray[i]==secondArray[j])
{
resArray[k++]=firstArray[i++];
j++;
}
else if(firstArray[i]<secondArray[j])
resArray[k++]=firstArray[i++];
else
resArray[k++]=secondArray[j++];
}
while(i<firstArraySize)
resArray[k++]=firstArray[i++];
while(j<secondArraySize)
resArray[k++]=secondArray[j++];
return resArray;
}
public static void main(String[] args)
{
int[] firstArray={1,2,6,9,10,27};
int[] secondArray={2,8,10,89};
for(int resIndividualElement: getMergedArrayWithoutDuplicates(firstArray,secondArray))
{
System.out.println(resIndividualElement);
}
}
}
This solution works fine but since we created an array of size (m+n) and when there are duplicates, we dont use some of these slots in the result array we are returning which are initialized to 0. Can someone please suggest how we could avoid this without having to create a whole new array only to accommodate the size.
 teli.vaibhav January 27, 2013By doing that someone into java but not C can probably follow an idea or vice versa.
 teli.vaibhav July 11, 2012Could someone please explain an algorithm of what they have implemented. Figuring from code is exceedingly difficult.
 teli.vaibhav July 11, 2012That would be absolutely correct if the provided tree was a binary search tree. Which I assume it must have been as this is a question asked in a phone interview.
 teli.vaibhav July 11, 2012But the given input is a string. If we make a StringBuffer and make changes to get the result and again convert to a string using the toString() method in the StringBuffer. The string that we finally obtain and the string that was given as input would still be different strings due to their immutable nature. Can we still call such a computation an inplace one?
 teli.vaibhav July 10, 2012I have come up with a code in java which involves character by character computation in the same string. But String being immutable I am doubtful whether it is in place reversal or not. Can someone please verify this:
public class ReverseWordsInStringInPlace {
public static void revInPlace(String s)
{
int sLength=s.length();
int j=0;
int beginIndex=0;
for(int i=0;i<(sLength)/2;i++)
{
s=inPlaceSwap(s,i);
}
while(j<s.length())
{
if(s.charAt(j)==' ')
{
s=indexSwap(s,beginIndex, j1);
beginIndex=j+1;
}
if(j==s.length()1)
{
s=indexSwap(s,beginIndex, j);
}
j++;
}
System.out.println(s);
}
public static String indexSwap(String s,int beginIndex,int endIndex)
{
System.out.println(s);
char temp;
StringBuilder sb=new StringBuilder(s);
for(int i=beginIndex;i<=(endIndex+beginIndex)/2;i++)
{
temp=s.charAt(endIndex);
System.out.println(temp);
sb.setCharAt(endIndex,s.charAt(i));
sb.setCharAt(i, temp);
endIndex;
}
s=sb.toString();
System.out.println(s);
return s;
}
public static String inPlaceSwap(String s,int index)
{
char temp;
int sLength=s.length();
temp=s.charAt(s.length()1index);
StringBuilder sb=new StringBuilder(s);
sb.setCharAt(s.length()1index, s.charAt(index));
sb.setCharAt(index, temp);
s=sb.toString();
return s;
}
public static void main(String[] args)
{
revInPlace("where are you");
}
}

teli.vaibhav
July 10, 2012 I took the liberty to implement your algorithm:
package com.careercup;
public class Max1sIn2dArray {
public static int getMax1sIn2dArray(int[][] array,int m,int n)
{
int numberOf1s=0;
int maxIndex=0;
for(int i=0;i<m;i++)
{
System.out.println(array[i][1]);
maxIndex=getIndexOfLast1BinarySearch(array[i],1,0,n1)+1;
System.out.println(maxIndex);
if(maxIndex>numberOf1s)
{
numberOf1s=maxIndex;
}
}
return numberOf1s;
}
public static int getIndexOfLast1BinarySearch(int[] array,int key,int startIndex,int lastIndex)
{
int middleIndex=(startIndex+lastIndex)/2;
if(array[middleIndex]==key && (middleIndex==lastIndex  array[middleIndex+1]==0))
{
return middleIndex;
}
else if(array[middleIndex]==key)
{
startIndex=middleIndex+1;
return getIndexOfLast1BinarySearch(array,key,startIndex,lastIndex);
}
else if(array[middleIndex]==0 && middleIndex!=lastIndex)
{
lastIndex=middleIndex1;
return getIndexOfLast1BinarySearch(array,key,startIndex,lastIndex);
}
return 1;
}
public static void main(String[] args)
{
int noOfRows=4;
int noOfColumns=4;
int[][] inputArray={{1,1,0,0},{1,0,0,0},{0,0,0,0},{1,1,1,1}};
System.out.println(getMax1sIn2dArray(inputArray,noOfRows,noOfColumns));
}
}

teli.vaibhav
July 08, 2012 With your logic i think the time complexity narrows down to O(m*log(n)) where m is the number of rows and n is the number of columns.
 teli.vaibhav July 08, 2012Its just the implementation of the first suggested algorithm where you reverse the entire string in the first scan and then reverse each word individually.
Can someone please tell me if using the split() method of the string class would be inappropriate or something in an interview?
code in java:
public class StringReverse {
public static String strRev(String s)
{
String reversedString="";
for(int i=(s.length()1);i>=0;i)
{
reversedString+=s.charAt(i);
}
return reversedString;
}
public static void reverseWordByWord(String s)
{
String wordFormed="";
String requiredString="";
for(int i=0;i<=s.length();i++)
{
if(i==s.length()  s.charAt(i)==' ')
{
wordFormed=strRev(wordFormed);
requiredString+=wordFormed+" ";
System.out.println(requiredString);
wordFormed="";
}
else
wordFormed+=s.charAt(i);
}
System.out.println(requiredString);
}
public static void main(String[] args)
{
String s="What is this";
String reversedString=strRev(s);
reverseWordByWord(reversedString);
}
}

teli.vaibhav
July 05, 2012 No where close to linear time complexity..
 teli.vaibhav July 05, 2012using min heap would only complicate the comparison. Using max heap makes more sense.
 teli.vaibhav July 05, 2012@subrata: well.. I had the definition of a complete binary tree and that of a full binary tree mixed up.. your sarcasm helped clarify a basic concept for me.. thanx.. :)
 teli.vaibhav July 04, 2012This need not be the case, if we have even number of elements in the given inorder then it would not make a complete binary tree. We simply convert the array into a max heap.
 teli.vaibhav July 04, 2012yes. It just says inorder traversal of a tree not BST. And yes, the given condition is a waste, its as good as an arbitrary array given.
 teli.vaibhav July 03, 2012The time complexity for the above code would be O(n). This would be achieved in the case where a binary tree would have all nodes on its left or all nodes on its right.
The space complexity is Theta(n).
Apologies for the ugly look of the code. I suppose writing separate methods for swapping elements and for adjusting heap would make the code more readable.
The time complexity for the above code would be Theta(n) as all elements are traversed atleast once and less than twice.
And space complexity would be O(1), as we are doing all the manipulations on the same given array.
:O
 teli.vaibhav July 03, 2012Here is the code in java taking the given inorder in an array:
class BuildMaxHeap {
public static void convertToMaxHeap(int[] array)
{
int temp;
int n=array.length;
for(int i=(n1)/2;i>=0;i)
{
int parentIndex=i;
while(getLeftChildIndex(array,parentIndex)<n)
{
Integer leftChildIndex=getLeftChildIndex(array,parentIndex);
Integer rightChildIndex=getRightChildIndex(array,parentIndex);
int maxChildIndex=leftChildIndex;
if(rightChildIndex!=null && array[rightChildIndex]>array[leftChildIndex])
{
maxChildIndex=rightChildIndex;
}
if(array[parentIndex]<array[maxChildIndex])
{
temp=array[parentIndex];
array[parentIndex]=array[maxChildIndex];
array[maxChildIndex]=temp;
parentIndex=maxChildIndex;
}
else
break;
}
}
for(int m:array)
{
System.out.println(m);
}
}
public static Integer getLeftChildIndex(int[] a,int parentIndex)
{
return (2*parentIndex+1);
}
public static Integer getRightChildIndex(int[] a,int parentIndex)
{
if(2*parentIndex+2<a.length)
return (2*parentIndex+2);
return null;
}
public static void main(String[] args)
{
int[] inorder={1,2,3,4,5,6};
convertToMaxHeap(inorder);
}
}

teli.vaibhav
July 03, 2012 I am guessing the number of pairs involved in the overlapping are asked. Correct me if I'm wrong.
 teli.vaibhav July 01, 2012We can take 2 arrays of size n, assuming n pairs of events exist.
Sort the first array consisting of start times.
Sort the second array consisting of end times.
Now, just like in the case of merge sort we merge the 2 arrays. But in addition to the merging we maintain a count variable. During the merging if the element is being picked from the first array, it is a start point, so we increment the count as count++. Whenever we pick the from the second array of end points, we decrement the count as count. At the end of the merging. The count value eventually will be the number of overlaps.
The time complexity is O(nlog)+O(nlogn)+O(n+n) =>O(nlogn)
nlogn for each sort and O(n+n) for the merging.
This gives us a better overall time complexity but I cannot retrieve the pairs with this procedure. Can someone come up with an idea for that.
public class Print1To500WithoutLoop {
public static boolean printNums(int n)
{
System.out.println(n);
n++;
boolean a=n!=501 && printNums(n);
return true;
}
public static void main(String[] args)
{
printNums(1);
}
}

teli.vaibhav
July 01, 2012 I suppose the condition should have said, the seed is smaller than the number. That makes more sense as far as I understand.
 teli.vaibhav June 27, 2012I understood why a0 * a1 * a2 * ... * ai <= n/(10^i + ... + 1000 + 100 + 10 +1) but can someone please explain how the space above is narrowed down to log n?
 teli.vaibhav June 27, 2012There is no need to sort the mobile number strings. We make an array of TrieNodes of size 10. The indices of this array would represent numbers from 09. Now each of these 9 slots in the array would have another array of TrieNodes of size 10 and so on.
So if 6 is entered then everything under the first array[5] would be displayed.
Because that would result in unnecessary space wastage.
 teli.vaibhav June 25, 2012I suppose a Ternary Search Tree would give a fitting solution, but I am not confident about its implementation.
 teli.vaibhav June 25, 2012Were you asked to implement the datastructure or just name it?
 teli.vaibhav June 25, 2012Trie is the datastructure to be used.
 teli.vaibhav June 25, 2012
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 20012006 creating marketing channels for tar worldwide. Was quite successful at building tobacco for farmers. Won several awards for ...
Open Chat in New Window
Here is an inplace solution:
Efficiency suggestions are invited. :)
 teli.vaibhav April 18, 2013