Airbnb Real Interview Questions

 Question: Add Two Numbers

	// You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
	// You may assume the two numbers do not contain any leading zero, except the number 0 itself.
	// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
	// Output: 7 -> 0 -> 8
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	public class AddTwoNumbers {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode current1 = l1;
	ListNode current2 = l2;
	ListNode head = new ListNode(0);
	ListNode currentHead = head;
	int sum = 0;
	while(current1 != null || current2 != null) {
	sum /= 10;
	if(current1 != null) {
	sum += current1.val;
	current1 = current1.next;
	}
	if(current2 != null) {
	sum += current2.val;
	current2 = current2.next;
	}
	currentHead.next = new ListNode(sum % 10);
	currentHead = currentHead.next;
	}
	if(sum / 10 == 1) {
	currentHead.next = new ListNode(1);
	}
	return head.next;
	}
	}

view raw AddTwoNumbers.java hosted with ❤ by GitHub

Question: Contains Duplicate

	//Given an array of integers, find if the array contains any duplicates. Your function should return
	//true if any value appears at least twice in the array, and it should return false if every element is distinct.
	class ContainsDuplicate {
	public boolean containsDuplicate(int[] nums) {
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i: nums) {
	if(map.containsKey(i)) {
	return true;
	} else {
	map.put(i, 1);
	}
	}
	return false;
	}
	}

view raw ContainsDuplicate.java hosted with ❤ by GitHub

Question: Contains Duplicate II

	//Given an array of integers and an integer k, find out whether there are two distinct indices i and
	//j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
	class ContainsDuplicatesII {
	public boolean containsNearbyDuplicate(int[] nums, int k) {
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i = 0; i < nums.length; i++) {
	int current = nums[i];
	if(map.containsKey(current) && i - map.get(current) <= k) {
	return true;
	} else {
	map.put(current, i);
	}
	}
	return false;
	}
	}

view raw ContainsDuplicateII.java hosted with ❤ by GitHub

Question: Convert Sorted Array to Binary Search Tree

	// Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public TreeNode sortedArrayToBST(int[] nums) {
	if(nums.length == 0) {
	return null;
	}
	TreeNode root = helper(nums, 0, nums.length - 1);
	return root;
	}
	private TreeNode helper(int[] nums, int start, int end) {
	if(start <= end) {
	int mid = (start + end) / 2;
	TreeNode current = new TreeNode(nums[mid]);
	current.left = helper(nums, start, mid - 1);
	current.right = helper(nums, mid + 1, end);
	return current;
	}
	return null;
	}
	}

view raw SortedArrayToBST.java hosted with ❤ by GitHub

Question: House Robber

	// You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
	// Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
	public class HouseRobber {
	public int rob(int[] nums) {
	if(nums.length == 0) {
	return 0;
	}
	if(nums.length == 1) {
	return nums[0];
	}
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
	for(int i = 2; i < nums.length; i++) {
	dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
	}
	return dp[dp.length - 1];
	}
	}

view raw HouseRobber.java hosted with ❤ by GitHub

Question: Merge K Sorted Lists

	// Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	public class MergeKSortedLists {
	public ListNode mergeKLists(ListNode[] lists) {
	if (lists==null||lists.length==0) {
	return null;
	}
	PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
	@Override
	public int compare(ListNode o1,ListNode o2){
	if (o1.val<o2.val) {
	return -1;
	} else if (o1.val==o2.val) {
	return 0;
	} else {
	return 1;
	}
	}
	});
	ListNode dummy = new ListNode(0);
	ListNode tail=dummy;
	for (ListNode node:lists) {
	if (node!=null) {
	queue.add(node);
	}
	}
	while (!queue.isEmpty()) {
	tail.next=queue.poll();
	tail=tail.next;
	if (tail.next!=null) {
	queue.add(tail.next);
	}
	}
	return dummy.next;
	}
	}

view raw MergeKSortedLists.java hosted with ❤ by GitHub

Question: Regular Expression Matching

	// Implement regular expression matching with support for '.' and '*'.
	// '.' Matches any single character.
	// '*' Matches zero or more of the preceding element.
	// The matching should cover the entire input string (not partial).
	// The function prototype should be:
	// bool isMatch(const char *s, const char *p)
	// Some examples:
	// isMatch("aa","a") → false
	// isMatch("aa","aa") → true
	// isMatch("aaa","aa") → false
	// isMatch("aa", "a*") → true
	// isMatch("aa", ".*") → true
	// isMatch("ab", ".*") → true
	// isMatch("aab", "c*a*b") → true
	public class RegularExpressionMatching {
	public boolean isMatch(String s, String p) {
	if(s == null || p == null) {
	return false;
	}
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int i = 0; i < p.length(); i++) {
	if(p.charAt(i) == '*' && dp[0][i - 1]) {
	dp[0][i + 1] = true;
	}
	}
	for(int i = 0; i < s.length(); i++) {
	for(int j = 0; j < p.length(); j++) {
	if(p.charAt(j) == '.') {
	dp[i + 1][j + 1] = dp[i][j];
	}
	if(p.charAt(j) == s.charAt(i)) {
	dp[i + 1][j + 1] = dp[i][j];
	}
	if(p.charAt(j) == '*') {
	if(p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
	dp[i + 1][j + 1] = dp[i + 1][j - 1];
	} else {
	dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
	}
	}
	}
	}
	return dp[s.length()][p.length()];
	}
	}

view raw RegularExpressionMatching.java hosted with ❤ by GitHub

Question: Two Sum

	// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
	// You may assume that each input would have exactly one solution, and you may not use the same element twice.
	// Example:
	// Given nums = [2, 7, 11, 15], target = 9,
	// Because nums[0] + nums[1] = 2 + 7 = 9,
	// return [0, 1].
	public class TwoSum {
	public int[] twoSum(int[] nums, int target) {
	int[] result = new int[2];
	HashMap<Integer, Integer> map = new HashMap<>();
	for(int i = 0; i < nums.length; i++) {
	if(map.containsKey(target - nums[i])) {
	result[1] = i;
	result[0] = map.get(target - nums[i]);
	return result;
	}
	map.put(nums[i], i);
	}
	return result;
	}
	}

view raw TwoSum.java hosted with ❤ by GitHub

Question: Valid Parenthesis

	// Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
	// The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
	public class ValidParentheses {
	public boolean isValid(String s) {
	if(s.length() % 2 == 1) {
	return false;
	}
	Stack<Character> stack = new Stack<Character>();
	for(int i = 0; i < s.length(); i++) {
	if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
	stack.push(s.charAt(i));
	} else if(s.charAt(i) == ')' && !stack.isEmpty() && stack.peek() == '(') {
	stack.pop();
	} else if(s.charAt(i) == ']' && !stack.isEmpty() && stack.peek() == '[') {
	stack.pop();
	} else if(s.charAt(i) == '}' && !stack.isEmpty() && stack.peek() == '{') {
	stack.pop();
	} else {
	return false;
	}
	}
	return stack.isEmpty();
	}
	}

view raw ValidParenthesis.java hosted with ❤ by GitHub