Amazon Interview Questions

JAVA PROGRAM TO PERFORM MATRIX MULTIPLICATION

IMPLEMENT SELECTION SORTING IN JAVA

HASHTABLE ITERATOR EXAMPLE

LOOP ARRAY LIST AND ITERATE ARRAY ELEMENTS W ENUMERATING INTERFACE

7. Java Programming examples on “Random Number Generation”

Java Program to Generate N Number of Passwords of Length M Each
Java Program to Generate Date Between Given Range
Java Program to Generate Randomized Sequence of Given Range of Numbers
Java Program to Generate Random Hexadecimal Bytes
Java Program to Generate Tetris Game Using Random Number Generation
Java Program to Create a Random Bitmap Image
Java Program to Emulate N Dice Roller
Java Program to Use rand and srand Functions
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Java Program to Generate Random Numbers Using Middle Square Method
Java Program to Generate Random Numbers Using Multiply with Carry Method
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Implement Inversion Method for Random Number Generation
Java Program to Perform Random Number Generation Using Inversion Method
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Java Program to Implement Park-Miller Random Number Generation Algorithm
Java Program to Implement Naor-Reingold Pseudo Random Function

Consider that your office provides an app to book meeting rooms. You provide the start and end time of the meeting. The app list the available rooms for that slot and you select a room and confirm your booking. All meeting happen between 9am – 6pm. Write a method for getAvailableRooms(startTime, endTime). Use appropriate data structures.

Top view of a binary tree in constant space

Given a pattern containing only Is and Ds. I for increasing and D for decreasing. Devise an algorithm to print the MINIMUM number following that pattern. Digits from 1-9 and digits can’t repeat.

Design a system having multiple jobs, interacting with each other such that :
1) A job can run for very long periods (1-2 days)
2) A node can fail/crash on which certain job is running
system should be scalable
3) Amount of data getting transferred is huge
4) Data in the system is very sensitive and needs security
job/s can fail

Given a decedents of nodes, write an algorithm to find whether it is a tree or a graph?

Find the minimum (index) distance sum of 3 words. For example: arr = {“2”, “1”, “0”, “2”, “0”, “3”, “0”}, input = “1”,”2″,”3″. The result should be 8 since the 2nd “2” and “1”, “3”‘s distance are 3, 1, 5 and abs(3,1)+abs(3,5)+abs(5,1)=8. Implement this in O(N)

Find the frequency of a number in array in less than bigo n time Array 1,2,2,3,4,5,5,5,2 Input 5 Output 3 Array 1,1,1,1, Input 1 Output 4 Keep in mind less than bigo n

Design a system to monitor services (like when they were down/ CPU time) etc.

Design a system for dashboard that effectively shows almost real time data.

Implement Concurrent HashMap class in Java

Implement Linked HashMap class in Java

Design garbage collector in Java

Design a system to upload images and tag them. Ability to search images with single and multiple tags.

You have been given a grid with some doors, walls and some empty spaces. 1st part : You have to tell the least no of moves to go from random position in the grid to the nearest door. You can move in four directions only, i.e, left, right, above, below. 2nd part : Least distance of every empty cell to the nearest door. Lots of discussion was done on both the parts of the problem.

Given a set of numbers, find out all subsets of the set such that the sum of all the numbers in the subset is equal to a target number.

s = [ 1, 2, 3, 4, 5 ]
target = 5
op = [ [ 1,4 ] , [2,3] , [5] ]
Application: Given a fixed budget, and work items we are doing back filling to check what all we can attain with the budget.

Continuation. Imagine the set is actually a set of work items, with cost and utility involved :

def work_item : { name : ‘foo bar’ , cost : 10 , utility : 14 }
Now, solve this to maximise utility.

Continuation. Imagine that the work items are related, so that, if work item w1 is already in the
subset of the work items selected, w2 ‘s utility increases further!.
( Can you imagine how it can happen? Effectiveness of Mesi increases when he plays for Barca)
So, you are given a list like this :

w1 -> normal utility 14, with w2 20, ….
Now maximize payoff.
NOTE: Payoff is a matrix. This comes from game theory.
Hence, a payoff matrix looks like :

w1 w2 w3 w4 ….
w1 w1
w2 w2
w3 w3
w4 w4
A cell ( i,j) is filled up with if a list contains both wi and wj, then how much the payoff would be. It is a symmetric matrix.

Interview Questions Design Patterns

Q: What design pattern is used to implement a Synchronized HashMap?

A: Decorator Pattern
Decorator pattern allows a user to add new functionality to an existing object without altering its structure. This type of design pattern comes under structural pattern as this pattern acts as a wrapper to existing class.

This pattern creates a decorator class which wraps the original class and provides additional functionality keeping class methods signature intact.

We are demonstrating the use of decorator pattern via following example in which we will decorate a shape with some color without alter shape class.

Synchronized HashMap Decorator Pattern Example

import java.util.Collections; 
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.Set;

public class HashMapSynchronizationDemo{

		    public static void main(String args[]) {

	        Map<String, String> currencies = new HashMap<String, String>();

				currencies.put("USA", "USD"); 
				currencies.put("England", "GBP"); 
				currencies.put("Canada", "CAD"); 
				currencies.put("HongKong", "HKD"); 
				currencies.put("Australia", "AUD");

	        currencies = Collections.synchronizedMap(currencies);
	        Set<String> keySet = currencies.keySet();  

	        synchronized(currencies) {  
				Iterator<String> itr = keySet.iterator();
	            while (itr.hasNext()){
						System.out.println(itr.next()); 
			} 
		} 
	} 
} 

Output
USA
Canada
HongKong
England
Australia

Another Decorator Pattern Example

import java.util.ArrayList;
import java.util.ListIterator;


public class ChaiDecorator extends Tea {
    private Tea teaToMakeChai;
    private ArrayList chaiIngredients = new ArrayList();
    
    public ChaiDecorator(Tea teaToMakeChai) {
        this.addTea(teaToMakeChai);
        chaiIngredients.add("bay leaf");
        chaiIngredients.add("cinnamon stick");
        chaiIngredients.add("ginger");
        chaiIngredients.add("honey");
        chaiIngredients.add("soy milk");
        chaiIngredients.add("vanilla bean");
    }


    private void addTea(Tea teaToMakeChaiIn) {
        this.teaToMakeChai = teaToMakeChaiIn;
    }
    
    public void steepTea() {
        this.steepChai();
    }


    public void steepChai() {
        teaToMakeChai.steepTea();
        this.steepChaiIngredients();
        System.out.println("tea is steeping with chai");
    }    
    
    public void steepChaiIngredients() {
        ListIterator listIterator = chaiIngredients.listIterator();
        while (listIterator.hasNext()) {
            System.out.println(((String)(listIterator.next())) + 
                                         " is steeping");
        }
        System.out.println("chai ingredients are steeping");
    }      
}

QUESTION 2

You are given an unsorted binary array.

Example [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]

And a letter K, which represents the number of swap operations allowed on this binary array.

You need to find out the maximum length continuous subarray that can be generated using K many swaps.

Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9.

QUESTION 3

You are given a binary matrix with each row sorted.
That means each row will have zeros at the front and ones at the back. You need to find out which row which contains a maximum number of ones.

Example:

[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]
[0 0 0 0 0 0 1 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]

Answer : Second row and Sixth with 8 ones.
You will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

QUESTION 4

Design a system to monitor services (like when they were down/ CPU time) etc.

QUESTION 5

Design a system for dashboard that effectively shows almost real time data.

QUESTION 6

Implement a stack that in addition to push and pop has a function that returns the min value of the stack.

I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.

QUESTION 7

Given a sorted array with “n” elements, distributed them into “k” nearly equally weighing buckets.

Space is not constraint.

Ex: [1,3,6,9,10]
bucket size: 3

output:[10],[9,1],[3,6]

QUESTION 8

Add two link list, can not modify the link list, can not reverse the link list first and second.

Link list 1 – 1->2->3->7
Link list 2 – 2->9
Output Sum – 1->2->6->6

Solution:
Iterate through the two lists twice. First time get the difference in length. Second time get the sum at every digit (allow a node to have 2 digits). And then iterate through the new result array once to deal with the carry.

public ListNode add(ListNode head1, ListNode head2) {


        if(head1 == null || head2 == null) {
            return head1 == null? head2: head1;
        }

        int diff = 0; //get the difference in lengths of the two lists

        ListNode p1 = head1, p2 = head2;
        while(p1 != null && p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        ListNode longer = p1 == null? head2: head1;
        ListNode shorter = p1 == null? head1: head2;

        while(p1 != null) {
            p1 = p1.next;
            diff++;
        }

        while(p2 != null) {
            p2 = p2.next;
            diff++;
        }

        ListNode dump = new ListNode(0);  //create a dummy head for the result list
        ListNode curr= dump;

        while(diff > 0) {   //create the longer part of the longer list
            diff--;
            curr.next = new ListNode(longer.val);
            longer = longer.next;
            curr = curr.next;
        }

        while(longer != null) { //add the two lists
            curr.next = new ListNode(longer.val + shorter.val);
            curr = curr.next;
            longer = longer.next;
            shorter = shorter.next;
        }

        curr = dump;
        ListNode carry = dump;
        while(curr != null) {       //carry always points at the number smaller than 9
            if(curr.val < 9) {      //when a carry is found at current node, add 1 to carry and change anything after carry and before curr to 0
                carry = curr;
            } else if(curr.val > 9){
                carry.val++;
                carry = carry.next;
                while(carry != curr) {
                    carry.val = 0;
                    carry = carry.next;
                }
                curr.val %= 10;
            }
            curr = curr.next;
        }

        return dump.val == 0 ? dump.next: dump;

    }

ANOTHER SOLUTION:

public class AddTwoLinkedList {

	
	public static void main(String[] args) {
		LL l2_4 = new LL(7, null);
		LL l2_3 = new LL(3, l2_4);
		LL l2_2 = new LL(2, l2_3);
		LL l2_1 = new LL(1, l2_2);
		
		LL l1_2 = new LL(9, null);
		LL l1_1 = new LL(2, l1_2);
		
		
		
		int s1 = 0;
		LL l1 = l1_1;
		while(l1 != null){
			l1 = l1.next;
			s1++;
		}
		int s2 = 0;
		LL l2 = l2_1;
		while(l2 != null){
			l2 = l2.next;
			s2++;
		}
		int c = s2-s1-1;
		LL prev = new LL(0, null);
		LL h = prev;
		while(c > 0){
			LL l = new LL(0, null);
			prev.next = l;
			prev = l;
			c--;
		}
		prev.next = l1_1;
		
		int carry = addLinkedList(l2_1, h, 0);
		LL lh = l2_1;
		if(carry > 0){
			lh = new LL(carry, l2_1);
		}
		
		while(lh != null){
			System.out.print(lh.val + " ");
			lh = lh.next;
		}
	}
	
	static int addLinkedList(LL l1, LL l2, int carry){
		if(l1 == null && l2 == null) return carry;
		
		carry = addLinkedList(l1.next, l2.next, carry);
		
		if(l1 != null && l2 != null){
			int sum = l1.val + l2.val + carry;
			if(sum > 9){
				String str = String.valueOf(sum);
				int toAdd = Integer.parseInt(str.substring(1,str.length()));
				carry = Integer.parseInt(str.substring(0,1));
				l1.val = toAdd;
			}else{
				l1.val = sum;
				carry = 0;
			}
		}
		return carry;
	}
	
}
class LL{
	int val;
	LL next;
	public LL(int val, LL next){
		this.val = val;
		this.next = next;
	}

ANOTHER SOLUTION

We must traverse both lists from their ends toward their beginnings. We can traverse one of the lists starting from the end via a recursive function, but it is a challenge to coordinate two different length lists that way. So we can traverse the other list first, pushing its elements into a stack. Then, as we unwind the recursion of the one list, we pop the elements of the converted list. In case the recursed list is shorter than the “stacked” list, we pop the rest of the elements, creating prefixing the “sum” with the elements of the stack that hadn’t been “added”. No counting necessary, O(m+n) time

In raw JavaScript, with a little NodeJS-ism for output:

// A Linked-list class
function LL(data, next) {
	// console.log("insert "+data)
	this.data = data;
	this.next = next;
}
LL.prototype.print = function () {
	process.stdout.write(this.data.toString())
	if (this.next) {
		process.stdout.write('-> ')
		this.next.print()
	}
	else
		process.stdout.write('\n')
}

// Recursive function to add a "stack" to a Linked-list
function _add(stack, list) {
	let sum;
	if (! list.next ) {
		sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data, null)
	}
	else {
		sum = _add(stack, list.next)
		sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data,
							  sum)
		if (sum.next.data > 9) {
		  sum.next.data -= 10
		  sum.data += 1
		}
	}
	return sum
} // _add()

// This is the function solution to the exercise:
function addLists( L1, L2 ) {
	let stack=[];						// Tempoary data struct
	for (let i=L1; i; i=i.next)	// Fill the stack w/one list
		stack.push(i.data)

	let sum = _add(stack, L2)		// Add the revised list to the other list
	let carry = ( sum.data > 9 )
	if (carry) sum.data -= 10;		// If most signifant element overflowed...

	while (stack.length)	{			// While there are list elements left
		sum = new LL(stack.pop(), sum)
		if (carry) {					// Make sure handle the carry-over
			sum.data += 1;				// is added to the next digit
			carry = false;				// This only needs to be done once
		}
	}
	if (carry) {						// Make sure carry-over was handled
		sum = new LL(1, sum)			// adding a node, since no stack elements
	}										// were able to absorb it

	return sum;							// Return final list
} // addLists()

// Create test Linked-lists
var first	= new LL( 1, new LL( 2, new LL( 3, new LL(7))))
var second	= new LL( 2, new LL (9, null))

// Make sure they're constructed correctly
process.stdout.write("First list:  ")
first.print()
process.stdout.write("Second list: ")
second.print()
process.stdout.write("Sum:         ")
addLists(first,second).print()

ANOTHER SOLUTION

The challenge here is to do it using constant memory.
The time complexity is theta of n+m so we cant do anything there.
All the solutions you guys posted are garbage.

1. Iterate over lists to get their length.
2. Add each corresponding digit from left to right disregarding the carry. Lets call this S.
3. Add each digit and only consider the carry. 1 if it produces a carry 0 if not. Call this C.
4. Return S+C*10

1 2 3 7
2 9

Produces S=1256 and C=1.

O(n+m) time O(1) space.


ANOTHER SOLUTION
C# – O(N) time and O(1) space

public void Adding2LinkedList(LinkedListNode<int> one = null, LinkedListNode<int> sec = null)
        {
            int sum = 0;
            int carry = 0;
            var wholeSize = Math.Max(LengthOfLinkedList(one), LengthOfLinkedList(sec));
            var result = new LinkedList<int>();
            for (int i = 0; i < wholeSize; i++)
            {
                count = 0;
                var elemOne = FindTheKthLastElement(one, i);
                count = 0;
                var elemSec = FindTheKthLastElement(sec, i);
                sum = (elemOne + elemSec + carry) % 10;
                carry = (elemOne + elemSec + carry) / 10;
                result.AddFirst(sum);
            }


        }

        public int FindTheKthLastElement(LinkedListNode<int> list, int k)
        {
            int num = 0;
            if (list == null) return num;

            num = FindTheKthLastElement(list.Next, k);
            if (count++ == k)
                return list.Value;
            return num;
        }

        public int LengthOfLinkedList(LinkedListNode<int> list)
        {
            if (list == null) return 0;
            return 1 + LengthOfLinkedList(list.Next);
        }

LATEST SOLUTION

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
Node *tf = reverse(l1);
Node *ts = reverse(l2);
Node dummy;
Node *result = &dummy;
int carry =0,sum=0;

while (tf || ts || carry) {
sum = carry;
if (tf) {
sum += tf->data;
tf = tf->next;
}
if (ts) {
sum += ts->data;
ts = ts->next;
}
result->next = new Node(sum % 10);
carry = sum/10;
result = result->next;
}
return (reverse(dummy.next));
}


ListNode *reverse(ListNode *head) {
Node *curr = head;
Node *temp, *result;
temp = result = NULL;

while (curr) {
temp = curr->next;
curr->next = result;
result = curr;
curr = temp;
}

return result;
}

QUESTION 9


ANOTHER SOLUTION


ANOTHER SOLUTION


QUESTION 10


QUESTION 11


QUESTION 12


QUESTION 12


QUESTION 12


QUESTION 12


QUESTION 12


ANOTHER SOLUTION


ANOTHER SOLUTION


ANOTHER SOLUTION


Top Software Developer Interview Questions

PROGRAMMING LANGUAGES
Java, C#, C/C++, Ruby
How does memory management work
Common collections or libraries

Q: How does memory management work in Objective-C?
With good target and confidence

Q: Write and aligned malloc() that gets memory size needed and an alignment mask as its arguments. Write a free() function to go with the aligned malloc that takes only the pointer to the allocated chunk of memory.
1. You basically need to allocated some extra memory with the memory segment that is requested so that you have enough space to align the said chunk and also save a pointer onto the original segment that you get from regular malloc. The free() method via some pointer math will get the “original pointer” and free it.
2. For malloc() you can use the concept of segregated list and do sbrk() to get that much chunk of memory from the kernel. It might lead to some internal fragmentation but thats fine…

Difference between Heap and Stack
3 Answers
I had no clue
all objects get stored in heap while all value type get stored in stack..heap automatically maage memory using garbage collection..while in stack explicitly memory is managed using destructors..in heap,CLR is responsile for memory management.
Heap : When you try to allocate memory by using “new ” keyword .The memory will be stored in heap memory. Stack : The memory will be allocated automatically and free automatically once variable out of the scope

Q: Difference between Memory leaks and memory management

Questions on prototype of dynamic memory management functions like malloc and free in C. Issues that can occur ( fragmentation , memory leak etc ). And use of static and auto variables in this context.

Facebook Interview Question for Software Engineers

Question 1: Binary tree to doubly linked list.

Question 2: Read 4 (Given the read4 API, read an entire file)

Question: System Design POI (Point of Interest. Given a point, find things within a radius).

Question 1: Decode way

Question 2: Random max index

Question: System design + component-wise design on download manager

All the algo questions were seen except the Random Max Index. Optimal solution is O(n) in time (single pass)and constant extra space.

Generate random max index
Given an array of integers, randomly return an index of the maximum value seen by far.

e.g.
Given [11,30,2,30,30,30,6,2,62, 62]

Having iterated up to the at element index 5 (where the last 30 is), randomly give an index among [1, 3, 4, 5] which are indices of 30 – the max value by far. Each index should have a ¼ chance to get picked.

Having iterated through the entire array, randomly give an index between 8 and 9 which are indices of the max value 62.

Solution:

public void sampleIdx(int[] array){
        if(array == null || array.length == 0){
            return;
        }
        Random rnd = new Random();
        int res = 0, max = Integer.MIN_VALUE, count = 0;
        for(int i = 0; i < array.length; i++){
            if(max < array[i]){
            	max = array[i];
                res = i;
                count = 1;
            }else if(max == array[i]){
                count++;
                int idx = rnd.nextInt(count); //(0, k - 1)
                if(idx == 0){

                    res = i;
		        System.out.print(“A max value index up to the ”+i +”th element is ” + res;
);

                }
            }
        }
    }

Algorithm Interview Questions
Page:1 2 3 4 5 6 7 8 9 10 »
Filter: Go Clear
Sort By: Date | Number of Comments | Most Recent Comment | Votes
facebook-interview-questions1
of 1 vote
1
Answer
Facebook Senior Engineer On-site 2017

1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)

2nd Round
Culture fit. No coding.

3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).

Lunch
4th Round
Question 1: Decode way
Question 2: Random max index

5th Round
Question: System design + component-wise design on download manager

– aonecoding April 17, 2017 in United States | Report Duplicate | Flag
Facebook Software Engineer Algorithm
google-interview-questions2
of 2 votes
7
Answers
5th Round
Open-ended question What happens when you type a url in the browser and hit enter?

Second question Given an array of integers, print all the numbers that meet the following requirement – when the number is greater than every number on its left and smaller than every number on the right.

– aonecoding April 13, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
google-interview-questions0
of 2 votes
1
Answer
interviewed by senior engineer
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Follow-up If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

– aonecoding April 13, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
google-interview-questions0
of 0 votes
3
Answers
Given a list of files. Return all the unique lines from all files.

– Ray April 12, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
amazon-interview-questions0
of 0 votes
4
Answers
You are given an unsorted binary array.
Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]
and a number K, which represents the number of swap operations allowed on this binary array.
you need to find out the maximum length continuous subarray that can be generated using K many swaps.
Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9.

– sonesh April 10, 2017 in United States | Report Duplicate | Flag
Amazon Software Engineer / Developer Algorithm
amazon-interview-questions0
of 0 votes
7
Answers
You are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.
Ex :

[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]
[0 0 0 0 0 0 1 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]
Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

– sonesh April 10, 2017 in United States | Report Duplicate | Flag
Amazon Software Engineer / Developer Algorithm
google-interview-questions-2
of 2 votes
0
Answers
Find the coordinates of the rectangle which is parallel to axis and has minimum area.

– Ray April 08, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
google-interview-questions0
of 0 votes
3
Answers
Suppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven’t been already encountered in the last X seconds.

– Ray April 08, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
facebook-interview-questions0
of 0 votes
34
Answers
Given an array of integers:
1. rearrange the array such that all non-zero members appear on the left of the array (order is not important)
2. return the number of non-zero members

e.g. [1,2,0,5,3,0,4,0] => [1,2,5,3,4,0,0,0] and return 5. The non-zero array members can be in any order.

– xjohnwu April 07, 2017 in UK | Report Duplicate | Flag
Facebook Software Engineer / Developer Algorithm
bloomberg-lp-interview-questions1
of 1 vote
10
Answers
You are given an array of integers both negative and positive.
Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.
Ex : [-20, -5, -2, -9] :> -2(-2)
Ex : [20, -19, 6, 9, 4] :-> 20(20)
Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)

Thanks velu007 for pointing out the mistake

– sonesh April 07, 2017 in United States | Report Duplicate | Flag
Bloomberg LP Software Engineer / Developer Algorithm
algorithm-interview-questions0
of 0 votes
1
Answer

– edboon06 April 06, 2017 in United States | Report Duplicate | Flag
Backend Developer Algorithm
amazon-interview-questions-1
of 3 votes
17
Answers
Find the frequency of a number in array in less than bigo n time
Array 1,2,2,3,4,5,5,5,2
Input 5
Output 3
Array 1,1,1,1,
Input 1
Output 4

Keep in mind less than bigo n

Thanks

– dinkar1708 April 01, 2017 in India | Report Duplicate | Flag
Amazon SDE-2 Algorithm Arrays
groupon-interview-questions0
of 0 votes
0
Answers
Delhi Route Traffic Optimizer

Traffic congestion is an annoying issue in Delhi, the capital of India. Every morning thousands of people drivea residential area to the International Technology Park (ITPL). There are various routes one can take to reach ITPL and each route takes its own time making some routes faster than the others. People obviously take faster routes which causes congestion on those roads too. Congestion results into increased travel time, air pollution and wastage of fuel. As a Traffic commissioner of Delhi, you are asked to optimize the traffic by putting toll to various roads so that resultant cost of every route (driving time cost and toll cost) ends up the same. This has to be done in such a way that any driver pays toll only once no matter which route he/she takes.roads have one-way traffic and there is no cycle in any of the routes. You need to create a toll plan for a given road layout.

The toll plan must adhere to following rules:

1. Toll should be levied in such a way that perceived cost (base road cost and toll cost) remains same forroads.
2. The tolls should be levied such that the total cost for each route is minimized.
3. A route cannot have more than one toll.
4. In case of multiple solutions for a route, add toll to a road that is closer to destination.
In some use cases, it might be impossible to impose tolls that satisfy the above conditions.

http://qa.geeksforgeeks.org/11340/delhi-route-traffic-optimizer

– raghunitb March 30, 2017 in India for Workflow | Report Duplicate | Flag
Groupon SDE1 Algorithm
facebook-interview-questions1
of 1 vote
11
Answers
Given some email ids, and a similarity function which says whether two email ids are similar, determine all the sets of email ids that are similar to each other.

– Ray March 28, 2017 in United States | Report Duplicate | Flag
Facebook Software Engineer Algorithm
facebook-interview-questions0
of 0 votes
12
Answers
You have a string consisting of open and closed parentheses, but parentheses may be imbalanced.
Make the parentheses balanced and return the new string.

– Ray March 26, 2017 in United States | Report Duplicate | Flag
Facebook Software Engineer Algorithm
bloomberg-lp-interview-questions1
of 1 vote
7
Answers
Given a list of URLs entered by a user write a program to print unique and most recently used URLs. For example if user entered the following: –
1. google.com
2. yahoo.com
3. wsj.com
4. google.com

The output should be :-
1. google.com
2. wsj.com
3.yahoo.com

– ik.yola March 25, 2017 in United States | Report Duplicate | Flag
Bloomberg LP Software Analyst Algorithm
adp-interview-questions0
of 0 votes
2
Answers
Given a movie X that the user had watched, write an algorithm to suggest more movies to the user. How to display the other movies based on same genre?

– suneel March 24, 2017 in India | Report Duplicate | Flag
ADP SDE-2 Algorithm
google-interview-questions2
of 2 votes
16
Answers
Given a sorted array, find all the numbers that occur more than n/4 times.

– alisonlee659 March 24, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
flipkart-interview-questions0
of 0 votes
1
Answer
How to Design an Meeting scheduler

– DuttaJ March 23, 2017 in India | Report Duplicate | Flag
Flipkart SDE-2 Algorithm
linkedin-interview-questions0
of 2 votes
7
Answers
How to randomly select a number in an array?
array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:
Could you complete the selection in a single-pass(go through each array only once)?

– aonecoding March 22, 2017 in United States | Report Duplicate | Flag
Linkedin Software Engineer Algorithm
google-interview-questions1
of 5 votes
12
Answers
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student’s attendance record represented by a string with 3 possible characters ‘L'(Late), ‘A'(Absent), ‘O’ (On time),
check whether the student qualifies for the reward.

e.g.
@INPUT (String) “OLLAOOOLLO”
@RETURN (Boolean) False
The student does not qualify for reward because “LLA” means he was late for 3 times in a row.

@INPUT (String) “OLLOAOLLO”
@RETURN (Boolean) True

Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.

– aonecoding March 22, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
google-interview-questions0
of 0 votes
0
Answers
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student’s attendance record represented by a string with 3 possible characters ‘L'(Late), ‘A'(Absent), ‘O’ (On time), check whether the student qualifies for the reward.

e.g.
@INPUT (String) “OLLAOOOLLO”
@RETURN (Boolean) False
The student does not qualify for reward because “LLA” means he was late for 3 times in a row.

@INPUT (String) “OLLOAOLLO”
@RETURN (Boolean) True

Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.

– aonecoding March 22, 2017 in United States | Report Duplicate | Flag
Google Software Engineer Algorithm
amazon-interview-questions-1
of 1 vote
15
Answers
Find K which decides the number of open brackets are equal to the number of closed brackets.

input : (())
output : 2
Reason : if we divide the string at 2nd position, we get two open brackets and two closing brackets, and they are same .

input : (())))(
output : 4
Reason : if we divide the string(not necessarily equally) at 4rth position, we have (()) on the left side and on the right side we have ))( , as you can see, on the left half, we have two opening brackets and on the right half we have two closing brackets and they are equal .

input : ))
output : 2
Reason : there is no open brackets , so if we divide taking the whole string’s length, we have )) on the left half and nothing on the right half. Now you can see that on the left half there is no open brackets and on the right half there is no closed brackets.

This question should be clear by now and remember you have to find out that K .

– SmashDUNK March 21, 2017 in United States | Report Duplicate | Flag
Amazon SDE-2 Algorithm
microsoft-interview-questions0
of 0 votes
18
Answers
There are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.

For example:

arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]

After shuffle:

arrayA = [24, 32, 8, 12]
arrayB = [13, 25, 32, 11]

– gzyeli123 March 20, 2017 in United States | Report Duplicate | Flag
Microsoft SDE1 Algorithm
amazon-interview-questions0
of 0 votes
4
Answers
Find the Maximum number of distinct nodes in a binary tree path

– SmashDUNK March 20, 2017 in United States | Report Duplicate | Flag
Amazon SDE-2 Algorithm
google-interview-questions0
of 0 votes
8
Answers
Check if two given binary trees(expression trees with two characters ‘a’ and ‘b’ and obviously operators like +,-,*) are mathematically equivalent?

– SmashDUNK March 16, 2017 in United States | Report Duplicate | Flag
Google Software Engineer / Developer Algorithm
dropbox-interview-questions0
of 0 votes
0
Answers
1) Given a file containing lines of chars, find if it contains “aaaaab\naaaaa” string pattern. Need to return true only if contains the EXACT pattern specified (observe the new line character).

2) How do you differentiate between actual new line and the new line character?

3) what if the file is way too big to bring it all in memory?

– xankar March 10, 2017 in United States | Report Duplicate | Flag
Dropbox Backend Developer Algorithm
amazon-interview-questions0
of 0 votes
5
Answers
Top View of a Binary Tree in constant space

– neer.1304 March 10, 2017 in United States | Report Duplicate | Flag
Amazon SDE-3 Algorithm
amazon-interview-questions0
of 0 votes
19
Answers
Given a pattern containing only Is and Ds. I for increasing and D for decreasing. Devise an algorithm to print the MINIMUM number following that pattern. Digits from 1-9 and digits can’t repeat.

Example:
1. Input: D Output: 21
2. Input: I Output: 12
3. Input: DD Output: 321
4. Input: II Output: 123
5. Input: DIDI Output: 21435
6. Input: IIDDD Output: 126543
7. Input: DDIDDIID Output: 321654798

– neer.1304 March 10, 2017 in United States | Report Duplicate | Flag
Amazon SDE-3 Algorithm
amazon-interview-questions0
of 0 votes
0
Answers
Implement ConcurrentHashMap class in Java

Garbage Collector Memory Management Interview Questions

MEMORY MANAGEMENT QUESTIONS

References:
Memory Management Glossary
Memory Pool System Manual

Q: Why do I need to test the return value from malloc? Surely it always succeeds?
For small programs and during light testing this is usually true. BUT there are all kinds of unpredictable reasons why malloc might fail one day:
Examples:
1. Someone uses your program for a far larger data set than you anticipated;
2. Your program is running on a machine with less memory than you expected;
3. The machine your program is running on is heavily loaded.
In this case malloc will return NULL, and your program will attempt to store data by resolving the null pointer. This might cause your program to exit immediately.
You must check all error or status codes returned by functions you call, locally or in other libraries, such as the C run-time library.
You can also wrap malloc in something like this:


#include 
#include 

void *my_malloc(size_t size)
{
    void *p = malloc(size);

    if (p == NULL) {
        fputs("Out of memory.\n", stderr);
        exit(EXIT_FAILURE);
    }

    return p;
}

Q: What’s the point of having a garbage collector? Why not use malloc and free?
Manual memory management (malloc and free) force you to keep track of which memory is still required, and who is responsible for freeing it. This works for small programs but can cause bugs in larger programs and a serious problem for interface abstraction. Automatic Memory Management will free you from these concerns.

Q: What’s wrong with ANSI malloc in the C Library?
Malloc is a very basic manual memory management service. A good memory manager provides the following:
– high performance for specified block sizes;
– tagged references;
– simultaneous frees;
– locality of reference hints;
– formatted objects;
– garbage collection;
– deallocation of partial blocks;
– multi-threading without synchronization;
– inlined allocation code;
– finalization.

Q: Can I use garbage collection in C++?
Yes, the C++ specification has always permitted garbage collection.

Q: Why is delete so slow?
Often DELETE must perform a more complex task than simply freeing the memory associated with an object, this is known as finalization. Finalization typically involves releasing any resources indirectly associated with the object, such as files that must be closed or ancillary objects that must be finalized themselves. This may involve going back over memory that has been unused and is paged out. Deallocating blocks in address order can result in poor performance.

Q: What happens if you use class libraries that leak memory?
In C++ it may be that class libraries expect you to call delete on objects they create, to invoke the destructor. Failing this, if there is truly a memory leak in a class library and you don’t have the source then the only option is to try a garbage collector.

Q: Can’t I get all the benefits of garbage collection using C++ constructors and destructors?
Garbage collection has the advantage, because it can determine when a given object is no longer of interest to anyone (or at least when there are no more references to it). This neatly avoids the problems of having multiple copies of the same data or complex conditional destruction. The program can construct objects and store references to them anywhere it finds convenient; the garbage collector will deal with all the problems of data sharing.

Q: What languages use garbage collection?
Java, C#, Python, Lisp, ML, the list goes on. Many implementations of BASIC use garbage collection to manage character strings efficiently. The idea of automatic memory management has stood the test of time and is becoming a standard part of modern programming environments. Some might say it isn’t ALWAYS necessary and opt out of automatic memory management in some cases. Most will say there is a place for garbage collection among tools of the modern programmer.

Q: What’s the advantage of garbage collection?
Garbage collection frees you from having to keep track of which part of your program is responsible for the deallocation of which memory. This freedom from tedious and error-prone bookkeeping allows you to concentrate on the problem you are trying to solve, without introducing additional problems of implementation.
This is particularly important in large-scale or highly modular programs, especially libraries, because the problems of manual memory management often dominate interface complexity. Additionally, garbage collection can reduce the amount of memory used because the interface problems of manual memory management are often solved by creating extra copies of data.
In terms of performance, garbage collection is often faster than manual memory management. It can also improve performance indirectly, by increasing locality of reference and hence reducing the size of the working set, and decreasing paging.

Q: Isn’t it much cheaper to use reference counts rather than garbage collection?
No, updating reference counts is quite expensive, and they have a couple of problems:
They can’t cope with cyclic data structures; that is, sets of objects that are referred to only by objects in that set, but that don’t have a zero reference count.
Reference counting gets more expensive if you have to allow for the count overflowing.
There are many systems that use reference counts, and avoid the problems described above by using a conventional garbage collector to complement it. This is usually done for real-time benefits. Unfortunately, experience shows that this is generally less efficient than implementing a proper real-time garbage collector, except in the case where most reference counts are one.

Q: Isn’t GC unreliable? I’ve heard that GCs often kill the program
Garbage collectors usually have to manipulate vulnerable data structures and must often use poorly-documented, low-level interfaces. Additionally, any garbage collection problems may not be detected until some time later. These factors combine to make most garbage collection bugs severe in effect, hard to reproduce, and difficult to work around.
On the other hand, commercial garbage collection code will generally be heavily tested and widely used, which implies it must be reliable. It will be hard to match that reliability in a manual memory manager written for one program, especially given that manual memory management doesn’t scale as well as the automatic variety.
In addition, bugs in the compiler or run-time (or application if the language is as low-level as C) can corrupt the heap in ways that only the garbage collector will detect later. The collector is blamed because it found the corruption. This is a classic case of shooting the messenger.

Q: I’ve heard that GC uses twice as much memory
This may be true of primitive collectors (like the two-space collector), but this is not generally true of garbage collection. The data structures used for garbage collection need be no larger than those for manual memory management.

Q: Doesn’t garbage collection make programs slow?
No. The CPU overhead of conservative garbage collection is comparable to that of explicit storage management techniques. Conservative garbage collection performs faster than some explicit algorithms and slower than others, the relative performance being largely dependent on the program.

Q: Manual memory management gives me control—it doesn’t pause.
It is possible for manual memory management to pause for considerable periods, either on allocation or deallocation. It certainly gives no guarantees about performance, in general.
With automatic memory management, such as garbage collection, modern techniques can give guarantees about interactive pause times, and so on.

Q: Why does my disk read so much?
When you are using a virtual memory system, the computer may have to fetch pages of memory from disk before they can be accessed. If the total working set of your active programs exceeds the physical memory(1) available, paging will happen continually, your disk will rattle, and performance will degrade significantly. The only solutions are to install more physical memory, run fewer programs at the same time, or tune the memory requirements of your programs.
The problem is aggravated because virtual memory systems approximate the theoretical working set with the set of pages on which the working set lies. If the actual working set is spread out onto a large number of pages, then the working page-set is large.
When objects that refer to each other are distant in memory, this is known as poor locality of reference. This happens either because the program’s designer did not worry about this, or the memory manager used in the program doesn’t permit the designer to do anything about it.
Note that copying garbage collection can dynamically organize your data according to the program’s reference patterns and thus mitigate this problem.

Q: Where can I get a garbage collector?
The Memory Pool System and the Boehm–Demers–Weiser collector are suitable for C or C++. The best way to get a garbage collector, however, is to program in a language that provides garbage collection natively.

Q: Why does my program use so much memory?
If you are using manual memory management (for example, malloc and free(2) in C), it is likely that your program is failing to free memory blocks after it stops using them. When your code allocates memory on the heap, there is an implied responsibility to free that memory. If a function uses heap memory for returning data, you must decide who takes on that responsibility. Pay special attention to the interfaces between functions and modules. Remember to check what happens to allocated memory in the event of an error or an exception.
If you are using automatic memory management (almost certainly garbage collection), it is probable that your code is remembering some blocks that it will never use in future. This is known as the difference between liveness and reachability. Consider clearing variables that refer to large blocks or networks of blocks, when the data structure is no longer required.

Q: I use a library, and my program grows every time I call it. Why?
If you are using manual memory management, it is likely that the library is allocating data structures on the heap every time it is used, but that they are not being freed. Check the interface documentation for the library; it may expect you to take some action when you have finished with returned data. It may be necessary to close down the library and re-initialize it to recover allocated memory.
Unfortunately, it is all too possible that the library has a memory management bug. In this case, unless you have the source code, there is little you can do except report the problem to the supplier.

It may be possible to add a garbage collector to your language, and this might solve your problems.
With a garbage collector, sometimes objects are retained because there is a reference to them from some global data structure. Although the library might not make any further use of the objects, the collector must retain the objects because they are still reachable.
If you know that a particular reference will never be used in future, it can be worthwhile to overwrite it. This means that the collector will not retain the referred object because of that reference. Other references to the same object will keep it alive, so your program doesn’t need to determine whether the object itself will ever be accessed in future. This should be done judiciously, using the garbage collector’s tools to find what objects are being retained and why.
If your garbage collector is generational, it is possible that you are suffering from premature tenuring, which can often be solved by tuning the collector or using a separate memory area for the library.

Q: Should I write my own memory allocator to make my program fast?
If you are sure that your program is spending a large proportion of its time in memory management, and you know what you’re doing, then it is certainly possible to improve performance by writing a suballocator. On the other hand, advances in memory management technology make it hard to keep up with software written by experts. In general, improvements to memory management don’t make as much difference to performance as improvements to the program algorithms.
In four of the programs investigated, the programmer felt compelled to avoid using the general-purpose storage allocator by writing type-specific allocation routines for the most common object types in the program. The general conclusion is that programmer optimizations in these programs were mostly unnecessary. Simply using a different algorithm appears to improve the performance even more. The conclusion, programmers, instead of spending time writing domain-specific storage allocators, should consider using other publicly-available implementations of storage management algorithms if the one they are using performs poorly.

Q: Why can’t I just use local data on the stack or in global variables?
Global, or static, data is fixed size; it cannot grow in response to the size or complexity of the data set received by a program. Stack-allocated data doesn’t exist once you leave the function (or program block) in which it was declared.
If your program’s memory requirements are entirely predictable and fixed at compile-time, or you can structure your program to rely on stack data only while it exists, then you can entirely avoid using heap allocation. Note that, with some compilers, use of large global memory blocks can bloat the object file size.
It may often seem simpler to allocate a global block that seems “probably large enough” for any plausible data set, but this simplification will almost certainly cause trouble sooner or later.

Q: Why should I worry about virtual memory? Can’t I just use as much memory as I want?
While virtual memory can greatly increase your capacity to store data, there are three problems typically experienced with it:
It does not provide an unlimited amount of memory. In particular, all memory that you actually allocate (as opposed to reserve) has to be stored somewhere. Usually you must have disk space available for all pages containing allocated memory. In a few systems, you can subtract the available physical memory from the disk space required. If the memory contains images of program or data files, then file mapping, or assigning existing files to regions of the virtual address space, can help considerably.
In most computers, there is a large difference in speed between main memory and disk; running a program with a working set that does not fit in physical memory almost always results in unacceptable performance.
An additional problem with using unnecessary quantities of memory is that poor locality of reference can result in heavy paging.

 

Memory Management in Java Interview Questions and Answers

Q: What does the statement “memory is managed in Java” mean?
Memory is the key resource an application requires to run effectively and like any resource, it is scarce. As such, its allocation and deallocation to and from applications or different parts of an application require a lot of care and consideration.

However, in Java, a developer does not need to explicitly allocate and deallocate memory – the JVM and more specifically the Garbage Collector – has the duty of handling memory allocation so that the developer doesn’t have to.

This is contrary to what happens in languages like C where a programmer has direct access to memory and literally references memory cells in his code, creating a lot of room for memory leaks.

Q: What is Garbage Collection and what are its advantages?
Garbage collection is the process of looking at heap memory, identifying which objects are in use and which are not, and deleting the unused objects.

An in-use object, or a referenced object, means that some part of your program still maintains a pointer to that object. An unused object, or unreferenced object, is no longer referenced by any part of your program. So the memory used by an unreferenced object can be reclaimed.

The biggest advantage of garbage collection is that it removes the burden of manual memory allocation/deallocation from us so that we can focus on solving the problem at hand.

Q: Are there any disadvantages of Garbage Collection?
Yes. Whenever the garbage collector runs, it has an effect on the application’s performance. This is because all other threads in the application have to be stopped to allow the garbage collector thread to effectively do its work.

Depending on the requirements of the application, this can be a real problem that is unacceptable by the client. However, this problem can be greatly reduced or even eliminated through skillful optimization and garbage collector tuning and using different GC algorithms.

Q: What is the meaning of the term “stop-the-world”?

When the garbage collector thread is running, other threads are stopped, meaning the application is stopped momentarily. This is analogous to house cleaning or fumigation where occupants are denied access until the process is complete.

Depending on the needs of an application, “stop the world” garbage collection can cause an unacceptable freeze. This is why it is important to do garbage collector tuning and JVM optimization so that the freeze encountered is at least acceptable.

Q: What are stack and heap? What is stored in each of these memory structures, and how are they interrelated?
The stack is a part of memory that contains information about nested method calls down to the current position in the program. It also contains all local variables and references to objects on the heap defined in currently executing methods.

This structure allows the runtime to return from the method knowing the address whence it was called, and also clear all local variables after exiting the method. Every thread has its own stack.

The heap is a large bulk of memory intended for allocation of objects. When you create an object with the new keyword, it gets allocated on the heap. However, the reference to this object lives on the stack.

Q: What is generational garbage collection and what makes it a popular garbage collection approach?
Generational garbage collection can be loosely defined as the strategy used by the garbage collector where the heap is divided into a number of sections called generations, each of which will hold objects according to their “age” on the heap.

Whenever the garbage collector is running, the first step in the process is called marking. This is where the garbage collector identifies which pieces of memory are in use and which are not. This can be a very time-consuming process if all objects in a system must be scanned.

As more and more objects are allocated, the list of objects grows and grows leading to longer and longer garbage collection time. However, empirical analysis of applications has shown that most objects are short-lived.

With generational garbage collection, objects are grouped according to their “age” in terms of how many garbage collection cycles they have survived. This way, the bulk of the work spread across various minor and major collection cycles.

Today, almost all garbage collectors are generational. This strategy is so popular because, over time, it has proven to be the optimal solution.

Q: Describe in detail how generational garbage collection works
To properly understand how generational garbage collection works, it is important to first remember how Java heap is structured to facilitate generational garbage collection.

The heap is divided up into smaller spaces or generations. These spaces are Young Generation, Old or Tenured Generation, and Permanent Generation.

The young generation hosts most of the newly created objects. An empirical study of most applications shows that majority of objects are quickly short lived and therefore, soon become eligible for collection. Therefore, new objects start their journey here and are only “promoted” to the old generation space after they have attained a certain “age”.

The term “age” in generational garbage collection refers to the number of collection cycles the object has survived.

The young generation space is further divided into three spaces: an Eden space and two survivor spaces such as Survivor 1 (s1) and Survivor 2 (s2).

The old generation hosts objects that have lived in memory longer than a certain “age”. The objects that survived garbage collection from the young generation are promoted to this space. It is generally larger than the young generation. As it is bigger in size, the garbage collection is more expensive and occurs less frequently than in the young generation.

The permanent generation or more commonly called, PermGen, contains metadata required by the JVM to describe the classes and methods used in the application. It also contains the string pool for storing interned strings. It is populated by the JVM at runtime based on classes in use by the application. In addition, platform library classes and methods may be stored here.

First, any new objects are allocated to the Eden space. Both survivor spaces start out empty. When the Eden space fills up, a minor garbage collection is triggered. Referenced objects are moved to the first survivor space. Unreferenced objects are deleted.

During the next minor GC, the same thing happens to the Eden space. Unreferenced objects are deleted and referenced objects are moved to a survivor space. However, in this case, they are moved to the second survivor space (S1).

In addition, objects from the last minor GC in the first survivor space (S0) have their age incremented and are moved to S1. Once all surviving objects have been moved to S1, both S0 and Eden space are cleared. At this point, S1 contains objects with different ages.

At the next minor GC, the same process is repeated. However this time the survivor spaces switch. Referenced objects are moved to S0 from both Eden and S1. Surviving objects are aged. Eden and S1 are cleared.

After every minor garbage collection cycle, the age of each object is checked. Those that have reached a certain arbitrary age, for example, 8, are promoted from the young generation to the old or tenured generation. For all subsequent minor GC cycles, objects will continue to be promoted to the old generation space.

This pretty much exhausts the process of garbage collection in the young generation. Eventually, a major garbage collection will be performed on the old generation which cleans up and compacts that space. For each major GC, there are several minor GCs.

Q: When does an object become eligible for garbage collection? Describe how the GC collects an eligible object?

An object becomes eligible for Garbage collection or GC if it is not reachable from any live threads or by any static references.

The most straightforward case of an object becoming eligible for garbage collection is if all its references are null. Cyclic dependencies without any live external reference are also eligible for GC. So if object A references object B and object B references Object A and they don’t have any other live reference then both Objects A and B will be eligible for Garbage collection.

Another obvious case is when a parent object is set to null. When a kitchen object internally references a fridge object and a sink object, and the kitchen object is set to null, both fridge and sink will become eligible for garbage collection alongside their parent, kitchen.

Q: How do you trigger garbage collection from Java code?

You, as Java programmer, can not force garbage collection in Java; it will only trigger if JVM thinks it needs a garbage collection based on Java heap size.

Before removing an object from memory garbage collection thread invokes finalize()method of that object and gives an opportunity to perform any sort of cleanup required. You can also invoke this method of an object code, however, there is no guarantee that garbage collection will occur when you call this method.

Additionally, there are methods like System.gc() and Runtime.gc() which is used to send request of Garbage collection to JVM but it’s not guaranteed that garbage collection will happen.

Q: What happens when there is not enough heap space to accommodate storage of new objects?

If there is no memory space for creating a new object in Heap, Java Virtual Machine throws OutOfMemoryError or more specifically java.lang.OutOfMemoryError heap space.

Q: Is it possible to «resurrect» an object that became eligible for garbage collection?
When an object becomes eligible for garbage collection, the GC has to run the finalize method on it. The finalize method is guaranteed to run only once, thus the GC flags the object as finalized and gives it a rest until the next cycle.

In the finalize method you can technically “resurrect” an object, for example, by assigning it to a static field. The object would become alive again and non-eligible for garbage collection, so the GC would not collect it during the next cycle.

The object, however, would be marked as finalized, so when it would become eligible again, the finalize method would not be called. In essence, you can turn this “resurrection” trick only once for the lifetime of the object. Beware that this ugly hack should be used only if you really know what you’re doing — however, understanding this trick gives some insight into how the GC works.

Q: How does Java allocate stack and heap memory?
Each time an object is created in Java it goes into the area of memory known as heap. The primitive variables like int and double are allocated in the stack (i.e. Last In First Out queue), if they are local variables and in the heap if they are member variables (i.e. fields of a class). In Java methods and local variables are pushed into stack when a method is invoked and stack pointer is decremented when a method call is completed. In a multi-threaded application each thread will have its own stack but will share the same heap. This is why care should be taken in your code to avoid any concurrent access issues in the heap space. The stack is thread-safe because each thread will have its own stack.

Q: Is there any possible memory leak in Java?
Memory leak is unused but referenced part of the memory. Though GC takes care of cleaning up your memory/heap, but if you have used some native objects and forgot to reclaim the memory explicitly because that’s anyway not going to be taken care by the GC (which takes care of heap memory management only).

Similarly, using ‘static’ also can be one of the potential reasons for memory leaks in Java. ‘static’ can’t straightway be blamed for causing memory leaks; but if programmer has not taken care of the setting the references to ‘null’ explicitly after using the static objects then they can definitely cause memory leaks. Since ‘static’ members will by default live for the entire life of an app unless they are explicitly set to ‘null’. So, always make it a point to nullify the references as soon as you reach at a point in your code where the use of the static member is over.

Ex: Suppose you have created a ‘Statement’ object from a DB Connection and the connection is a pooled one. Now as you know calling close() method on a pooled connection will not actually close the connection instead it will return the Connection object to the pool to be re-used.

Memory Pool Examples:

Allocate a block of memory in a pool


my_object *obj;
res = mps_alloc((mps_addr_t *)&obj, pool, sizeof *obj);
if (res != MPS_RES_OK)
    error(...);

Allocation point protocol in C


mps_addr_t p;
obj_t obj;
size_t aligned_size = ALIGN(size); /* see note 1 */
do {
    mps_res_t res = mps_reserve(&p, ap, aligned_size);
    if (res != MPS_RES_OK)
        /* handle the error */;
    /* p is now an ambiguous reference to the reserved block */
    obj = p;
    /* initialize obj */
} while (!mps_commit(ap, p, aligned_size)); /* see note 2 */
/* obj is now valid and managed by the MPS */

So, in such a case unless you explicitly close the ‘Statement’ object, it would keep consuming precious memory space for no real use. Now if you have declared the ‘Statement’ object as a static member, it’ll be maintained in the memory for the entire life time of the app even when the control is out of the scope. Now that if your Statement object is non-static, it will eligible for garbage collection, once it is out-of-scope. However, there is still wastage of memory after using the Statement last and before reaching the end of the local scope.

Therefore, in summary we can say that one should/must :-
Always think if you really need to make this variable/member a ‘static’.
Always try to confine the scope of an object to restrict its usage only to the section it’s actually needed.
Always make a conscious effort to explicitly nullify objects once you finish using them (especially the large objects)

Q: Explain memory management in java.
In java, memory is managed via garbage collector. Few techniques for memory management are:

1. Reference Counting: A count of references to each object is maintained. When garbage collector runs, it deletes objects with zero reference count.
Drawback: Circular references are maintained in memory.

2. Tracing collectors/Copy Collector/Stop and copy collector: Start from a root object and keep track of all references which have direct or indirect reference to the root object. Then all the live objects are moved to another heap, taking care of references properly.
Drawback: At each point of time, you will have 2 heaps thus consuming twice the memory.

3. Mark sweep collectors/Stop and work collector: Similar to tracing collector except that instead of copying the references to the new heap, they are swept out of memory, after a list of live and dead objects is known.

Mark and sweep is a stop-the-world garbage collection technique; that is all application threads stop until garbage collection completes or until a higher-priority thread interrupts the garbage collector. If the garbage collector is interrupted it must restart which can lead to application thrashing with little apparent result.

http://www.ibm.com/developerworks/java/library/j-jtp10283/

Q: Does Java have destructors?
Garbage collector does the job working in the background. Java does not have destructors; but it has finalizer that does a similar job.
Syntax is: public void finalize() { }

If an object has a finalizer, the method is invoked before the system garbage collects the object.

Q: Does the finalize method in subclass invoke finalize method in super class?
Finalize is not implicitly chained. A finalize method in sub-class should call finalize in super class explicitly as its last action for proper functioning. Compilers don’t enforce this check.

Q: Can finalize method be overloaded?
Yes but only the following version is called by garbage collector:

protected void finalize() throws Throwable { };

Q: Should I override finalize method?
Unlike C++ destructors, the finalize() method in Java is unpredictable, often dangerous and generally unnecessary. Use try and finally blocks while implementing finalize method. The finalize() method should only be used in rare instances as a safety net or to terminate non-critical native resources. If you do happen to call the finalize() method in some rare instances then remember to call the super.finalize() as shown below:

protected void finalize() throws Throwable {
try {
//finalize subclass state
}

finally {
super.finalize();
}
}

Q: An object is resurrected by making other object refer to the dying object in finalize method. Will this object be ever garbage collected?
Resurrection can happen in finalize method which will prevent GC to reclaim the object memory. However this could be done only once. Next time GC will not invoke finalize method before garbage collection.

Well, the problem is that an object which overrides finalize() must now be determined to be garbage in at least two separate garbage collection cycles in order to be collected. When the first cycle determines that it is garbage, it becomes eligible for finalization. Because of the (slim, but unfortunately real) possibility that the object was “resurrected” during finalization, the garbage collector has to run again before the object can actually be removed. And because finalization might not have happened in a timely fashion, an arbitrary number of garbage collection cycles might have happened while the object was waiting for finalization. This can mean serious delays in actually cleaning up garbage objects, and is why you can get OutOfMemoryErrors even when most of the heap is garbage.

Q: Explain types of references in Java? java.lang.ref package can be used to declare soft, weak and phantom references.
There are actually four different degrees of reference strength: strong, soft, weak, and phantom, in order from strongest to weakest:

Strong Reference: By default.

Weak references: A weak reference is a reference that isn’t strong enough to force an object to remain in memory. Weak references allow you to leverage the garbage collector’s ability to determine reachability for you, so you don’t have to do it yourself. You create a weak reference like this:

WeakReference weakWidget = new WeakReference(widget);
weakWidget.get() // get the actual Widget

Of course the weak reference isn’t strong enough to prevent garbage collection, so you may find (if there are no strong references to the widget) that weakWidget.get() suddenly starts returning null.

Soft references: A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers. An object which is only weakly reachable (the strongest references to it are WeakReferences) will be discarded at the next garbage collection cycle, but an object which is softly reachable will generally stick around for a while. Soft References aren’t required to behave any differently than WeakReferences, but in practice softly reachable objects are generally retained as long as memory is in plentiful supply. This makes them an excellent foundation for a cache, since you can let the garbage collector worry about both how reachable the objects are and how badly it needs the memory they are consuming.

Phantom references
A phantom reference is quite different than either SoftReference or WeakReference. Its grip on its object is so tenuous that you can’t even retrieve the object — its get() method always returns null. The only use for such a reference is keeping track of when it gets enqueued into a ReferenceQueue, as at that point you know the object to which it pointed is dead. How is that different from WeakReference, though?

The difference is in exactly when the enqueuing happens. WeakReferences are enqueued as soon as the object to which they point becomes weakly reachable. This is before finalization or garbage collection has actually happened. In case of Weak Reference, object could even be “resurrected” by an finalize() method, but the WeakReference would remain dead. PhantomReferences are enqueued only when the object is physically removed from memory, and the get() method always returns null specifically to prevent you from being able to “resurrect” an almost-dead object.

Use of Phantom Reference:
1. They allow you to determine exactly when an object was removed from memory. They are in fact the only way to determine that. This isn’t generally that useful, but might come in handy in certain very specific circumstances like manipulating large images: if you know for sure that an image should be garbage collected, you can wait until it actually is before attempting to load the next image, and therefore make the dreaded OutOfMemoryError less likely.

2. PhantomReferences avoid a fundamental problem with finalization – resurrection. With PhantomReference, resurrection is impossible. When a PhantomReference is enqueued, there is absolutely no way to get a pointer to the now-dead object.Arguably, the finalize() method should never have been provided in the first place. PhantomReferences are definitely safer and more efficient to use, and eliminating finalize() would have made parts of the VM considerably simpler. But, they’re also more work to implement, so I confess to still using finalize() most of the time. The good news is that at least you have a choice.

Q: Talk about garbage collector for various references.
If an element is determined to be eligible for processing, GC must determine if it is eligible for collection. The first criterion here is simple. Is the referent marked? If it is marked, the reference object is not eligible for collection and GC moves onto the next element of the list. However, if the referent is not marked and is eligible for collection, the process differs for each reference type.

Soft references are collected if their referent has not been marked for the previous 32 garbage collection cycles. You adjust the frequency of collection with the -Xsoftrefthreshold option. If there is a shortage of available storage, all soft references are cleared. All soft references are guaranteed to have been cleared before the OutOfMemoryError is thrown.

Weak and phantom references are always collected if their referent is not marked.

Q: Explain garbage collection on Remote Objects or Distributed Garbage collection.
In a distributed system, just as in the local system, it is desirable to automatically delete those remote objects that are no longer referenced by any client. This frees the programmer from needing to keep track of the remote objects’ clients so that it can terminate appropriately. RMI uses a reference-counting garbage collection algorithm for the same.

To accomplish reference-counting garbage collection, the RMI runtime keeps track of all live references within each Java virtual machine. When a live reference enters a Java virtual machine for first time, it sends a “referenced” message to the server for the object. Going forward, whenever a live reference enters JVM, its reference count is incremented and is decremented as soon as it leaves the JVM. When the last reference has been discarded, an unreferenced message is sent to the server. Many subtleties exist in the protocol; most of these are related to maintaining the ordering of referenced and unreferenced messages in order to ensure that the object is not prematurely collected.

When a remote object is not referenced by any client, the RMI runtime refers to it using a weak reference. The weak reference allows the Java virtual machine’s garbage collector to discard the object if no other local references to the object exist. As long as a local reference to a remote object exists, it cannot be garbage-collected and it can be passed in remote calls or returned to clients. Remote objects are only collected when no more references, either local or remote, still exist. The distributed garbage collection algorithm interacts with the local Java virtual machine’s garbage collector in the usual ways by holding normal or weak references to objects.

In addition to the reference counting mechanism, a live client reference has a lease with a specified time. When the client is done with the reference and allows the remote stub to go out of scope, or when the lease on the object expires, the reference layer on the host automatically deletes the record of the remote reference and notifies the client’s reference layer that this remote reference has expired. The lease time is controlled by the system property java.rmi.dgc.leaseValue. The value is in milliseconds and defaults to 10 minutes. The concept of expirable leases, as opposed to strict on/off references, is used to deal with situations where a client-side failure or a network failure keeps the client from notifying the server that it is done with its reference to an object.

A remote object needing unreferenced notification must implement the java.rmi.server.Unreferenced interface. When those references no longer exist, the unreferenced method will be invoked.

Q: Does OutOfMemoryError and StackOverFlowError cause JVM crash?
Any problem in PURE Java code throws a Java exception or error. Java exceptions or errors will NOT cause a core dump (on UNIX systems) or a Dr.Watson error (on WIN32systems). Any serious Java problem will result in an OutOfMemoryError thrown by the JVM with the stack trace and consequently JVM will exit. An OutOfMemoryError (not jvm crash) can be thrown due to one of the following 4 reasons:

1. JVM may have a memory leak due to a bug in its internal heap management implementation. But this is highly unlikely because JVMs are well tested for this.

2. The application may not have enough heap memory allocated for its running. You can allocate more JVM heap size (with –Xmx parameter to the JVM) or decrease the amount of memory your application takes to overcome this. You can increase heap size as below:
java -Xms1024M -Xmx1024M

Care should be taken not to make the –Xmx value too large because it can slow down your application.

3. Another not so prevalent cause is the running out of a memory area called the “perm” which sits next to the heap. All the binary code of currently running classes is archived in the “perm” area. The ‘perm’ area is important if your application or any of the third party jar files you use dynamically generate classes.
For example: “perm” space is consumed when XSLT templates are dynamically compiled into classes, J2EE application servers, JasperReports, JAXB etc use Java reflection to dynamically generate classes and/or large amount of classes in your application. To increase perm space:
java -XX:PermSize=256M -XX:MaxPermSize=256M

4. The fourth and the most common reason is that you may have a memory leak in your application.

Q: Different OutOfMemory errors.
Let’s have a look at the Sun HotSpot JVM and its concrete implementation of OutOfMemoryError errors.

1. In the heap we get an OutOfMemoryError, if the garbage collector cannot reclaim enough memory for a new object. In such situation the Sun HotSpot JVM shows this error message:
java.lang.OutOfMemoryError: Java heap space

2. An alternative for this is as below, it occurs when application tries to create an array on the heap that is bigger than the total heap size.
java.lang.OutOfMemoryError: Requested array size exceeds VM limit

3. If there is not enough memory in the method area for creating a new class, the Sun HotSpot implementation gets an error in the permanent generation:
java.lang.OutOfMemoryError: PermGen space

4. OutOfMemory errors in thread exclusive memory areas occur less frequently and are identified by the following error messages in the Sun HotSpot JVM:
java.lang.OutOfMemoryError: unable to create new native thread

This occurs if there are too many threads in the JVM and there is not enough memory left to create a new thread. I’ve seen this because the memory limits of a process have been reached (especially in 32bit operating systems, e.g. on Windows 32bit it is 2GB) or the maximum number of file handles for the user that executes the java process has been reached.

5. It indicates that a memory allocation error on a native stack (JNI method call) has occured.
java.lang.OutOfMemoryError: (Native method)

6. It is also interesting that a memory allocation error on the JVM stack (too many frames on the stack) does not throw an Java OutOfMemory error but as the JVM specification mandates.
java.lang.StackOverflowError

7. The last variant of the OutOfMemoryError is out of swap space. This error is thrown if there is not enough memory left on the operating system level – which is normally true if other processes are using all of the available memory or the swap space is configured too small.
java.lang.OutOfMemoryError: request bytes for .

Q: Why does the JVM crash with a core dump or a Dr.Watson error?
Both the core dump on UNIX operating system and Dr.Watson error on WIN32 systems mean the same thing. If you define a crash as an unhandled problem (i.e. no Java Exception or Error); then this cannot be done from within Java. The JVM is a process like any other and when a process crashes a core dump is created. A core dump is a memory map of a running process. This can happen due to one of the following reasons:

1. Using JNI (Java Native Interface) code containing a fatal bug in it. Typical crashes in native code happen by dereferencing pointers to wrong memory areas (like Nullpointer) or illegal opcodes.
For ex: using Oracle OCI drivers, which are written partially in native code or JDBC-ODBC bridge drivers, which are written in non Java code. Using 100% pure Java drivers (communicates directly with the database instead of through client software utilizing the JNI) instead of native drivers can solve this problem.

2. The OS on which your JVM is running might require a patch or service pack.

3. The JVM implementation may have a bug in translating system resources like threads, file handles, sockets etc from the platform neutral Java byte code into platform specific operations. If this JVM’s translated native code performs an illegal operation then the operating system will instantly kill the process and mostly will generate a core dump file.

The core dump files are generated by the operating system in response to certain signals. The JVM can also intercept certain signals like SIGQUIT which is kill -3 from the operating system and it responds to this signal by printing out a Java stack trace and then continue to run. On the other hand signals like SIGSTOP (kill -23 ) and SIGKILL (kill -9 ) will cause the JVM process to stop or die. The JVM argument “java –Xsqnopause” will indicate JVM not to pause on SIGQUIT signal from OS.

4. On Linux/Unix, it is easy to crash JVM crash by sending it a Signal to the running process.

Note: You should not use “SIGSEGV” for this, since JVM catches this signal and re-throws it as a NullPointerException in most places. So it is better to send a SIGBUS.

Q: Describe strong, weak, soft and phantom references and their role in garbage collection.

Much as memory is managed in Java, an engineer may need to perform as much optimization as possible to minimize latency and maximize throughput, in critical applications. Much as it is impossible to explicitly control when garbage collection is triggered in the JVM, it is possible to influence how it occurs as regards the objects we have created.

Java provides us with reference objects to control the relationship between the objects we create and the garbage collector.

By default, every object we create in a Java program is strongly referenced by a variable:

1
StringBuilder sb = new StringBuilder();

In the above snippet, the new keyword creates a new StringBuilder object and stores it on the heap. The variable sb then stores a strong reference to this object. What this means for the garbage collector is that the particular StringBuilder object is not eligible for collection at all due to a strong reference held to it by sb. The story only changes when we nullify sb like this:

1
sb = null;

After calling the above line, the object will then be eligible for collection.

We can change this relationship between the object and the garbage collector by explicitly wrapping it inside another reference object which is located inside java.lang.ref package.

A soft reference can be created to the above object like this:

1
2
3
StringBuilder sb = new StringBuilder();
SoftReference<StringBuilder> sbRef = new SoftReference<>(sb);
sb = null;

In the above snippet, we have created two references to the StringBuilder object. The first line creates a strong reference sb and the second line creates a soft reference sbRef. The third line should make the object eligible for collection but the garbage collector will postpone collecting it because of sbRef.

The story will only change when memory becomes tight and the JVM is on the brink of throwing an OutOfMemory error. In other words, objects with only soft references are collected as a last resort to recover memory.

A weak reference can be created in a similar manner using WeakReference class. When sb is set to null and the StringBuilder object only has a weak reference, the JVM’s garbage collector will have absolutely no compromise and immediately collect the object at the very next cycle.

A phantom reference is similar to a weak reference and an object with only phantom references will be collected without waiting. However, phantom references are enqueued as soon as their objects are collected. We can poll the reference queue to know exactly when the object was collected.

Q: Suppose we have a circular reference (two objects that reference each other). Could such pair of objects become eligible for garbage collection and why?

Yes, a pair of objects with a circular reference can become eligible for garbage collection. This is because of how Java’s garbage collector handles circular references. It considers objects live not when they have any reference to them, but when they are reachable by navigating the object graph starting from some garbage collection root (a local variable of a live thread or a static field). If a pair of objects with a circular reference is not reachable from any root, it is considered eligible for garbage collection.

Q: How are strings represented in memory?

A String instance in Java is an object with two fields: a char[] value field and an int hash field. The value field is an array of chars representing the string itself, and the hash field contains the hashCode of a string which is initialized with zero, calculated during the first hashCode() call and cached ever since. As a curious edge case, if a hashCode of a string has a zero value, it has to be recalculated each time the hashCode() is called.

Important thing is that a String instance is immutable: you can’t get or modify the underlying char[] array. Another feature of strings is that the static constant strings are loaded and cached in a string pool. If you have multiple identical String objects in your source code, they are all represented by a single instance at runtime.

Q: What is a StringBuilder and what are its use cases? What is the difference between appending a string to a StringBuilder and concatenating two strings with a + operator? How does StringBuilder differ from StringBuffer?

StringBuilder allows manipulating character sequences by appending, deleting and inserting characters and strings. This is a mutable data structure, as opposed to the String class which is immutable.

When concatenating two String instances, a new object is created, and strings are copied. This could bring a huge garbage collector overhead if we need to create or modify a string in a loop. StringBuilder allows handling string manipulations much more efficiently.

StringBuffer is different from StringBuilder in that it is thread-safe. If you need to manipulate a string in a single thread, use StringBuilder instead.