unique

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Posted on July 30, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Method 1 - Using hashset on str2 and boolean array or hashset on str2 Break down the problem into two tasks. i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose. ii) Finding if all the characters hashed in the first string are available in the second string. [Read More]

Determine if a string has all unique characters

Posted on February 4, 2014 (Last modified on August 7, 2020) | 5 minutes | Kinshuk Chandra

Problem: Implement an algorithm to determine if a string has all unique characters. Solution Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop. bool uniqueChars(string myString) { for (int x = 0; x < myString. [Read More]

kodeknight String java-code Bit Vector CrackingTheCodingInterview unique

2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

Posted on January 6, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

how to build the hash table in the approach 3. als… Unknown - Feb 3, 2014how to build the hash table in the approach 3. also i think you should check if hash(T-arr[i]) is empty first. This comment has been removed by the author. Hi Jianchen, I think we can use hashmap or we can use element as an index in the array. I think only way hash() is empty when the given array is null or has no element. [Read More]

kodeknight 2Sum sorting array hashtable pair unique sum

2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

Posted on January 6, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x,y in A with x+y=T. Example : Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and T = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4). There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. [Read More]

kodeknight 2Sum sorting array hashtable pair unique sum

First non repeating element in the array

Posted on December 31, 2011 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. [Read More]

kodeknight String duplicate array hashes unique

To find the longest substring with unique characters in a given string

Posted on September 22, 2011 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

#include <stdio.h> #include <string.h> typedef struct { const char \*start; size\_t len; }Substring; Substring longestSubstring(const char \*s){ Substring ret = {s, 1}; Substring cur = {s, 1}; size\_t i, len = strlen(s); const char \*p = NULL; for(i = 1; i < len; ++i){ p = memchr(cur.start, s\[i\], cur.len); if(p){ if(cur.len > ret.len) ret = cur; cur.len -= (p - cur.start) + 1; cur.start = p + 1; } cur.len++; } if(cur. [Read More]

kodeknight String Dynamic Programming DP unique LCS