Scribd
Upload
3 views18 pages

JavaProblemSolving 1

The document provides a comprehensive guide for coding interviews, focusing on problem-solving techniques using Java. It includes essential topics such as arrays, linked lists, strings, and various algorithms with example problems and solutions. The guide emphasizes frequently asked questions from major tech companies and offers explanations for each solution to aid understanding.

Uploaded by

Shaik Nagulshareef
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
3 views18 pages

JavaProblemSolving 1

The document provides a comprehensive guide for coding interviews, focusing on problem-solving techniques using Java. It includes essential topics such as arrays, linked lists, strings, and various algorithms with example problems and solutions. The guide emphasizes frequently asked questions from major tech companies and offers explanations for each solution to aid understanding.

Uploaded by

Shaik Nagulshareef
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
INTERVIEW - PROBLEM SOLVING /2— \ sk GUIDE R ae > Crack Coding Interviews < 7 with Confidence ———— @ Arrays @ Linked Lists ; 48> @ Strings ' @ Stack & Queue MUST-KNOW @ Hashing @ Recursion Ue @ Sliding Window | © Binary Search @ Two Pointers @ Trees & Graphs oe = BEGINNER TO 1 INTERVIEW-FOCUSED JAVA SOLUTIONS INTERMEDIATE LEVEL | EXPLANATIONS INCLUDED vUvUUyuviviyiuiiid. “@ FREQUENTLY ASKED 13, 14, 15 Google Microsoft Infosys TCS. [Link] Problem Name Topic ) @) | Two Sum Arrays + HashMap @ | Best Time to Buy and Sell Stock | Arrays (@) | Maximum Subarray Sum ee (Kadane’s Algorithm) Z @ | Contains Duplicate Hashing © | Valid Anagram Strings + HashMap © | ketineGactan™ | i wo @_| Move Zeroes Two Pointers (@) | Merge Sorted Arrays Two Pointers @® | Binary Search Searching Reverse Linked List Linked List @® | Middle of Linked List Linked List (@) | Valid Parentheses Stack 43) | Implement Queue Using Stacks | Stack & Queue @_|_ Fibonacci Using Recursion Recursion @®)_| Flood Fill / Number of Islands Graphs Hashing Y Sliding Window 1 V Linked List 8 V Two Pointers t v Recursion V Binary Search | V Graph Troversal Infosys ECS accenture “re ' v Stack & Queue ' (BFS/DFS) I (1. TWO SUM { a £ U SO Example 1. ums = (2, 7, 11, 15], target = 9 (R2uligze leans Oumar er Zier J prrmonat a Glicst cine save Given an integer array mums | and an integer target, return indices of the two numbers i such that they add up to ! target. * | You may assume that each 1 input would have exactly | ‘one solution, and you may | Output: [0, 1] i | \ ' | rrumber and its index as we iterate through the array. ) For each number, calculate its complement = target - number. ) Hf the complement exists in the map, return the stored index (and current index. wy not use the same element oh i twice. cna rums = [3, 2, 4], target = 6 * 2 4 instead of checking every pair (O(n#)), we store mumbers in @ moped emp 1 @ Create an empty HashMap | (number -> index). | @ literate through the array. | @ For each number, find fe iaddlak 9 eka aria | © If complement exists in map, | 1 ‘import java-util.*; class Solution ( public int{] twoSum(int{] nuns, int target) { MapcInteger, Integer> map = new Hashtapc>(); for (int 1 = 0; 1 < [Link]; i++) { int complenent = target - nuns[i); if ([Link](complenent)) { return new int{]{[Link](conplenent), 1}; ? [Link](nums{i), 1); > Feturn new int{}{); // not possible | return [[Link](complement), | © Else, put current number and | its index in map. | If no pair found (not possible | as per constraints), return empty. ‘VW HashMap helps to solve this in linear time. V Each number is processed once. ‘V Make sure to return indices, not numbers! uae “2. BEST TIME TO BUY AND SELL stock > -[]- < PROFIT * Given an integer array prices where Input: prices = [7, 1, 5, 3, 6, 4] | ( © Keep track of the minimum prices{i) is the price of a given stock on price seen so far (minPric). * lectin 71+ 5[3[¢]* } ie Gases ceteris Ld De ee” | | © For each day, caelte the } igileenseiticr: [profit if we sll on that doy © You may buy on any day and sell on | PAS > 6 ) profit = prices(t] ~ minPrice H ) a future day © You may nat buy and sell on the same day ( @ Update the maximum profit (aaProfit) # the current ! ' ' t illic seal ) i H L (eee y Of 23 #5 | | pre te leat than minPrie Best Buy on day 1 (price = 1) and Sell on day 4 (price = 6) Profit = 6-1=5 ‘ce —. 1 @ Traverse the array from \ teh & ight eb Ripa were alerts public int maxProfit(int{) prices) { tte cocoa | uit ma weg = tn : tne prin «nego ES vigdee neni an Tne Complenity: O(n) ‘for (nt price + prices) ( 46 (price < minPrice) minPrice = price; We traverse the array once Space Complety: (1) | i ' | | prcestid) ! i | i O | prefit | Return maxProfit felse {f (price - minPrice > maxProfit) rmuxtrofit = price ~ minPrice; > We use only constant return maxProfits hate py 0 | a [2 y, Duplicate found! | Think: We only need to | | | i i ! | i | | know if @ duplicate exists, | \ y We iterate Uhrough the ar ‘Space Complexity: O(n) Tn the worst case, we store all n elements in the set *! import [Link] class Solution { Or: Time Complexity: O(n) iM V HashSet gives 0(1) average time = ar 8: | Use a HashSet to store elements eo iterate through the array © If the current element is already | in the set, it means a duplicate exists > return true. © Otherwise, add the element to the set and continue. © If we finish the loop without finding duplicates > return false. _& public boolean containsDuplicate(intL] runs) { SetcInteger> set = new HashSet<>(); for (int mum : nuns) { 4F (set contains(rum)) { return trues > [Link](num); > return false; | for contains() and add(). | | v7 Works for any data thet con be | stored in a set. | i| V Simple, efficient and clean approach! w I Given two strings s and t, return true if ¢ is an anagram of s, and false otherwise. Output: true Explanation: Both strings have the same characters with same ‘An anagram means two strings Frequency, contain the same characters with the same frequencies, but in any order. Input: 5 = "rat", Output: false increment its count. | | @ For each character in t, | decrement its count | © If any count becomes magi, Gita, Oe oN —, EES QO Tine Comply Om) | TN ve travers bth strings onc. Space Complexity: 0(1) We use fined sie array of 26 w 5. VALID ANAGRAM strings are anagrams of each Explanation: Characters or Frequencies Amport [Link]; class Solution { “GY Anagrams are about the same letters, just in a different order! \A @: w © If lengths of both strings are different, return false. Count the frequency of each character in string s. Decrement the frequency using characters of string t. | } | | TF all frequencies become zero, strings are anagrams. Otherwise, return false. public boolean istnagram(String s, String t) { Af ([Link]() != telength()) return false; snt() count = new int(26); for (char eh + s-toCharArray()) count(ch = ‘a'}+e; for (char ch countch 4€ (count{ch ~ ‘'a"] < 0) return false: ‘[Link]()) Only works for lowercase leters (a-2) \ Fer uricode, ute HashMap Character, Integer>. | Age ck length Fat fer an el eit \ v v v Tk treo Fey ak kl gy | | ' | | | Given a string 5, find the length | | of the longest substring without repeating characters f | i | | i | 1 | 1 | 1 1 | | i i Input: 5 = “abcabebb” Output: 3 Explanation: The answer is “abe”, Explanation: The answer is “uke”, with length 3. MapeCharacter, Integer> map TRerate with right from 0 to nt 1 sight) ic brandy in map and imaplstright)) >= left, move left to mapCstright]) + 4 © Updte maplatright) = right Update masLen = max(maxen, wit +1) © Return mastn rahe ~ 6. LONGEST SUBSTRING Nae | WITHOUT REPEATING CHARACTERS - °, © We will use the sliding window technique with two pointers. © Use a HashMap (or HashSet) to store the last seen index of characters. © Expand the window by moving the right pointer. © If a duplicate character is found inside the window, move the left pointer to the right of the last occurrence of that character. © Update the maximum length at each step with length 3. (=. — a lass Selution { public int engthOfLongetSubrtring( String #) ( HapcCharacer, Integer» map = new Hashape(); Ink lft = 0, wenden = 0; for Gink right = i right < slegth(s right) \ hare» #.charkright)s | 1 (map cntaintg) BE map gee) >» lat) ( | | marten = 0 left = [Link]) + 1; > [Link](e, right) rmaxlen = [Link](maalen, right ~ left + 1); Om comp O(n) Use HashMap to sore last index Each character i vied of characters | | eee tae | | | Space Complesity: OCmin(n, m)) | | ¥ The window abs contains | Where n= length of string, unique characters. gf | ib Faget tp | - toh g move all the 0's to the end of it while maintaining the relative order of the an ste aoa Example 2: Output: Enola 3 P rums = [0, 1, 0, 3, 12] [ep 1} ata | lt || Is fa mls | ee [s [mea(@ees ml] | Ss [| 2 [raat .@s asl | Reaaaloteuniaa lll | | | SSS fete citt 3, 12, 0, 0] \ Gee © ie | (4, 0, 5, 0, 0, 1] > (4, 5, 4, 0, 0, 0] | | 1 | | | > 02,3, 0,0) | + ums = [0, 1, 0, 3, 12] 4, 3, 12, 0, 0] Explanation: The order of non-zero elements [1, 3, 12] is maintained A | np: mums = (0, 0, 1] 1, 0, 0] Input : rams = [1, 2, 3, 0] Output: [1, 2, 3, 0} Explanation: No change needed. yf | is || thas te ne we of ] | © Fe army oh J © 1 mumsfs] t= 0: © nums{i] © msl] © Aiter the toop, @ Te omit ote) \ ' \ Space Complexity: O(1) y i We use only constant \{ @® Use two pointers: | | => position to place next | Hee | J > iterate through the array | ® IF rums{j] is non-zero, place it at rums{i] and increment i. | / | @ After the loop, fill the remaining | positions from i to end with O's. | } | } non-zero elements. & — lass Solution { public void moveZeroes(int{] mums) { int = 0; for (int j = 0; j < [Link]; e+) ( 4 (ramst] = 0) rums[i] = mame js ies d y 7 FALL remaining with O's while (4 < rams Length) rrums(t] = 0; Y In-place luton Maintains relative order of non-zero elements S Simple ond efficient! x \ wa w TID \ | L | fogenpenal (2 Onn aeeeras | and nums2, merge them into | Output: [1, 2, 3, 4, 5, 6] ® Compare the elements pointed by | | one sorted array, | | planation: Marg in sorted erer. | both printers. \ | ee Fe ns be © Add the smaller element to the \ Example 2: result array and move that pointer. | | Inputs raat (2,4, Tm [5,6] || Pa et om ry soba | Output: 1, 2, 3, 4, 5, 6, 7] ei od | | remaining elements | Explanation: Marge in srtad de 4 | | \ | Ae) | the ther array v 4,3, 5] rnd = (2, 4, 6] Saar | [stop [i [a] mont oi] Atin | Moye ay || 8M 08 amply rent rag [melo] o [2 | - |] © Wie i cm and jem © IF mit) <= meni), add runs to result pubic int) merge int] rams, it{) am) ( ink m= runs length, m = mans. Length; ink) res = new itn + mdi int i= 0, j= 0, k=O; to] o | 2 [wer] o-m 2|r] a | 2 [ue2 [soa mites while (i t23) | Space Complexity: O(n + m) | © mumst = (1, 2,2, 3},mm2= (2, 24] | Foe the resut array | 1 >, 2 22, 2,3, 4] | \ w 1 | @ mums = (1, 2,3], mam = C4, 5,6] | Om cy O(n + m) | ¥ eth erage mtb rd. | | | | | eT TTIT ITT IIIT III II III - 9, BINARY SEARCH ->y | | Array: (2, §, 8, 12, 16, 23, 38, 56.721) | @ start with two pointers: |G alam te eas | arp rein ee of | Stape \ : Aerget if it exes | MD mid = 4 + 16 « 23 - search right haf) | @ Find mid = (ow + high) / 2 Ae 2[e]e [a [eee] e] © IF mumafmid) =» target, : O12 3 f 8 6 7 8 || return mid. search in the right half (low = mid + 1). ® IF mums{mid] > target, search in the left half (high = mid - 0. ® Repeat until low > high FF rot Fad ent | | | | | | | © 1 rumsfmid] < target, \ | | | | | | | | | | | | fa ieee Sskoy ses i fea erect so Th] td fig aJ6y tabfvuad) ='2 Piste hae ad stot wp ' mumsLmid] == target: | © © White tow high id Claw + igh 112 16 puma) = target { { i | i | | | 1 | | return mid | | | | | | | | | | | | vO Tiemann tet Bho | aris | @ Return -1 © Array must be sorted. Best for large datasets v Binary search is much faster han linear search, Space Complexity V Be careful with caleulating ou) the mid to avid overflow in We use ony a constant sae amount of extra space. YE) of ela | we [ucasmes We discard half oF the laments in every stp. s | 5] 5 | 23 | Found! rtuen 5 | EO) \ | | | | s |e | 6 | 38 [wrzmpes]! | | | | | i CUT TIT II V IT IT TIT IIT IT III UI IIIT 1 Given the head of «singly con || © Use three pointrs: pre, cr, next, | linked list, reverse the list head || @ Traverse the Ut and return the new head. THEE ME | each ned, rere the | eurrent node's next pointer. | @® Move prev and curr one step forward. @ When curr becomes NULL, prev Und Lit -G-O-G-G-me -E-D-O-B-m { | @ Inittze def reverse ist(head): \ + prey = NULL prev = None + curr = head curr = head + next = NULL G-B-B-@-B-m| While curr is not None: rnext_node = [Link] next = [Link] + [Link] = prev prev = curr Now prev is at last node (5), © s[2 [4] 5 [GGG e-em 2 | 5 [ra |G-S}-G}-G} me 5 | + [wu] = |O-G-G+ Gms | \ i | \ | \ \ @ hie aris vot MUL: \ | | ' | | | cure = next ! | | | | | | | | | | [Link] = prev | | | | | | | | ' i j PSEUDOCODE reversList(head): | prev = NUL | fate ial li ite eure = NULL | ee aaa | Garret = prey ere | J \ L We We use 'O= Complexity: O(n) | ack at pain wate deme |g rts pia |S Be careful with pointer updates! only three pointers Works for empty ist ond singe node list too J PROBLEM STATEMENT ( Gen the head of 6 singly eka at return the wide node of the list. Ie oresanas | Output: @ | Example 2: IF there are two middle nodes, Input 2 1923345556 ran the cid wide ee. | Output: =o 1 doe wt bet the id | Example 3: - ® Return slow. - Settee. | @ | See 37? 7 @ IF head is NUL, return MUL. | def middle_node head): 1S bade bere if not head © dow = head Ssh Ne + fast = head See = few @® While fast '= NULL ond fait @ toad oso tp fat ot tg || ast Io RL while Fast and [Link] Te: © ah = sowed slow = [Link] = fat = fst net nt fast = [Link] Return slow > rode wth vale 3 (nie) G)|] @ Return slow (middle rode). | return slow ASUAL EXPLANATION (TWO POINTERS) “{ [EVEN NODES (6 NODES) @ Every open bracket has « corresponding close bracket | ® Brackets must close in the i correct order. © Every close bracket has @ Input: s = “or 1 TF ch isn opening bracket Coe "0 or "(push it 1 Else (ch is cong bracket): =F stack amp + urn foe = dh des wok math tack top + urn fle = Ea pp fom ak \ | @ For each character chin ss © Mar the op Use a stack to store open brackets Traverse the string ‘© If current char is an open bracket, ‘= TF current char is a close bracket, check if it matches the top of the | eres stack | @ If it matches, pop from stack @ If it doesn't match, return fle. @ After troversl oat return true. Others, flo. cop a bracket map = (9) for ch in iF chin CLC stack append(ch) else: if not stack return False if stack{-1] 1 bracket_mapleh: return False stack pop() (stack) == 0 Ts Valid So Far? Yer Ge TF ob eny pit ere Pap (matches “CD Yer ‘i @ mismatch or stack Pash Yee Pap (matches Yee is empty while expecting Pash Pop (natcbes “CY match — false! v We traverse the sing eee { | CB) Tine Complexity 0 |Or plexity: O(n) ! Space Complexity: O(n) Tn the worst case, the stack contains al opering bracets. | | WF Stack is the perfect tool (LIFO). Works for any combination of 0,0. 0 w s+ true Cenpty string) aC fae 5 = MO" false 5 = OD + tue ao o v i © Eng 1, 2,3 tak ond ~ sutStack (tp) 3 ® Deguee (pop front) outStack is empl, 50 move all rom Stack to otStack utc (top) Operation: enue), eng, enguu(), {| | Enqueve(o) Ph x int inStack, | @ dequee() 1 etc i empl owe al sane Fon tack te ata (oe by oe erqueue(s) “> add x to the back dequeue() > remove from Front peck() > get front element empty() > ack if queue is empty self inStack =) # for enqueue self soutStack = (0 for daguee enqueuelealf, 0) lf inStack. appends) 7 tet transi Teeter iad 1 Poe all From nSlack te ottack ae ren See while self, inStack: Popa ten fom atch | self out Stack. ppnd( nao | | set inStack pop) | 1 Stack egy || tt duet ‘Move all elements from inStack | 1 eh Soh ett | : | eth treater) | ae er | Stack | : one | turn fencers | Can empty ret =t | return self outStack ppt) | Return tap of outStack (do not pop). | | dat pedis | | Th nt sah ouStak | | ‘elf —transferO | |e not self outStack | | tien “A | nt scat | at ents \ eget), dg, eg) deg) _| (Tine Conny Be] Grain [asic =) [ata =) [Rena] | ngs = OCH) 1 [ove [1 0 =] due + C4) amertind 2 [wwe |. a a Top penk CY) amertnd [mo [| 0 —]omty = 0M) + [oped [OF ea St) ees swe S| epee 0 (je ama Pewee ener 6 | emt | _O01 (2 S| at a. \ oo Bats) es eee eee aaa Canes L_PURPOSE {~~} WHAT TO INCLUDE (. Keep it short and clear © Wrap up the topic Restate he main iea || 6 Pincrdesn repr) | © Summarice hay pots eer ae ae ‘Avoid. introducing || exercise is essential for | ‘© Rewtforcethe. win iden: rs eS key poi || new information ify es body me ae ' os || © Be positive and confident || Tt improves our physical | pee [9 Shae he a eee cutece| | Pres, reduces stress, | = | svete eee ee ee and boosts overall i © Provide « sense | + COpinal) End with @ || End with impact || ne EE ae | of elosure call to action, suggestion, | ThA seric part cPtour | or thought tt etl ! 3 +i ~ 2 | | daily life for a better ° (es i . \ fe] i || temeer @) ‘A good conclusion doesn't just end your content, Finish strong, it stays in the reader's mind. leove @ tates Strong ending = Strong impact! @ impression!

You might also like