Archive for July 2017
Problem statement Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., might become ). You are given a target value to search. If found in the array return its index, otherwise return . You may assume no duplicate exists in the array. . . . Read more
Problem statement The string PAYPALISHIRING is written in a zigzag pattern on a given number of rows like this: P A H N A P L S I I G Y I R And then read line by line: PAHNAPLSIIGYIR. Write the code that will take a string and make . . . Read more
Problem statement Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. . . . Read more
Problem statement Merge k sorted linked lists and return it as one sorted list. Solution We reduce the problem to the merging of two linked lists problem. This can be done in time and space. So we first write out the function to merge two sorted lists: def merge(self, lst1, . . . Read more
Problem statement Given a set of candidate numbers (without duplicates) and a target number , find all unique combinations in where the candidate numbers sums to . The same repeated number may be chosen from unlimited number of times. Note: All numbers (including target) will be positive integers. The solution . . . Read more
Problem statement Given a linked list: class ListNode(object): def __init__(self, x): self.val = x self.next = None remove the node from the end of list and return its head. Sample input 1->2->3->4->5 2 Sample output 1->2->3->5 Note: will always be valid. Solution For this we will use a two pointer . . . Read more
Problem statement Given an array of integers, are there elements in such that ? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array , A solution set is: Solution The idea behind the . . . Read more
Problem statement Given pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given , a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] Solution class Solution(object): def generate(self, n, open_count, closed_count, s, result, visited): visited.add(s) if open_count == n and closed_count == . . . Read more
Problem statement Given a string , find the longest palindromic substring in . You may assume that the maximum length of is . Sample input 1 babad Output 1 bab Sample input 1 cbbd Output 1 bb Solution We are going to iterate over each character in the input string . . . Read more
Problem statement Given an array of strings, group anagrams together. Sample input [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] Sample output [ [“ate”, “eat”,”tea”], [“nat”,”tan”], [“bat”] ] Note: All inputs will be in lower-case. Full code class Solution(object): def groupAnagrams(self, strs): “”” :type strs: List[str] :rtype: List[List[str]] “”” map = {} . . . Read more