Developer Interview Questions

One possibility that comes in mind: * Walk the array, create a hashmap (key is the value in array, value is the count of such values). * Walk the array again and check the count in the hash map, once you hit 1, you have the first unique value. This is O(n) both space and time.

Are you sure that this is O(n), it is definitely O(n^2), you go over all items twice.

dear utk O(2n) = O(n) != O(n^2)...

use recursion

2^n possibility...

F(n) = F(n-1)+F(n-2)

!!!! There can be some bugs not fully tested use at your own risk =)... import java.util.ArrayList; public class OrdinalToColumn { public static void main(String[] args) { // TODO Auto-generated method stub int valueToConvert = 64; System.out.println(ordinalToColumnConversion(valueToConvert)); } private static char[] ordinalToColumnConversion(int valueToConvert) { // TODO Auto-generated method stub ArrayList numbersReverse = new ArrayList(); int sizeOfArr; int curIndex, rollBackIndex; while(valueToConvert>0){ // base conversion numbersReverse.add(valueToConvert % 26); valueToConvert /= 26; } sizeOfArr = numbersReverse.size(); curIndex = rollBackIndex = 0; while(curIndex rollBackIndex){ // borrowing can lead some cascading operation we have to roll back until all digits are more than 0 int barrowNumber = numbersReverse.get(tempIndx); // barrow from previous barrowNumber--; numbersReverse.set(tempIndx, barrowNumber); tempIndx--; int nextNumber = numbersReverse.get(tempIndx); // add to the current one nextNumber += 26; numbersReverse.set(tempIndx, nextNumber); } } else { curIndex++; } } if(sizeOfArr > 0 && numbersReverse.get(sizeOfArr-1) == 0){ // remove the highest significant bit if it is 0 numbersReverse.remove(sizeOfArr-1); sizeOfArr--; } char [] returnNumbers = new char [sizeOfArr]; for(int i = sizeOfArr-1, n=0; i>=0; --i, ++n){ returnNumbers[n] = (char)(numbersReverse.get(i)+64); // converting to capital letter } return returnNumbers; } }

Here my solution in Java: public class SpreadSheetLabel { private static char LABEL[] = new char[] {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; private static void printLabel(int n) { if (n = 26) { n /= 26; str.append(LABEL[(n-1) % LABEL.length]); } System.out.println(str.reverse()); } public static void main(String[] args) { for(int i = 1; i <= 2600; i++) { printLabel(i); } } }

I haven't tried interwee's solution, but that code is so complex and long for such a simple problem I don't even wish to try and understand it :) Anyways, here is my simple and elegant solution in Java: // Precondition: i >=1 public static String excelNumbering(int i){ if(i >=1 && i<= 26) return ""+(char)(i+64); else return excelNumbering((i-1)/26) + excelNumbering((i-1)%26+1); }

1) Pour water in 5 litre container 2) Pour 5 litre container into 3 litre until full. You are left with 2 litre in 5 litre container 3) Empty 3 liter container. Pour 2 litre into 3 litre container 4) Fill 5 litre container until full 5) Pour 1 litre into 3 litre container until full. Left with 4 litres in 5 litre container.

1. fill half of the 3 litre container 2. fill half of the 5 litre container

http://brainteaserbible.com/interview-brainteaser-puzzle-water-jug

Change it. The probability for door A is 1/3, the probability for the set Door C + Door B is 2/3. The interview adds information on the set stating that Door B prob is 0, so the probability for Door C is 2/3 while Door A stays at 1/3

Balls. Once you know that there is no prize behind door B, prob(B) becomes 0. Then, since the prize must be behind A or C, and you don't know anything about them, prob(A) = prob(C) = 1/2. Any of the doors is OK.

Sorry Filippo (F?) but u r wrong on this one. U may see also it in this way: in the game You ll never be told that your initial choice is wrong, the information added is only about the other two doors. This breaks the symmetry, the probability that your initial choice stays at 1/3 ( It is secluded by the bit of more information added ) , but now the prob of b goes to zero and because all the probabilities must add up to 1, the prob(c) becomes 2/3. I understand it is not intuitive, but not all the math is :)

Recursively

Hello! When did you interview?

Beginning of November

public static void noRepeat(int n) { int[] ar; for(int i=1;i1) { flag = 1; } temp = temp/10; } if(flag==0) { System.out.println(i); } } }

Your answer is correct, but it is slow. Here you are an algorithm that does same thinkg as you do, but also one more algorithm - using permutations. Instead of outputting to System.out I simply calculate how many numbers are there. Run and see how slow is your method for n = 8 (where n is the number of digits). import java.io.*; import java.util.*; public class NumbersNoRepeatDigits{ public class StopWatch { private long startTime = 0; private long stopTime = 0; private boolean running = false; public void start() { this.startTime = System.currentTimeMillis(); this.running = true; } public void stop() { this.stopTime = System.currentTimeMillis(); this.running = false; } //elaspsed time in milliseconds public long getElapsedTime() { long elapsed; if (running) { elapsed = (System.currentTimeMillis() - startTime); } else { elapsed = (stopTime - startTime); } return elapsed; } //elaspsed time in seconds public long getElapsedTimeSecs() { long elapsed; if (running) { elapsed = ((System.currentTimeMillis() - startTime) / 1000); } else { elapsed = ((stopTime - startTime) / 1000); } return elapsed; } } // mode complicated solution public static void permuteArray(int[] a){ permuteArrayCore(a, a.length - 1); } public static void permuteArrayCore(int[] a, int i){ if (i == -1) { if (a[0] > 0) printArray(a); return; } permuteArrayCore(a, i-1); // when ith element is on place; for (int j=i-1; j>=0; j--) { //swap i and j swap(a, i, j); permuteArrayCore(a, i-1); swap(a, i, j); } } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void selectMAmong10(int m) { boolean[] take = new boolean[10]; selectMAmongNCore(m, 0, take, 0); } public static void selectMAmongNCore(int m, int next, boolean[] take, int countTaken) { if (countTaken == m){ int[] x = new int[m]; int xi = 0; for (int i = 0; i = m - countTaken) selectMAmongNCore(m, next + 1, take, countTaken); } // simpliest solution public static boolean checkDistinct(int i) { boolean[] digits = new boolean[10]; while (i > 0) { int rem = i % 10; if (digits[rem]) return false; digits[rem] = true; i = i / 10; } return true; } public static int totalCount = 0; public static void printArray(int[] a){ totalCount++; /* for (int i = 0; i < a.length; ++i) System.out.format("%d ", a[i]); System.out.println(); */ } public static void main(String[] args){ int n = 8; NumbersNoRepeatDigits t = new NumbersNoRepeatDigits(); NumbersNoRepeatDigits.StopWatch st = t.new StopWatch(); st.start(); for (int i = 1; i <= n; ++i) selectMAmong10(i); System.out.println(totalCount); System.out.println(st.getElapsedTime()); totalCount = 0; System.out.println("-----------"); int max = (int)Math.pow(10, n); for (int i = 1; i < max ; ++i) { if (checkDistinct(i)) // System.out.println(i); printArray(null); } System.out.println(totalCount); st.stop(); System.out.println(st.getElapsedTime()); } }

looks really simple (if I understood it right). Here is the SHORT java version. static boolean hasDupDigit(int i){ boolean[] digits = new boolean[10]; while(i!=0){ int r = i%10; if(digits[r])return true; digits[r] = true; i/=10; } return false; } static void printNums(){ for (int i=1;i<=1000000;i++) if(!hasDupDigit(i)) System.out.println(i); }