Problem Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x) Pushes element x to the top of the stack. int pop() Removes the element on the top of the stack and returns it. int top() Returns the element on the top of the stack. boolean empty() Returns true if the stack is empty, false otherwise. Notes: ...
Problem Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers. You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit) You may also assume each line in the text file must not contain leading or trailing white spaces. ...
Problem Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C. ...
Problem You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete. Given the integer n, return the number of complete rows of the staircase you will build. Examples Example 1: $$ \begin{matrix} \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ &\colorbox{white} 0 \end{matrix} $$ ...
Problem Given an array of integer write an algorithm to find the majority element in it (if exist). Boyer Moore Majority Vote Algorithm We have already seen the problem and some solutions - Majority Element 1 In this article we will see O(n) solution with constant extra space. As per above algorithm we can divide out implementation into two parts First iteration – Find the element which could be a majority element. Second iteration – check the element(found in first iteration) count is greater than n/2 First Iteration – Find the Element Which Could Be a Majority Element Iterate through array and maintain the count of majority_element.(starts with first element in the array.) If next element is same then increment the count If next element is not same then decrement the count. If count becomes zero then majority_element = current element, count =1. After the first iteration majority_element will be the candidate which might have the count > n/2. Second Iteration – Check the Element (found in First iteration) Count is Greater Than n/2 Iterate through array and get the count of element found in first step. If count is >n/2 then print it. If count is less than n/2 then ignore it, array does not have majority element. Complexity ⏰ Time complexity: O(n) 🧺 Space complexity: O(1) Code Java public int majorityElement(int[] arrA) { int size = arrA.length; if (size == 0) return; int majorityElement = arrA[0]; int count = 1; for (int i = 1; i<size; i++) { if (majorityElement == arrA[i]) { count++; } else if (count == 0) { majorityElement = arrA[i]; count = 1; } else { count--; } } //check if majorityElement is appearing more than n/2 times count = 0; for (int i = 0; i<size; i++) { if (arrA[i] == majorityElement) { count++; } } if (count > size / 2) return majorityElement; else return -1; } ...
Problem Write a function that takes a string as input and reverse only the vowels of a string. Examples Example 1: Input : s = hello Output : holle Example 2: Input : s = hello world Output : hollo werld Solution Method 1 - Store the vowels and place them in reverse order One simple solution is to store all the vowels while scanning the string and placing the vowels in the reverse order in another iteration of string. ...
Symmetric Tree Problem Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). Examples Example 1: ...
Problem Given an array of integers, every element appears twice except for one. Find that single one. Examples Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums = [1] Output: 1 ...
Problem Write a function that takes a string as input and returns the string reversed. Examples Example 1: Given s = "hello", return "olleh". Given s = “kodeknight” , return “thginkedok“. Solution Method 0 - Iterative, Not in Place In Java, string is immutable. So, cannot do in place!. public String reverseString(String s) { int n = s.length; char[] reversed = s.toCharArray(); return reverse(reversed); } ...
Problem Given a sorted linked list, delete all duplicates such that each element appear only once. Examples Example 1: Given 1->1->2, return 1->2. Input: head = [1,1,2] Output: [1,2] ...