Yahoo Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
10
of 12 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, that is right

- Anonymous October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good Stuff!

- Anonymous October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That won't work when the array b is not sorted

- Just chill October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

^^ 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...

- JustCoding October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This could potentially have quadratic complexity.

- Anonymous October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes marking the elements is a good technique. exactly what i have suggested

- codemonkey October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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());
}
}

- Siva October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Pankaj K. December 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

// 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);
	}

- xdoer October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- VJ October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if any element of array A will have 0[zero] value genuinely ?
in this case it will fail.

- Trozen October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can the minimum value from array in one pass assume min.
Then we can make the removable elements as min-1.

- Anonymous November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void main(String args[]) {
		List<Integer> a = new ArrayList<>();
		a.add(2);
		a.add(3);
		a.add(5);
		a.add(7);
		a.add(8);


		List<Integer> b = new ArrayList<>();
		b.add(1);
		b.add(3);

		for(int i = b.size() - 1 ; i >=0 ; i--) {
			a.remove(b.get(i) - 1);		
		}
	}

- Jeremy January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- einstein October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

U can replace the num at the postion with a garbeled character or say -1.

- Dashdash October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

simple and good

- siva October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
.

- qj October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code is expecting sorted Arraylist B ..

If B is not sorted, code is breaking

- einstein October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- JustCoding October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the second array in decreasing order and remove the corresponding elements one after the other...

- just chill October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work if the second array has duplicates.

- Anonymous October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if we remove the duplicates during the sorting

- NKN May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

No need to sort ArrayList B.
After removing every element , decrement all values in ArrayList B by 1 and continue the loop.

- Buzz_Lightyear November 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

won't work

lets say B is like "3,4,5,2,1"

- NKN May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kds December 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- Kannan December 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0; i<listB.size ; i++){
listA.remove(listB.get(i)-i-1);
}

- Anonymous January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

*** 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);

- -Manpreet February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

- chandraa March 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One more thing arraylist is index based which starts from 0

- chandraa March 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take another array C[] of size n. Initialize it to 1;
for every element in B[i], make C[i]=0
Now copy elements in A[] in place only when the corresponding value in C[] is 1.

int i=0;j=0;

while(j<n){
if(C[j]==1){
a[i]=a[j];
i++;
j++;
}
else
j++;
}
while(i<n){
free(a[i]);
i++;
}

- amazing February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- balraj.techs February 01, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More