Yahoo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
^^ this has been discussed in an earlier comment... the assumption is that array B is sorted... if not, it can be sorted in O(n log n)... the other assumption is that B does not contain duplicates... if it does, then multiple elements will be deleted for the same index value...
one possible solution is to just MARK the array elements as "to be deleted"... and in another run delete those actually...
public class Test {
public static void main(String[] args) {
List<Integer> a=new ArrayList<Integer>();
a.add(2);
a.add(3);
a.add(5);
a.add(7);
a.add(8);
List<Integer> b=new ArrayList<Integer>();
b.add(1);
b.add(3);
Map<Integer,Integer> indexValueMap=new HashMap<Integer,Integer>();
for(int i:a){
indexValueMap.put(a.indexOf(i), i);// store the index and value of list in map
}
for(int i:b){
indexValueMap.remove(i);//remove the elemnt from the map based on the List B value
}
System.out.println("Modified List A values...."+indexValueMap.values());
}
}
But, what if second ArrayList contains locations in random order, i.e. instead of (1,3), what happens if the locations are (3,1)?
I was thinking of the following approach:
First set the values for the given locations to 0. That is, now location 1 and 3 in the ArrayList A have 0. Now, we can remove the elements from A, where value is 0.
// If listB is not sorted, sort listB in ascending order before calling
// this method.
public static void removeFromListA(LinkedList<Integer> listA, int[] listB){
int pre = 0;
for(int i=0; i<listB.length; i++){
int index = listB[i]-pre;
if(index >= 0 && index < listA.size()){
listA.remove(index);
}
pre = pre+1;
}
}
public static void testRemoveFromListA(){
LinkedList<Integer> listA = new LinkedList<Integer>();
listA.add(2);
listA.add(3);
listA.add(5);
listA.add(7);
listA.add(8);
int[] listB = {0,1,2,3,4,5};
// expected result of listA [2,5,8];
removeFromListA(listA, listB);
System.out.println("listA after removal operation: " + listA);
}
Removing from last is a nice option... i do have a complicated version as well:
1. Read the indexes from array B.
2. Make all entries at indexes from arrayB into arrayA as 0.
3. Copy array values starting with first index of arrayA when a value is not zero. Make sure to use two increments one for normal read of all values of arrayA, one to copy the values into the same arrayA
What if any element of array A will have 0[zero] value genuinely ?
in this case it will fail.
public static void Main(){
ArrayList a = new ArrayList();
a.Add(1);
a.Add(2);
a.Add(3);
a.Add(4);
a.Add(5);
a.Add(6);
ArrayList b = new ArrayList();
b.Add(3);
b.Add(4);
foreach (int k in b) {
a.Insert(k, -1);
a.RemoveAt(k+1);
}
while (a.Contains(-1)) {
a.Remove(-1);
}
foreach (int i in a)
Console.WriteLine(i);
}
}
Assume B is sorted and all elements are unique.
Maintain a 'how much to shift' (say a variable called shift) and shift the value in B by shift when you are removing from A.
Once you remove, increment shift.
So the code will be something like:
// Note: A starts at 1.
void remove(int [] A, int [] B) {
int shift = 0;
foreach (int position in B) {
if (position - shift > A.Length) {
break;
}
A.removeAt(position - shift);
shift++;
}
}
No silly -1 business.
One question: is shift should be 0 or 1.
I did one experiment using Java. If shift be 0, then the result is [2, 5, 8]. It is not right. If shift is 1, then the result is [3, 7, 8].
The reason I think is that the arraylist starts at 0
.
that's an assumption we need to check with the interviewer... but yes "sorted" on B is expected... if not tats O(n log n) for sorting it...
This could be quadratic complexity. Each shift requires up to O(n) time and you have up to O(n) shifts.
Also, if you did want to do it this way, consider deleting in decreasing order of position instead of increasing. If you delete the rightmost elements first, other elements you need to delete are not shifted at all. Each deletion only shifts elements you don't need to delete, so you don't have to worry about them. No need for a counter or anything.
sort the second array in decreasing order and remove the corresponding elements one after the other...
No need to sort ArrayList B.
After removing every element , decrement all values in ArrayList B by 1 and continue the loop.
arrayList A 2,3,5,7,8
arrayList B 1, 3, 5
we can remove element from the beginning regardless List A is sorted or not.
Let's say number M in index N in List B
Then we can actually remove element from the beginning in List A of which index matches to M[M-1-N] in List B
for example,
1 --> removable index in List A 1-1-0 = 0
3 --> removable index in List A 3-1-1 = 1 after remove 2 in A
5 --> removable index in List A 5-1-2 = 2 after remove 5 in A
import java.util.*;
public class removeList {
List<Integer> a;
List<Integer> b;
removeList(List<Integer> a,List<Integer> b)
{
this.a=a;
this.b=b;
}
public static void main(String args[])
{
List<Integer> a = new ArrayList<Integer>();
List<Integer> b = new ArrayList<Integer>();
a.add(2);
a.add(3);
a.add(6);
a.add(7);
a.add(9);
b.add(3);
b.add(2);
//b.add(4);
System.out.println("sd");
removeList r = new removeList(a,b);
r.remove();
System.out.println("value = "+a);
}
void remove()
{
int d=0;
int m=0;
int i =0;
int temp =0;
while(i<b.size())
{
temp = b.get(i);
m=greater(temp);
a.remove(temp-(d-m));
d++;
i++;
}
}
int greater(int i)
{
int k=0;
int count =0;
while(k<b.size() && i != b.get(k))
{
if(i < b.get(k))
{
count++;
}
k++;
}
System.out.println("grea "+count);
return count;
}
}
*** Simplest way ***
LinkedList<Integer> listA = new LinkedList<Integer>();
listA.add(1);
listA.add(2);
listA.add(3);
listA.add(4);
listA.add(5);
LinkedList<Integer> listB = new LinkedList<Integer>();
listB.add(2);
listB.add(5);
Iterator<Integer> iterator = listA.iterator();
int i =1;
while(iterator.hasNext()){
iterator.next();
if(listB.contains(i)){
iterator.remove();
}
i++;
}
System.out.println(listA);
you can do like this.
List<Integer> intList = new ArrayList<Integer>();
List<Integer> indexList = new ArrayList<Integer>();
intList.add(2);
intList.add(3);
intList.add(5);
intList.add(7);
intList.add(8);
indexList.add(0);
indexList.add(2);
intList.removeAll(indexList);
System.out.println(intList);
One possible solution.......
public class ArrayListQ1 {
public static void main(String[] args) {
List<Integer> A = new ArrayList<Integer>(Arrays.asList(2,3,5,7,7,6,8,7,7));
List<Integer> B = new ArrayList<Integer> (Arrays.asList(1,5,3));
Collections.sort(B);
int shift = 0;
Iterator<Integer> ib = B.iterator();
while(ib.hasNext()){
A.remove(ib.next().intValue() - shift);
shift++;
}
System.out.println(A);
}
}
Start removing from the "last" position of B... so remove A[3] first.. and then remove A[1]... going in reverse order on B... that won't change the preceding positions...
- JustCoding October 04, 2012