Java > Concurrency > Difference between invokeAll and invokeAny

Posted on

package com.exact.tests.thread;

import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import org.junit.Ignore;
import org.junit.Test;

public class ThreadTests {
    @Test
    public void testExecutorServiceInvokeAll() throws Exception{
        ExecutorService srv = Executors.newFixedThreadPool(5);
        AtomicInteger counter = new AtomicInteger();
        Callable<String> task = ()->{
            String name = "TunaThread"+counter.incrementAndGet();
            for(int i=0;i<100;i++){
                System.out.println(name+" - Test "+i);
                if(Thread.interrupted()){
                    System.out.println(name+" - Interruppted and BROKE LOOP");
                    break;
                }
            }
            return "Finished";
        };

        srv.invokeAll(new ArrayList<Callable<String>>(){{add(task);add(task);add(task);}});
    }
    @Test
    public void testExecutorServiceInvokeAll() throws Exception{
        ExecutorService srv = Executors.newFixedThreadPool(5);
        AtomicInteger counter = new AtomicInteger();
        Callable<String> task = ()->{
            String name = "TunaThread"+counter.incrementAndGet();
            for(int i=0;i<100;i++){
                System.out.println(name+" - Test "+i);
                if(Thread.interrupted()){
                    System.out.println(name+" - Interruppted and BROKE LOOP");
                    break;
                }
            }
            return "Finished";
        };

        srv.invokeAny(new ArrayList<Callable<String>>(){{add(task);add(task);add(task);}});
    }
}
//your code comes here

Beğendiğim Özlü Sözler

Posted on Updated on

Ne yavuz ol asıl, ne yavaş ol basıl – Anonim

Dere geçerken at değiştirilmez – Anonim

Çalıda gül bitmez, cahile söz yetmez – Anonim

Bal tutan parmağını yalar – Anonim

Interview Question and Answer: Elevator Algorithm

Posted on Updated on

Image

One of the interview questions asked is “Elevator Algorithm”. As you think this problem seems easy, but you might not be easily think of the algorithm in a fast manner. I have written a simple version of it and I think this would be enough for an interview.

ElevatorCabin Class

This class is the core class that nearly all of the logic runs, so it will be enough for you to view this thorough.

package org.tuna.elevator;

import java.util.TreeSet;

public class ElevatorCabin {
	
	public int currentFloor = 0;
	public UpDownEnum direction = UpDownEnum.UP;
	public TreeSet<Integer> callingFloorList  = new TreeSet<Integer>();
	
	public void add(Integer floor){
		callingFloorList.add(floor);
	}
	
	public Integer gotoNext(){
		Integer nextFloor = currentFloor;
		switch(direction){
		case UP:
			for (Integer floor : callingFloorList) {
				if(floor > nextFloor){
					nextFloor = floor;
					direction = UpDownEnum.UP;
					break;
				}
			}
			
			if(nextFloor == currentFloor){
				for (Integer floor : callingFloorList.descendingSet()) {
					if(floor < nextFloor){
						nextFloor = floor;
						direction = UpDownEnum.DOWN;
						break;
					}
				}
			}
			break;
		case DOWN:
			for (Integer floor : callingFloorList.descendingSet()) {
				if(floor < nextFloor){
					nextFloor = floor;
					direction = UpDownEnum.DOWN;
					break;
				}
			}
			
			if(nextFloor == currentFloor){
				for (Integer floor : callingFloorList) {
					if(floor > nextFloor){
						nextFloor = floor;
						direction = UpDownEnum.UP;
						break;
					}
				}
			}
		}
		callingFloorList.remove(nextFloor);
		currentFloor = nextFloor;
		return nextFloor;
	}
}

ElevatorEngine Class

This class is the engine that will simulate the work of an elevator using the thread mechanism.

package org.tuna.elevator;

public class ElevatorEngine extends Thread{
	
	private ElevatorCabin cabin = new ElevatorCabin();
	private volatile boolean stopFlag = false;
	
	public void startEngine(){
		stopFlag = false;
		this.start();
	}
	
	public void stopEngine(){
		stopFlag = true;
	}
	
	public void run(){
		while(true){
			if(stopFlag){
				if(cabin.callingFloorList.isEmpty()){					
					break;
				}
			}
			Integer next = cabin.gotoNext();
			System.out.println("Next floor is "+next);
			
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
	
	public void pressButton(int floor){
		System.out.println("Pressed "+floor);
		cabin.add(floor);
	}
}

ElevatorEngineDriver Class

The driver classs to test the algorithm.

package org.tuna.elevator;

public class ElevetorEngineDriver {
	public static void main(String[] args) {
		ElevatorEngine engine = new ElevatorEngine();
		engine.startEngine();
		
		engine.pressButton(1);
		sleep();
		engine.pressButton(5);
		engine.pressButton(6);
		engine.pressButton(1);
		engine.pressButton(4);
		sleep();sleep();sleep();
		engine.pressButton(2);
		engine.pressButton(9);
		engine.pressButton(1);
		sleep();
		engine.stopEngine();
		try {
			engine.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
	
	public static void sleep(){
		try {
			Thread.sleep(1500);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
}

Json Sample To Pojo Generator

Posted on Updated on

I developed a generator for JSON. This generator gets a json sample as the input and outputs the generated Java classes that you can use as entities in your project.

Input Example

{
    "account_uri": "https://test.com/1.0/user/accounts/123abc124",
    "account_uuid": "123abc124",
    "correlation_tag": "123tag124",
    "account_info_uri": "https://test.com/1.0/user/account_info/123abc124",
    "login_history_uri": "https://test.com/1.0/user/login_history/123abc124",
    "account_info": {
        "create_date": "2012-03-01T12:00:11Z",
        "created_by": "11gg22cc33",
        "create_channel": "X01",
        "last_update_date": "2012-09-01T14:22:15Z",
        "last_updated_by": "11gg22cc33",
        "anonymization_date": ""
    }
}

Output Example

Output is two Java classes

AccountDetail Class

package org.tuna.model.types;

import com.fasterxml.jackson.annotation.JsonProperty;
import com.fasterxml.jackson.annotation.JsonPropertyOrder;
import java.lang.String;
import com.sony.gcim.client.model.types.AccountInfo;

@JsonPropertyOrder({"accountUri","accountUuid","correlationTag","accountInfoUri","loginHistoryUri","accountInfo"})
public class AccountDetail {
    private String accountUri;
    private String accountUuid;
    private String correlationTag;
    private String accountInfoUri;
    private String loginHistoryUri;
    private AccountInfo accountInfo;

    @JsonProperty("account_uri")
    public String getAccountUri(){
        return this.accountUri;
    }

    public void setAccountUri(String accountUri){
        this.accountUri = accountUri;
    }

    @JsonProperty("account_uuid")
    public String getAccountUuid(){
        return this.accountUuid;
    }

    public void setAccountUuid(String accountUuid){
        this.accountUuid = accountUuid;
    }

    @JsonProperty("correlation_tag")
    public String getCorrelationTag(){
        return this.correlationTag;
    }

    public void setCorrelationTag(String correlationTag){
        this.correlationTag = correlationTag;
    }

    @JsonProperty("account_info_uri")
    public String getAccountInfoUri(){
        return this.accountInfoUri;
    }

    public void setAccountInfoUri(String accountInfoUri){
        this.accountInfoUri = accountInfoUri;
    }

    @JsonProperty("login_history_uri")
    public String getLoginHistoryUri(){
        return this.loginHistoryUri;
    }

    public void setLoginHistoryUri(String loginHistoryUri){
        this.loginHistoryUri = loginHistoryUri;
    }

    @JsonProperty("account_info")
    public AccountInfo getAccountInfo(){
        return this.accountInfo;
    }

    public void setAccountInfo(AccountInfo accountInfo){
        this.accountInfo = accountInfo;
    }



    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append("AccountDetail[").append("accountUri : ").append(accountUri).append(",\n")
               .append("accountUuid : ").append(accountUuid).append(",\n")
               .append("correlationTag : ").append(correlationTag).append(",\n")
               .append("accountInfoUri : ").append(accountInfoUri).append(",\n")
               .append("loginHistoryUri : ").append(loginHistoryUri).append(",\n")
               .append("accountInfo : ").append(accountInfo).append(",\n")
               .append("]");
        return builder.toString();
    }
}

AccountInfo Class

package org.tuna.model.types;

import com.fasterxml.jackson.annotation.JsonProperty;
import com.fasterxml.jackson.annotation.JsonPropertyOrder;
import java.lang.String;
import java.lang.String;
import java.lang.String;
import java.lang.String;
import java.lang.String;
import java.lang.String;

@JsonPropertyOrder({"createDate","createdBy","createChannel","lastUpdateDate","lastUpdatedBy","anonymizationDate"})
public class AccountInfo {
    private String createDate;
    private String createdBy;
    private String createChannel;
    private String lastUpdateDate;
    private String lastUpdatedBy;
    private String anonymizationDate;

    @JsonProperty("create_date")
    public String getCreateDate(){
        return this.createDate;
    }

    public void setCreateDate(String createDate){
        this.createDate = createDate;
    }

    @JsonProperty("created_by")
    public String getCreatedBy(){
        return this.createdBy;
    }

    public void setCreatedBy(String createdBy){
        this.createdBy = createdBy;
    }

    @JsonProperty("create_channel")
    public String getCreateChannel(){
        return this.createChannel;
    }

    public void setCreateChannel(String createChannel){
        this.createChannel = createChannel;
    }

    @JsonProperty("last_update_date")
    public String getLastUpdateDate(){
        return this.lastUpdateDate;
    }

    public void setLastUpdateDate(String lastUpdateDate){
        this.lastUpdateDate = lastUpdateDate;
    }

    @JsonProperty("last_updated_by")
    public String getLastUpdatedBy(){
        return this.lastUpdatedBy;
    }

    public void setLastUpdatedBy(String lastUpdatedBy){
        this.lastUpdatedBy = lastUpdatedBy;
    }

    @JsonProperty("anonymization_date")
    public String getAnonymizationDate(){
        return this.anonymizationDate;
    }

    public void setAnonymizationDate(String anonymizationDate){
        this.anonymizationDate = anonymizationDate;
    }



    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append("AccountInfo[").append("createDate : ").append(createDate).append(",\n")
               .append("createdBy : ").append(createdBy).append(",\n")
               .append("createChannel : ").append(createChannel).append(",\n")
               .append("lastUpdateDate : ").append(lastUpdateDate).append(",\n")
               .append("lastUpdatedBy : ").append(lastUpdatedBy).append(",\n")
               .append("anonymizationDate : ").append(anonymizationDate).append(",\n")
               .append("]");
        return builder.toString();
    }
}

You can download source code which also includes build.xml from here

How To Proceed

the jsontopojo/src/main/resources/build.xml is the part that does the generation.
1. First thing is that you have eclipse, when you import this project as a maven project you will have the dependencies downloaded from maven repos.
2. You should change the maven.repo path in build.xml with your own.

<property name="maven.repo" value="TODO: Path to your maven repo"/>

3. Put you sample json as jsontopojo/build/jsontest.json
4. Finally run ant using the build.xml, the default task is set to jsontopojo.gen already, so you just run it.
5. You will have your source code generated, you will see it in the eclipse project when you refreshed it.

Interview Question and Answer [06]

Posted on

QUESTION: Given a dictionary of millions of words, give an algorithm to find the largest possible
rectangle of letters such that every row forms a word (reading left to right) and every
column forms a word (reading top to bottom).

EXAMPLE: You will create a rectangle of words using word in the given word array.

strafer
taeniae
resters
antiflu
fiefdom
earlobe
resumes

Interview Question and Answer [05]

Posted on Updated on

QUESTION: You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE: Input: {2, -8, 3, -2, 4, -10}, Output: 5 (i.e., {3, -2, 4} )

public class InterviewQuestion {
    public static Integer largestSum(int[] numArr){
        Integer largest = null;
        for(int i=1;i<numArr.length;i++){
            for(int j=0;j<numArr.length-i;j++){
                int summation = 0;
                for(int a=i;a>=0;a--){
                    summation += numArr[j+a];
                }
                if(largest == null || summation > largest){
                    largest = summation;
                }
            }
        }
        
        return largest;
    }
    
    public static void main(String[] args) {
        Integer largestSum = largestSum(new int[]{4,-9,9,-5,6});
        System.out.println(largestSum);
        
    }
}

Interview Question and Answer [04]

Posted on Updated on

QUESTION: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?
ANSWER: The answer to this question would be like this

  1. Create three thread group; one for reading html files, one for searching the read html file texts for phone numbers, the last one is for monitoring the other two thread groups.
  2. The important thing here is to provide the balance between reader threads and search threads. Search thread’s execution will be faster than reader thread because search is all about CPU. but read is all about I/O.

The answer will be enough of course for a interview in microsoft, amazon, apple…etc. But I have also written the code :). I hope someone finds it useful.

Application Written In Java

InterviewQuestion Driver Class

package org.devpattern.interview;

import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class InterviewQuestion {

    public static void main(String[] args) {
        findPhoneNumbersInHtmls("C:/htmls");
    }
    
    /**
     * Creates threads and lists the html files and found phone numbers inside those html files.
     * @param baseFolder
     */
    public static void findPhoneNumbersInHtmls(String baseFolder){
        ThreadContext context = new ThreadContext();
        //20 MB will be allowed as the buffer for html files.
        context.maxSizeInMemory = (long)Math.pow(2, 10)*20;
        createFileList(baseFolder, context);
        
        List<ThreadCommon> threads  = new ArrayList<ThreadCommon>();
        threads.addAll(startSearchThreads(context, 5));
        threads.addAll(startReaderThreads(context, 10));
        startMonitoringThread(context, threads);
    }

    private static void createFileList(String baseFolderPath, ThreadContext context) {
        File baseFolder = new File(baseFolderPath);
        String[] list = baseFolder.list();
        for (String filePath : list) {
            context.htmlFiles.add(new File(baseFolder, filePath));
        }
    }
    
    private static void startMonitoringThread(ThreadContext context, List<ThreadCommon> monitoredThreads){
        MonitoringThread monitor = new MonitoringThread(context, monitoredThreads);
        monitor.start();
    }

    private static List<PhoneSearchThread> startSearchThreads(ThreadContext context, int threadAmount){
        List<PhoneSearchThread> threads = new ArrayList<PhoneSearchThread>();
        for(int i=0;i<threadAmount;i++){
            PhoneSearchThread thread = new PhoneSearchThread(context);
            threads.add(thread);
            thread.start();
        }
        return threads;
    }

    private static List<ReadHtmlThread> startReaderThreads(ThreadContext context, int threadAmount){
        List<ReadHtmlThread> threads = new ArrayList<ReadHtmlThread>();
        for(int i=0;i<threadAmount;i++){
            ReadHtmlThread thread = new ReadHtmlThread(context);
            threads.add(thread);
            thread.start();
        }
        return threads;
    }
}

ThreadCommon Common Thread Class For Reader and Search Threads

package org.devpattern.interview;

import java.util.concurrent.atomic.AtomicBoolean;

public class ThreadCommon extends Thread{
    protected AtomicBoolean stopFlag = new AtomicBoolean(false);
    protected ThreadContext context;
    
    public ThreadCommon(ThreadContext context){
        this.context = context;
    }
    
    public void stopThread(){
        this.stopFlag.set(true);
    }
}

ReadHtmlThread Thread Class For Reading HTML Files

package org.devpattern.interview;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

/**
 * This is the reader thread. This reads the HTML file from the list given in ThreadContext.
 * @author Tuna Ozkasap
 *
 */ 
public class ReadHtmlThread extends ThreadCommon{
    public ReadHtmlThread(ThreadContext context){
        super(context);
    }
    
    public void waitOnContext(){
        synchronized (context) {
            try {
                context.wait();
            } catch (InterruptedException e) {
                System.out.println(this.getClass().getName()+" wait on context interrupted.");
            }
        }
    }

    public void notifyOnContext(){
        synchronized (context) {
            context.notify();
        }
    }

    public boolean readFileIntoContext(File file){
        try {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            StringBuilder builder = new StringBuilder();
            String line = null;
            while((line = reader.readLine()) != null){
                builder.append(line);
            }
            HtmlInfo htmlInfo = new HtmlInfo(builder.toString(), file.getAbsolutePath(), file.getTotalSpace());
            context.htmlInfos.add(htmlInfo);
            reader.close();
            return true;
        } catch (IOException e) {
            context.filesFailed.add(file);
            return false;
        }
    }

    public void run(){
        while(true){
            if(stopFlag.get()){break;}
            
            File htmlFileToRead = null;
            synchronized (context) {
                if(context.htmlFiles.size() > 0){                    
                    htmlFileToRead = context.htmlFiles.remove(context.htmlFiles.size()-1);
                }
            }
            if(htmlFileToRead != null){                
                boolean exceededMaxLimit = false;
                synchronized (context) {
                    exceededMaxLimit = htmlFileToRead.length() + context.totalSizeInMemory > context.maxSizeInMemory;
                }
                if(exceededMaxLimit){
                    waitOnContext();
                }else{
                    if(this.readFileIntoContext(htmlFileToRead)){
                        synchronized (context) {
                            context.totalSizeInMemory += htmlFileToRead.length();
                        }
                        this.notifyOnContext();
                    }
                }
            }else{
                waitOnContext();
            }
        }
    }
}

PhoneSearchThread Thread Class For Searching Phone Number In HTML File

package org.devpattern.interview;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * This thread reads the phone numbers from the list of html string
 * @author Tuna Ozkasap
 *
 */
public class PhoneSearchThread extends ThreadCommon{
    private static Pattern phonePattern = Pattern.compile("(\\+[0-9]{2,3})[1-9][0-9]{9}");
    
    public PhoneSearchThread(ThreadContext context){
        super(context);
    }

    public List<String> findPhoneNumbers(String htmlText){
        List<String> phoneList = new ArrayList<String>();
        Matcher matcher = phonePattern.matcher(htmlText);

        while(matcher.find()){
            phoneList.add(matcher.group());
        }

        return phoneList;
    }

    public void waitOnContext(){
        synchronized (context) {
            try {
                context.wait();
            } catch (InterruptedException e) {
                System.out.println(this.getClass().getName()+" wait on context interrupted.");
            }
        }
    }

    public void run(){
        while(true){
            if(stopFlag.get()){break;}
            
            HtmlInfo htmlInfo = null;
            synchronized (context) {
                if(context.htmlInfos.size() > 0){                        
                    htmlInfo = context.htmlInfos.remove(context.htmlInfos.size()-1);
                    context.totalSizeInMemory -= htmlInfo.fileSize;
                    context.notify();
                }
            }
            if(htmlInfo != null){                    
                List<String> phoneNums = this.findPhoneNumbers(htmlInfo.htmlText);
                for (String phoneNum : phoneNums) {
                    System.out.println(phoneNum+" - "+htmlInfo.filePath);
                    context.phoneNumbers.add(phoneNum+" - "+htmlInfo.filePath);
                }
            }else{
                this.waitOnContext();
            }

        }
    }
}

ThreadContext Class For Holding the Common Context Used By Read and Search Threads

package org.devpattern.interview;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ThreadContext{
    public long totalSizeInMemory;
    public long maxSizeInMemory;
    public List<String> phoneNumbers = Collections.synchronizedList(new ArrayList<String>());
    public List<HtmlInfo> htmlInfos = Collections.synchronizedList(new ArrayList<HtmlInfo>());
    public List<File> htmlFiles = Collections.synchronizedList(new ArrayList<File>());
    public List<File> filesFailed = Collections.synchronizedList(new ArrayList<File>());
}

MonitoringThread Thread Class For Monitoring Read and Search Threads

package org.devpattern.interview;

import java.util.List;

public class MonitoringThread extends Thread{
    
    private ThreadContext context;
    private List<ThreadCommon> monitoredThreads;
    
    public MonitoringThread(ThreadContext context, List<ThreadCommon> monitoredThreads){
        this.context = context;
        this.monitoredThreads = monitoredThreads;
    }
    
    public void run(){
        while(true){
            if(context.htmlFiles.size() == 0 && context.htmlInfos.size() == 0){
                for (ThreadCommon monitoredThread : monitoredThreads) {
                    monitoredThread.stopThread();
                    monitoredThread.interrupt();
                }
                break;
            }
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Interview Question and Answer [03]

Posted on Updated on

QUESTION: Given an N x M dimension array by the algorithm you will create you should color all of the elements in the array. The constraint is that no adjacent element in 2D-plane should have the same color. The output should give the minimum amount of colors required and the colored two-dimensional array as the output.
EXAMPLE: Here is an example of two-dimensional array which is not colored

    1   2   3
 1  1   2   3 
 2  4   5   6 
 3  7   8   9 

This is the result after the coloring operation is done. The id numbers stays the same.

     1   2   3
 1  c1  c2  c1
 2  c3  c4  c3
 3  c2  c1  c2 

Algorithm Written In Java

public class InterviewQuestion {
    
    public static void main(String[] args) {
        calc(new int[][]{{1, 2, 3, 4, 5, 6, 7, 8},
                         {9,10,11,12,13,14,15,16},
                         {17,18,19,20,21,22,23,24},
                         {25,26,27,28,29,30,31,32},
                         {33,34,35,36,37,38,39,40}});
    }
    
    static class Ball{
        public Ball(int id, int vIndex, int hIndex){
            this.id = id;
            this.colorIndex = 0;
            this.vIndex = vIndex;
            this.hIndex = hIndex;
        }
        public int id;
        public Integer colorIndex;
        public int vIndex;
        public int hIndex;
    }
    
    public static void calc(int[][] ballMatrix){
        List<Integer> colorList = new LinkedList<Integer>();
        
        //From the ball number matrix create a matrix filled with Ball objects.
        Ball[][] balls = new Ball[ballMatrix.length][ballMatrix[0].length];
        for(int i=0; i<ballMatrix.length; i++){
            for(int j=0; j<ballMatrix[i].length; j++){
                balls[i][j] = new Ball(ballMatrix[i][j], i ,j);
            }
        }
        
        //Using breadth-first search we will color all of the balls in the matrix.
        createByBfs(colorList, balls, 0, 0);
       
        printColorList(colorList);
        printBallMatrix(balls);
    }
    
    private static void createByBfs(List<Integer> existingColorList, Ball[][] ballMatrix, int vIndex, int hIndex){
        //Get neighbors as a list
        List<Ball> neighbors = getNeighbors(ballMatrix, vIndex, hIndex);
        //Create a new color for the current ball or use an existing color from the set.
        ballMatrix[vIndex][hIndex].colorIndex = createColor(neighbors, existingColorList);
        for (Ball neighbor : neighbors) {
            if(neighbor.colorIndex == 0){
                //Do the action for all of the neighbors.
                createByBfs(existingColorList, ballMatrix, neighbor.vIndex, neighbor.hIndex);
            }
        }
    }
    
    private static List<Ball> getNeighbors(Ball[][] ballMatrix, int vIndex, int hIndex){
        List<Ball> neighborList = new ArrayList<Ball>();
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex-1, hIndex-1);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex-1, hIndex);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex-1, hIndex+1);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex, hIndex-1);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex, hIndex+1);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex+1, hIndex-1);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex+1, hIndex);
        checkBallAndAddToNeighborList(neighborList, ballMatrix, vIndex+1, hIndex+1);
        return neighborList;
    }
    
    private static void checkBallAndAddToNeighborList(List<Ball> neighborList, Ball[][] ballMatrix, int vIndex, int hIndex){
        if(vIndex >= 0 && vIndex < ballMatrix.length && hIndex >=0 && hIndex < ballMatrix[0].length){
            neighborList.add(ballMatrix[vIndex][hIndex]);
        }
    }
    
    private static int createColor(List<Ball> neighborBalls, List<Integer> existingColorList){
        List<Integer> existingColorListClone = new LinkedList<Integer>(existingColorList);
        for (Ball ball : neighborBalls) {
            existingColorListClone.remove((Object)ball.colorIndex);
        }
        if(!existingColorListClone.isEmpty()){
            return existingColorListClone.get(0);
        }else{
            int newColorId = existingColorList.size()+1;
            existingColorList.add(newColorId);
            return newColorId;
        }
    }
    
    private static void printBallMatrix(Ball[][] balls) {
        for(int i=0; i<balls.length; i++){
            System.out.println("");
            for(int j=0; j<balls[i].length; j++){
                System.out.printf("%1$4s", balls[i][j].colorIndex);
            }
        }
    }

    private static void printColorList(List<Integer> colorList) {
        System.out.print("[");
        for (Integer color : colorList) {
            System.out.print(color+",");
        }
        System.out.print("]");
    }
}

Interview Question and Answer [02]

Posted on Updated on

QUESTION: Given an N arrays of size K each.

  • Each of these K elements in the N arrays are sorted,
  • Each of these N*K elements are unique.

Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this difference should be least possible Minimum. Create the most efficient algorithm for this computational problem.
EXAMPLE: N=3, K=3

  • N=1 : 6, 16, 67
  • N=2 : 11, 17, 68
  • N=3 : 10, 15, 100

CORRECT ANSWER: 17-15 = 2

Algorithm Written In Java

package org.devpattern.interview;

import java.util.Map.Entry;
import java.util.TreeMap;

public class InterviewQuestion {

    public static void main(String[] args) {
        Integer[][] arr = new Integer[][]{{1, 4, 5, 6, 7, 22,25,26},
                                          {13,16,17,19,20,23,24,28},
                                          {14,18,21,30,31,32,33,34}};
        System.out.println("RES: "+calc(arr));
    }
    
    static class Value{
        public Value(int vIndex, int hIndex, Integer value){
            this.vIndex = vIndex;
            this.hIndex = hIndex;
            this.value = value;
        }
        int vIndex;
        int hIndex;
        Integer value;
    }

    public static Integer calc(Integer[][] sortedArr){
        Integer calculatedRes = null;
        
        TreeMap<Integer, Value> redBlackTree = new TreeMap<Integer, Value>();
        //Create TreeMap RUNTIME: N
        for(int i=0; i<sortedArr.length; i++){
            redBlackTree.put(sortedArr[i][0], new Value(i, 0, sortedArr[i][0]));
        }
        
        //RUNTIME: Best: K*(lg(N)), Worst: (K*N)*(lg(N))
        while(true){
            //RUNTIME: lg(N)
            Value lowestValue = redBlackTree.firstEntry().getValue();

            //RUNTIME: lg(N)
            if( lowestValue.hIndex < sortedArr[0].length-1){				
                redBlackTree.remove(lowestValue.value);
                Integer val = sortedArr[lowestValue.vIndex][lowestValue.hIndex+1];
                redBlackTree.put(val, new Value(lowestValue.vIndex, lowestValue.hIndex+1, val));
            }else{
                break;
            }
            
            //RUNTIME: lg(N)
            Integer tmp = redBlackTree.lastKey() - redBlackTree.firstKey();
            if(calculatedRes == null || calculatedRes < tmp){
                calculatedRes = tmp;
            }
        }

        return calculatedRes;
    }
}

Interview Question and Answer [01]

Posted on Updated on

QUESTION: There is an array which has N integers in it. You will be given a number S and your algorithm is to find if there are M (M < N) numbers in the array whose summation is equal to S.
EXAMPLE: [4,7,12,54,23,76,6,3,9,10] for this array if you are given the number 26 and asked to find if there are 4 numbers in this array that adds up to 26. Algorithm should find numbers 4+7+12+3 = 26. You should only return a boolean value

Algorithm Written In Java

public class InterviewQuestion {
    public static void main(String[] args) {
        boolean bool = calc(new Integer[]{5,6,7,8,9,23,4,7,8,2,3,6,7,8,15}, 5, 24);
        System.out.println("Result "+bool);
    }	
    
    static class HashElement{
        public HashElement(Integer[] userdNumbers, Integer summation) {
            this.usedNumbers = userdNumbers;
            this.summation = summation;
        }
        public Integer[] usedNumbers;
        public Integer summation;
    }

    ////O(pow(n,varCount)) worst-case algorithm.
    public static boolean calc(Integer[] arr, int varCount, int num){
        //Change array into hash map, O(n) time
        HashMap<Integer, Integer> numberCountMap = new HashMap<Integer, Integer>();
        for (Integer arrNum : arr) {
            if(numberCountMap.get(arrNum) == null){
                numberCountMap.put(arrNum, 1);
            }else{
                numberCountMap.put(arrNum, numberCountMap.get(arrNum)+1);
            }
        }
		
        HashMap<Integer, HashElement> currentMap = new HashMap<Integer, HashElement>();
        //O(pow(n,varCount)) worst case
        for(int i=0;i<varCount;i++){
            currentMap = createCombinationHashMap(currentMap, numberCountMap, num);
        }
		
        //O(1) time
        return currentMap.get(num) != null;
    }
	
    public static HashMap<Integer, HashElement> createCombinationHashMap(HashMap<Integer, HashElement> map, HashMap<Integer, Integer> numberCountMap, int wantedResult){
        HashMap<Integer, HashElement> newMap = new HashMap<Integer, HashElement>();
        Set<Integer> keySet = map.keySet();
        if(keySet.isEmpty()){
            //Create the initial set which is for one element summation (that is the number itself).
            for(Integer key : numberCountMap.keySet()){
                newMap.put(key, new HashElement(new Integer[]{key}, key));
            }
        }else{			
            for (Integer hashElementKey : keySet) {
                HashElement element = map.get(hashElementKey);
                //Decrement used number counts in numberMap
                for(Integer usedNumber : element.usedNumbers){
                    numberCountMap.put(usedNumber, numberCountMap.get(usedNumber)-1);
                }
				
                //For the numbers save summation combination into newMap, ex: [(56)=(23+23+10)] is a map entry
                Set<Integer> numberCountMapKeySet = numberCountMap.keySet();
                for(Integer numberCountMapKey : numberCountMapKeySet){
                    if(numberCountMap.get(numberCountMapKey) > 0 && hashElementKey + numberCountMapKey <= wantedResult){
                        newMap.put(hashElementKey+numberCountMapKey, new HashElement(addNumToArr(element.usedNumbers, numberCountMapKey), hashElementKey+numberCountMapKey));
                    }
                }
				
                //Increment used number counts in numberMap
                for(Integer usedNumber : element.usedNumbers){
                    numberCountMap.put(usedNumber, numberCountMap.get(usedNumber)+1);
                }
            }
        }
        return newMap;
    }
	
    private static Integer[] addNumToArr(Integer[] oldArr, int newNum){
        Integer[] newArr = new Integer[oldArr.length+1];
        for (int i=0; i<newArr.length; i++) {
            if(i < oldArr.length){				
                newArr[i] = oldArr[i];
            }else{
                newArr[i] = newNum;
            }
        }
        return newArr;
    }
}

If someone can calculate average running time for this algorithm please let me know.