Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Accenture. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Smallest Divisible Digit Product II

You are given a string num which represents a positive integer, and an integer t. A number is called zero-free if none of its digits are 0. Return a string representing the smallest zero-free number greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return "-1". Example 1: Input: num = "1234", t = 256 Output: "1488" Explanation: The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256. Example 2: Input: num = "12355", t = 50 Output: "12355" Explanation: 12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150. Example 3: Input: num = "11111", t = 26 Output: "-1" Explanation: No number greater than 11111 has the product of its digits divisible by 26. Constraints: 2 <= num.length <= 2 * 105 num consists only of digits in the range ['0', '9']. num does not contain leading zeros. 1 <= t <= 1014

Topics: Math, String, Backtracking, Greedy, Number Theory

Problem #2: Smallest Divisible Digit Product I

You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t. Example 1: Input: n = 10, t = 2 Output: 10 Explanation: The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition. Example 2: Input: n = 15, t = 3 Output: 16 Explanation: The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition. Constraints: 1 <= n <= 100 1 <= t <= 10

Topics: Math, Enumeration

Problem #3: Water Bottles

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink. Example 1: Input: numBottles = 9, numExchange = 3 Output: 13 Explanation: You can exchange 3 empty bottles to get 1 full water bottle. Number of water bottles you can drink: 9 + 3 + 1 = 13. Example 2: Input: numBottles = 15, numExchange = 4 Output: 19 Explanation: You can exchange 4 empty bottles to get 1 full water bottle. Number of water bottles you can drink: 15 + 3 + 1 = 19. Constraints: 1 <= numBottles <= 100 2 <= numExchange <= 100

Topics: Math, Simulation

Problem #4: Shortest Palindrome

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation. Example 1: Input: s = "aacecaaa" Output: "aaacecaaa" Example 2: Input: s = "abcd" Output: "dcbabcd" Constraints: 0 <= s.length <= 5 * 104 s consists of lowercase English letters only.

Topics: String, Rolling Hash, String Matching, Hash Function

Problem #5: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: strs = ["flower","flow","flight"] Output: "fl" Example 2: Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Constraints: 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lowercase English letters if it is non-empty.

Topics: String, Trie

Problem #6: Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3: Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. Constraints: 1 <= nums.length <= 105 -104 <= nums[i] <= 104 Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Topics: Array, Divide and Conquer, Dynamic Programming

Problem #7: Maximum Width Ramp

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0. Example 1: Input: nums = [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5. Example 2: Input: nums = [9,8,1,0,1,9,4,0,4,1] Output: 7 Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1. Constraints: 2 <= nums.length <= 5 104 0 <= nums[i] <= 5 104

Topics: Array, Two Pointers, Stack, Monotonic Stack

Problem #8: Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. Constraints: 1 <= prices.length <= 105 0 <= prices[i] <= 104

Topics: Array, Dynamic Programming

Problem #9: Reverse Words in a String

Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces. Example 1: Input: s = "the sky is blue" Output: "blue is sky the" Example 2: Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces. Example 3: Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string. Constraints: 1 <= s.length <= 104 s contains English letters (upper-case and lower-case), digits, and spaces ' '. There is at least one word in s. Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Topics: Two Pointers, String

Problem #10: Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example 1: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] Example 2: Input: digits = "" Output: [] Example 3: Input: digits = "2" Output: ["a","b","c"] Constraints: 0 <= digits.length <= 4 digits[i] is a digit in the range ['2', '9'].

Topics: Hash Table, String, Backtracking