Microsoft Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

I propose my solution:

CREATE TABLE Lists
	(ListID int, ListItem char(1));

Function that split the comma separated items and returns them as table rows.

CREATE FUNCTION Split_fn
( @string varchar(MAX), @delimiter char(1) )       
RETURNS @restable TABLE (items varchar(MAX))       
AS       
BEGIN      
    DECLARE @idx int, @slice varchar(8000)       

    SELECT @idx = 1       
        IF len(@string)<1 OR @string IS NULL RETURN       

    WHILE @idx!= 0       
     BEGIN       
        SET @idx = CHARINDEX(@delimiter, @string)       
        IF @idx!=0       
            SET @slice = LEFT(@string, @idx - 1)       
        ELSE       
            SET @slice = @string       

        IF (LEN(@slice)>0)  
            INSERT INTO @restable(items) VALUES (@slice)       

        SET @String = RIGHT(@string, LEN(@String) - @idx)       
        IF LEN(@string) = 0 BREAK       
     END   
 RETURN 
END;

Procedure that calls the function and adds the items into a table as separate rows with identifier.

CREATE PROCEDURE InsertListItems_sp
( @ListID int, @items varchar(MAX)=NULL )
AS
BEGIN
    INSERT INTO Lists(ListID, ListItem)
    SELECT @ListID, items
    FROM Split_fn (@items, ',')
END;

Execution of the procedure:

EXEC InsertListItems_sp 1, 'A,B,C,A,B'
EXEC InsertListItems_sp 2, 'A,B,A,A,A'
EXEC InsertListItems_sp 3, 'C,D,C'

Query that counts occurrences of items and returns those that are repeated more than once.

SELECT ListID, ListItem, COUNT(*) AS CountOfItem
FROM Lists
GROUP BY ListID, ListItem
HAVING COUNT(*) > 1
ORDER BY ListID ASC

Finally, the query that sums duplicates by identifiers.

SELECT ListID, SUM(CountOfItem) AS SumOfDuplicates
FROM
  (SELECT ListID, ListItem, COUNT(*)-1 AS CountOfItem
   FROM Lists
   GROUP BY ListID, ListItem
   HAVING COUNT(*) > 1) AS s
GROUP BY ListID
ORDER BY ListID ASC

The result is:
ListID SumOfDuplicates
----------- ---------------
1 2
2 3
3 1

- cvetygeorg August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Another way for creating function Split_fn is:

CREATE FUNCTION Split_fn 
(   @string varchar(max), 
    @delimiter char(1)  )
RETURNS TABLE
AS
RETURN 
(
WITH tokens(p, a, b) 
AS 
 (  SELECT 1, CAST(1 AS bigint), 
           CHARINDEX(@delimiter, @string)
    UNION ALL
    SELECT p + 1, b + 1, 
           CHARINDEX(@delimiter, @string, b + 1)
    FROM tokens
    WHERE b > 0  )
 SELECT p AS ItemIndex,
        SUBSTRING(@string, a, 
              CASE WHEN b > 0 THEN b-a ELSE LEN(@string) END) 
        AS Items
 FROM tokens
);
GO

- cvetygeorg August 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findDuplicates(string list)
{
    IDictionary<char, int> kvp = new Dictionary<char,int>();
    int counter = 0;
    foreach(char character in list.split(","))
    {
        if(kvp.get(character)!=null)
        {
            counter++;
        }
        else
        {
            kvp.add(character,1);
        }
    }
    return counter;
}

void findDuplicateInStrings(string[] strings)
{
    foreach(string s in strings)
    {
        System.Console.Writeline(findDuplicates(s));
    }
}

- Maddy May 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't this a SQL question?

- mrid August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

FOR SQL BELOW CODE WOULD WORK:
select count(*), b.item ITEM
from ( select a.ITEM
from (select substr('A,B,C,A,B,C,',level,1 ) ITEM
from dual connect by level < length('A,B,C,A,B,C,') + 1
) a
) b
group by b.item
order by b.item;

- SHIVENDRA August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

alter function getDups (@a varchar(20), @b int)
returns @t table
(
a char(2)
, rowss int
)
as
begin

declare @tempTable TABLE (a char(2))

while @b <= (Select len(@a))
begin
insert into @tempTable
select SUBSTRING(@a, @b, 1)
set @b += 1
end

insert into @t
select *, DENSE_RANK() OVER (PARTITION BY a ORDER BY a) as rowss from @tempTable

return
end

-- Execute function by passing desired string to identify number of duplicates ...

select a, (sum(rowss) - 1) as numberOfDups from getDups('AABBBCCCCCC', 1)
group by a, rowss
having count(a) > 1

- Niraj September 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To get no of duplicate from a table userTab(id,name):

select sum(duplicate) from
(select id, (count(id)-1) as duplicate
from userTab
group by id
having count(id)>1);


TestData:
create table userTab(id number,salary number)

Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (2,2000);
Insert into "userTab" (ID,SALARY) values (3,3000);
Insert into "userTab" (ID,SALARY) values (4,4000);
Insert into "userTab" (ID,SALARY) values (4,4000);
Insert into "userTab" (ID,SALARY) values (5,5000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);

- PKT October 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

select list,A+B+C COUNT_LETTER FROM (
select list,case when A>1 THEN A-1 ELSE 0 END A,
case when B>1 THEN B-1 ELSE 0 END B,
case when C>1 THEN C-1 ELSE 0 END C from(
select list,regexp_count(list,'[A]') A,regexp_count(list,'[B]') B,regexp_count(list,'[C]') C
from list_count))

- Ashwini Kumar Padhy August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

select list,A+B+C COUNT_LETTER FROM (
select list,case when A>1 THEN A-1 ELSE 0 END A,
case when B>1 THEN B-1 ELSE 0 END B,
case when C>1 THEN C-1 ELSE 0 END C from(
select list,regexp_count(list,'[A]') A,regexp_count(list,'[B]') B,regexp_count(list,'[C]') C
from list_count))

- Ashwini Kumar Padhy August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

table name: tab
Columns:Id,val1,val2,val3,val4,val5

1,a,b,c,a,b
2,a,b,a,a,a
3,c,d,c

create table #tab
(
id int,
val1 varchar(1),
val2 varchar(1),
val3 varchar(1),
val4 varchar(1),
val5 varchar(1)
);
insert into #tab values(1,'a','b','c','a','b')
insert into #tab values(2,'a','b','a','a','a')
insert into #tab values(3,'c','d','c',null,null)

Select id,count(*)-COUNT(distinct val) from
(
Select id,val
from #tab
unpivot(val for valtype in (val1,val2,val3,val4,val5)) unpvt) a
group by id

- Ram September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

create table #tab
(
id int,
val1 varchar(1),
val2 varchar(1),
val3 varchar(1),
val4 varchar(1),
val5 varchar(1)
);
insert into #tab values(1,'a','b','c','a','b')
insert into #tab values(2,'a','b','a','a','a')
insert into #tab values(3,'c','d','c',null,null)

Select id,count(*)-COUNT(distinct val) from
(
Select id,val
from #tab
unpivot(val for valtype in (val1,val2,val3,val4,val5)) unpvt) a
group by id

- Ram September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

create table #tab
(
id int,
val1 varchar(1),
val2 varchar(1),
val3 varchar(1),
val4 varchar(1),
val5 varchar(1)
);
insert into #tab values(1,'a','b','c','a','b')
insert into #tab values(2,'a','b','a','a','a')
insert into #tab values(3,'c','d','c',null,null)

Select id,count(*)-count(distinct(val)) from
(Select id,val
from #tab
unpivot(val for valtype in (val1,val2,val3,val4,val5)) unpvt) a
group by id

- Ram86dude September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Assume we don't have strings longer than 256 symbols (actually doesn't matter, we can process any string. Just for performance).
- Lets 'duplicates' is our input table having just a single column str.
Here is a solution for oracle 12 (should work for ms sql. Just remove 'from dual')

WITH
  -- let's add some row number to our input table
  nrows (id , symb) AS
  (
    SELECT row_number() over(order by str) AS id, str symb
    FROM duplicates
  ),
  -- generate a sequence of numbers: 1, 3, 5...
  -- these are char positions of our letters
  numbs (id) AS
  (
    SELECT 1 AS id
    FROM dual
    UNION ALL
    SELECT id + 2 AS id
    FROM numbs
    WHERE
      id < 256
  ),
  -- convert strings to rows
  pvt_rows (id, sym) AS
  (
    SELECT r.id, SUBSTR(r.symb,n.id, 1)
    FROM nrows r
    INNER JOIN numbs n ON LENGTH(r.symb) >= n.id
  ),
  -- count duplicates of each symbol
  preagg(id, sym, cnt) AS
  (
    SELECT id, sym, COUNT(sym) - 1
    FROM pvt_rows
    GROUP BY id, sym
    ORDER BY id
  )
-- final select to output the result
SELECT
  id, SUM(cnt) as dups_cnt
FROM preagg
GROUP BY id;

- Vitalii Novytskyi June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

select a,val1,count(val1) as duplicates from
(
SELECT a,
regexp_substr(b,'[^,]+',1,1) as b1,
regexp_substr(b,'[^,]+',1,2) as c,
regexp_substr(b,'[^,]+',1,3) as d,
regexp_substr(b,'[^,]+',1,4) as e,
regexp_substr(b,'[^,]+',1,5) as f
FROM A
)
UNPIVOT
(
val1
for val2 in (b1,c,d,e,f)
)
group by a,val1 having count(val1)>1
order by A;

- sriharsha vemuri July 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class Duplicate {
	private static int getDuplicates(char arr[]){
		int x = 1,y = 0,counter=0; 
		
		for (int i=0;i<arr.length;i++){
			//To get the number in the range 0-26
			//Assuming only capital letters are in the array, we are subtracting by 65
			//65 is the ascii value of 'A'
			int num = arr[i] - 65;
			//Shifting the 1 to as many bits as the value of "num"
			x=x<<num;
			//Here the particular bt is being added to 'y' by the OR method
			if((x & y) == 0 ){
				y = x | y;
			}
			else{
				//means there was a duplicate character
				counter ++;
			}
			//because we need to again do the same thing with 'x'. So restoring to the previous state	
			x=1;
		}
		
		return counter;
	}
	public static void main(String args[]){
		char arr[]  = {'A','B','C','A','B'};
		char arr1[] = {'A','B','A','A','A'};
		char arr2[] = {'C','D','C'};
		 
		
		System.out.println(getDuplicates(arr));
		System.out.println(getDuplicates(arr1));
		System.out.println(getDuplicates(arr2));
	}
}

//Just make use of bit shifting. In an integer just make those bits 1 that corresponding to the letter 'A or 'B. And check if a char is a duplicate if the bit for that in the integer is 1 already.

Time O(n)
Space O(1)

- dhirajb1989 May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int calcDup(List<String> aListofStringArray)
{

int counter = 0;

 for(String aRow : aListOfStringArray)
{
   String[] tempArr = aRow.split(",");
   Set<String> aSet = Sets.newHashSet(); 
 
 for(String temp : tempArr )
  { 
    if(aSet.contains(temp))
   {
    aSet.remove(temp);
    counter++;     
   } 
   else
   {
    aSet.add(temp);
   }
  }
}

return counter;

}

- debo May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Besides that trivial approach where we can keep an array of 26 letters, there is one thing which we can do is to re-use the provided array.

i.e.,

Case 2: A, B, A, A, A
Could become 3, B, A, A, A as we parse through the array or we can replace A (or the character we are counting in the loop) with any random character

//pseudo code
while N

index = index of first legit character
char = char we are looping at
count of that char = 0

for all array
count ++ if char = array[current_id]

push in map (char, count)


At the end of iterations we will have a map with all characters with their respective count
The array will have all wild_character

- Random May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will you be iterating the array (a,b,a,a,a) multiple times?
I dont see what you want to do

- Sugarcane_farmer May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

package com.careercup;

import java.util.HashMap;
import java.util.Map;

public class HelloWorld {

    public static void main(String[] args) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();
               //for convenience, I am taking space separated input from command line rather comma separated
		for (int i = 0; i < args.length; i++) {
			String ch = args[i];
			Integer val = map.get(ch);
			
			if (val == null){
				map.put (ch, new Integer(1));
			}
			else {
				map.put (ch, new Integer(val.intValue() + 1));
			}
		}
		
		int charRepeated = 0;
		for (Map.Entry<String, Integer> entry : map.entrySet()){
			charRepeated += entry.getValue().intValue() - 1;
		}
		
		System.out.println ("Repeated Characters: " + charRepeated);
	}
}

- Math.random() May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class Program
    {
        static int CalcDuplicates(string s)
        {
            char[] arr = s.ToArray();
	        int index = 0, counter = 0;
	        foreach (char c in s)
	        {
                index++;
                if (c == ' ') continue;
		        for (int i = index; i < s.Length; i++)
		        {
                    if (c == arr[i])
                    {
                        arr[i] = ' ';
                        counter++;
                    }
		        }
	        }
            return counter;
        }

        static void Main(string[] args)
        {
            Console.WriteLine(CalcDuplicates("ABCAB").ToString());
            Console.WriteLine(CalcDuplicates("ABAAA").ToString());
            Console.WriteLine(CalcDuplicates("CDC").ToString());
        }

- Anonymous May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

initilize an array of 26 size with fasle (for each char)
iterate the given array if fetched char is appering first time make its index true
else increase counter

- Anonymous May 11, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More