5 programozási feladat fejlesztőknek állásinterjúkról - Hányra tudsz válaszolni?

A fejlesztői állásinterjúk szinte kihagyhatatlan lépése a szakmai teszt, melynek során különböző problémákat kell megoldanunk az adott nyelven, lehetőleg minél optimálisabb, és elegánsabb módon. Gyakori, de nem feltétlenül egyszerű Java feladatokat gyűjtöttünk össze, és mindegyikre mutatunk egy megoldást is (természetesen több jó megoldás is lehetséges). Teszteljétek magatokat az ITHubbal!

1. Keressük meg egy paraméterként kapott szöveg összes palindrom felosztását

Például az "aab" bemenetre az alábbi eredményt adjuk:

[
    ["aa","b"],
    ["a","a","b"]
  ]

Megoldás

public ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
 
	if (s == null || s.length() == 0) {
		return result;
	}
 
	ArrayList<String> partition = new ArrayList<String>();
	addPalindrome(s, 0, partition, result);
 
	return result;
}
 
private void addPalindrome(String s, int start, ArrayList<String> partition,
		ArrayList<ArrayList<String>> result) {
	//stop condition
	if (start == s.length()) {
		ArrayList<String> temp = new ArrayList<String>(partition);
		result.add(temp);
		return;
	}
 
	for (int i = start + 1; i <= s.length(); i++) {
		String str = s.substring(start, i);
		if (isPalindrome(str)) {
			partition.add(str);
			addPalindrome(s, i, partition, result);
			partition.remove(partition.size() - 1);
		}
	}
}
 
private boolean isPalindrome(String str) {
	int left = 0;
	int right = str.length() - 1;
 
	while (left < right) {
		if (str.charAt(left) != str.charAt(right)) {
			return false;
		}
 
		left++;
		right--;
	}
 
	return true;
}

2. Ugrálós játék

Adott egy nemnegatív egész számokból álló tömb, melynek az első elemén állunk. A tömb minden eleme az adott pozícióból történő legnagyobb ugorható távolságot jelöli. Döntsük el a tömbről, hogy el tudunk-e jutni benne az utolsó elemig a fenti szabályt követve. Példák: A = [2,3,1,1,4], eredménye igaz. B = [3,2,1,0,4], eredménye hamis.

Megoldás

public boolean canJump(int[] A) {
    if(A.length <= 1)
        return true;
 
    int max = A[0];
 
    for(int i=0; i<A.length; i++){
        //ha nem tudunk a következőre ugrani
        if(max <= i && A[i] == 0) 
            return false;
 
        //max frissítése    
        if(i + A[i] > max){
            max = i + A[i];
        }
 
        //max elég az utolsó pozícióba ugráshoz
        if(max >= A.length-1) 
            return true;
    }
 
    return false;    
}

3. Cseréljük meg két számot tartalmazó változó értékét úgy, hogy nem használunk egy harmadik változót a megoldáshoz

Nem túl Java specifikus, de érdekes feladat :)

Megoldás

int a = 10;
int b = 20;

a = a+ b; //a most 30, b pedig 20
b = a -b; //a most 30, b viszont 10 (a eredeti értéke)
a = a -b; //a most már 20, b pedig 10

4. Járjunk be egy n*m-es mátrixot spirál alakban, a bal felső sarokból indulva

[
 [ 1, 2, 3, 4 ],
 [ 5, 6, 7, 8 ],
 [ 9, 10, 11, 12 ]
]

A fenti mátrix bejárása: 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7

Megoldás

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
 
        if(matrix == null || matrix.length == 0) return result;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int x=0; 
        int y=0;
 
        while(m>0 && n>0){
 
            //ha már csak egy sor vagy oszlop maradt, akkor nem tudunk körben haladni
            if(m==1){
                for(int i=0; i<n; i++){
                    result.add(matrix[x][y++]);
                }
                break;
            }else if(n==1){
                for(int i=0; i<m; i++){
                    result.add(matrix[x++][y]);
                }
                break;
            }
 
            //lentebb a körben haladás mozdulatai
 
            //felül vagyunk, jobbra mozgunk
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y++]);
            }
 
            //jobbszélen vagyunk, lefelé mozgunk
            for(int i=0;i<m-1;i++){
                result.add(matrix[x++][y]);
            }
 
            //alul vagyunk, balra mozgunk
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
 
            //balszélen vagyunk - felfelé mozgunk
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
 
            x++;
            y++;
            m=m-2;
            n=n-2;
        }
 
        return result;
    }
}

5. Három szám összegével közelítés

Adott egy tetszőleges elemszámú tömb (A), elemei egész számok, valamint egy másik egész szám (X). Válasszunk ki A elemei közül pontosan hármat úgy, hogy összeadva őket az X-hez legközelebbi számot kapjuk, és adjuk is vissza ezt az összeget.
Például: A = {-1 2 1 -4}, X = 1. Az X-hez legközelebbi összeg: 2 (-1 + 2 + 1 = 2).

Megoldás

public class Solution {
	public int threeSumClosest(int[] num, int target) {
		int min = Integer.MAX_VALUE;
		int result = 0;
 
		Arrays.sort(num);
 
		for (int i = 0; i < num.length; i++) {
			int j = i + 1;
			int k = num.length - 1;
			while (j < k) {
				int sum = num[i] + num[j] + num[k];
				int diff = Math.abs(sum - target);
 
				if(diff == 0) return 0;
 
				if (diff < min) {
					min = diff;
					result = sum;
				}
				if (sum <= target) {
					j++;
				} else {
					k--;
				}
			}
		}
 
		return result;
	}
}

Forrás: Program Creek, Javarevisited