Hey all, here are a few snapshot onsite interview questions for you
1. Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Note: All words have the same length. All words contain only lowercase alphabetic characters.
public class Solution {
public List<List><String>> findLadders(String start, String end,
Set<String> dict) {
List<List><String>> ladders = new ArrayList<List><String>>();
Map<String, List><String>> map = new HashMap<String, List><String>>();
Map<String, Integer> distance = new HashMap<String, Integer>();

dict.add(start);
dict.add(end);

bfs(map, distance, start, end, dict);

List<String> path = new ArrayList<String>();

dfs(ladders, path, end, start, distance, map);

return ladders;
}

void dfs(List<List><String>> ladders, List<String> path, String crt,
String start, Map<String, Integer> distance,
Map<String, List><String>> map) {
path.add(crt);
if (crt.equals(start)) {
Collections.reverse(path);
ladders.add(new ArrayList<String>(path));
Collections.reverse(path);
} else {
for (String next : map.get(crt)) {
if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) {
dfs(ladders, path, next, start, distance, map);
}
}
}
path.remove(path.size() - 1);
}

void bfs(Map<String, List><String>> map, Map<String, Integer> distance,
String start, String end, Set<String> dict) {
Queue<String> q = new LinkedList<String>();
q.offer(start);
distance.put(start, 0);
for (String s : dict) {
map.put(s, new ArrayList<String>());
}

while (!q.isEmpty()) {
String crt = q.poll();

List<String> nextList = expand(crt, dict);
for (String next : nextList) {
map.get(next).add(crt);
if (!distance.containsKey(next)) {
distance.put(next, distance.get(crt) + 1);
q.offer(next);
}
}
}
}

List<String> expand(String crt, Set<String> dict) {
List<String> expansion = new ArrayList<String>();

for (int i = 0; i < crt.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch != crt.charAt(i)) {
String expanded = crt.substring(0, i) + ch
+ crt.substring(i + 1);
if (dict.contains(expanded)) {
expansion.add(expanded);
}
}
}
}

return expansion;
}
}
2.Merge k sorted linked lists and return it as one sorted list.
// version 1: Divide & Conquer
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists.size() == 0) {
return null;
}
return mergeHelper(lists, 0, lists.size() - 1);
}

private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
if (start == end) {
return lists.get(start);
}

int mid = start + (end - start) / 2;
ListNode left = mergeHelper(lists, start, mid);
ListNode right = mergeHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
tail = list1;
list1 = list1.next;
} else {
tail.next = list2;
tail = list2;
list2 = list2.next;
}
}
if (list1 != null) {
tail.next = list1;
} else {
tail.next = list2;
}

return dummy.next;
}
}
3. Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Example For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3 For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/


public int longestIncreasingSubsequence(int[] nums) {
int []f = new int[nums.length];
int max = 0;
for (int i = 0; i < nums.length; i++) {
f[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
f[i] = f[i] > f[j] + 1 ? f[i] : f[j] + 1;
}
}
if (f[i] > max) {
max = f[i];
}
}
return max;
}
}
Hopefully, these information will benefit for you. .