Daily Archives: July 18, 2015

Determines whether a 2d-integer array contains duplicate values within k

This problem is given by junmin: determines whether a 2d m*n integer array contains duplicate values within k indices of each other.

For example:
1 2
3 4
k = 1
Outout: no

1 1
3 4
k=0
Output: no

1 1
3 4
k=1
Output: Yes

1 2 3
3 4 1
k=3
Output: Yes

Let’s think about 1-d array [1  2  3  4  5  4  6 ]. Let k=2. An O(n) solution would be use a 2-size window to slide over  the array. Use hashset to store the elements in window:

Then, let’s think about 2-d array like below. And we know arr[1][4]==arr[3][4]==99

In this case, we can use a ‘+’ shape 2-d window to scan array. The whole process will be like below:

When k is odd, let’s say k=5. We can’t use regular ‘+’ shape window. Instead, we use similar one. A similar move will be like below:

A problem of this unregular shape window is that it will miss elements 22, which both stay in the same column and length is 5. It is easy to solve this issue. Every time when a new window is moved, we just check if there are elements equal in same column which has length 5.

The time complexity of this solution is O(m*n*k), space complexity is O(k^2).

The code is a bit long. Please check it in github: https://github.com/allenlipeng47/algorithm/blob/master/src/main/java/com/pli/project/algorithm/array/DuplicateInKLength.java

Ftp in java

Below code download file from ftp server:

package ftp;

import org.apache.commons.net.ftp.FTPClient;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import org.apache.commons.net.PrintCommandListener;
import org.apache.commons.net.ftp.FTP;
import org.apache.commons.net.ftp.FTPReply;


/**
 * Created by pli on 7/16/2015.
 */

public class FtpDownloader {

    FTPClient ftp = null;

    public FtpDownloader(String host, String user, String pwd) throws Exception {
        ftp = new FTPClient();
        ftp.addProtocolCommandListener(new PrintCommandListener(new PrintWriter(System.out)));
        int reply;
        ftp.connect(host);
        reply = ftp.getReplyCode();
        if (!FTPReply.isPositiveCompletion(reply)) {
            ftp.disconnect();
            throw new Exception("Exception in connecting to FTP Server");
        }
        ftp.login(user, pwd);
        ftp.setFileType(FTP.BINARY_FILE_TYPE);
        ftp.enterLocalPassiveMode();
    }

    public void downloadFile(String remoteFilePath, String localFilePath) {
        try  {
            FileOutputStream fos = new FileOutputStream(localFilePath);
            this.ftp.retrieveFile(remoteFilePath, fos);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void disconnect() {
        if (this.ftp.isConnected()) {
            try {
                this.ftp.logout();
                this.ftp.disconnect();
            } catch (IOException f) {
                // do nothing as file is already downloaded from FTP server
            }
        }
    }

    public static void main(String[] args) {
        try {
            FtpDownloader ftpDownloader = new FtpDownloader("127.0.0.1", "pli", "pli");
            ftpDownloader.downloadFile("/tmp/1.java", "/home/2.txt");
            ftpDownloader.disconnect();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

pom.xml dependency:

<dependency>
    <groupId>org.springframework.integrationgroupId>
    <artifactId>spring-integration-sftpartifactId>
    <version>4.1.6.RELEASEversion>
dependency>

Sftp in java

Below code can download/upload from/to sftp server:

package ftp;

import com.jcraft.jsch.*;
import lombok.Data;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.file.*;
import java.util.Vector;


/**
 * Created by pli on 7/16/2015.
 */
@Data
public class SftpService {

    private static Logger logger = LoggerFactory.getLogger(SftpService.class);

    private String host;
    private String username;
    private String password;

    public void downloadFilesFromSftp(String sftpFromDir, String downloadFileName, String toLocalDir) {
        JSch jSch = new JSch();
        Session session = null;
        Channel channel = null;
        try {

            session = jSch.getSession(username, host, 22);
            session.setPassword(password);

            java.util.Properties config = new java.util.Properties();
            config.put("StrictHostKeyChecking", "no");
            config.put("PreferredAuthentications", "publickey,password");
            session.setConfig(config);
            session.connect();

            channel = session.openChannel("sftp");
            channel.connect();

            ChannelSftp channelSftp;
            channelSftp = (ChannelSftp) channel;
            channelSftp.cd(sftpFromDir);
            Vector<ChannelSftp.LsEntry> list = channelSftp.ls(downloadFileName);
            for(ChannelSftp.LsEntry entry : list) {
                try {
                    Path filePath;
                    filePath = Paths.get(toLocalDir +  "/" + entry.getFilename());
                    Files.copy(channelSftp.get(sftpFromDir + "/" + entry.getFilename()), filePath, StandardCopyOption.REPLACE_EXISTING);
                }catch (IOException e){
                    logger.error("Encountered error when dealing with " + entry.getFilename() + ":" + e.toString());
                }
            }
        } catch (Exception e) {
            logger.error(e.getMessage());
        }
        finally {
            if(channel != null ){
                channel.disconnect();
            }
            if(session != null){
                session.disconnect();
            }
        }
    }

    public void uploadFilesFromSftp(String localFromDir, String uploadFileName, String toSftpDir)  {
        JSch jSch = new JSch();
        Session session = null;
        Channel channel = null;
        try {

            session = jSch.getSession(username, host, 22);
            session.setPassword(password);

            java.util.Properties config = new java.util.Properties();
            config.put("StrictHostKeyChecking", "no");
            config.put("PreferredAuthentications", "publickey,password");
            session.setConfig(config);
            session.connect();

            channel = session.openChannel("sftp");
            channel.connect();

            ChannelSftp channelSftp;
            channelSftp = (ChannelSftp) channel;
            DirectoryStream<Path> ds = Files.newDirectoryStream(Paths.get(localFromDir), uploadFileName);
            for (Path localFileFrom : ds) {
                try {
                    channelSftp.put(new FileInputStream(new File(localFileFrom.toString())), toSftpDir + "/" + localFileFrom.getFileName());
                }catch (IOException e){
                    logger.error("Encountered error when dealing with " + localFileFrom.toString() + ":" + e.toString());
                }
            }
        } catch (Exception e) {
            logger.error(e.getMessage());
        }
        finally {
            if(channel != null ){
                channel.disconnect();
            }
            if(session != null){
                session.disconnect();
            }
        }
    }

    public static void main(String[] args) {
        SftpService sftpServiceDownload = new SftpService();
        sftpServiceDownload.setHost("hostname");
        sftpServiceDownload.setUsername("username");
        sftpServiceDownload.setPassword("password");
        sftpServiceDownload.downloadFilesFromSftp("/home", "*.txt", "/home");


        SftpService sftpServiceUpload = new SftpService();
        sftpServiceUpload.setHost("hostname");
        sftpServiceUpload.setUsername("username");
        sftpServiceUpload.setPassword("password!ake");
        sftpServiceUpload.uploadFilesFromSftp("/home", "*", "/root");
    }

}

pom dependency:

<dependency>
    <groupId>org.springframework.integration</groupId>
    <artifactId>spring-integration-sftp</artifactId>
    <version>4.1.6.RELEASE</version>
</dependency>