Google Interview Question
1. find duplicates in an array
2. design a method which consumes an integer and output the corresponding column number in Microsoft Excel ( ex. A, B, C......Z, AA, AB....ZZ....)
Interview Answers
def column(n): # n belongs to [1..N], N is integer
A = ord('A')
Z = ord('Z')
num_letters = Z - A + 1
s = ''
while n > 0:
d,r = divmod(n-1, num_letters) # d = (n-1)/26; r = (n-1)%26
s += chr(A + r)
n = d
s = s[::-1] # reverse string
return s
if __name__ == '__main__':
print(column(1)) #A
print(column(26)) #Z
print(column(1*26 + 1)) #AA
print(column(26*26 + 26)) #ZZ
print(column(1*26*26 +26*26 + 2)) #AZB
1. Java Code
import java.util.HashMap;
/**
* Created by admin on 3/1/16.
*/
public class Solution {
public int findDuplicate(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
HashMap hm = new HashMap();
for (int num: nums) {
if (hm.containsKey(num)) {
hm.put(num, hm.get(num)+1);
} else {
hm.put(num, 1);
}
}
for (int key: hm.keySet()) {
if (hm.get(key) > 1) {
return key;
}
}
return 0;
}
}
2. Java Code:
import java.util.Stack;
/**
* Created by admin on 3/1/16.
*/
public class Solution {
public String convertToTitle(int n) {
Stack records = new Stack();
int current = n;
while (current > 0) {
current--;
int right = current%26;
records.push(Character.toString((char)(right + 'A')));
current = current/26;
}
String result = "";
while(!records.empty()) {
result = result + records.pop();
}
return result;
}
}